Embed Size (px)
Citation preview
D I P L O M A R B E I T
Analytische Behandlung von Urnenmodellen
Ausgefuhrt am Institut fur
Diskrete Mathematik und Geometrie
der Technischen Universitat Wien
unter der Anleitung von
Ao.Univ.Prof. Dipl.-Ing. Dr.techn. Alois Panholzer
durch
Lukas Riegler
Ruzickagasse 88-104/20
1230 Wien
Datum Unterschrift
2
Ich danke meiner Familie fur die Unterstutzung der Studien
und meinem Diplomarbeitsbetreuer
Ao.Univ.Prof. Dipl.-Ing. Dr.techn. Alois Panholzer
fur Ratschlage und seine ansteckende Begeisterung
auf dem Gebiet der Diskreten Mathematik.
Inhaltsverzeichnis
1 Einleitung 51.1 Anforderungen an die Ubergangsmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Teilbarkeitsbedingung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.2 Balanciertheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Verwendete Satze, Funktionen, Notationen . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.1 Gamma-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.2 Euler’sche Beta-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.3 Wachsende/Fallende Faktorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.4 Stirling-Zahlen zweiter Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Weitere Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Isomorphismus-Methode 112.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Herleitung des Isomorphismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Erstes Integral des Differentialgleichungsystems . . . . . . . . . . . . . . . . . . . . . . . . 152.4 Beispiele zur Losung mittels Isomorphismus . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Polya Seuchen-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4.2 Ehrenfest-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4.3 Coupon-Collector Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.4 Ziehen ohne Zurucklegen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4.5 Balancierte Urnen mit Dreiecks-Ubergangsmatrix . . . . . . . . . . . . . . . . . . . 27
2.5 Herleitung der erzeugenden Funktion fur α < 0 . . . . . . . . . . . . . . . . . . . . . . . . 322.5.1 Ehrenfest-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.5.2 [-1, 3; 1, 1] - Urne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.5.3 Hinreichende Bedingungen zur Berechnung von J(u) . . . . . . . . . . . . . . . . . 39
3 Losung uber Methode der Charakteristiken 433.1 Methode der Charakteristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.2 Anwendung fur Urnenmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.3 Ableiten der Grenzverteilungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.4 Verallgemeinertes Ziehen ohne Zurucklegen . . . . . . . . . . . . . . . . . . . . . . . . . . 503.5 OK Corral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.6 Verallgemeinertes Pillen-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
A MATLAB-Code 87
Literaturverzeichnis 93
3
4 INHALTSVERZEICHNIS
Kapitel 1
Einleitung
Ausgangspunkt fur ein Urnenmodell mit Kugeln zweier verschiedener Farben (weiß und schwarz)ist eine quadratische Ubergangsmatrix
M =
(
α β
γ δ
)
,
die folgendermaßen interpretiert wird: Ist die gezogene Kugel weiß, werden α weiße Kugelnhinzugefugt (bzw. −α weiße Kugeln entfernt, falls α < 0) und β schwarze Kugeln hinzugefugt(bzw. −β schwarze Kugeln entfernt, falls β < 0). Wird eine schwarze Kugel gezogen, wird analogdie Anzahl weißer Kugeln um γ und jene schwarzer Kugeln um δ verandert. In allen Fallenwird die gezogene Kugel wieder in die Urne zuruckgelegt. Unter einer Evolution der Lange nversteht man den Vorgang von n Ziehungen. Zu Beginn befinden sich a0 weiße Kugeln und b0schwarze Kugeln in der Urne (a0, b0 ≥ 0). Das Tupel (a0, b0) wird im Folgenden auch als Initial-oder Anfangskonfiguration bezeichnet. Die Abbruchbedingung variiert je nach Problemstellung:Zu den behandelten Abbruchbedingungen gehoren Evolutionen fixer Lange (Kapitel 2) oderdie Vorgabe einer Absorptionsmenge A ⊆ Z2, wobei ein Abbruch erfolgt, falls die momentaneKonfiguration (n,m), d.h. es befinden sich n weiße Kugeln und m schwarze Kugeln in der Urne,ein Element der Absorptionsmenge ist (Kapitel 3). Als Spezialfall einer Absorptionsmenge wirdhaufig die Abbruchbedingung verwendet, dass eine bestimmte oder eine beliebige Kugelsortenicht mehr in der Urne vorhanden ist.
1.1 Anforderungen an die Ubergangsmatrix
1.1.1 Teilbarkeitsbedingung
Zu jedem Zeitpunkt soll die Anzahl der Kugeln aller Farben nichtnegativ sein. Diese Forde-rung kann nur dann verletzt werden, wenn das Ziehen einer Kugel das Entfernen von Kugelnzumindest einer Farbe zur Folge hat.
5
6 KAPITEL 1. EINLEITUNG
Definition 1: Eine Ubergangsmatrix M erfullt die Teilbarkeitsbedingung, falls jeder negativeEintrag der Matrix alle anderen Eintrage derselben Spalte und die Anfangsanzahl an Kugelnder zur Spalte korrespondierenden Farbe teilt.
Bemerkung 1: Die Anzahl der Kugeln einer Farbe in der Urne ist stets eine Linearkombinationder zur Farbe korrespondierenden Spalteneintrage und der Anfangsanzahl. Daher kann fur eineUbergangsmatrix, die die Teilbarkeitsbedingung erfullt, nie der Fall eintreten, dass eine positiveAnzahl an Kugeln einer Farbe vorhanden ist, und mehr Kugeln, als vorhanden sind, entferntwerden sollen.
Die Teilbarkeitsbedingung soll fur alle im Rahmen der Diplomarbeit behandelten Urnenmodelleeine Generalvoraussetzung sein.
Bemerkung 2: Desweiteren wird im Folgenden vorausgesetzt, dass es keine naturliche Zahlk > 1 gibt, die samtliche Eintrage der Ubergangsmatrix teilt. Gabe es namlich ein derartiges kist das Urnenmodell mit Initialkonfiguration (a0, b0), das k|a0 und k|b0 erfullt, isomorph zu demUrnenmodell mit Ubergangsmatrix
M =
(
αk
βk
γk
δk
)
und Initialkonfiguration (a0k, b0k). Die Eigenschaft der Ubergangsmatrix, dass die Eintrage keinen
echten gemeinsamen Teiler besitzen, wird im Weiteren als Irreduzibilitat bezeichnet.
1.1.2 Balanciertheit
Definition 2: Eine Ubergangsmatrix M heißt balanciert, falls die Zeilensummen von M denkonstanten Wert σ annehmen. Gilt weiters σ > 0, nennt man M nicht-verschwindend.
Der Vorteil in der Behandlung von Urnenmodellen mit balancierter Ubergangsmatrix ist, dass dieGesamtanzahl der Kugeln nach n Ziehungen einen deterministischen Wert annimmt. Bezeichnetsn die Gesamtanzahl der Kugeln nach der n-ten Ziehung, gilt sn = s0 + nσ. Die Behandlungvon Urnenmodellen mit balancierter Ubergangsmatrix wird in Kapitel 2 behandelt.
1.2 Verwendete Satze, Funktionen, Notationen
Um die Koeffizienten einer Potzenzreihe abzulesen, die implizit durch eine Funktionalgleichunggegeben ist, kann die Inversionsformel von Lagrange-Burmann verwendet werden:
Satz 1 (Inversionsformel von Lagrange-Burmann): Sei y(x) eine Potenzreihe, und φ(x)eine Potenzreihe mit φ(0) 6= 0, sodass
y(x) = xφ(y(x)).
1.2. VERWENDETE SATZE, FUNKTIONEN, NOTATIONEN 7
Dann gilt fur jede beliebige Potenzreihe f(x) und n ≥ 1:
[xn]f(y(x)) =1
n[un−1]f ′(u)φ(u)n.
1.2.1 Gamma-Funktion
Definition 3: Die Gamma-Funktion ist fur komplexe Argumente z mit positivem Realteil durch
Γ(z) =
∫ ∞
0tz−1e−tdt
definiert.
Fur reelles, positives z folgt mit partieller Integration direkt die Eigenschaft
Γ(z + 1) = zΓ(z).
Insbesondere gilt
Γ(n+ 1) = n!
fur naturliche Zahlen n. Somit gilt auch ein Zusammenhang mit dem Binomialkoeffizienten:
(
x
k
)
=Γ(x+ 1)
Γ(x− k + 1)Γ(k + 1). (1.1)
Aufgrund dieses Zusammenhangs treten im Rahmen der Diplomarbeit Ausdrucke der Bauart
Γ(x+ 1)
Γ(x+ 1 + α), α ∈ R
auf, bei denen die Asympotik fur festes α und x → ∞ von Interesse ist. Diese kann mit Hilfeder Stirling-Formel in der logarithmischen Form
log(Γ (x)) ∼(
x− 1
2
)
log x− x+1
2log(2π), x > 0,
folgendermaßen bestimmt werden:
log
(
Γ(x)
Γ(x+ α)
)
= log(Γ(x))− log(Γ(x+ α)) ∼
∼(
x− 1
2
)
log x− x−(
x+ α− 1
2
)
log(x+ α) + x+ α.
Unter Verwendung der Potenzreihendarstellung des Logarithmus folgt
log(
1 +α
x
)
=∑
k≥1
(−1)k+1 αk
xkk∼ α
x,
8 KAPITEL 1. EINLEITUNG
und somit
log
(
Γ(x)
Γ(x+ α)
)
∼(
x− 1
2
)
log x−(
x+ α− 1
2
)
(
log x+ log(
1 +α
x
))
+ α =
= −(
x− 1
2
)
log(
1 +α
x
)
− α log x− α log(
1 +α
x
)
+ α ∼
∼ −(
x− 1
2
)
α
x− α log x− α
α
x+ α ∼
∼ log x−α.
Insgesamt gilt daher fur festes α ∈ R und x→ ∞:
Γ(x+ 1)
Γ(x+ 1 + α)∼ x−α. (1.2)
1.2.2 Euler’sche Beta-Funktion
Definition 4: Die Euler’sche Betafunktion ist fur komplexe Argumente x, y mit positivemRealteil durch
B(x, y) =
∫ 1
0tx−1(1− t)y−1dt
definiert.
Ein wichtiger Zusammenhang zwischen der Euler’schen Beta-Funktion und der Gamma-Funktionist mit
B(x, y) =Γ(x)Γ(y)
Γ(x+ y)
gegeben.
1.2.3 Wachsende/Fallende Faktorielle
Definition 5: Die wachsenden Faktoriellen werden mit einem Uberstrich im Exponenten no-tiert:
xk := x(x+ 1) · · · (x+ k − 1).
Die fallenden Faktoriellen werden mit einem Unterstrich im Exponenten notiert:
xk := x(x− 1) · · · (x− k + 1).
1.2.4 Stirling-Zahlen zweiter Art
Definition 6: Die Stirling-Zahl zweiter Art Sn,k ist die Anzahl der k-elementigen Partitioneneiner n-elementigen Menge.
1.3. WEITERE BEMERKUNGEN 9
Eine weitere Notation fur Stirling-Zahlen zweiter Art sind geschwungenen Klammern:
Sn,k =
{
n
k
}
.
Die Berechnung der gewohnlichen Momente uber die faktoriellen Momente kann mit Hilfe derStirling-Zahlen zweiter Art und der Identitat ([4])
xn =n∑
k=0
{
n
k
}
xk
erfolgen.
1.3 Weitere Bemerkungen
Die Urnenevolutionen wurden mit MATLAB 7.7.0 (R2008b) simuliert (siehe Anhang). Zur Er-stellung der Graphiken und fur weitere Berechnungen wurden MATLAB 7.7.0 (R2008b), Maple11.01 und Microsoft Office Excel 2007 verwendet.
10 KAPITEL 1. EINLEITUNG
Kapitel 2
Isomorphismus-Methode
2.1 Grundlagen
Fur balancierte, nicht-verschwindende Urnen mit zwei Kugelsorten soll untersucht werden, wiegroß die Wahrscheinlichkeit ist, dass ausgehend von a0 weißen Kugeln und b0 schwarzen Kugelnnach n Ziehungen genau a weiße Kugeln und b schwarze Kugeln in der Urne sind.
Definition 7: Eine Evolution der Lange n bezeichnet die Abfolge von n Ziehungen, wobei alle
Kugeln unterscheidbar sind. En(
a0 a
b0 b
)
bezeichne die Anzahl verschiedener Evolutionen der
Lange n, die ausgehend von a0 weißen und b0 schwarzen Kugeln, zu einer Urnenkonfiguration mit
a weißen und b schwarzen Kugeln fuhren. Weiters sei durch En(
a0b0
)
=∑
a≥0
∑
b≥0
En(
a0 a
b0 b
)
die Anzahl verschiedener Evolutionen der Lange n mit Anfangskonfiguration (a0, b0) festgelegt.
Lemma 1: Balancierte, nicht-verschwindende Urnen erfullen
En(
a0b0
)
= σnΓ(n+ s0
σ)
Γ( s0σ)
= n!σn(
n+ s0σ− 1
n
)
, s0 = a0 + b0. (2.1)
Beweis. Vor der 1.Ziehung befinden sich s0 Kugeln in der Urne, vor der 2.Ziehung s0 + σ, vorder n-ten Ziehung (wegen σ > 0) s0+(n−1)σ. Fur die Gesamtanzahl verschiedener Evolutionengilt daher:
En(
a0b0
)
=n−1∏
i=0
(s0 + iσ) = σnn−1∏
i=0
(s0
σ+ i).
Wegen σ > 0 und Γ(x+ 1) = xΓ(x) fur positives x folgt
En(
a0b0
)
= σnΓ(n+ s0
σ)
Γ( s0σ)
= n!σn(
n+ s0σ− 1
n
)
.
11
12 KAPITEL 2. ISOMORPHISMUS-METHODE
Zur weiteren Behandlung werden die univariat sowie die trivariat erzeugende Funktion fur dieAnzahl der Evolutionen eingefuhrt:
H(z) :=∑
n≥0
En(
a0b0
)
zn
n!,
H(x, y, z) :=∑
n≥0
∑
a≥0
∑
b≥0
En(
a0 a
b0 b
)
xaybzn
n!.
Lemma 2: Die univariat erzeugende Funktion erfullt
H(z) =1
(1− σz)s0σ
, s0 = a0 + b0.
Beweis. Aus Lemma 1 folgt
H(z) =∑
n≥0
En(
a0b0
)
zn
n!=∑
n≥0
σn(
n+ s0σ− 1
n
)
zn =
=∑
n≥0
(− s0σ
n
)
(−1)n(σz)n = (1− σz)−s0σ .
Lemma 3: Die trivariat erzeugende Funktion H(x, y, z) ist als Funktion von z fur beliebigesR > 1 und σ > 0 analytisch im Bereich
|x| ≤ R, |y| ≤ R, |z| ≤ 1
σR2σ.
Beweis. Die Funktion z 7→ H(x, y, z) ist analytisch, falls die Potenzreihe im gegebenen Bereichkonvergent ist. Es gilt:
|[zn]H(x, y, z)| =
∣
∣
∣
∣
∣
∣
∑
a≥0
∑
b≥0
En(
a0 a
b0 b
)
xayb1
n!
∣
∣
∣
∣
∣
∣
.
Da En(
a0 a
b0 b
)
nur dann ungleich Null sein kann, falls a+ b = s0 + nσ, folgt
|[zn]H(x, y, z)| ≤ Rs0+nσ
Γ(n+ 1)
∑
a≥0
∑
b≥0
En(
a0 a
b0 b
)
=Rs0+nσ
Γ(n+ 1)En(
a0b0
)
.
Wegen Lemma 1 gilt somit
|H(x, y, z)| ≤∑
n≥0
|zn|Rs0+nσσn(
n+ s0σ− 1
n
)
≤ c1∑
n≥0
R−nσ
(
n+ s0σ− 1
n
)
.
2.2. HERLEITUNG DES ISOMORPHISMUS 13
Aufgrund von σ ≥ 1 und (1.1) folgt
|H(x, y, z)| ≤ c2∑
n≥0
Γ(
n+ s0σ
)
Γ(n+ 1)Rn.
Die Voraussetzungen des Quotientenkriteriums sind wegen
∣
∣
∣
∣
∣
Γ(
n+ 1 + s0σ
)
Γ(n+ 1)Rn
Γ(
n+ s0σ
)
Γ(n+ 2)Rn+1
∣
∣
∣
∣
∣
=n+ s0
σ
(n+ 1)R−→ 1
R< 1
erfullt, woraus die Konvergenz der Potenzreihe und die Analytizitat folgt.
Lemma 4: Die Zufallsvariablen An bzw. Bn fur die Anzahl weißer bzw. schwarzer Kugeln nachn Ziehungen mit anfangs a0 weißen bzw. b0 schwarzen Kugeln erfullen in einem balanciertenUrnenmodell
P{An = a,Bn = b} =
En(
a0 a
b0 b
)
En(
a0b0
) .
Beweis. Aus der Balanciertheit des Urnenmodells folgt, dass die Zufallsvariable Cn = An +Bn
deterministisch den Wert a0+b0+nσ annimmt, d.h. die Gesamtanzahl der Kugeln in der Urne istin einem balancierten Urnenmodell nur von der Initialkonfiguration und der Anzahl an erfolgtenZiehungen abhangig. Da stets zufallig eine der unterscheidbaren Kugeln gezogen wird, ist jede
der En(
a0b0
)
verschiedenen Evolutionen gleichwahrscheinlich.
2.2 Herleitung des Isomorphismus
Nun soll den Schritten in [1] folgend, ein Isomorphismus zwischen balancierten 2×2-Urnenmodellenund Systemen zweier Differentialgleichungen hergestellt werden, die eine Berechnung der triva-riat erzeugenden Funktion fur die Anzahl der Evolutionen ermoglicht.
Hierzu ist es zunachst hilfreich einen Zusammenhang von Differentialoperatoren mit der Zie-hung im Urnenmodell herzustellen. Interpretiert man gemaß der erzeugenden Funktionen xayb
als”eine Evolution, die zu a weißen und b schwarzen Kugeln fuhrt“, hat der partielle Differen-
tialoperator ∂x die Wirkung ∂x(xayb) = axa−1yb, das entsprechend als
”a mogliche Evolutionen,
die zu a − 1 weißen und b schwarzen Kugeln fuhren“ interpretiert werden kann. Mochte maneine Ziehung fur ein Urnenmodell simulieren, erweist sich daher der Operator
D = xα+1yβ∂x + xγyδ+1∂y
fur erzeugende Funktionen als zielfuhrend:
14 KAPITEL 2. ISOMORPHISMUS-METHODE
Lemma 5: Der partielle Differentialoperator
D = xα+1yβ∂x + xγyδ+1∂y
erfullt fur n ≥ 0
Dn(xa0yb0) =∑
a≥0
∑
b≥0
En(
a0 a
b0 b
)
xayb. (2.2)
Beweis.
Induktionsanfang: Fur n = 0 gilt
D0(xa0yb0) = xa0yb0 =∑
a≥0
∑
b≥0
E0(
a0 a
b0 b
)
xayb.
Induktionsschritt: Es gilt
Dn+1(xa0yb0) = Dn(a0xa0+αyb0+β + b0x
a0+γyb0+δ).
Wegen der Linearitat von D folgt unter Verwendung der Induktionsvoraussetzung
Dn+1(xa0yb0) = a0∑
a≥0
∑
b≥0
En(
a0 + α a
b0 + β b
)
xayb + b0∑
a≥0
∑
b≥0
En(
a0 + γ a
b0 + δ b
)
xayb =
=∑
a≥0
∑
b≥0
(
a0En(
a0 + α a
b0 + β b
)
+ b0En(
a0 + γ a
b0 + δ b
))
xayb =
=∑
a≥0
∑
b≥0
En+1
(
a0 a
b0 b
)
xayb.
Es lasst sich nun ein Isomorphismus zu dem System von Differentialgleichungen
Σ :
{
x = xα+1yβ
y = xγyδ+1(2.3)
herleiten:
Satz 2 (Isomorphismus): Sei M die balancierte Ubergangsmatrix eines Urnenmodells mitAnfangskonfiguration (a0, b0) und X(t) bzw. Y (t) Losungen des zugehorigen Differentialglei-chungsystems (2.3) mit Anfangswerten X(0) 6= 0 bzw. Y (0) 6= 0. Dann gilt fur z in einerUmgebung von 0
H(X(0), Y (0), z) = X(z)a0Y (z)b0 . (2.4)
Beweis. Die Existenz und Eindeutigkeit einer Losung (X(t), Y (t)) des Differentialgleichungssy-stems (2.3) in einer Umgebung von t = 0 folgt aus dem Satz von Cauchy-Kowalewski (siehe[10]). Voraussetzung hierfur ist die Analytizitat der rechten Seiten von (2.3) in einer Umgebung
2.3. ERSTES INTEGRAL DES DIFFERENTIALGLEICHUNGSYSTEMS 15
von (X(0), Y (0)). Da die in (2.3) auftretenden Exponenten auch negativ sein konnen, werdendie Voraussetzungen X(0) 6= 0 und Y (0) 6= 0 benotigt. Der Isomorphismus basiert dann auf derGleichheit
∂t(X(t)aY (t)b) = aX(t)a−1X(t)Y (t)b + bX(t)aY (t)b−1Y (t) =
= aX(t)a+αY (t)b+β + bX(t)a+γY (t)b+δ =
=[
D(xayb)]
x→X,y→Y,
woraus induktiv
∂nt (X(t)aY (t)b) =[
Dn(xayb)]
x→X,y→Y(2.5)
folgt. Wegen Lemma 5 gilt
H(x, y, z) =∑
n≥0
Dn(xa0yb0)zn
n!,
und Anwendung von (2.5) und dem Taylorschen Lehrsatz fuhren fur z in einer Umgebung von0 zu
H(X(t), Y (t), z) =∑
n≥0
∂nt (X(t)a0Y (t)b0)zn
n!= X(t+ z)a0Y (t+ z)b0 .
Fur t = 0 folgt der Zusammenhang zwischen der trivariaten erzeugenden Funktion H und denLosungen des isomorphen Systems von Differentialgleichungen.
Mit Hilfe von Satz 2 kann die trivariat erzeugende Funktion eines Urnenmodells mit balancierterUbergangsmatrix somit in folgenden Schritten ermittelt werden:
1. Ubersetzung der Ubergangsmatrix in das isomorphe System von Differentialgleichungen(2.3).
2. Bestimmung der Losungen X(t) bzw. Y (t) des Differentialgleichungssystemsin Abhangigkeit der Anfangswerte (x0, y0).
3. Anwendung von Satz 2 unter Durchfuhrung der Substitutionen t→ z, x0 → x, y0 → y.
Bemerkung 3: Da fur balancierte Ubergangsmatrizen die Gesamtanzahl der Kugeln zu jedemZeitpunkt einen deterministischen Wert annimmt, kann in der trivariat erzeugenden FunktionH(x, y, z) auch y = 1 gesetzt werden, ohne dass Information verloren geht.
2.3 Erstes Integral des Differentialgleichungsystems
Ein Parameter, der bei balancierten Ubergangsmatrizen in [1] bereits untersucht wurde, ist derGrad der Ungleichheit:
Definition 8: Fur ein 2 × 2 Urnenmodell mit balancierter Ubergangsmatrix ist der Grad derUngleichheit p definiert als
p = γ − α = β − δ.
16 KAPITEL 2. ISOMORPHISMUS-METHODE
Aufgrund der Balanciertheit ist p wohldefiniert und hat folgende Interpretation: Ist p > 0,wachst die Anzahl an Kugeln einer Farbe dann starker, wenn Kugeln der anderen Farbe gezogenwerden. Ist p < 0, wachst die Anzahl an Kugeln einer Farbe dann starker, wenn Kugeln dergleichen Farbe gezogen werden. Im Fall p = 0 hat das Urnenmodell deterministisches Verhalten:Wegen α = γ bzw. β = δ befinden sich nach n Ziehungen a0 + nα weiße und b0 + nβ schwarzeKugeln in der Urne.
Lemma 6: Die Losung des zu einer balancierten 2 × 2 Ubergangsmatrix isomorphen Systemsvon Differentialgleichungen (2.3) mit Anfangswerten x0 6= 0 bzw. y0 6= 0 erfullt fur t in einerUmgebung von 0
X(t)p − Y (t)p = xp0 − y
p0 ,
wobei p den Grad der Ungleichheit bezeichnet.
Beweis. Wegen
∂
∂t(X(t)p − Y (t)p) = pX(t)p−1 ˙X(t)− pY (t)p−1 ˙Y (t) =
p(X(t)α+pY (t)β −X(t)γY (t)δ+p) = 0
ist X(t)p − Y (t)p konstant, und fur t = 0 folgt die Behauptung.
2.4 Beispiele zur Losung mittels Isomorphismus
Fur balancierte Urnenmodelle mit α, δ ∈ {−1, 0, 1} und β, γ ∈ {0, 1} kann das isomorphe Diffe-rentialgleichungssystem (2.3) stets gelost werden ([1]), wodurch mit Satz 2 die trivariat erzeugen-de Funktion bestimmt werden kann. Exemplarisch wird dies fur vier dieser Modelle durchgefuhrt:
2.4.1 Polya Seuchen-Modell
Ein Modell fur die Ausbreitung von Seuchen (”Polya contagion model“) ist mit der Einheitsma-
trix als Ubergangsmatrix
M =
(
1 00 1
)
gegeben. Die zwei Kugelfarben konnen als zwei verschiedene Krankheiten interpretiert werden,wobei die nachste Ansteckung proportional zur momentanen Ausbreitung der beiden Krankhei-ten erfolgt. In Abbildung 2.1 sind 50 verschiedene Evolutionsverlaufe mit Initialkonfiguration(1, 1) dargestellt.
Das isomorphe System von Differentialgleichungen ist gemaß (2.3) durch
x = x2, y = y2 (2.6)
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 17
Abbildung 2.1: Krankheitsverbreitung im Polya Seuchen-Modell. Simulation durch MATLAB-Aufruf urnEvolutionPlot([1 0; 0 1], 100, [1,1], 50, 1, 4).
mit Anfangswerten x(0) = x0 bzw. y(0) = y0 gegeben. Eine Losung von (2.6) kann durchTrennung der Variablen bestimmt werden:
∫
1
x2dx =
∫
1dt,
⇒ − x−1 = t+ c1,
⇒ x(t) =1
c− t=
x0
1− tx0,
⇒ y(t) =y0
1− ty0.
Nach Satz 2 ist die trivariat erzeugende Funktion fur die Evolutionsanzahlen mit Initialkonfigu-ration (a0, b0) durch
H(x, y, z) =xa0yb0
(1− zx)a0(1− zy)b0(2.7)
gegeben. Durch Ablesen der Koeffizienten kann nun die Verteilung weißer und schwarzer Kugelnzum Zeitpunkt n bestimmt bestimmt werden:
Satz 3: Bezeichnen An bzw. Bn die Zufallsvariablen fur die Anzahl weißer bzw. schwarzerKugeln zum Zeitpunkt n im Polya Seuchen-Modell, gilt bei einer Initialkonfiguration von (a0, b0)fur a+ b = n+ a0 + b0
P{An = a,Bn = b} =
(
a−1a0−1
)(
b−1b0−1
)
(
a0+b0+n−1a0+b0−1
) .
18 KAPITEL 2. ISOMORPHISMUS-METHODE
Beweis. Die Evolutionsanzahlen erfullen wegen (2.7)
En(
a0 a
b0 b
)
= [xaybzn
n!]H(x, y, z) = n−a0(1− zy)−b0
= n![zn]
( −a0a− a0
)
(−z)a−a0
( −b0b− b0
)
(−z)b−b0 =
= n!
(
a− 1
a− a0
)(
b− 1
b− b0
)
= n!
(
a− 1
a0 − 1
)(
b− 1
b0 − 1
)
.
Aus Lemma 1 folgt mit σ = 1 fur die Anzahl der Evolutionen der Lange nmit Initialkonfiguration(a0, b0):
En(
a0b0
)
= n!
(
n+ a0 + b0 − 1
n
)
= n!
(
a0 + b0 + n− 1
a0 + b0 − 1
)
.
Die behauptete Gleichheit ist somit wegen Lemma 4 gegeben.
Insbesondere folgt, dass bei anfangs einer weißen und einer schwarzen Kugel zu jedem Zeitpunktjede mogliche Aufteilung weißer und schwarzer Kugeln gleichwahrscheinlich ist (vgl. Abbildung2.1):
Korollar 1: Mit der Initialkonfiguration (1, 1) gilt fur die Anzahl weißer Kugeln zum Zeitpunktn im Polya Seuchen-Modell
P{An = a} =1
n+ 1, a = 1, . . . , n+ 1.
Beweis. Aus Satz 3 folgt fur a0 = b0 = 1 und a ∈ {1, . . . , n+ 1} direkt:
P{An = a} = P{An = a,Bn = n+ 2− a} =1
n+ 1.
In Abbildung 2.2 wird die Abhangigkeit der Krankheitsverbreitung von der Initialkonfigurationim Polya Seuchen-Modell deutlich. Es wurden je 10000 Evolutionen fur jede der Initialkonfi-gurationen (a0, 1) mit a0 ∈ {1, 2, 3, 4, 5} durchgefuhrt. Die Histogramme uber die Endanzahlweißer Kugeln nach 100 Ziehungen in den 5 Fallen sind der Ubersichtlichkeit halber als Flachendargestellt.
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 19
Abbildung 2.2: Abhangigkeit der Verbreitung im Polya Seuchen-Modell von der Initial-konfiguration. Simulation durch MATLAB-Aufruf histogramPlotEndConfig([1 0; 0 1], 100,[a0,1],10000,1,4) mit a0 ∈ {1, 2, 3, 4, 5}.
20 KAPITEL 2. ISOMORPHISMUS-METHODE
2.4.2 Ehrenfest-Modell
Das Ehrenfest-Modell stammt ursprunglich aus dem folgenden physikalischen Kontext: Zweidurch eine Membran getrennte Behalter beinhalten anfangs a0 bzw. b0 Teilchen, wobei einTeilchen zufallig ausgesucht wird, das den Behalter wechselt. Dies kann durch die balancier-te Ubergangsmatrix
M =
(
−1 11 −1
)
beschrieben werden. Das zugehorige System von Differentialgleichungen
x = y, y = x (2.8)
mit Anfangswerten x(0) = x0 bzw. y(0) = y0 erfullt x = x und y = y. Der Ansatz
X(t) = A cosh(t) +B sinh(t),
Y (t) = C cosh(t) +D sinh(t),
mit den hyperbolischen Funktionen Sinus Hyperbolicus
sinh(z) =ez − e−z
2=∑
k≥0
z2k+1
(2k + 1)!
und Cosinus Hyperbolicus
cosh(z) =ez + e−z
2=∑
k≥0
z2k
(2k)!
fuhrt zu
∂2
∂t2X(t) = X(t),
∂2
∂t2Y (t) = Y (t).
Aus den Anfangswerten folgt wegen sinh(0) = 0 bzw. cosh(0) = 1 direkt A = x0 und C = y0.Wegen x = y folgt A = D bzw. B = C, und somit sind durch
X(t) = x0 cosh(t) + y0 sinh(t),
Y (t) = y0 cosh(t) + x0 sinh(t),
die Losungen des Systems (2.8) gegeben. Nach Satz 2 konnen diese direkt in die trivariat erzeu-gende Funktion
H(x, y, z) = (x cosh(z) + y sinh(z))a0 (y cosh(z) + x sinh(z))b0
ubersetzt werden. Startet man mit a0 = N bzw. b0 = 0 Teilchen, vereinfacht sich H(x, y, z) zu
H(x, y, z) = (x cosh(z) + y sinh(z))N . (2.9)
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 21
Satz 4: Startet man im Ehrenfest-Modell mit a0 = N bzw. b0 = 0 Teilchen, ist die Wahrschein-lichkeitsverteilung nach n Ziehungen fur l = 0, . . . , N durch
P{An = N − l, Bn = l} =
=
(
Nl
)
Nn2N
n∑
s=0
(
n
s
)
(
N−l∑
k=0
(
N − l
k
)
(2k −N + l)s
)(
l∑
m=0
(
l
m
)
(−1)m(l − 2m)n−s
)
(2.10)
gegeben.
Beweis. Wegen σ = 0 gibt es Nn verschiedene Evolutionen der Lange n. Zusammen mit (2.9)und Lemma 4 folgt
P{An = N − l, Bn = l} =1
Nn
[
xN−lylzn
n!
]
H(x, y, z) =
=n!
Nn
[
xN−lylzn]
(x cosh(z) + y sinh(z))N =
=n!
Nn
(
N
l
)
[zn] coshN−l(z) sinhl(z) =
=n!
Nn2N
(
N
l
)
[zn](ez + e−z)N−l(ez − e−z)l =
=n!
Nn2N
(
N
l
)
[zn]
(
N−l∑
k=0
(
N − l
k
)
ez(2k−N+l)
)(
l∑
m=0
(
l
m
)
(−1)mez(l−2m)
)
=
=n!
Nn2N
(
N
l
) n∑
s=0
(
N−l∑
k=0
(
N − l
k
)
(2k −N + l)s
s!
)(
l∑
m=0
(
l
m
)
(−1)m(l − 2m)n−s
(n− s)!
)
=
=
(
Nl
)
Nn2N
n∑
s=0
(
n
s
)
(
N−l∑
k=0
(
N − l
k
)
(2k −N + l)s
)(
l∑
m=0
(
l
m
)
(−1)m(l − 2m)n−s
)
.
Bemerkung 4: Startet man mit N bzw. 0 Teilchen kann nur dann die Wahrscheinlichkeit furAn = N−l bzw. Bn = l positiv sein, falls die Anzahl n der Ziehungen die gleiche Paritat wie l hat.Dies spiegelt sich auch beim Ablesen der Koeffizienten wider: In der Potenzreihenentwicklung vonsinh(z) bzw. cosh(z) treten lediglich ungerade bzw. gerade Potenzen von z auf. Der Koeffizientbei zn in coshN−l(z) sinhl(z) kann daher nur dann ungleich Null sein, falls n und l beide geradeoder beide ungerade sind.
Mit MATLAB wurden 5 Simulationen mit N = 50, n = 100 und jeweils 10000 Evolutionendurchgefuhrt. Die aus Satz 4 erhaltene Verteilung und die Ergebnisse der Simulationen sind inAbbildung 2.3 gegenubergestellt. Das Ergebnis stimmt mit der intuitiven Vermutung uberein,dass auf lange Sicht ein Gleichgewicht zwischen den beiden Kugelsorten hergestellt wird. LautSatz 4 ist die Anzahl weißer Kugeln nach 100 Ziehungen bei der Initalkonfiguration (50, 0)mit einer Wahrscheinlichkeit von rund 91, 27% im Intervall [20, 30]. Von den insgesamt 50000Evolutionen war bei 45688 Evolutionen (≈ 91, 37%) am Ende die Anzahl der weißen Kugeln imIntervall [20, 30].
22 KAPITEL 2. ISOMORPHISMUS-METHODE
Abbildung 2.3: Verteilung der weißen Kugeln im Ehrenfest-Modell mit Initialkonfiguration (50, 0)und 100 Ziehungen. Simulation durch MATLAB-Aufruf histogramPlotEndConfig([-1 1; 1 -1],100, [50,0], 10000, 1, 4).
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 23
2.4.3 Coupon-Collector Problem
Im Coupon-Collector Problem ist das Ziel N verschiedene Coupons zu sammeln. Hierzu werdenunter der Annahme, dass alle Coupons gleich oft vorkommen, so lange Coupons gekauft, bis alleN verschiedenen Coupons gefunden werden. Interpretiert man weiße Kugeln als Coupons, dienoch nicht gefunden wurden, und schwarze Kugeln als Coupons, die bereits gefunden wurden,beschreibt die Ubergangsmatrix
M =
(
−1 10 0
)
mit Initialkonfiguration (N, 0) das Coupon-Collector Problem. Aus dem entsprechenden isomor-phen Differentialgleichungssystem
x = y, y = y (2.11)
mit Anfangswerten x(0) = x0 bzw. y(0) = y0 kann durch Trennung der Variablen direkt Y (t)und daraufhin durch Integration X(t) bestimmt werden. Es folgt:
Y (t) = y0et,
X(t) = x0 − y0 + y0et.
Gemaß Satz 2 ist die trivariat erzeugende Funktion des Coupon-Collector Problems mit a0 = N
und b0 = 0 daher durchH(x, y, z) = (x− y + yez)N (2.12)
gegeben.
Satz 5: Im Coupon-Collector Problem mit N Coupons ist die Verteilung der Anzahl an gesam-melten Coupons Bn zum Zeitpunkt n durch
P{Bn = b} =b!
Nn
(
N
b
){
n
b
}
, b ∈ {0, 1, . . . , N} :
bestimmt.
Beweis. Die Anzahl verschiedener Evolutionen der Lange n betragt Nn, da σ = 0. Somit folgtaus (2.12) fur 0 ≤ b ≤ N
P{Bn = b} = P{An = N − b, Bn = b} =1
Nn
[
xN−bybzn
n!
]
H(x, y, z) =
=n!
Nn
[
xN−bybzn]
(x− y + yez)N =
=n!
Nn[zn]
(
N
b
)
(ez − 1)b =
=n!
Nn
(
N
b
)
[zn]b∑
k=0
(
b
k
)
ezk(−1)b−k =
=1
Nn
(
N
b
) b∑
k=0
(
b
k
)
kn(−1)b−k.
24 KAPITEL 2. ISOMORPHISMUS-METHODE
Abbildung 2.4: Verteilung der fehlenden Coupons im Coupon-Collector Problem mit50 verschiedenen Coupons und 100 Ziehungen. Simulation durch MATLAB-AufrufhistogramPlotEndConfig([-1 1; 0 0], 100, [50 0], 10000, 1, 4).
Es gilt fur m,n ≥ 0 die Identitat (siehe [4])
m!
{
n
m
}
=m∑
k=0
(
m
k
)
kn(−1)m−k,
und somit
P{Bn = b} =b!
Nn
(
N
b
){
n
b
}
.
Die in Satz 5 gezeigte Verteilung wurde mit den Parametern N = 50, n = 100 in 5 Simulatio-nen zu je 10000 Evolutionen getestet. Die gemaß der bewiesenen Verteilung erwartete Anzahlfehlender Coupons und die Ergebnisse der Simulationen sind als Histogramme in Abbildung 2.4dargestellt.
2.4.4 Ziehen ohne Zurucklegen
Ziehen ohne Zurucklegen wird durch die Ubergangsmatrix
M =
(
−1 00 −1
)
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 25
modelliert. Das isomorphe System von Differentialgleichungen
x = 1, y = 1 (2.13)
mit Anfangswerten x(0) = x0 bzw. y(0) = y0 besitzt die Losungen
X(t) = t+ x0,
Y (t) = t+ y0.
Die trivariat erzeugende Funktion beim Ziehen ohne Zurucklegen mit anfangs a0 weißen und b0schwarzen Kugeln ist nach Satz 2 daher durch
H(x, y, z) = (x+ z)a0(y + z)b0 (2.14)
gegeben.
Satz 6: Die Wahrscheinlichkeit, dass sich beim Ziehen ohne Zurucklegen mit anfangs a0 weißenund b0 schwarzen Kugeln nach n Ziehungen noch a weiße und b schwarze Kugeln in der Urnebefinden (a0 + b0 = n+ a+ b), betragt
P{An = a,Bn = b} =
(
a0a
)(
b0b
)
(
a0+b0a+b
) .
Beweis. Da aus anfangs a0 + b0 Kugeln n Stuck in beliebiger Reihenfolge ausgewahlt werdenkonnen, betragt die Anzahl verschiedener Evolutionen der Lange n
En(
a0b0
)
=
(
a0 + b0
n
)
n! =
(
a0 + b0
a0 + b0 − a− b
)
n! =
(
a0 + b0
a+ b
)
n!.
Mit (2.14) folgt:
P{An = a,Bn = b} =1
(
a0+b0a+b
)
n!
[
xaybzn
n!
]
H(x, y, z) =1
(
a0+b0a+b
) [xaybzn](x+ z)a0(y + z)b0 =
=
(
a0a
)(
b0b
)
(
a0+b0a+b
) .
Es wurden mit MATLAB 5 Simulationen zu je 50000 Evolutionen mit Initialkonfiguration(30, 30) und n = 30 durchgefuhrt. Die Erwartung, eine um 15 Kugeln symmetrische Vertei-lung fur die Endanzahl weißer Kugeln zu erhalten, wurde in den Simulationen bestatigt. DieErgebnisse sind in Abbildung 2.5 als Histogramm dargestellt.
26 KAPITEL 2. ISOMORPHISMUS-METHODE
Abbildung 2.5: Verteilung der verbleibenden weißen Kugel beim klassischen Ziehen ohneZurucklegen mit Initialkonfiguration (30, 30) und 30 Ziehungen. Simulation durch MATLAB-Aufruf histogramPlotEndConfig([-1 0; 0 -1], 30, [30 30], 50000, 1, 4).
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 27
2.4.5 Balancierte Urnen mit Dreiecks-Ubergangsmatrix
Eine weitere Klasse von balancierten Ubergangsmatrizen, fur die die Losung des isomorphenDifferentialgleichungssystems direkt bestimmt werden kann, ist jene mit γ = 0 und δ = σ > 0.In diesem Fall hat die Ubergangsmatrix Dreiecksgestalt:
M =
(
α σ − α
0 σ
)
, 0 < α < σ.
Der Fall α = σ ist gemaß Bemerkung 2 isomorph zum bereits behandelten Polya Seuchen-Modell.Der Fall α = 0 fuhrt auf ein Urnenmodell mit deterministischem Verhalten. Eine Interpretationder Klasse von Dreiecks-Ubergangsmatrizen ist die Populationsentwicklung zweier Spezies, wobeiNachkommen der ersten Spezies zum Teil der ersten und zum Teil der zweiten (evolutionar weiterentwickelten) Spezies angehoren, und Nachkommen der zweiten Spezies stets der zweiten Speziesangehoren.
Im isomorphen System von Differentialgleichungen
x = xα+1yσ−α, y = yσ+1, (2.15)
mit Anfangswerten x(0) = x0 bzw. y(0) = y0 kann durch Trennung der Variablen zunachst Y (t)bestimmt werden:
∫
y−σ−1dy =
∫
1dt,
⇒ − 1
σy−σ = t+ c1,
⇒ Y (t) = (c2 − σt)−1σ = (y−σ
0 − σt)−1σ = y0(1− yσ0σt)
− 1σ .
Integriert man xx−α−1 = yσ−α, folgt
− 1
αx−α =
∫
yσ−αdt =
∫
yσ+1y−1−αdt =
∫
yy−1−αdt = − 1
αy−α + d1,
und somit
X(t) =(
y−α + d2)− 1
α =(
y−α + x−α0 − y−α
0
)− 1α =
(
y−α0 (1− yσ0σt)
ασ + x−α
0 − y−α0
)− 1α.
Wegen Satz 2 ist die trivariat erzeugende Funktion mit Initialkonfiguration (a0, b0) durch
H(x, y, z) =(
y−α(1− yσσz)ασ + x−α − y−α
)−a0αyb0 (1− yσσz)−
b0σ (2.16)
bestimmt.
Satz 7: Die Wahrscheinlichkeitsverteilung fur die Population der ersten Spezies zum Zeitpunktn bei anfanglichen Populationsgroßen a0 bzw. b0 ist durch (s0 = a0 + b0)
P{An = a0 + kα} =Γ(n+ 1)Γ
(
s0σ
)
Γ(
s0σ+ n
)
(
k + a0α− 1
k
) k∑
i=0
(−1)i(
k
i
)(
n+ b0−αiσ
− 1
n
)
fur 0 ≤ k ≤ n gegeben.
28 KAPITEL 2. ISOMORPHISMUS-METHODE
Beweis. Gemaß Bemerkung 3 genugt es wegen der Balanciertheit die bivariat erzeugende Funk-tion
H(x, 1, z) =(
(1− σz)ασ + x−α − 1
)−a0α(1− σz)−
b0σ =
= xa0(
1− xα(1− (1− σz)ασ ))−a0
α(1− σz)−
b0σ
(2.17)
zu betrachten. Aus Lemma 1 erhalt man fur die Anzahl der Evolution der Lange n:
En(
a0b0
)
= σnΓ(n+ s0
σ)
Γ( s0σ)
. (2.18)
Wegen γ = 0 kann An nur die Werte a0 + kα mit 0 ≤ k ≤ n annehmen. Die entsprechendenWahrscheinlichkeiten erhalt man durch Ablesen der Koeffizienten:
P{An = a0 + kα} =1
En(
a0b0
)
[
xa0+kα zn
n!
]
H(x, 1, z).
Der Koeffizient bei xa0+kα von H(x, 1, z) erfullt
[xa0+kα]H(x, 1, z) = [xkα](
1− xα(1− (1− σz)ασ ))−a0
α(1− σz)−
b0σ =
= (1− σz)−b0σ [xkα]
∑
k≥0
(−a0α
k
)
(−1)kxkα(1− (1− σz)ασ )k =
= (1− σz)−b0σ
(a0α+ k − 1
k
)
(1− (1− σz)ασ )k.
Es folgt:
[zn](1− σz)−b0σ (1− (1− σz)
ασ )k =
= [zn]
∑
j≥0
(− b0σ
j
)
(−1)jσjzj
∑
l≥0
(
k
l
)
(−1)l(1− σz)lασ
=
=n∑
i=0
(− b0σ
i
)
(−1)iσi[zn−i]
∑
l≥0
(
k
l
)
(−1)l∑
m≥0
(
lασ
m
)
(−1)mσmzm
=
=n∑
i=0
(− b0σ
i
)
(−1)iσik∑
l=0
(
k
l
)
(−1)l(
lασ
n− i
)
(−1)n−iσn−i =
= σn(−1)nk∑
l=0
(
k
l
)
(−1)ln∑
i=0
(− b0σ
i
)(
lασ
n− i
)
.
Unter Anwendung der Chu-Vandermonde-Identitat ([4])
n∑
k=0
(
r
m+ k
)(
s
n− k
)
=
(
r + s
m+ n
)
, r, s ∈ R,m, n ∈ N
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 29
folgt schließlich
[zn](1− σz)−b0σ (1− (1− σz)
ασ )k =
= σn(−1)nk∑
l=0
(
k
l
)
(−1)l( lα−b0
σ
n
)
=
= σnk∑
l=0
(
k
l
)
(−1)l( b0−lα
σ+ n− 1
n
)
.
Insgesamt erhalt man somit die behauptete Verteilung:
P{An = a0 + kα} =1
En(
a0b0
)
[
xa0+kα zn
n!
]
H(x, 1, z) =
=n!Γ( s0
σ)
Γ(n+ s0σ)
(a0α+ k − 1
k
) k∑
l=0
(
k
l
)
(−1)l( b0−lα
σ+ n− 1
n
)
.
Durch Differenzieren der erzeugenden Funktion kann der Erwartungswert E(An) fur die Anzahlan Tieren der ersten Spezies nach n Fortpflanzungen und somit gemaß Bn = s0 +nσ−An auchder Erwartungswert E(Bn) fur die Anzahl an Tieren der zweiten Spezies nach n Fortpflanzungenbestimmt werden:
Satz 8: Die erwartete Anzahl an Tieren der ersten Spezies zum Zeitpunkt n bei anfanglichenPopulationsgroßen a0 bzw. b0 = s0 − a0 betragt
E(An) = a0Γ(
s0σ
)
Γ(
s0+ασ
)
Γ(
n+ s0+ασ
)
Γ(
s0σ+ n
) .
Asymptotisch folgt fur n→ ∞ daraus
E(An) ∼ a0Γ(
s0σ
)
Γ(
s0+ασ
)nασ .
Beweis. Durch Bildung der Ableitung ∂∂xH(x, 1, z) und anschließendes Setzen von x = 1 erhalt
man nach Skalierung durch die Anzahl der verschiedenen, gleichwahrscheinlichen Evolutionender Lange n die exponentiell erzeugende Funktion fur die erwartete Anzahl an Tieren der erstenSpezies nach n Fortpflanzungen:
E(An) =1
En(
a0b0
)
[
zn
n!
] [
∂
∂xH(x, 1, z)
]
x=1
.
30 KAPITEL 2. ISOMORPHISMUS-METHODE
Aus (2.17) folgt
[
∂
∂xH(x, 1, z)
]
x=1
=
[
∂
∂xxa0(
1− xα(1− (1− σz)ασ ))−a0
α(1− σz)−
b0σ
]
x=1
=
= (1− σz)−b0σ
[
a0
(
(1− σz)ασ
)−a0α+ a0
(
(1− σz)ασ
)−a0α−1
(1− (1− σz)ασ )
]
=
= a0(1− σz)−b0σ
[
(1− σz)−a0σ−α
σ
]
=
= a0(1− σz)−s0+α
σ .
Der Erwartungswert berechnet sich wegen (2.18) daher zu
E(An) = a0Γ(n+ 1)Γ
(
s0σ
)
σnΓ(
s0σ+ n
) [zn](1− σz)−s0+α
σ = a0Γ(n+ 1)Γ
(
s0σ
)
σnΓ(
s0σ+ n
)
(− s0+ασ
n
)
(−1)nσn =
= a0Γ(n+ 1)Γ
(
s0σ
)
Γ(
s0σ+ n
)
(
n+ s0+ασ
− 1
n
)
=
= a0Γ(
s0σ
)
Γ(
s0+ασ
)
Γ(
n+ s0+ασ
)
Γ(
s0σ+ n
) .
Die Asymptotik folgt nun direkt unter Verwendung von (1.2):
E(An) = a0Γ(
s0σ
)
Γ(
s0+ασ
)
Γ(
n+ s0+ασ
)
Γ(
s0σ+ n
) ∼ a0Γ(
s0σ
)
Γ(
s0+ασ
)
(
n+s0
σ
)ασ ∼ a0
Γ(
s0σ
)
Γ(
s0+ασ
)nασ .
Als Beispiel soll nun das Modell behandelt werden, in dem Nachkommen der ersten Spezies zurHalfte der ersten Spezies und zur Halfte der zweiten Spezies angehoren:
Satz 9: Im Urnenmodell mit der Dreiecks-Ubergangsmatrix
M =
(
1 10 2
)
ist bei einer Initialkonfiguration von (1, 0) die Wahrscheinlichkeitsverteilung der Anzahl Tiereder ersten Spezies nach n ≥ 1 Fortpflanzungen durch
P{An = k} =Γ(n+ 1)Γ(12)
Γ(n+ 12)
k−1∑
i=0
(−1)i(
k − 1
i
)(
n− i2 − 1
n
)
=k − 1
n2k−1
(
2n−kn−1
)
(
2nn
) , 1 ≤ k ≤ n+1
bestimmt.
Beweis. Aus Satz 7 folgt mit den Werten a0 = 1, b0 = 0, s0 = 1, σ = 2, α = 1 fur 0 ≤ k ≤ n
P{An = 1 + k} =Γ(n+ 1)Γ(12)
Γ(n+ 12)
k∑
i=0
(−1)i(
k
i
)(
n− i2 − 1
n
)
,
2.4. BEISPIELE ZUR LOSUNG MITTELS ISOMORPHISMUS 31
und somit direkt die erste behauptete Gleichheit fur 1 ≤ k ≤ n + 1. Fur die zweite Gleichheitbetrachte man die erzeugende Funktion H(x, 1, z) aus dem Beweis von Satz 7. Es gilt:
H(x, 1, z) =x
1− x(1−√1− 2z)
.
Zum Ablesen der Koeffizienten benotigt man [zn](1−√1− 2z)k, welcher mit der Inversionsformel
von Lagrange-Burmann (Satz 1) folgendermaßen bestimmt werden kann: Die Funktion y(z) =1−
√1− 2z erfullt
(1− y(z))2 = 1− 2z,
⇒ y(z)2 − 2y(z) = −2z,
⇒ y(z) =z
1− y(z)2
.
Wahlt man fur φ(z) aus der Inversionsformel daher
φ(z) =1
1− z2
,
folgt φ(0) 6= 0 und y(z) = zφ(y(z)). Mit der Funktion f(x) = xk folgt aus der Inversionsformelfur n ≥ 1 und 1 ≤ k ≤ n:
[zn](1−√1− 2z)k =
1
n[un−1]kuk−1
(
1
1− u2
)n
=
=k
n[un−k]
∑
j≥0
(−nj
)
(−1)j2−juj =
=k
n
(
2n− k − 1
n− k
)
2k−n =
=k
n
(
2n− k − 1
n− 1
)
2k−n.
Nun konnen die Koeffizienten in H(x, 1, z) fur 2 ≤ k ≤ n+ 1 abgelesen werden:[
xkzn
n!
]
H(x, 1, z) = n![xk−1zn]1
1− x(1−√1− 2z)
=
= nk−1 =
= n!k − 1
n
(
2n− k
n− 1
)
2k−1−n.
Die Anzahl der Evolutionen der Lange n betragt nach Lemma 1
En(
10
)
= 2nΓ(n+ 1
2)
Γ(12).
Es folgt daher fur n ≥ 1 und 2 ≤ k ≤ n+ 1:
P{An = k} =k − 1
n2k−1
(
2n− k
n− 1
)
n!Γ(12)
4nΓ(n+ 12).
32 KAPITEL 2. ISOMORPHISMUS-METHODE
Abbildung 2.6: Verteilung der Tiere der ersten Spezies nach 1000 Fortpflanzungen bei Initialkon-figuration (1, 0). Simulation durch MATLAB-Aufruf histogramPlotEndConfig([1 1; 0 2], 1000,[1 0], 10000, 1, 4).
Unter Beachtung von
4nΓ(n+ 12)
n!Γ(12)=
2n
n!(2n− 1)(2n− 3) · · · 3 · 1 =
(2n)!
n!n!=
(
2n
n
)
folgt somit auch die zweite behauptete Gleichheit fur 2 ≤ k ≤ n+1. Fur n ≥ 1 ist P{An = 1} = 0,womit die zweite Gleichheit auch fur k = 1 gilt.
Die bewiesene Verteilung aus Satz 9 fur die Anzahl der Tiere der ersten Spezies bei einer In-itialkonfiguration von (1, 0) wurde fur n = 1000 getestet. Es wurden 5 Simulationen mit je10000 Evolutionen durchgefuhrt, wobei die Endanzahl der Tiere der ersten Spezies in Klassender Große 5 eingeteilt wurden. Das Ergebnis ist in Abbildung 2.6 als Histogramm dargestellt.Wegen Satz 8 betragt der asymptotisch angenaherte Erwartungswert der Anzahl an Tieren der
ersten SpeziesΓ( 1
2)Γ(1) 1000
12 =
√1000π ≈ 56.
2.5 Herleitung der erzeugenden Funktion fur α < 0
Im Fall balancierter Ubergangsmatrizen ist aufgrund der Existenz eines ersten Integrals fur dasisomorphe System von Differentialgleichungen die Existenz einer Losung gesichert. Die einfa-che Bestimmung der trivariat erzeugenden Funktion in Abhangigkeit von α, β, γ und δ scheitert
2.5. HERLEITUNG DER ERZEUGENDEN FUNKTION FUR α < 0 33
allerdings am Auffinden der Losung des isomorphen Systems von Differentialgleichngen fur belie-bige Anfangswerte (x0, y0). Man versucht daher fur Klassen von Ubergangsmatrizen eine Mengevon Funktionen zu bestimmen, aus denen man die trivariat erzeugende Funktion zusammen-setzen kann. In diesem Abschnitt wird dies fur die Klasse balancierter, nicht-verschwindenderUbergangsmatrizen mit α ≤ −1, β, γ ∈ N0, δ 6= 0 durchgefuhrt:
Definition 9: Seien r ∈ N+, s ∈ Q 6=0 und λ ∈ Q≥0. In einer Umgebung von 0 kann die Funktion
Jr,λ(u) :=
∫ u
0
dζ
(1 + ζr)λ(2.19)
invertiert werden. Ihre inverse Funktion Sr,λ
Sr,λ(Jr,λ(u)) = Jr,λ(u)(Sr,λ(u)) = u
wird Pseudo-Sinusfunktion genannt. Die Funktion Cr,s,λ
Cr,s,λ(z) := (1 + S(z)r)1s (2.20)
wird als Pseudo-Cosinusfunktion bezeichnet.
Bemerkung 5: Die Existenz einer Umkehrfunktion von Jr,λ in einer Umgebung von 0 folgt ausdem aus der komplexen Analysis bekannten Satz von der inversen Funktion wegen J ′
r,λ(0) 6= 0.
Satz 10: Sei M =
(
α β
γ δ
)
eine balancierte Ubergangsmatrix mit α ≤ −1, β, γ ∈ N0, δ 6= 0
und σ > 0. Weiters bezeichne p den Grad der Ungleichheit, d.h.
p = γ − α = β − δ,
und J = Jr,λ, S = Sr,λ = J−1 bzw. C = Cr,s,λ die Funktionen aus Definition 9 mit denParametern
r := − p
α, s := −p
δ. λ :=
β
p
Dann ist die erzeugende Funktion H(x, 1, z) fur die Anzahl der Evolutionen mit Initialkonfigu-ration (a0, b0) durch
H(x, 1, z) = ∆a0+b0S
(
−αz∆σ + J
(
( x
∆
)−α))−a0
α
C
(
−αz∆σ + J
(
( x
∆
)−α))− b0
δ
(2.21)
gegeben, wobei
∆ := ∆(x) = (1− xp)1p .
Beweis. Zunachst sei festgestellt, dass alle Variablen im Satz wohldefiniert sind: Es gilt p =γ − α > 0, α|γ wegen der Teilbarkeitsbedingung und somit r ∈ N, s ∈ Q 6=0 und λ ∈ Q≥0. DenSchritten in [1] folgend, betrachtet man das isomorphe System von Differentialgleichungen
x = xα+1yβ , x(0) = x0, y = xγyδ+1, y(0) = y0.
34 KAPITEL 2. ISOMORPHISMUS-METHODE
Nach Anwendung von Satz 2 werden die Ersetzungen x0 → x, y0 → 1 durchgefuhrt. Zur kurzeren
Schreibweise bezeichne im Folgenden daher ∆ := ∆(x0, y0) = (yp0 − xp0)
1p . Es folgt aus Lemma
6, dass
x = xα+1yβ = xα+1 (xp − xp0 + y
p0)
βp = xα+1 (xp +∆p)
βp ,
y = xγyδ+1 = (yp + xp0 − y
p0)
γp yδ+1 = (yp −∆p)
γp yδ+1
fur t in einer Umgebung von 0. Definiert man Funktionen ξ(t) bzw. η(t) uber die Beziehungen
x(t) = ∆ξ(t∆σ),
y(t) = ∆η(t∆σ),
folgt durch Ableiten nach t
x(t) = ∆σ+1ξ(t∆σ),
y(t) = ∆σ+1η(t∆σ).
Andererseits gilt
x(t) = x(t)α+1 [x(t)p +∆p]βp = ∆α+1ξα+1(t∆σ) [∆pξp(t∆σ) + ∆p]
βp
= ∆α+β+1ξα+1(t∆σ) [ξp(t∆σ) + 1]βp
bzw.
y(t) = [y(t)p −∆p]γp y(t)δ+1 = [∆pηp(t∆σ)−∆p]
γp ∆δ+1ηδ+1(t∆σ) =
= ∆γ+δ+1ηδ+1(t∆σ) [ηp(t∆σ)− 1]γp .
Das transformierte System von Differentialgleichungen ist somit insgesamt gegeben durch
ξ = ξα+1(ξp + 1)βp , ξ(0) = x0
∆ , (2.22)
η = ηδ+1(ηp − 1)γp , η(0) = y0
∆ . (2.23)
Da nach Anwendung von Satz 2 in der erzeugenden Funktion y = 1 gesetzt werden kann,und die erzeugende Funktion als Potenzreihe in x mit Entwicklungspunkt 0 behandelt wird, isthierbei x0 in einer Umgebung von 0 und y0 in einer Umgebung von 1 von Interesse. Daher ist
∆ = ∆(x0, y0) = (yp0 − xp0)
1p verschieden von 0.
Durch Trennung der Variablen in (2.22) folgt
t =
∫
ξ−α−1
(ξp + 1)βp
dξ =
∫ ξ(t)
ξ(0)
w−α−1
(wp + 1)βp
dw.
Substituiert man ζ = w−α, erhalt man daraus ( dζdw
= −αw−α−1)
t = − 1
α
∫ ξ(t)−α
(x0∆ )
−α
dζ
(ζ−pα + 1)
βp
= − 1
α
∫ ξ(t)−α
(x0∆ )
−α
dζ
(1 + ζr)λ.
2.5. HERLEITUNG DER ERZEUGENDEN FUNKTION FUR α < 0 35
Es folgt
−αt = J(ξ(t)−α)− J
(
(x0
∆
)−α)
.
Da die Pseudo-Sinusfunktion S als Umkehrfunktion von J definiert ist, erhalt man
ξ(t)−α = S
(
−αt+ J
(
(x0
∆
)−α))
,
und daraus nach Rucksubstitution
x−α(t) = ∆−αξ(t∆σ)−α = ∆−αS
(
−αt∆σ + J
(
(x0
∆
)−α))
.
Die Losung X(t) des isomorphen Differentialgleichungssystems ist somit durch
X(t) = ∆S
(
−αt∆σ + J
(
(x0
∆
)−α))− 1
α
gegeben. Mit Lemma 6 folgt
xp0 − y
p0 = X(t)p − Y (t)p = ∆p(ξ(t∆σ)− η(t∆σ)) = (yp0 − x
p0)(ξ(t∆
σ)p − η(t∆σ)p)
und somit
η(t) = (1 + ξ(t)p)1p =
(
1 + S
(
−αt+ J
(
(x0
∆
)−α))− p
α
) 1p
=
=
(
1 + S
(
−αt+ J
(
(x0
∆
)−α))r)− 1
sδ
= C
(
−αt+ J
(
(x0
∆
)−α))− 1
δ
.
Durch Rucksubstitution erhalt man daher
Y (t) = ∆C
(
−αt∆σ + J
(
(x0
∆
)−α))− 1
δ
.
Nach Verwendung von Satz 2 und Setzen von y = 1, folgt die behauptete Gleichung:
H(x, 1, z) = ∆a0+b0S
(
−αz∆σ + J
(
( x
∆
)−α))−a0
α
C
(
−αz∆σ + J
(
( x
∆
)−α))− b0
δ
.
36 KAPITEL 2. ISOMORPHISMUS-METHODE
2.5.1 Ehrenfest-Modell
Das Ehrenfest-Modell mit Ubergangsmatrix
M =
(
−1 11 −1
)
wurde bereits in Abschnitt 2.4.2 behandelt: Durch Losen des isomorphen Differentialgleichungs-ystems hat man die erzeugende Funktion
H(x, 1, z) = (x cosh(z) + sinh(z))a0(cosh(z) + x sinh(z))b0
erhalten. Aus Satz 10 kann die erzeugende Funktion nun direkt gewonnen werden (σ = 0, p = 2):
H(x, 1, z) =√
1− x2a0+b0
S
(
z + J
(
x√1− x2
))a0
C
(
z + J
(
x√1− x2
))b0
,
Es gilt (r = s = 2, λ = 12):
J(u) =
∫ u
0
dζ√
1 + ζ2= arcsinh(u),
⇒ S(u) = sinh(u),
⇒ C(u) =√
1 + sinh(u)2 = cosh(u).
Aus den Identitaten
sinh(x+ y) = sinh(x) cosh(y) + sinh(y) cosh(x),
cosh(x+ y) = cosh(x) cosh(y) + sinh(x) sinh(y),
arcsinh(x) = arccosh(√
1 + x2)
folgt
√
1− x2S
(
z + J
(
x√1− x2
))
=√
1− x2 sinh
(
z + arcsinh
(
x√1− x2
))
=
=√
1− x2 sinh(z) cosh
(
arcsinh
(
x√1− x2
))
+ x cosh(z) =
=√
1− x2 sinh(z)
√
1 +x2
1− x2+ x cosh(z) =
= sinh(z) + x cosh(z)
und
√
1− x2C
(
z + J
(
x√1− x2
))
=√
1− x2 cosh
(
z + arcsinh
(
x√1− x2
))
=
=√
1− x2 cosh(z) cosh
(
arcsinh
(
x√1− x2
))
+ x sinh(z)
= cosh(z) + x sinh(z).
2.5. HERLEITUNG DER ERZEUGENDEN FUNKTION FUR α < 0 37
Das aus Satz 10 gewonnene Resultat stimmt somit mit jenem aus Abschnitt 2.4.2 uberein:
H(x, 1, z) =√
1− x2a0+b0
S
(
z + J
(
x√1− x2
))a0
C
(
z + J
(
x√1− x2
))b0
=
= (x cosh(z) + sinh(z))a0(cosh(z) + x sinh(z))b0 .
2.5.2 [-1, 3; 1, 1] - Urne
Fur das Urnenmodell mit Ubergangsmatrix
M =
(
−1 31 1
)
soll untersucht werden, wie sich die Anzahl weißer Kugeln im Zuge einer fortschreitender Evo-lution verhalt. Das Integral J(u) kann mit Hilfe der Substitution ζ = tanx ( dζ
dx= 1 + tan2 x)
folgendermaßen berechnet werden (p = 2, r = 2, λ = 32):
J(u) =
∫ u
0
dζ
(1 + ζ2)32
=
∫ arctanu
0
dx√1 + tan2 x
=
∫ arctanu
0cosxdx = sin(arctan(u)).
Betrachtet man ein rechtwinkeliges Dreieck mit einem spitzen Winkel der Große α, zugehorigerAnkathete der Lange 1, Gegenkathete der Lange u und Hypotenuse der Lange H, folgt tanα = u
und dahersin(arctan(u)) = sinα =
u
H=
u√1 + u2
.
Die Pseudo-Sinus bzw. Pseudo-Cosinusfunktion berechnen sich bei dieser Urne daher zu (r =2, s = −2):
J(u) =u√
1 + u2,
⇒ S(u) =u√
1− u2,
⇒ C(u) =√
1− u2.
Startet man mit einer schwarzen Kugel in der Urne und keiner weißen Kugel, erhalt man dieerzeugende Funktion mit Satz 10 folgendermaßen:
H(x, 1, z) =√
1− x2C
(
z(1− x2) + J
(
x√1− x2
))−1
=
=√
1− x2C(
z(1− x2) + x)−1
=
=
√
1− x2
1− (z(1− x2) + x)2.
38 KAPITEL 2. ISOMORPHISMUS-METHODE
Nun soll gezeigt werden, dass die Wahrscheinlichkeit, dass sich nach 2n Evolutionen ausschließ-lich schwarze Kugeln in der Urne befinden, asymptotisch exponentiell in n gegen 0 konvergiert.Hierzu liest man den Koeffizienten bei x0 z2n
(2n)! in H(x, 1, z) ab, oder man setzt aquivalent dazu
x = 0 in H(x, 1, z) und liest den Koeffizienten bei z2n
(2n)! ab:
[
z2n
(2n)!
]
H(0, 1, z) = (2n)![z2n]
√
1
1− z2= (2n)![z2n]
∑
k≥0
(−12
k
)
(−1)kz2k =
= (2n)!
(−12
n
)
(−1)n = (2n)!
(
n− 12
n
)
.
Die Anzahl verschiedener Evolutionen der Lange 2n, falls sich zu Beginn eine Kugel in der Urnebefindet, betragt wegen σ = 2
E2n(
01
)
=
2n∏
i=1
(2i− 1).
Somit erhalt man wegen Lemma 4
P{A2n = 0} =
[
z2n
(2n)!
]
H(0, 1, z)
E2n(
01
) =(2n)!
(
n− 12
n
)
∏2ni=1(2i− 1)
=(2n)!
∏ni=1(n+ 1
2 − i)
n!∏2n
i=1(2i− 1)=
=(2n)!
∏ni=1(2n+ 1− 2i)
n!2n∏2n
i=1(2i− 1)=
(2n)!2∏2n
i=1(2i)
n!2n(4n)!∏n
i=1(2i)=
(2n)!3
n!2(4n)!.
Die Asymptotik kann man nun mit der Stirlingformel
n! ∼√2πn
(n
e
)n
erhalten:
P{A2n = 0} =(2n)!3
n!2(4n)!∼
√4πn
3(2n)6n
e6ne2n
2πnn2ne4n√
8πn(4n)4n=
1
22n−12
Die Wahrscheinlichkeit, dass sich nach 2n Ziehungen keine weißen Kugeln befinden, konvergiertsomit asymptotisch exponentiell in n gegen 0. Die Asymptotik des Erwartungswerts und derVarianz von An wurde in [1] mit Hilfe von Maple bestimmt. Diese betragen
E(An) =n
2+
1
4+
1
8n+O
(
1
n2
)
,
V(An) =n
4+
1
8+
1
8n+O
(
1
n2
)
.
Das erwartete Verhaltnis weißer und schwarzer Kugeln ist somit asympotisch 1 : 3. Dieses Ergeb-nis bestatigt sich auch in einer durchgefuhrten MATLAB-Simulation mit 100000 Evolutionen,n = 1000 und Initialkonfiguration (0, 1). Das erhaltene Histogramm ist in Abbildung 2.7 darge-stellt. Die beobachtete Verteilung der Endanzahl weißer Kugeln liegt konzentriert um den Wert500: In rund 94, 95% der Evolutionen befindet sich die Endanzahl der weißen Kugeln im Intervall[470, 530].
2.5. HERLEITUNG DER ERZEUGENDEN FUNKTION FUR α < 0 39
Abbildung 2.7: Verteilung der Endanzahl weißer Kugeln im Urnenmodell [−1 3; 1 1]mit Initialkonfiguration (0, 1) nach 1000 Ziehungen. Simulation durch MATLAB-AufrufhistogramPlotEndConfig([-1 3; 1 1], 1000, [0 1], 100000, 1, 4).
2.5.3 Hinreichende Bedingungen zur Berechnung von J(u)
In der Berechnung der erzeugenden Funktion aus Satz 10 beinhaltet das Argument der Pseudo-Sinusfunktion bzw. Pseudo-Cosinusfunktion das Integral (2.19). Es stellt sich nun die Frage, obes hinreichende Bedingungen an die Parameter gibt, sodass
∫
dζ
(1 + ζr)βp
(2.24)
berechnet werden kann. In der Herleitung von Satz 10 ist man auf dieses Integral nach derSubstitution ζ = w−α in
∫
w−α−1
(wp + 1)βp
dw (2.25)
gestoßen. Die Integrabilitat von (2.24) ist daher zur Integrabilitat von (2.25) aquivalent. Einehinreichende Bedingung erhalt man beispielsweise, falls
∂
∂w(wp + 1) = cw−α−1,
da dann eine Substitution von wp + 1 zielfuhrend ist. Dies ist der Fall, falls p − 1 = −α − 1und somit γ = 0. Das entspricht somit dem bereits behandelten Fall der Ubergangsmatrizen mitDreiecksgestalt.
Eine weitere hinreichende Bedingung kann gefunden werden, indem zunachst die Substitution
40 KAPITEL 2. ISOMORPHISMUS-METHODE
v = 1w
durchgefuhrt wird. Dann folgt(
dvdw
= − 1w2
)
:
∫
w−α−1
(wp + 1)βp
dw = −∫
vα−1
(v−p + 1)βp
dv = −∫
vα+β−1
(1 + vp)βp
dv.
Eine hinreichende Bedingung ist daher p − 1 = α + β − 1, und somit β = γ − 2α. Aus derBalanciertheit folgt damit δ = −α. Da α negativ ist, muss wegen der Teilbarkeitsbedingungγ = kα gelten. Da nach Bemerkung 2 nur irreduzible Ubergangsmatrizen betrachtet werden,fuhrt diese hinreichende Bedingung auf den Fall α = −1. Die Ubergangsmatrix hat daher dieGestalt
M =
(
−1 σ + 1σ − 1 1
)
.
Satz 11: Die erzeugende Funktion fur die Anzahl der Evolutionen im Urnenmodell mit derbalancierten Ubergangsmatrix
M =
(
−1 σ + 1σ − 1 1
)
, σ ≥ 2
und anfangs s0 = a0 + b0 Kugeln ist durch
H(x, 1, z) =(1− xσ)
s0σ (x+ z(1− xσ))a0
(1− (x+ z(1− xσ))σ)s0σ
gegeben.
Beweis. Die zur Berechnung von J(.), S(.) bzw. C(.) benotigten Parameter sind p = σ, r =σ, s = −σ, λ = σ+1
σ. Es folgt
J(u) =
∫ u
0
dζ
(1 + ζr)λ=
∫ u
0
dζ
(1 + ζσ)σ+1σ
,
und mit der Substitution w = 1ζfolgt weiters
(
dwdζ
= − 1ζ2
)
:
J(u) = −∫ 1
u
∞
w−2
(1 + w−σ)σ+1σ
dw = −∫ 1
u
∞
wσ−1
(wσ + 1)1+1σ
dw =
= −(wσ + 1)−1σ (−σ) 1
σ
∣
∣
∣
∣
1u
∞= (1 + u−σ)−
1σ .
Die Pseudo-Sinusfunktion berechnet sich als Umkehrfunktion von J(.) zu
S(z) = (z−σ − 1)−1σ ,
und die Pseudo-Cosinusfunktion daraus zu
C(z) = (1 + S(z)r)1s = (1 + (z−σ − 1)−1)−
1σ =
z
(z−σ − 1)−1σ
= (1− zσ)1σ .
2.5. HERLEITUNG DER ERZEUGENDEN FUNKTION FUR α < 0 41
Wegen Satz 10 ist die erzeugende Funktion durch
H(x, 1, z) = ∆a0+b0S
(
−αz∆σ + J
(
( x
∆
)−α))−a0
α
C
(
−αz∆σ + J
(
( x
∆
)−α))− b0
δ
gegeben. Das Argument der Pseudo-Sinusfunktion und Pseudo-Cosinusfunktion lasst sich zu
−αz∆σ + J
(
( x
∆
)−α)
= z(1− xσ) + (1 +( x
∆
)−σ
)−1σ = z(1− xσ) +
(
1 +1− xσ
xσ
)− 1σ
=
= z(1− xσ) + x
vereinfachen. Somit folgt schließlich
H(x, 1, z) = (1− xσ)s0σ
1
((z(1− xσ) + x)−σ − 1)a0σ
1
(1− (z(1− xσ) + x)σ)b0σ
=
= (1− xσ)s0σ
(z(1− xσ) + x)a0
(1− (z(1− xσ) + x)σ)s0σ
.
Bemerkung 6: Wendet man Satz 10 mit σ = 2, a0 = 0 und b0 = 1 an, erhalt man direkt dieerzeugende Funktion des bereits behandelten Urnenmodells mit Ubergangsmatrix
M =
(
−1 31 1
)
.
Mit Satz 10 erhalt man nun auch direkt die erzeugende Funktion fur beliebige Anfangskonfigu-rationen.
42 KAPITEL 2. ISOMORPHISMUS-METHODE
Kapitel 3
Losung uber Methode derCharakteristiken
Eine andere Methode zur Berechnung der erzeugenden Funktionen (vgl. [2] und [3]) bestehtdarin, fur die gesuchten Wahrscheinlichkeiten eine Rekursion aufzustellen, aus der eine partielleDifferentialgleichung fur die erzeugende Funktion hergeleitet werden kann, und diese mit derMethode der Charakteristiken zu losen.
3.1 Methode der Charakteristiken
Ausgangspunkt ist eine bivariat erzeugende Funktion H(z, w), fur die eine partielle Differenti-algleichung der Bauart
f1(z, w)Hz(z, w) + f2(z, w)Hw(z, w) + f3(z, w)H(z, w) + f4(z, w) = 0 (3.1)
hergeleitet wird.
Zur Losung (vgl. [5]) einer partiellen Differentialgleichung dieser Bauart betrachtet man zunachstdie sogenannte Rumpf-Differentialgleichung
f1(z, w)Hz(z, w) + f2(z, w)Hw(z, w) = 0. (3.2)
Fasst man z und w als Funktionen von t auf (z = z(t), w = w(t)), und betrachtet man dasSystem von Differentialgleichungen
z = f1(z, w), w = f2(z, w) (3.3)
gilt nach der Kettenregel
∂
∂tH(z(t), w(t)) = Hz(z(t), w(t))z +Hw(z(t), w(t))w =
= Hz(z, w)f1(z, w) +Hw(z, w)f2(z, w)
43
44 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
und somit
Hz(z, w)f1(z, w) +Hw(z, w)f2(z, w) = 0 ⇔ H(z(t), w(t)) = const.
Das Auffinden einer Losung der Rumpf-Differentialgleichung ist also gleichbedeutend mit derBestimmung eines ersten Integrals des zugehorigen charakteristischen Differentialgleichungssy-stems (3.3).
Zur Losung der allgemeinen PDG (3.1) wird die Variablensubstitution ξ = ξ(z, w), η = η(z, w),G(ξ, η) = H(z, w) als Ansatz gewahlt. Es folgt nach Substitution in (3.1) und der Kettenregel
f1(z, w)Hz(z, w) + f2(z, w)Hw(z, w) + f3(z, w)H(z, w) + f4(z, w) =
= f1(z, w)(Gξξz +Gηηz) + f2(z, w)(Gξξw +Gηηw) + f3(z, w)G+ f4(z, w) =
= [f1(z, w)ξz + f2(z, w)ξw]Gξ + [f1(z, w)ηz + f2(z, w)ηw]Gη + f3(z, w)G+ f4(z, w) = 0.
Wahlt man bei der Substitution fur ξ(z, w) eine Losung der Rumpf-Differentialgleichung, wirddie partielle Differentialgleichung daher zu einer gewohnlichen Differentialgleichung erster Ord-nung in η reduziert:
[f1(z, w)ηz + f2(z, w)ηw]Gη + f3(z, w)G+ f4(z, w) = 0. (3.4)
Aus der Losung von (3.4) erhalt man nach Rucksubstitution eine Losung H(z, w) der partiellenDifferentialgleichung (3.1).
3.2 Anwendung fur Urnenmodelle
Den Schritten in [2] folgend, wird als Grundlage ein 2 × 2-Urnenmodell, eine DefinitionsmengeS ⊆ Z2, und eine Absorptionsmenge A ⊆ S betrachtet, wobei A derart gewahlt sein muss, dassman von einer beliebigen Initialkonfiguration (n,m) ∈ S, d.h. mit n weißen und m schwarzenKugeln, nach einer endlichen Anzahl von Ziehungen einen Absorptionspunkt (j, k) ∈ A erreicht.
Untersucht wird dann das Paar von Zufallsvariablen (X(1)n,m, X
(2)n,m) mit der Eigenschaft, dass die
Wahrscheinlichkeit von einer Initialkonfiguration (n,m) ausgehend in dem Absorptionspunkt
(j, k) zu landen, durch P{(X(1)n,m, X
(2)n,m) = (j, k)} gegeben ist.
Gemaß der Uberlegung fur (n,m) ∈ S\A:
P{(X(1)n,m, X
(2)n,m) = (j, k)} =
= P{weiße Kugel gezogen}P{(X(1)n+α,m+β , X
(2)n+α,m+β) = (j, k)}+
+ P{schwarze Kugel gezogen}P{(X(1)n+γ,m+δ, X
(2)n+γ,m+δ) = (j, k)},
erfullt die wahrscheinlichkeitserzeugende Funktion
hn,m(v1, v2) :=∑
j≥0
∑
k≥0
P{(X(1)n,m, X
(2)n,m) = (j, k)}vj1vk2
3.2. ANWENDUNG FUR URNENMODELLE 45
die Rekursion
hn,m(v1, v2) =n
n+mhn+α,m+β(v1, v2) +
m
n+mhn+γ,m+δ(v1, v2), (n,m) ∈ S\A, (3.5)
mit den Anfangswerten hn,m(v1, v2) = vn1 vm2 fur (n,m) ∈ A.
Lemma 7: Die erzeugende Funktion H(z, w, v1, v2) :=∑
(n,m)∈S\Ahn,m(v1, v2)z
nwm ist analy-
tisch als Funktion von z und als Funktion von w fur |v1|, |v2| ≤ 1, |z|, |w| < 1.
Beweis. Die Analytizitat ist gleichbedeutend mit der Konvergenz der Potenzreihe im gegebenenBereich:
|H(z, w, v1, v2)| =
∣
∣
∣
∣
∣
∣
∑
(n,m)∈S\Ahn,m(v1, v2)z
nwm
∣
∣
∣
∣
∣
∣
≤∑
(n,m)∈S\A|znwm| ≤
≤∑
m≥0
|w|m∑
n≥0
|z|n =1
(1− |z|)(1− |w|) <∞.
Im Folgenden wird die Abkurzung H(z, w) := H(z, w, v1, v2) verwendet.
Lemma 8: Die erzeugende Funktion
H(z, w) =∑
(n,m)∈S\Ahn,m(v1, v2)z
nwm
erfullt die partielle Differentialgleichung
z(1− z−αw−β)Hz(z, w) + w(1− z−γw−δ)Hw(z, w)+
+ (αz−αw−β + δz−γw−δ)H(z, w) = F (z, w).(3.6)
F (z, w) besteht aus Summanden S(n,m, z, w) mit n,m derart, dass nicht gleichzeitig (n,m) ∈S\A und (n− α,m− β) ∈ S\A bzw. (n− γ,m− δ) ∈ S\A erfullt ist.
Beweis. Multipliziert man (3.5) mit dem Faktor (n+m)znwm und summiert uber alle (n,m) ∈S\A, erhalt man auf der linken Seite
∑
(n,m)∈S\Ahn,m(v1, v2)(n+m)znwm =
=∑
(n,m)∈S\Ahn,m(v1, v2)nz
nwm +∑
(n,m)∈S\Ahn,m(v1, v2)mz
nwm =
= zHz(z, w) + wHw(z, w).
46 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Der erste Summand auf der rechten Seite von (3.5) erfullt nach Multiplikation und Summation∑
(n,m)∈S\Ahn+α,m+β(v1, v2)nz
nwm =
=∑
(n−α,m−β)∈S\Ahn,m(v1, v2)(n− α)zn−αwm−β =
= z1−αw−β
∑
(n−α,m−β)∈S\Ahn,m(v1, v2)nz
n−1wm
−
− αz−αw−β
∑
(n−α,m−β)∈S\Ahn,m(v1, v2)z
nwm
=
= z1−αw−βHz(z, w)− αz−αw−βH(z, w) + F1(z, w),
wobei F1(z, w) jene Summanden beinhaltet, die nicht gleichzeitig (n − α,m − β) ∈ S\A und(n,m) ∈ S\A erfullen.
Analog erhalt man fur den zweiten Summanden auf der rechten Seite von (3.5)
z−γw1−δHw(z, w)− δz−γw−δH(z, w) + F2(z, w),
woraus nach Zusammenfassen der Funktionen Fi auf der rechten Seite und der anderen Termeauf der linken Seite die behauptete partielle Differentialgleichung folgt.
Eine Frage besteht nun darin, ob die Summanden der Funktion F (z, w) bekannt sind, daS(n,m, z, w) die wahrscheinlichkeitserzeugende Funktion hn,m(v1, v2) beinhaltet. Man muss da-her die folgenden zwei Falle unterscheiden:
• (n − α,m − β) ∈ S\A und (n,m) ∈ A: In diesem Fall startet man bereits in einemAbsorptionspunkt. Daher gilt hn,m(v1, v2) = vn1 v
m2 .
• (n,m) ∈ S\A und (n− α,m− β) ∈ A: In diesem Fall ist hn,m(v1, v2) unbekannt.
Eine hinreichende Bedingung, um den zweiten Fall zu verhindern, ist gegeben durch α, β, γ, δ ≤ 0mit A = {0, 1, . . . , x} × N0 ∪ N0 × {0, 1, . . . , y}.Fur 2× 2-Urnen mit nicht-positiven Eintragen
M =
(
−α −β−γ −δ
)
, α, β, γ, δ ∈ N0
erfullt die zugehorige erzeugende Funktion H(z, w) somit die Rumpf-Differentialgleichung
z(1− zαwβ)Hz(z, w) + w(1− zγwδ)Hw(z, w) = 0. (3.7)
Eine allgemeine Losung fur derartige Urnen mit Hilfe der Methode der Charakteristiken zubestimmen, scheitert am Finden eines ersten Integrals des zugehorigen charakteristischen Diffe-rentialgleichungssystems
z = z(1− zαwβ), w = w(1− zγwδ). (3.8)
3.3. ABLEITEN DER GRENZVERTEILUNGEN 47
Dennoch lasst sich fur mehrere Klassen solcher Urnenmodelle eine Losung finden ([2],[3]). ImFolgenden wird dies fur die Modelle
”Verallgemeinertes Ziehen ohne Zurucklegen“,
”OK Corral“
und das”verallgemeinerte Pillen-Problem“ ausgefuhrt.
3.3 Ableiten der Grenzverteilungen
Nach Bestimmung der erzeugenden Funktion H(z, w) konnen die Wahrscheinlichkeiten aus denKoeffizienten abgelesen werden. Zur Bestimmung der Grenzverteilungen fur n → ∞ und/oderm→ ∞ in der Inititalkonfiguration mit n weißen und m schwarzen Kugeln, wird im Folgendenofters die
”Methode der Momente“ verwendet, die auf dem Satz von Frechet und Shohat basiert:
Satz 12 (Satz von Frechet und Shohat): Sei X eine Zufallsvariable mit einer Verteilung,sodass alle Momente existieren und keine andere Verteilung die gleichen Momente besitzt. Istweiters Xn eine Folge von Zufallsvariablen, die
limn→∞
E(Xkn) = E(Xk), fur alle k ≥ 1
erfullt, dann folgt Xn(D)−−→ X, d.h. Xn konvergiert in der Verteilung (punktweise Konvergenz
der Verteilungsfunktionen) gegen X.
Beweis. [6]
Um die Eindeutigkeit der Verteilung aus den Momenten festzustellen, stehen hinreichende Be-dingungen zur Verfugung:
Lemma 9: Bezeichnet X eine reellwertige Zufallsvariable mit den s-ten Momenten µs undψX(t) := E(etX) =
∑
s≥0
ts
s!µs die momenterzeugende Funktion, so gilt: Konvergiert ψX(t) in einer
Umgebung von 0, wird durch (µs)s≥0 eine eindeutige Verteilung festgelegt.
Beweis. [7]
Satz 13 (Carleman’s Condition): Eine Folge von endlichen Momenten (µs)s≥1 legt eineeindeutige Verteilung fest, falls
∑
s≥1
µ− 1
2s2s = ∞.
Beweis. [8]
Im Bereich der Urnenmodelle haufig auftretende Verteilungen werden nun vorgestellt.
Definition 10: Die Kumaraswamy-Verteilung Kr,u mit den reellen, positiven Parametern r
und u ist durch die auf [0, 1] definierte Dichtefunktion
fr,u(t) = rutr−1(1− tr)u−1
48 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
festgelegt.
Lemma 10: Die Momente der Kumaraswamy-Verteilung Kr,u sind durch
E(Ks) =Γ(u+ 1)Γ(1 + s
r)
Γ(u+ 1 + sr)
, u, r > 0
gegeben und legen eine eindeutige Verteilung fest.
Beweis.
E(Ks) =
∫ 1
0tsfr,u(t)dt = ru
∫ 1
0tr+s−1(1− tr)u−1dt.
Substituiert man q = tr, folgt (dqdt
= rtr−1)
E(Ks) = u
∫ 1
0q
sr (1− q)u−1dq = uB
(s
r+ 1, u
)
=
=Γ(u+ 1)Γ(1 + s
r)
Γ(u+ 1 + sr)
.
Die momenterzeugende Funktion ψK erfullt
ψK(t) =∑
j≥0
tj
j!E(Kj) =
∑
j≥0
tj
j!
Γ(u+ 1)Γ(1 + jr)
Γ(u+ 1 + jr)
.
Fur j → ∞ giltΓ(1 + j
r)
Γ(1 + jr+ u)
∼ ru
ju,
und daher folgt mit
∣
∣
∣
∣
Γ(1+ jr)
Γ(1+ jr+u)
− ru
ju
∣
∣
∣
∣
< ǫ fur alle j ≥ j0
|ψK(t)| ≤ c1 + c2∑
j≥j0
|t|jj!j−u + c3
∑
j≥j0
|t|jj!
≤ c1 + c2e|t| + c3e
|t| <∞.
Aus Lemma 9 folgt, dass die Momente eine eindeutige Verteilung festlegen.
Definition 11: Die Weibull-Verteilung Wr,u mit den reellen, positiven Parametern r und u istdurch die auf [0,∞) definierte Dichtefunktion
fr,u(t) =u
r
(
t
r
)u−1
exp
(
−(
t
r
)u)
festgelegt.
Lemma 11: Das s-te Moment einer Weibull-verteilten Zufallsvariable mit Parametern r und uerfullt
E(W s) = rsΓ(
1 +s
u
)
.
Fur u ≥ 12 legen die Momente eine eindeutige Verteilung fest.
3.3. ABLEITEN DER GRENZVERTEILUNGEN 49
Beweis. Es gilt
E(W s) =
∫ ∞
0xsu
r
(x
r
)u−1exp
(
−(x
r
)u)
dx.
Substituiert man q =(
xr
)u, folgt ( dq
dx= u
r
(
xr
)u−1)
E(W s) = rs∫ ∞
0q
su e−qdq = rsΓ(1 +
s
u).
Fur u ≥ 1 und |t| < 12r folgt unmittelbar die Konvergenz der momenterzeugenden Funktion:
|ψW (t)| ≤∑
s≥0
|t|ss!rsΓ (1 + s) ≤
∑
s≥0
1
2s<∞.
Der Fall 0 < u < 1 wird in [9] behandelt. Es wird nachgewiesen, dass fur 12 ≤ u < 1 die Momente
eine eindeutige Verteilung festlegen, wahrend fur 0 < u < 12 verschiedene Verteilungen mit s-tem
Moment rsΓ(
1 + su
)
existieren.
50 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.1: Verlaufe beim klassischen Ziehen ohne Zurucklegen. Simulation durch MATLAB-Aufruf urnEvolutionPlot([-1 0; 0 -1], 200, [100,100],20,1,3).
3.4 Verallgemeinertes Ziehen ohne Zurucklegen
Verallgemeinertes Ziehen ohne Zurucklegen wird durch die UbergangsmatrixM =
(
−α 00 −δ
)
modelliert (α, δ ≥ 1). Im klassischen Fall (α = δ = 1) werden aus einer Urne, die anfangs n weißeund m schwarze Kugeln enthalt, so lange zufallig Kugeln ohne Zurucklegen gezogen, bis keineschwarzen Kugeln mehr vorhanden sind. Von Interesse ist dann die Anzahl der verbleibendenweißen Kugeln in der Urne. Im verallgemeinerten Fall befinden sich zu Beginn αn weiße und δmschwarze Kugeln in der Urne. Es wird wieder zufallig eine Kugel gezogen, aber im Unterschiedzum klassischen Fall, werden beim Ziehen einer weißen Kugel weitere α − 1 weiße Kugeln undbeim Ziehen einer schwarzen Kugel weitere δ − 1 schwarze Kugeln aus der Urne entfernt.
Den Schritten in [3] folgend, soll die Zufallsvariable Xαn,δm untersucht werden, die mitP{Xαn,δm = αk} die Wahrscheinlichkeit beschreibt, dass beim verallgemeinerten Ziehen ohneZurucklegen bei einer Initialkonfiguration von αn weißen Kugeln und δm schwaren Kugeln ge-nau αk (0 ≤ k ≤ n) weiße Kugeln in der Urne verbleiben, nachdem alle schwarzen Kugelngezogen wurden.
In Abbildung 3.1 sind die Verlaufe von 20 klassischen Ziehungen mit Zurucklegen mit 100 weißenund 100 schwarzen Kugeln dargestellt.
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 51
Ubergangsmatrix: M :=
(
−α 00 −δ
)
, α, δ ∈ N
Definitionsmenge: S := {(αn, δm)|m,n ∈ N0}Absorptionsmenge: A := {(αn, 0)|n ∈ N0} ⊆ SInitialkonfiguration: I := (αn, δm)Wahrscheinlichkeitserzeugende Funktion: hn,m(v) :=
∑
k≥0
P{Xαn,δm = αk}vαk
Erzeugende Funktion: H(z, w) :=∑
n≥1
∑
m≥1hn,m(v)znwm
Durch Unterscheidung, welche Kugelfarbe gezogen wird, erhalt man wie bei (3.5) fur hn,m(v)die Rekursion
hn,m(v) =δm
αn+ δmhn,m−1(v) +
αn
αn+ δmhn−1,m(v), n,m ≥ 1. (3.9)
Sind zu Beginn keine schwarzen Kugeln in der Urne, stoppt der Vorgang mit Wahrscheinlichkeit1 mit αn weißen Kugeln, d.h. hn,0(v) = vαn, n ≥ 0. Startet man ohne weiße Kugeln, sindnach dem Ziehen der letzten schwarzen Kugel weiterhin keine weißen Kugeln in der Urne, d.h.h0,m(v) = 1,m ≥ 0.
Die partielle Differentialgleichung fur H(z, w) erhalt man durch Multiplikation von (3.9) mitden Faktoren αn+ δm, zn, wm und anschließender Summation fur n,m ≥ 1:
Die linke Seite von (3.9) ergibt somit direkt
αzHz(z, w) + δwHw(z, w).
Fur den ersten Summanden auf der rechten Seite von (3.9) berechnet man
∑
m≥1
∑
n≥1
δmhn,m−1(v)znwm = δw
∑
m≥0
∑
n≥1
(m+ 1)hn,m(v)znwm =
= δw2Hw(z, w) + δw∑
n≥1
hn,0(v)zn + δwH(z, w) =
= δw2Hw(z, w) + δwvαz
1− vαz+ δwH(z, w).
Aufgrund der Symmetrie (z, α, n) ↔ (w, δ,m) ergibt der zweite Summand auf der rechten Seitevon (3.9)
αz2Hz(z, w) + αz∑
m≥1
h0,m(v)wm + αzH(z, w) =
= αz2Hz(z, w) + αzw
1− w+ αzH(z, w).
Insgesamt erhalt man daher die folgende partielle Differentialgleichung fur H(z, w):
αz(1− z)Hz + δw(1− w)Hw − (αz + δw)H =δwvαz
1− vαz+
αzw
1− w. (3.10)
52 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Gemaß der Methode der Charakteristiken betrachet man zunachst die Rumpf-Differentialgleichung
αz(1− z)Hz + δw(1− w)Hw = 0 (3.11)
und ermittelt eine Losung durch Auffinden eines Integrals des entsprechenden charakteristischenDifferentialgleichungssystems (z = z(t), w = w(t)):
z = αz(1− z), w = δw(1− w).
Durch Trennung der Variablen erhalt man
dz
dw=
αz(1− z)
δw(1− w),
⇒∫
δ
z(1− z)dz =
∫
α
w(1− w)dw,
⇒ δ
∫
1
z+
1
1− zdz = α
∫
1
w+
1
1− wdw,
⇒ δ(log z − log (1− z)) = α(logw − log (1− w)) + c1,
⇒ log
(
zδ
(1− z)δ
)
= log
(
wα
(1− w)α
)
+ c1,
⇒ zδ(1− w)α
wα(1− z)δ= const.
Die gesuchte Losung der Rumpf-Differentialgleichung ist durch das erste Integral ξ(z, w) =zδ(1−w)α
wα(1−z)δgegeben. Nach Substitution von ξ(z, w) und einer noch zu definierenden Funktion
η(z, w) vereinfacht sich die partielle Differentialgleichung (3.10) aufgrund von (3.4) undG(ξ, η) := H(z, w) zu
[αz(1− z)ηz + δw(1− w)ηw]Gη − (αz + δw)G =δwvαz
1− vαz+
αzw
1− w.
Wahlt man η(z, w) := zδ
(1−z)δ, folgt ηz = δ zδ−1
(1−z)δ+1 bzw. ηw = 0 und es resultiert die lineare
Differentialgleichung 1.Ordnung in η:
αδηGη − (αz + δw)G =δwzvα
1− vαz+
αzw
1− w.
Aus η = zδ
(1−z)δbzw. η
ξ= wα
(1−w)α folgt z = η1δ
1+η1δbzw. w = η
1α
ξ1α+η
1α
und nach Substitution
αδηGη −(
αη
1δ
1 + η1δ
+ δη
1α
ξ1α + η
1α
)
G =δvαη
1α+ 1
δ
(η1α + ξ
1α )(1 + η
1δ (1− vα))
+αη
1α+ 1
δ
ξ1α (1 + η
1δ ). (3.12)
(η, ξ)-Transformation:
ξ(z, w) = zδ(1−w)α
wα(1−z)δ, η(z, w) = zδ
(1−z)δ,
z(η, ξ) = η1δ
1+η1δ, w(η, ξ) = η
1α
ξ1α+η
1α.
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 53
Die homogene Differentialgleichung
αδηGη −(
αη
1δ
1 + η1δ
+ δη
1α
ξ1α + η
1α
)
G = 0
kann durch Trennung der Variablen gelost werden:
dG
dη=
(
η1δ−1
δ(1 + η1δ )
+η
1α−1
α(ξ1α + η
1α )
)
G,
⇒ logG(ξ, η) =
∫
η1δ−1
δ(1 + η1δ )dη +
∫
η1α−1
α(ξ1α + η
1α )dη.
Das erste Integral kann mit der Substitution u = 1 + η1δ berechnet werden (du
dη= η
1δ−1
δ):
∫
η1δ−1
δ(1 + η1δ )dη =
∫
1
udu = log(1 + η
1δ ) + C1(ξ).
Das zweite Integral berechnet man analog mit der Substitution u = ξ1α + η
1α :
∫
η1α−1
α(ξ1α + η
1α )dη = log(ξ
1α + η
1α ) + C2(ξ)
und erhalt daraus die Losung der homogenen Differentialgleichung
G[h](ξ, η) = (1 + η1δ )(ξ
1α + η
1α )C(ξ).
Nach Rucksubstitution erhalt man die homogene Losung in z und w:
H [h](z, w) =z
δα
(1− z)δα+1
1
wC
(
zδ(1− w)α
(1− z)δwα
)
.
Eine Partikularlosung findet man durch Variation der Konstanten (C = C(η, ξ)):
G[p](ξ, η) := (1 + η1δ )(ξ
1α + η
1α )C(η, ξ),
G[p]η (ξ, η) = C(η, ξ)
(
1
δη
1δ−1(ξ
1α + η
1α ) +
1
αη
1α−1(1 + η
1δ )
)
+ Cη(η, ξ)(
(1 + η1δ )(ξ
1α + η
1α ))
.
Nach Einsetzen in die Differentialgleichung (3.12) werden gemaß Variation der Konstanten dieTerme mit Faktor C(η, ξ) ausgeloscht und es verbleibt
ηαδCη(η, ξ)(
(1 + η1δ )(ξ
1α + η
1α ))
=δvαη
1α+ 1
δ
(η1α + ξ
1α )(1 + η
1δ (1− vα))
+αη
1α+ 1
δ
ξ1α (1 + η
1δ ).
Es folgt
C(η, ξ) =vα
α
∫
η1α+ 1
δ−1
(η1α + ξ
1α )2(1 + η
1δ )(1 + η
1δ (1− vα))
dη +1
δ
∫
η1α+ 1
δ−1
(1 + η1δ )2ξ
1α (ξ
1α + η
1α )dη =
=vα
α
∫ η
0
s1α+ 1
δ−1
(s1α + ξ
1α )2(1 + s
1δ )(1 + s
1δ (1− vα))
ds+1
δ
∫ η
0
s1α+ 1
δ−1
(1 + s1δ )2ξ
1α (ξ
1α + s
1α )ds,
54 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
und mit der Substitution q = sηschließlich
C(η, ξ) =vα
α
∫ 1
0
η1α+ 1
δ q1α+ 1
δ−1
(η1α q
1α + ξ
1α )2(1 + η
1δ q
1δ )(1 + η
1δ q
1δ (1− vα))
dq+1
δ
∫ 1
0
η1α+ 1
δ q1α+ 1
δ−1
(1 + η1δ q
1δ )2ξ
1α (ξ
1α + q
1α η
1α )dq.
Die Rucksubstitution im ersten Integral erfolgt unter Verwendung der Gleichungen
1− z + zq1δ =
1 + η1δ q
1δ
1 + η1δ
,
1− z + zq1δ (1− vα) =
1 + η1δ q
1δ (1− vα)
1 + η1δ
,
1− w + wq1α =
ξ1α + η
1α q
1α
ξ1α + η
1α
,
zw =η
1α+ 1
δ
(1 + η1δ )(ξ
1α + η
1α ).
Es folgt
∫ 1
0
η1α+ 1
δ q1α+ 1
δ−1
(η1α q
1α + ξ
1α )2(1 + η
1δ q
1δ )(1 + η
1δ q
1δ (1− vα))
dq =
=zw
(1 + η1δ )(η
1α + ξ
1α )
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )(1− z + zq
1δ (1− vα))(1− w + wq
1α )2
dq.
Zur Rucksubsitution des zweiten Integrals verwendet man zusatzlich
zw
1− w=
η1α+ 1
δ
ξ1α (1 + η
1δ )
und erhalt
∫ 1
0
η1α+ 1
δ q1α+ 1
δ−1
(1 + η1δ q
1δ )2ξ
1α (ξ
1α + q
1α η
1α )dq =
=zw
(1− w)(1 + η1δ )(η
1α + ξ
1α )
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )2(1− w + wq
1α )dq.
Die Partikularlosung H [p](z, w) = G[p](ξ, η) = C(η, ξ)(1+η1δ )(η
1α +ξ
1α ) der Differentialgleichung
(3.12) ist somit gegeben durch
H [p](z, w) =zwvα
α
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )(1− z + zq
1δ (1− vα))(1− w + wq
1α )2
dq
+zw
δ(1− w)
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )2(1− w + wq
1α )dq.
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 55
Die allgemeine Losung ist durch H(z, w) = H [h](z, w) + H [p](z, w) gegeben, wobei die unbe-kannte, stetig differenzierbare Funktion C der homogenen Losung aus der AnfangsbedingungH(0, 0) = 0 bestimmt werden kann. Nahert man sich dem Ursprung entlang z = z(w) = w
αδ x
1δ ,
wobei x eine beliebige, feste, reelle Zahl ist, folgt aus der Analytizitat von H in einer Umgebungvon 0:
0 = H(0, 0) = limw→0
H(z(w), w) = limw→0
H [h](z(w), w) + limw→0
H [p](z(w), w) = x1αC (x) .
Folglich gilt C(x) = 0 fur alle x ∈ R und schließlich wurde mit H(z, w) = H [p](z, w) der folgendeSatz gezeigt:
Satz 14: Die erzeugende Funktion H(z, w), in der der Koeffizient bei znwmvαk die Wahrschein-lichkeit angibt, dass beim verallgemeinerten Ziehen ohne Zurucklegen mit anfangs αn weißenund δm schwarzen Kugeln noch αk weiße Kugeln in der Urne sind, nachdem die letzte schwarzeKugel gezogen wurde, ist gegeben durch
H(z, w) =zwvα
α
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )(1− z + zq
1δ (1− vα))(1− w + wq
1α )2
dq
+zw
δ(1− w)
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )2(1− w + wq
1α )dq.
(3.13)
Satz 15: Die Wahrscheinlichkeit P{Xαn,δm = αk}, dass beim verallgemeinerten Ziehen ohneZurucklegen mit anfangs αn weißen und δm schwarzen Kugeln noch αk weiße Kugeln in der Urnesind, nachdem die letzte schwarze Kugel gezogen wurde, betragt fur n,m ≥ 1 und 0 ≤ k ≤ n:
P{Xαn,δm = αk} = [znwmvαk]H(z, w) =mδ
α
n!
k!
m−1∑
l=0
(−1)l(
m− 1
l
)
Γ((l + 1) δα+ k)
Γ((l + 1) δα+ n+ 1)
.
Beweis. Sei zunachst k = 0.Aufgrund von α ≥ 1 liefert nur der zweite Summand von (3.13) einen Beitrag fur [v0]H(z, w).Es folgt
P{Xαn,δm = 0} = [znwm]zw
δ(1− w)
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )2(1− w + wq
1α )dq.
Aus
1
(1− z(1− q1δ ))2
=
∑
j≥0
zj(1− q1δ )j
∑
k≥0
zk(1− q1δ )k
=∑
m≥0
(m+ 1)zm(1− q1δ )m
56 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
folgt fur n,m ≥ 1:
P{Xαn,δm = 0} =
=1
δ[zn−1wm]
∑
j≥1
wj
∫ 1
0q
1α+ 1
δ−1
∑
i≥0
(i+ 1)zi(1− q1δ )i
∑
k≥0
wk(1− q1α )k
dq =
=n
δ[wm]
∑
j≥1
wj
∫ 1
0q
1α+ 1
δ−1(1− q
1δ )n−1
∑
k≥0
wk(1− q1α )k
dq =
=n
δ
m−1∑
l=0
∫ 1
0q
1α+ 1
δ−1(1− q
1δ )n−1(1− q
1α )ldq =
=n
δ
∫ 1
0q
1α+ 1
δ−1(1− q
1δ )n−1 (1− q
1α )m − 1
−q 1α
dq.
Substituiert man q = uδ ( dqdu
= δuδ−1), folgt die gewunschte Gleichheit fur k = 0:
P{Xαn,δm = 0} = −n∫ 1
0u1−δ(1− u)n−1
(
(1− uδα )m − 1
)
uδ−1du =
= −nm∑
l=1
(−1)l(
m
l
)∫ 1
0(1− u)n−1u
δlα du =
= n
m−1∑
l=0
(−1)l(
m
l + 1
)
B
(
n,δ(l + 1)
α+ 1
)
=
= n!m−1∑
l=0
(−1)l(
m− 1
l
)
m
l + 1
Γ( δ(l+1)α
+ 1)
Γ( δ(l+1)α
+ n+ 1)=
=mδ
αn!
m−1∑
l=0
(−1)l(
m− 1
l
)
Γ( δ(l+1)α
)
Γ( δ(l+1)α
+ n+ 1).
Sei nun 1 ≤ k ≤ n. Fur den Koeffizienten bei vk liefert in (3.13) nur der erste Summand einenBeitrag. Aus der Entwicklung
1(
1− z + zq1δ
)(
1− z + zq1δ (1− vα)
) =1
(
1− z + zq1δ
)2
1(
1− zq1δ vα
1−z+zq1δ
) =∑
k≥0
vαkzkqkδ
(1− z + zq1δ )k+2
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 57
folgt fur 1 ≤ k ≤ n:
P{Xαn,δm = αk} = [znwmvαk]H(z, w) =
= [znwmvαk]zwvα
α
∫ 1
0
q1α+ 1
δ−1
(1− z + zq1δ )(1− z + zq
1δ (1− vα))(1− w + wq
1α )2
dq =
=1
α[zn−1wm−1vα(k−1)]
∫ 1
0q
1α+ 1
δ−1
∑
l≥0
vαlzlqlδ
(1− z + zq1δ )l+2
∑
i≥0
(i+ 1)wi(1− q1α )i
dq =
=1
α[zn−1wm−1]
∫ 1
0q
1α+ 1
δ−1 zk−1q
k−1δ
(1− z + zq1δ )k+1
∑
i≥0
(i+ 1)wi(1− q1α )i
dq =
=1
α[zn−1]
∫ 1
0q
1α+ 1
δ−1 zk−1q
k−1δ
(1− z + zq1δ )k+1
m(1− q1α )m−1dq =
=m
α
∫ 1
0q
1α+ k
δ−1(1− q
1α )m−1[zn−k]
1
(1− z + zq1δ )k+1
dq.
Die Funktion f(z) = 1
(1−z+zq1δ )k+1
ist analytisch in einer Umgebung von 0.
Nach der Cauchy’schen Integralformel gilt daher fur festes 0 < q < 1
[zn−k]f(z) =1
2πi
∮
Kr(0)
1
(1− ζ(1− q1δ ))k+1
1
ζn−k+1dζ.
Substituiert man z = ζ(1− q1δ ), folgt (dz
dζ= 1− q
1δ )
[zn−k]f(z) =1
2πi
∮
Kr(1−q1/δ)
(0)
1
(1− z)k+1
1
zn−k+1(1− q
1δ )n−kdz
= (1− q1δ )n−k[zn−k]
1
(1− z)k+1.
Aus 1(1−z)k+1 =
∑
j≥0
(−k−1j
)
(−1)jzj =∑
j≥0
(
k+jj
)
zj folgt schließlich
[zn−k]f(z) = (1− q1δ )n−k
(
n
k
)
und damit
P{Xαn,δm = αk} =m
α
(
n
k
)∫ 1
0q
1α+ k
δ−1(1− q
1α )m−1(1− q
1δ )n−kdq
=m
α
(
n
k
)m−1∑
l=0
(−1)l(
m− 1
l
)∫ 1
0q
l+1α
+ kδ−1(1− q
1δ )n−kdq.
58 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.2: Verteilung der verbleibenden weißen Kugeln beim klassischen Ziehen oh-ne Zurucklegen mit Initialkonfiguration (50, 50). 5 Simulationen durch MATLAB-Aufruf:histogramPlotEndConfig([-1 0; 0 -1], 100, [50 50], 10000, 1, 1)
Substituiert man q = uδ, folgt
P{Xαn,δm = αk} =mδ
α
(
n
k
)m−1∑
l=0
(−1)l(
m− 1
l
)∫ 1
0u
δ(l+1)α
+k−1(1− u)n−kdu =
=mδ
α
(
n
k
)m−1∑
l=0
(−1)l(
m− 1
l
)
B
(
δ(l + 1)
α+ k, n− k + 1
)
=
=mδ
α
n!
k!
m−1∑
l=0
(−1)l(
m− 1
l
)
Γ( δ(l+1)α
+ k)
Γ( δ(l+1)α
+ n+ 1).
Die in Satz 15 bestimmte Verteilung wurde in mehreren MATLAB-Simulationen getestet. DieErgebnisse sind in den Abbildungen 3.2 und 3.3 dargestellt.
Satz 16: Die Momente von Xαn,δm bzw. die faktoriellen Momente vonXαn,δm
αsind fur s ≥ 1
durch
E(Xsαn,δm) = αs
s∑
j=0
{
s
j
}
nj
(
m+αjδ
m
)
, E
((
Xαn,δm
α
)s)
=ns
(
m+αsδ
m
)
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 59
Abbildung 3.3: Verteilung der verbleibenden weißen Kugeln beim verallgemeinerten Ziehen ohneZurucklegen (α = 1, δ = 2) mit Initialkonfiguration (50, 50). 5 Simulationen durch MATLAB-Aufruf: histogramPlotEndConfig([-1 0; 0 -2], 100, [50 50], 10000, 1, 1)
60 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
gegeben, wobei
{
s
j
}
die Stirling-Zahlen zweiter Art bezeichnet.
Beweis. Fur Yαn,δm :=Xαn,δm
αgilt
E(Ysαn,δm) =
n∑
k=0
ksP{Yαn,δm = k} =n∑
k=s
ksP{Xαn,δm = αk} =
=δm
αn!
n∑
k=s
1
(k − s)!
m−1∑
l=0
(−1)l(
m− 1
l
)
Γ((l + 1) δα+ k)
Γ((l + 1) δα+ n+ 1)
=
=δm
αn!
m−1∑
l=0
(−1)l(
m− 1
l
)
1
Γ((l + 1) δα+ n+ 1)
n−s∑
k=0
1
k!Γ
(
(l + 1)δ
α+ k + s
)
.
Unter Verwendung der Identitat (siehe [4])
n∑
k=0
(
x+ k
k
)
=
(
x+ n+ 1
n
)
folgt
n−s∑
k=0
1
k!Γ
(
(l + 1)δ
α+ k + s
)
=n−s∑
k=0
1
k!
Γ((l + 1) δα+ k + s)
Γ((l + 1) δα+ s)
Γ
(
(l + 1)δ
α+ s
)
=
= Γ
(
(l + 1)δ
α+ s
) n−s∑
k=0
(
(l + 1) δα+ k + s− 1
k
)
=
= Γ
(
(l + 1)δ
α+ s
)(
(l + 1) δα+ n
n− s
)
,
und damit
E(Ysαn,δm) =
δm
αn!
m−1∑
l=0
(−1)l(
m− 1
l
)
Γ((l + 1) δα+ s)
Γ((l + 1) δα+ n+ 1)
(
(l + 1) δα+ n
n− s
)
=δm
αns
m−1∑
l=0
(−1)l(
m− 1
l
)
1
(l + 1) δα+ s
=
= mnsm−1∑
l=0
(−1)l(
m− 1
l
)
1
l + 1 + sαδ
.
Verwendet man nun die Idenditat (siehe [4])
n∑
k=0
(
n
k
)
(−1)k
x+ k=
1
x(
x+nn
) ,
erhalt man die behauptete Gleichung fur die faktoriellen Momente vonXαn,δm
α:
E(Ysαn,δm) = mns
1
(1 + αsδ)(m+αs
δm−1
)=
ns(
m+αsδ
m
).
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 61
Aus der Eigenschaft (siehe [4])
xs =s∑
j=1
{
s
j
}
xj (3.14)
der Stirling-Zahlen zweiter Art folgt
E(Y sαn,δm) =
n∑
j=0
jsP{Yαn,δm = j} =n∑
j=0
s∑
k=1
{
s
k
}
jkP{Yαn,δm = j} =
=s∑
k=1
{
s
k
} n∑
j=0
jkP{Yαn,δm = j} =s∑
k=1
{
s
k
}
E(Ykαn,δm) =
=s∑
k=1
{
s
k
}
nk
(
m+αkδ
m
)
,
und schließlich wegen
{
s
0
}
= 0, s ≥ 1:
E(Xsαn,δm) = αs
s∑
j=0
{
s
j
}
nj
(
m+αjδ
m
)
.
Satz 17: Die ZufallsvariableXαn,δm
αnkonvergiert fur festes m und n → ∞ in der Verteilung
gegen eine Kumaraswamy-verteilte Zufallsvariable mit Parametern δαund m:
Xαn,δm
αn
(D)−−→ K δα,m.
Beweis. Der Beweis erfolgt uber den Satz von Frechet und Shohat:
limn→∞
E
((
Xαn,δm
αn
)s)
= limn→∞
1
ns
s∑
j=0
{
s
j
}
nj
(
m+αjδ
m
)
= limn→∞
1
ns
{
s
s
}
ns(
m+αsδ
m
)=
1(
m+αsδ
m
).
Aus Lemma 10 folgt
E(Ks) =Γ(m+ 1)Γ(1 + αs
δ)
Γ(m+ 1 + αsδ)
=m!
(m+ αsδ)(m+ αs
δ− 1) · · · (1 + αs
δ)=
1(
m+αsδ
m
)=
= limn→∞
E
((
Xαn,δm
αn
)s)
,
womit der Satz von Frechet und Shohat angewandt werden kann.
In Abbildung 3.4 werden die gemaß Satz 17 erwartete Grenzverteilung und die durch eineMATLAB-Simulation erhaltene Haufigkeitsverteilung gegenubergestellt. Die Simulation wur-de mit den Parametern α = 1, δ = 2 und anfangs 10000 weißen Kugeln bzw. 50 schwarzenKugeln gestartet. In insgesamt 10000 Durchgangen wurde jeweils die Anzahl der verbleibendenweißen Kugeln gespeichert. Das erhaltene Histogramm und die skalierte Kumaraswamy-Dichtemit Parametern 2 und 25 (100 ∗ f2,25( t
10000)) sind in Abbildung 3.4 dargestellt.
62 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.4: Grenzverteilung der verbleibenden weißen Kugeln beim verallgemeinerten Zie-hen ohne Zurucklegen (α = 1, δ = 2) mit Initialkonfiguration (10000, 50). MATLAB-Aufruf:histogramPlotEndConfig([-1 0; 0 -2], 100000, [10000 50], 10000, 1, 1)
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 63
Satz 18: Die Zufallsvariable Xαn,δm konvergiert fur festes n und m → ∞ in der Verteilunggegen 0:
Xαn,δm(D)−−→ 0.
Beweis. Wegen(
m+ αjδ
m
)
=Γ(m+ αj
δ+ 1)
Γ(αjδ+ 1)Γ(m+ 1)
∼ 1
Γ(αjδ+ 1)
mαjδ
folgt
limm→∞
E(Xsαn,δm) = lim
m→∞αs
s∑
j=0
{
s
j
}
nj
(
m+αjδ
m
)
= 0.
Satz 19: Im Fall, dass m→ ∞ und n = n(m) als Funktion von m wachst, ist die Grenzvertei-
lung vom Verhalten des Quotienten mαδ
n(m) abhangig:
1. mαδ
n(m) → 0: Das Wachstum der Anfangsanzahl schwarzer Kugeln wird (exponentiell gemaß
dem Verhaltnis αδ) vom Wachstum weißer Kugeln dominiert. Dann konvergiert
mαδ Xαn,δm
αn
fur 2δ ≥ α in der Verteilung gegen eine Weibull-verteilte Zufallsvariable mit Parametern1 und δ
α:
mαδXαn,δm
αn
(D)−−→W1, δα.
2. mαδ
n(m) → ρ: Die Anfangsanzahl schwarzer Kugeln wachst (exponentiell gemaß
dem Verhaltnis αδ) im Vergleich zur Anfangsanzahl weißer Kugeln mit der Rate ρ. Dann
konvergieren die Momente der ZufallsvariableXαn,δm
αgegen
E(Xs) =s∑
j=0
{
s
j
}
ρ−jΓ
(
1 +αj
δ
)
.
3. mαδ
n(m) → ∞: Das Wachstum der Anfangsanzahl schwarzer Kugeln dominiert (exponentiell
gemaß dem Verhaltnis αδ) das Wachstum der Anfangsanzahl weißer Kugeln. Dann konver-
giert Xαn,δm in der Verteilung gegen 0.
Xαn,δm(D)−−→ 0.
Beweis. Es gilt
E
((
mαδXαn,δm
αn
)s)
= mαsδ
1
n(m)s
s∑
j=0
{
s
j
}
n(m)j
(
m+αjδ
m
)
.
Wegen (1.2) folgt
mαsδ
1
n(m)s
{
s
j
}
n(m)j
(
m+αjδ
m
)
∼(
mαδ
n(m)
)s{
s
j
}
Γ
(
αj
δ+ 1
)
n(m)j
mαjδ
.
64 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.5: Schwache Konvergenz gegenWeibull-verteilte Zufallsvariable. Simulationen durchMATLAB-Aufruf histogramPlotEndConfig([-1 0; 0 -2], 100000, [10000 10000], 10000, 1, 1).
Fur j < s konvergieren daher im Fall mαδ
n(m) → 0 die Summanden gegen 0 und somit gilt
E
((
mαδXαn,δm
αn
)s)
m→∞−−−−→ Γ(αs
δ+ 1)
.
Aus Lemma 11 folgtm
αδ Xαn,δm
αn
(D)−−→W1, δα.
Im Fall mαδ
n(m) → ρ folgt wegen(
m+αjδ
m
)
∼ mαjδ
Γ(1+αjδ):
E
((
Xαn,δm
α
)s)
=s∑
j=0
{
s
j
}
n(m)j
(
m+αjδ
m
)
m→∞−−−−→s∑
j=0
{
s
j
}
ρ−jΓ(1 +αj
δ).
Im Fall mαδ
n(m) → ∞ folgt
E(
Xsαn,δm
)
= αss∑
j=0
{
s
j
}
n(m)j
(
m+αjδ
m
)
m→∞−−−−→ 0.
3.4. VERALLGEMEINERTES ZIEHEN OHNE ZURUCKLEGEN 65
Fur den Fall mαδ
n(m) → 0 wurde eine Simulation mit den Parametern α = 1, δ = 2 und n(m) = 2m
durchgefuhrt. Gemaß Satz 19 konvergiert wegen√m
2m → 0 die Zufallsvariable√mXn(m),2m
n(m) gegeneine Weibull-verteilte Zufallsvariable mit Parametern 1 und 2. Dies wurde fur m = 5000 undsomit anfangs 10000 weißen und 10000 schwarzen Kugeln mit 10000 Simulationen getestet. Dieerhaltene Haufigkeitsverteilung fur die Anzahl verbleibender weißer Kugeln und die in Satz 19gezeigte, skalierte Grenzverteilung sind in Abbildung 3.5 gegenubergestellt.
66 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.6: Verlaufe im klassischen OK Corral-Problem. Simulation durch MATLAB-AufrufurnEvolutionPlot([0 -1; -1 0], 200, [100,100],50,1,1).
3.5 OK Corral
Das verallgemeinerte OK Corral-Problem wird durch die Ubergangsmatrix
M =
(
0 −β−γ 0
)
beschrieben und modelliert fur β = γ = 1 die Westernschießerei von Tombstone. Der Kampffindet zwischen zwei Gruppen mit anfangs n bzw. m Personen statt. Eine Person wird zufalligausgesucht und landet einen todlichen Treffer in der gegnerischen Gruppe. Von den verbleiben-den m + n − 1 Personen wird wieder zufallig eine Person ausgewahlt, die einen Gegner trifft.Der Kampf wird so lange fortgesetzt, bis von einer Gruppe keine Person mehr ubrig ist. Maninteressiert sich nun fur die Gewinnwahrscheinlichkeiten in Abhangigkeit von den Anfangsgroßenim fairen Fall (n ≈ m) bzw. im unfairen Fall (n ≪ m) und fur die Verteilung der ubrig blei-benden Personen in der Gewinnergruppe. Die Verallgemeinerung mit β ≥ 1 bzw. γ ≥ 1 kannals Verstarkung der Waffen interpretiert werden. In Abbildung 3.6 sind die Verlaufe von 50Auseinandersetzungen im klassischen Fall mit zwei gleich großen Gruppen von 100 Personendargestellt.
Fur das verallgemeinerte OK Corral Problem werden die folgenden Definitionen vorgenommen:
3.5. OK CORRAL 67
Ubergangsmatrix: M =
(
0 −β−γ 0
)
Definitionsmenge: S := {(γn, βm)|n,m ∈ N0}Absorptionsmenge: A := {(0, βm)|m ∈ N0} ∪ {(γn, 0)|n ∈ N0} ⊆ SInitialkonfiguration: I := (γn, βm)Wahrscheinlichkeitserz. Funktion: hn,m(v) :=
∑
k≥0
P{Xγn,βm = γk}vγk
Erzeugende Funktion: H(z, w) :=∑
n≥1
∑
m≥1hn,m(v)znwm
Den Schritten in [3] folgend, wird die Zufallsvariable Xγn,βm definiert, die die Anzahl deruberlebenden Personen aus der ersten Gruppe mit anfangs γn Personen zahlt. Die gesuchteWahrscheinlichkeit, dass bei den anfanglichen Gruppengroßen (n,m) aus der ersten Gruppe γkPersonen uberleben, ist somit durch [znwmvγk]H(z, w) gegeben.
Durch Unterscheidung welche Gruppe den ersten Treffer landet, erhalt man wie bei (3.5) eineRekursion fur die wahrscheinlichkeitserzeugende Funktion:
hn,m(v) =βm
γn+ βmhn−1,m(v) +
γn
γn+ βmhn,m−1(v), n,m ≥ 1. (3.15)
Sind zu Beginn in der zweiten Gruppe keine Personen, bleiben”nach“ dem Kampf γn Personen
in der ersten Gruppe ubrig. Startet die erste Gruppe ohne Personen, sind”nach“ dem Kampf
auch keine Personen in der Gruppe, daher hn,0(v) = vγn und h0,m(v) = 1. Multiplikation von(3.15) mit den Faktoren (γn + βm), zn und wm und anschließende Summation fur n,m ≥ 1liefert analog zu den Rechnungen in Lemma 8:
γzHz(z, w)+βwHw(z, w) = βzwHw(z, w)+βz∑
m≥1
mh0,m(v)wm+γwzHz(z, w)+γw∑
n≥1
nhn,0(v)zn.
Unter Verwendung von∑
n≥1nzn−1 =
(
11−z
)2resultiert daraus die partielle Differentialgleichung
fur H(z, w):
γz(1− w)Hz(z, w) + βw(1− z)Hw(z, w) =βzw
(1− w)2+
γwvγz
(1− vγz)2. (3.16)
Um eine Losung fur die Rumpf-Differentialgleichung
γz(1− w)Hz(z, w) + βw(1− z)Hw(z, w) = 0
zu finden, betrachtet man gemaß der Methode der Charakteristiken das zugehorige charakteri-stische System von Differentialgleichungen (z = z(t), w = w(t)):
z = γz(1− w), w = βw(1− z).
68 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Ein erstes Integral kann durch Trennung der Variablen folgendermaßen bestimmt werden:
dz
dw=γz(1− w)
βw(1− z),
⇒ β
γ
∫
1− z
zdz =
∫
1− w
wdw,
⇒ β
γ(log z − z) = logw − w + c1,
⇒ log
(
zβγ
ez βγ
)
= log( w
ew
)
+ c1,
⇒ zβγ
wew−z β
γ = const.
Eine Losung der Rumpf-Differentialgleichung ist daher durch ξ(z, w) := zβγ
wew−z β
γ gegeben.Wahlt man η := z wird die partielle Differentialgleichung (3.16) wegen (3.4) mit G(ξ, η) =H(z, w) zu einer gewohnlichen Differentialgleichung in η reduziert:
Gη(ξ, η) =wvγ
(1− vγz)2(1− w)+
βw
γ(1− w)3. (3.17)
Aufgrund von
w(η, ξ) =η
βγ
ξew−η β
γ (3.18)
besteht ein Zusammenhang zwischen w(ξ, η) und der Lambert’schen W-Funktion: Die Funktionx 7→ xex ist - wie man durch Differenzieren sieht - eine bijektive Abbildung von [−1,∞) auf[−1
e,∞). Die inverse AbbildungW ist daher auf [−1
e,∞) eindeutig durch die Funktionalgleichung
W (x)eW (x) = x gegeben und wird als Lambert’sche W-Funktion bezeichnet. Fur w in einer Um-
gebung von 0 liegt x(ξ, η) := −ηβγ e
−η βγ 1ξ= −z
βγ e
−z βγ w
zβγ
ez βγ−w
= −we−w im Eindeutigkeitsbe-
reich von W . Aus −w = x(ξ, η)e−(−w) folgt daher w(η, ξ) = −W (x(ξ, η)) = −W(
−ηβγ e
−η βγ 1ξ
)
.
(η, ξ)-Transformation:
ξ(z, w) = zβγ
wew−z β
γ , η(z, w) = z,
z(η, ξ) = η, w(η, ξ) = −W(
−ηβγ e
−η βγ 1ξ
)
.
Die Losung von (3.17) kann somit bestimmt werden:
H(z, w) = G(ξ, η) =
=
∫ η
0
−vγW(
−sβγ e
−sβγ 1ξ
)
(1− vγs)2(
1 +W(
−sβγ e
−sβγ 1ξ
))ds+
∫ η
0
−βW(
−sβγ e
−sβγ 1ξ
)
γ(
1 +W(
−sβγ e
−sβγ 1ξ
))3ds+ C(ξ) =
=
∫ 1
0
−vγηW(
−ηβγ q
βγ e
−qη βγ 1ξ
)
(1− vγqη)2(
1 +W(
−ηβγ q
βγ e
−qη βγ 1ξ
))dq +
∫ 1
0
−βηW(
−ηβγ q
βγ e
−qη βγ 1ξ
)
γ(
1 +W(
−ηβγ q
βγ e
−qη βγ 1ξ
))3dq + C(ξ).
3.5. OK CORRAL 69
Das Argument von W nach Rucksubstitution ist wegen (3.18) gegeben durch
−ηβγ q
βγ e
−qη βγ1
ξ= −weη
βγ−wq
βγ e
−qη βγ = −wq
βγ e
z βγ(1−q)−w
und daher
H(z, w) = −vγz∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
(1− vγzq)2(
1 +W(
−wqβγ e
z βγ(1−q)−w
))dq
− βz
∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
γ(
1 +W(
−wqβγ e
z βγ(1−q)−w
))3dq + C
(
zβγ
wew−z β
γ
)
.
Aus der Anfangsbedingung H(0, 0) = 0 und der Analytizitat von H(z, w) in einer Umgebungvon 0, kann die Funktion C bestimmt werden. Die Funktionalgleichung der Lambert’schen W-
Funktion liefert direkt W (0) = 0. Bildet man fur beliebiges, festes x ∈ R mit z = z(w) = (wx)γβ
den Grenzubergang w → 0 erhalt man
0 = H(0, 0) = limw→0
H(z(w), w) = C(x).
Satz 20: Die erzeugende Funktion H(z, w) des verallgemeinerten OK Corral Problems, wobeider Koeffizient bei znwmvγk die Wahrscheinlichkeit dafur angibt, dass bei einem Kampf zwischenzwei Gruppen mit anfangs γn bzw. βm Personen nach Ende der Schießerei γk Personen der erstenGruppe uberleben, ist gegeben durch
H(z, w) = −vγz∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
(1− vγzq)2(
1 +W(
−wqβγ e
z βγ(1−q)−w
))dq
− βz
γ
∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
(
1 +W(
−wqβγ e
z βγ(1−q)−w
))3dq.
(3.19)
Zum Ablesen der Koeffizienten mussen zunachst fur die Ausdrucke, die die Lambert’sche W-Funktion enthalten, Entwicklungen hergeleitet werden. Dies kann mit der Inversionsformel vonLagrange-Burmann erfolgen:
Lemma 12: Die Lambert’sche W-Funktion erfullt
−W (−x)1 +W (−x) =
∑
k≥1
kk−1
(k − 1)!xk, (3.20)
−W (−x)(1 +W (−x))3 =
∑
k≥1
kk
(k − 1)!xk. (3.21)
70 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Beweis. Um (3.20) herzuleiten, verwendet man die Inversionsformel von Lagrange-Burmann(Satz 1) mit y(x) = −W (−x), φ(x) = ex, f(x) = x
1−x. Dann folgt fur n ≥ 1:
[xn]− W (−x)1 +W (−x) =
1
n[un−1]
1
(1− u)2enu =
1
n
n−1∑
k=0
nk
k!(n− k) =
n−1∑
k=0
nk
k!−
n−1∑
k=1
nk−1
(k − 1)!
=nn−1
(n− 1)!.
Um (3.21) herzuleiten, folgt unter Anwendung der Inversionsformel mit f(x) = x(1−x)3
fur n ≥ 1:
[xn]−W (−x)
(1 +W (−x))3 =
=1
n[un−1]
1 + 2u
(1− u)4enu =
1
n
n−1∑
k=0
(
n− k + 2
3
)
nk
k!+
2
n
n−2∑
k=0
(
n− k + 1
3
)
nk
k!=
=nn−2
(n− 1)!+
1
6n
n−2∑
k=0
(n− k + 2)(n− k + 1)(n− k)nk
k!+
1
3n
n−2∑
k=0
(n− k + 1)(n− k)(n− k − 1)nk
k!=
=nn−2
(n− 1)!+
1
2n
n−2∑
k=0
(n− k)2(n− k + 1)nk
k!=
=nn−2
(n− 1)!+
1
2n
(
n−2∑
k=0
(n− k)(n− k + 1)nk+1
k!−
n−2∑
k=1
(n− k)(n− k + 1)nk
(k − 1)!
)
=
=nn−2
(n− 1)!+ 3
nn−2
(n− 2)!+
1
n
n−2∑
k=1
(n− k + 1)nk
(k − 1)!=
=nn−2
(n− 1)!+ 3
nn−2
(n− 2)!+
1
n
(
n−2∑
k=1
nk+1
(k − 1)!−
n−2∑
k=2
nk
(k − 2)!
)
=
=nn−2
(n− 1)!+ 3
nn−2
(n− 2)!+
nn−2
(n− 3)!=
=1
(n− 1)!
(
nn−2 + 3(n− 1)nn−2 + (n− 1)(n− 2)nn−2)
=
=nn
(n− 1)!
Satz 21: Die Wahrscheinlichkeit, dass im verallgemeinerten OK Corral-Problem mit Initial-konfiguration (γn, βm) aus der Gruppe mit γn Personen nach Ende der Schießerei genau γk
3.5. OK CORRAL 71
Personen uberleben ist gegeben durch (n,m ≥ 1):
P{Xγn,βm = 0} =1
n!(m− 1)!
βn
γn
m∑
l=1
(−1)m−l
(
m−1l−1
)
(
n+βγl
n
)
ln+m−1, (3.22)
P{Xγn,βm = γk} =k
(n− k + 1)!(m− 1)!
βn−k
γn−k
m∑
l=1
(−1)m−l
(
m−1l−1
)
( n+βγl
n−k+1
)
ln+m−1−k, 1 ≤ k ≤ n.
(3.23)
Beweis. Sei zunachst k = 0. Dann liefert in (3.19) nur das zweite Integral einen Beitrag:
P{Xγn,βm = 0} = [znwmv0]H(z, w) = [znwm]− βz
γ
∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
(
1 +W(
−wqβγ e
z βγ(1−q)−w
))3dq.
Aus (3.21) folgt
P{Xγn,βm = 0} =β
γ
∫ 1
0[zn−1wm]
∑
l≥1
ll
(l − 1)!wlq
βlγ e
z βlγ(1−q)−lw
dq =
=β
γ
∫ 1
0
m∑
l=1
ll
(l − 1)!q
βlγ [zn−1wm−l]e
z βlγ(1−q)
e−lwdq =
=β
γ
∫ 1
0
m∑
l=1
ll
(l − 1)!q
βlγβn−1
γn−1ln−1(1− q)n−1 1
(n− 1)!(−1)m−llm−l 1
(m− l)!dq =
=βn
γn
m∑
l=1
(−1)m−l 1
(l − 1)!(n− 1)!(m− l)!lm+n−1
∫ 1
0q
βlγ (1− q)n−1dq =
=1
(n− 1)!(m− 1)!
βn
γn
m∑
l=1
(−1)m−l
(
m− 1
l − 1
)
lm+n−1Γ(βl
γ+ 1)Γ(n)
Γ(βlγ+ n+ 1)
=
=1
n!(m− 1)!
βn
γn
m∑
l=1
(−1)m−l
(
m−1l−1
)
(βlγ+nn
)
lm+n−1.
Sei nun 1 ≤ k ≤ n. In diesem Fall liefert nur das erste Integral von (3.19) einen Beitrag. Unter
72 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Verwendung von (3.20) folgt
P{Xγn,βm = γk} = [znwmvγk]H(z, w) =
= [znwmvγk]− vγz
∫ 1
0
W(
−wqβγ e
z βγ(1−q)−w
)
(1− vγzq)2(
1 +W(
−wqβγ e
z βγ(1−q)−w
))dq =
=
∫ 1
0[zn−1wmvγ(k−1)]
1
(1− vγzq)2
∑
l≥1
ll−1
(l − 1)!wlq
βlγ e
z βlγ(1−q)−lw
dq =
=
∫ 1
0
m∑
l=1
ll−1
(l − 1)![zn−1wm]kzk−1qk−1wlq
βlγ e
z βlγ(1−q)−lw
dq =
=
∫ 1
0
m∑
l=1
ll−1
(l − 1)!kq
k−1+βlγ [zn−kwm−l]e
z βlγ(1−q)
e−lwdq =
=
∫ 1
0
m∑
l=1
ll−1
(l − 1)!kq
k−1+βlγβn−k
γn−kln−k(1− q)n−k 1
(n− k)!(−1)m−llm−l 1
(m− l)!dq =
=k
(n− k)!
βn−k
γn−k
m∑
l=1
(−1)m−l 1
(l − 1)!(m− l)!lm+n−1−k
∫ 1
0qk−1+βl
γ (1− q)n−kdq =
=k
(n− k)!(m− 1)!
βn−k
γn−k
m∑
l=1
(−1)m−l
(
m− 1
l − 1
)
lm+n−1−kΓ(k + βl
γ)Γ(n− k + 1)
Γ(βlγ+ n+ 1)
=
=k
(n− k + 1)!(m− 1)!
βn−k
γn−k
m∑
l=1
(−1)m−l
(
m−1l−1
)
(βlγ+n
n−k+1
)
lm+n−1−k.
Mit MATLAB wurde in 10000 Simulationen fur α = 1 und fixe Anfangsgroßen der ersten Gruppemit 1000 Personen und der zweiten Gruppe mit 500 Personen getestet, wie der durchschnittlicheAusgang des Kampfes von γ abhangt. Die Ergebnisse fur γ = 1, 2, 3, 4, 5 sind in Abbildung3.7 mit Histogrammen (zur besseren Ubersichtlichkeit als Flachen) dargestellt. Im Fall γ = 2ist deutlich ersichtlich, dass die doppelte Große der ersten Gruppe nicht durch das Verhaltnisγβ
= 2 kompensiert werden kann. Der Grund liegt darin, dass - auch wenn beide Gruppenfur einen Sieg gleich viele Treffer landen mussen - gemaß dem Urnenmodell die erste Gruppeanfangs mit doppelt so hoher Wahrscheinlichkeit trifft. Die erste Gruppe hat in allen 10000Simulationen gewonnen, wobei die geringste Anzahl an Uberlebenden in allen Durchgangen bei548 Personen lag. Im Fall γ = 3 wurden nur 4 Kampfe von der ersten Gruppe verloren. Erstbei γ = 4 kann die anfangliche Uberlegenheit der ersten Gruppe ausgeglichen werden. In diesemFall konnte die zweite Gruppe mit insgesamt 5025 knapp mehr als die Halfte der Duelle fursich entscheiden. Bei γ = 5 wird die erste Gruppe von der zweiten Gruppe dominiert, welche9891 Auseinandersetzungen gewinnt. Dennoch sind noch Ausreißer moglich: In einem Kampfuberlebten 375 Personen aus der ersten Gruppe.
Aus Satz 21 folgt im Speziellen auch das Resultat aus [1]:
3.5. OK CORRAL 73
Abbildung 3.7: Abhangigkeit der Verteilung der Uberlebenden vom Parameter γ ∈ {1, 2, 3, 4, 5}.Simulationen durch MATLAB-Aufruf histogramPlotEndConfig([0 -1; −γ 0], 100000, [1000 500],10000, 1, 1).
Korollar 2: Die Wahrscheinlichkeit, dass im klassischen OK Corral-Problem (β = γ = 1) mitGruppengroßen n bzw. m aus der Gruppe mit n Personen genau k Personen die Schießereiuberleben, ist gegeben durch
P{Xn,m = k} =k!
(m+ n)!
m∑
l=1
(−1)m−l
(
m+ n
m− l
)(
l + k − 1
l
)
lm+n−k.
Beweis. Setzt man β = γ = 1 in (3.23) folgt
P{Xn,m = k} =k
(n− k + 1)!(m− 1)!
m∑
l=1
(−1)m−l
(
m−1l−1
)
(
n+ln−k+1
) lm+n−1−k.
Aus
k(
m−1l−1
)
(n− k + 1)!(m− 1)!(
n+ln−k+1
) =k(l + k − 1)!
(l − 1)!(m− l)!(n+ l)!=
k!(
l+k−1l
)
(m− l)!(n+ l)!l =
=k!
(m+ n)!
(
l + k − 1
l
)(
m+ n
m− l
)
l
folgt direkt
P{Xn,m = k} =k!
(m+ n)!
m∑
l=1
(−1)m−l
(
m+ n
m− l
)(
l + k − 1
l
)
lm+n−k.
74 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.8: Abhangigkeit der Verlustwahrscheinlichkeit von anfanglichen Gruppengroßen.Simulationen durch MATLAB-Aufruf iterEvolution([0 -1; -1 0], 1000, [variableN 100], numberI-terations, 1).
Das Ergebnis wird in Abbildung 3.8 veranschaulicht: Im klassischen OK-Corral-Problem wurdegetestet, wie stark die anfanglichen Gruppengroßen den Ausgang des Kampfes beeinflussen.Bei insgesamt 100 bzw. 1000 bzw. 10000 Kampfen startet die zweite Gruppe mit 100 Personen,wahrend fur die erste Gruppe eine variable Anzahl zwischen 80 und 120 Personen gewahlt wurde.
Korollar 3: Die s-ten Momente von Xγn,βm sind gegeben durch
E(Xsγn,βm) =
m∑
l=1
(−1)m−l 1
l!(m− l)!
n∑
k=1
ks+1lm+n−k βn−k
γn−k−s
1
(n+ βγl)n−k+1
.
Beweis. Mit der Zufallsvariable Yγn,βm =Xγn,βm
γfolgt aus (3.23):
E(Xsγn,βm) = γsE(Y s
γn,βm) = γsn∑
k=1
ksP{Yγn,βm = k} =
=n∑
k=1
ks+1
(n− k + 1)!(m− 1)!
βn−k
γn−k−s
m∑
l=1
(−1)m−l
(
m−1l−1
)
( n+βγl
n−k+1
)
lm+n−1−k.
3.5. OK CORRAL 75
Aus der Gleichung
(
m−1l−1
)
(n− k + 1)!(m− 1)!( n+β
γl
n−k+1
)
=1
(l − 1)!(m− l)!(n+ βγl)n−k+1
folgt
E(Xsγn,βm) =
m∑
l=1
(−1)m−l 1
l!(m− l)!
n∑
k=1
ks+1lm+n−k βn−k
γn−k−s
1
(n+ βγl)n−k+1
.
76 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.9: Verlaufe der Einzelpillenanzahl beim klassischen Pillen-Problem. Simulationdurch MATLAB-Aufruf urnEvolutionPlot([-1 0; 1 -1], 300, [100,100],50,1,1).
3.6 Verallgemeinertes Pillen-Problem
Das klassische Pillen-Problem wird durch die Matrix M =
(
−1 01 −1
)
beschrieben und
lasst sich folgendermaßen interpretieren: Es gibt Einzelpillen (weiße Kugeln) und Doppelpillen(schwarze Kugeln). Es wird zufallig eine Pille genommen, wobei Einzelpillen geschluckt werdenund Doppelpillen zerbrochen werden, eine Halfte geschluckt wird und die andere Halfte als Ein-zelpille zuruckgelegt wird. Gesucht ist dann die Verteilung der Anzahl der Einzelpillen, die ubrigbleiben, sobald die letzte Doppelpille gezogen wurde. Im verallgemeinerten Pillen-Problem wird
die Ubergangsmatrix M =
(
−α 0α −δ
)
betrachtet. In diesem Modell gibt es Pillen der Große
α und Pillen der Große δ. Es wird eine Pille ausgewahlt, wobei die Wahrscheinlichkeit, eine Pilleder Große α zu ziehen, sich um den Faktor δ
αvon der Wahrscheinlichkeit, eine Pille der Große
δ zu ziehen, unterscheidet. Die gezogene Pille wird geschluckt und im Fall, dass eine Pille derGroße δ gezogen wurde, wird eine Pille der Große α hinzugefugt.
In Abbildung 3.9 sind 50 Verlaufe der Anzahl von Einzelpillen im klassischen Pillen-Problemmit anfangs 100 Doppelpillen und 100 Einzelpillen dargestellt.
3.6. VERALLGEMEINERTES PILLEN-PROBLEM 77
Ubergangsmatrix: M =
(
−α 0α −δ
)
, α 6= δ
Definitionsmenge: S := {(αn, δm)|n,m ∈ N0}Absorptionsmenge: A := {(αn, 0)|n ∈ N0} ⊆ SInitialkonfiguration: I := (αn, δm)Wahrscheinlichkeitserzeugende Funktion: hn,m(v) :=
∑
k≥0
P{Xαn,δm = αk}vαk
Erzeugende Funktion: H(z, w) :=∑
n≥0
∑
m≥1hn,m(v) z
n
n!wm
m!
Den Schritten in [3] folgend, wird die Zufallsvariable Xαn,δm untersucht, wobei P{Xαn,δm = αk}die Wahrscheinlichkeit angibt, dass ausgehend von n Pillen der Große α und m Pillen der Großeδ, k Pillen der Große α ubrig bleiben, sobald die letzte Pille der Große δ gezogen wurde. DurchUnterscheidung welche Große die gezogene Pille hat, erhalt man fur m,n ≥ 1 die Rekursion
hn,m(v) =αn
αn+ δmhn−1,m(v) +
δm
αn+ δmhn+1,m−1(v) (3.24)
mit den bekannten Anfangswerten hn,0(v) = vαn und den unbekannten Anfangswerten h0,m(v) =h1,m−1(v). Durch Einsetzen sieht man, dass die Rekursion auch fur n = 0 gilt. Aufgrund vonα > 0 in der Ubergangsmatrix treten unbekannte Anfangswerte auf. Daher ist es notwendigeine modifizierte erzeugende Funktion H(z, w) einzufuhren. Multipliziert man (3.24) mit (αn+δm) z
n
n!wm
m! und summiert anschließend uber n ≥ 0,m ≥ 1 erhalt man auf der linken Seite
α∑
n≥1
∑
m≥1
nhn,m(v)zn
n!
wm
m!+ δ
∑
n≥0
∑
m≥1
mhn,m(v)zn
n!
wm
m!= αzHz(z, w) + δwHw(z, w).
Der erste Summand auf der rechten Seite von (3.24) ergibt sich zu
α∑
n≥1
∑
m≥1
nhn−1,m(v)zn
n!
wm
m!= α
∑
n≥0
∑
m≥1
(n+ 1)hn,m(v)zn+1
(n+ 1)!
wm
m!= αzH(z, w)
und der zweite Summand zu
δ∑
n≥0
∑
m≥1
mhn+1,m−1(v)zn
n!
wm
m!= δ
∑
n≥1
∑
m≥0
(m+ 1)hn,m(v)zn−1
(n− 1)!
wm+1
(m+ 1)!=
= δw∑
n≥1
∑
m≥0
hn,m(v)nzn−1
n!
wm
m!=
= δwHz(z, w) + δw∑
n≥1
hn,0(v)zn−1
(n− 1)!=
= δwHz(z, w) + δwvαevαz.
Aufgrund der modifizierten erzeugenden Funktion ist die Kenntnis der unbekannten Anfangs-werte nicht notwendig, und man erhalt insgesamt die folgende partielle Differentialgleichung furH(z, w):
(αz − δw)Hz(z, w) + δwHw(z, w)− αzH(z, w) = δwvαevαz. (3.25)
78 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Gemaß der Methode der Charakteristiken wird zunachst die Rumpf-Differentialgleichung
(αz − δw)Hz(z, w) + δwHw(z, w) = 0
bzw. das zugehorige System von Differentialgleichungen (z = z(t), w = w(t))
z = αz − δw, w = δw
betrachtet. Ein erstes Integral kann nun folgendermaßen bestimmt werden:
dz
dw=αz − δw
δw,
⇒ (δw)dz + (δw − αz)dw = 0.
Wegen ∂∂w
(δw) = δ 6= −α = ∂∂z(δw− αz) ist die Differentialgleichung nicht exakt. Da allerdings
∂∂w
(δw)− ∂∂z
(δw−αz)
δw= δ+α
δwnicht von z abhangt, ist der Ansatz fur einen integrierenden Faktor der
Bauart m = m(w) erfolgreich:
∂
∂w(δwm(w)) =
∂
∂z((δw − αz)m(w)),
⇒ m′(w) = −m(w)δ + α
δw,
⇒ log(m) = −δ + α
δlog(w),
⇒ m(w) = w−1−αδ .
Eine zugehorige exakte Differentialgleichung lautet somit
(w−αδ δ)dz + (w−α
δ δ − αzw−1−αδ )dw = 0.
Ein erstes Integral ξ(z, w) erfullt dann
∂ξ
∂z= w−α
δ δ,∂ξ
∂w= w−α
δ δ − αzw−1−αδ ,
woraus nach Integration
ξ(z, w) =z
wαδ
− δw
(α− δ)wαδ
folgt. Bei diesem Schritt wird erstmals die zusatzliche Voraussetzung α 6= δ notwendig. Wahltman η(z, w) := w berechnen sich die Umkehrfunktionen zu w(η, ξ) = η bzw. z(η, ξ) = ξη
αδ + ηδ
α−δ.
(η, ξ)-Transformation:
ξ(z, w) = z
wαδ− δw
(α−δ)wαδ, η(z, w) = w,
z(η, ξ) = ξηαδ + ηδ
α−δ, w(η, ξ) = η.
Die partielle Differentialgleichung (3.25) wird nach Substitution wegen (3.4) zu der folgendengewohnlichen Differentialgleichung in η reduziert (H(z, w) = G(η, ξ)):
Gη − α
(
ξ
δη
αδ−1 +
1
α− δ
)
G = vαevα(ξη
αδ + ηδ
α−δ). (3.26)
3.6. VERALLGEMEINERTES PILLEN-PROBLEM 79
Die homogene Differentialgleichung kann durch Trennung der Variablen gelost werden:
log(G[h](η, ξ)) = ξηαδ +
ηα
α− δ+ C1(ξ),
⇒ G[h](η, ξ) = C(ξ) exp
(
ξηαδ +
ηα
α− δ
)
,
⇒ H [h](z, w) = C
(
z
wαδ
− δw
(α− δ)wαδ
)
exp (z + w).
Mit Variation der Konstanten (G[p](η, ξ) := C(η, ξ) exp(
ξηαδ + ηα
α−δ
)
) kann die Partikularlosung
bestimmt werden. Beim Einsetzen in die Differentialgleichung (3.26) heben sich die Terme mitFaktor C(η, ξ) auf und es folgt
∂
∂η(C(η, ξ)) exp
(
ξηαδ +
ηα
α− δ
)
= vα exp
(
vα(ξηαδ +
ηδ
α− δ)
)
,
⇒ C(η, ξ) =
∫
vα exp
(
vα(ξηαδ +
ηδ
α− δ)− ξη
αδ − ηα
α− δ
)
dη =
= vαη
∫ 1
0exp
(
vα(ξηαδ q
αδ +
ηqδ
α− δ)− ξq
αδ η
αδ − ηqα
α− δ
)
dq.
Es folgt
H [p](z, w) = G[p](η, ξ) =
= vαη
∫ 1
0exp
(
vα(ξηαδ q
αδ +
ηqδ
α− δ)− ξq
αδ η
αδ − ηqα
α− δ+ ξη
αδ +
ηα
α− δ
)
dq =
= vαw
∫ 1
0exp
(
vα(zqαδ − δwq
αδ
α− δ+
wqδ
α− δ)− zq
αδ +
δwqαδ
α− δ− wqα
α− δ+ z − wδ
α− δ+
wα
α− δ
)
dq =
= vαw
∫ 1
0exp
(
z(1 + (vα − 1)qαδ ) + w
(
1− αq − qαδ δ
α− δ+
vαδ
α− δ(q − q
αδ )
))
dq.
Die allgemeine Losung der partiellen Differentialgleichung (3.25) ist durchH(z, w) = H [h](z, w)+H [p](z, w) gegeben. Die Funktion C(x) wird durch die Anfangsbedingung H(0, 0) = 0 bestimmt:Nahert man sich dem Ursprung entlang z = z(w) = xw
αδ + w δ
α−δmit einer beliebigen, festen
Zahl x ∈ R, folgt aus H [p](0, 0) = 0 und der Analytizitat von H in einer Umgebung von 0
0 = H(0, 0) = limw→0
H [h](z(w), w) = C(x),
Es folgt C ≡ 0 und somit H(z, w) = H [p](z, w). Dies liefert:
Satz 22: Die exponentiell erzeugende Funktion H(z, w) im verallgemeinerten Pillen-Problemmit α 6= δ, in der der Koeffizient von zn
n!wm
m! vαk die Wahrscheinlichkeit angibt, dass bei anfangs n
Pillen der Große α und m Pillen der Große δ genau k Pillen der Große α ubrig bleiben, nachdemdie letzte Pille der Große δ gezogen wurde, ist gegeben durch
H(z, w) = vαw
∫ 1
0exp
(
z(1 + (vα − 1)qαδ ) + w
(
1− αq − qαδ δ
α− δ+
vαδ
α− δ(q − q
αδ )
))
dq.
80 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Die wahrscheinlichkeitserzeugende Funktion hn,m(v) kann nun direkt abgelesen werden:
hn,m(v) =∑
k≥0
P{Xαn,δm = αk}vαk = n!m![znwm]H(z, w) =
= mvα∫ 1
0
(
1 + (vα − 1)qαδ
)n(
1− αq − qαδ δ
α− δ+
vαδ
α− δ(q − q
αδ )
)m−1
dq.
Die Tatsache, dass am Ende zumindest α weiße Kugeln ubrig bleiben, spiegelt sich in[v0]hn,m(v) = 0 wider. Ein einfaches Ablesen des Koeffizienten bei vαk fur k ≥ 1 scheitertjedoch an der Integration. Dennoch ist es moglich die Momente von Xαn,δm zu bestimmen und
daraus im Folgenden die Grenzverteilungen. Seien hierzu Yαn,δm :=Xαn,δm
αund
Jn,m(v) := m
∫ 1
0
(
1 + (v − 1)qαδ
)n
(
1− αq − qαδ δ
α− δ+
vδ
α− δ(q − q
αδ )
)m−1
dq,
sodass vJn,m(v) =∑
k≥0
P{Yαn,δm = k}vk. Bezeichnet Ev den Auswertungsoperator v = 1 und Dv
den Ableitungsoperator nach v, dann gilt
E(Ysαn,δm) =
∑
k≥0
ksP{Yαn,δm = k} = EvDsv(vJn,m(v)) = EvD
svJn,m(v) + sEvD
s−1v Jn,m(v).
(3.27)Der Ausdruck EvD
svJn,m(v) kann direkt aus der Definition von Jn,m berechnet werden:
EvDsvJn,m(v) =
= m
∫ 1
0
s∑
k=0
(
s
k
)
(m− 1)k
(
1− αq − qαδ δ
α− δ+
δ
α− δ(q − q
αδ )
)m−1−k
(
δ
α− δ
)k
(q − qαδ )kns−kq
αδ(s−k)dq =
= ms!s∑
k=0
(
n
s− k
)(
m− 1
k
)
1
(αδ− 1)k
∫ 1
0(1− q)m−1−kq
αkδ (−1)k(1− q1−
αδ )kq
αδ(s−k)dq =
= s!s∑
k=0
(
ns−k
)(
mk
)
(αδ− 1)k
(m− k)
∫ 1
0(−1)k(1− q)m−1−kq
αsδ
k∑
i=0
(
k
i
)
(−1)iqi−αδidq =
= s!s∑
k=0
(
ns−k
)(
mk
)
(αδ− 1)k
(m− k)k∑
i=0
(−1)k+i
(
k
i
)
B(m− k,α
δ(s− i) + i+ 1).
Es gilt somit
EvDsvJn,m(v) = s!
s∑
k=0
(
ns−k
)(
mk
)
(αδ− 1)k
k∑
i=0
(−1)k−i
(
ki
)
(m−k+i+αδ(s−i)
m−k
)
. (3.28)
Unter Verwendung von (3.27) kann somit ein expliziter Ausdruck fur die faktoriellen Momenteangegeben werden:
3.6. VERALLGEMEINERTES PILLEN-PROBLEM 81
Satz 23: Die faktoriellen Momente der Zufallsvariable Xαn,δm im verallgemeinerten Pillen-Problem mit α 6= δ sind gegeben durch
E(Xsαn,δm) = αss!
s∑
k=0
(
mk
)
(αδ− 1)k
k∑
i=0
(−1)k−i
(
k
i
)
(
ns−k
)
(m−k+i+αδ(s−i)
m−k
)
+
(
ns−1−k
)
(m−k+i+αδ(s−1−i)
m−k
)
.
Ausgehend von (3.14) kann daher auch eine explizite Formel fur die gewohnlichen Momente vonXαn,δm angegeben werden:
E(Xsαn,δm) =
s∑
j=0
{
s
j
}
E(Xj
αn,δm).
Im Fall m ∈ N fest, ist die Art der Grenzverteilung unabhangig davon, ob α < δ oder α > δ:
Satz 24: Im Fallm ∈ N fest und n→ ∞ konvergiert die ZufallsvariableXαn,δm
αnin der Verteilung
gegen eine Kumaraswamy-verteilte Zufallsvariable mit Parametern δαund m:
Xαn,δm
αn
(D)−−→ K δα,m.
Beweis. Fur festes m und n→ ∞ ist in (3.28) der Summand k = 0, und somit i = 0, dominantund es folgt
EvDsvJn,m(v) ∼ ns
(
m+αδs
m
).
Wegen
limn→∞
EvDs−1v Jn,m(v)
EvDsvJn,m(v)
= 0
folgt aus (3.27)
E(Ysαn,δm) ∼ ns
(
m+αδs
m
)
und damit
E(Y sαn,δm) =
s∑
k=0
{
s
k
}
nk(
m+αδk
m
)∼ ns(
m+αδs
m
).
Aus dem Satz von Frechet und Shohat folgt wegen
E
((
Xαn,δm
αn
)s)n→∞−−−→ 1
(
m+αδs
m
)=
Γ(m+ 1)Γ(1 + αsδ)
Γ(m+ 1 + αsδ)
die behauptete Grenzverteilung.
In einer MATLAB-Simulation wurde die Haufigkeitsverteilung im Fall α = 1, δ = 2 mit 10000Pillen der Große 1 und 50 Pillen der Große 2 bestimmt. Das Histogramm und die skalierteGrenzverteilung aus Satz 24 sind in Abbildung 3.10 zu sehen.
82 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.10: Grenzverteilung der verbleibenden Pillen der Große 1 beim verallgemeinertenPillen-Problem (α = 1, δ = 2) fur n → ∞. MATLAB-Aufruf: histogramPlotEndConfig([-1 0; 1-2], 100000, [10000 50], 10000, 1, 3)
3.6. VERALLGEMEINERTES PILLEN-PROBLEM 83
Bemerkung 7: Vergleicht man Satz 24 mit Satz 17 fallt auf, dass die Grenzverteilungen im Fallm fest und n → ∞ fur das verallgemeinerte Pillen-Problem und verallgemeinertes Ziehen ohneZurucklegen ident sind (vgl. Abbildung 3.10 und Abbildung 3.4). Der Unterschied zwischenden beiden Problemen fur festes m ist, dass im verallgemeinerten Pillen-Problem im Laufeeiner Urnenevolution eine konstante Anzahl, namlich αm, weißer Kugeln zur Urne hinzugefugtwerden. Auch wenn eine konstante Anzahl weißer Kugeln fur n→ ∞ irrelevant erscheinen mag,ist das Ergebnis dennoch bemerkenswert, da diese Kugeln mit hohererer Wahrscheinlichkeiterst gegen Ende der Evolution hinzugefugt werden. Satz 24 und Satz 17 zeigen aber, dass dies -unabhangig von der Wahl der Parameter α und δ - dennoch keine Auswirkung auf die Gleichheitder Grenzverteilungen hat.
Um das asymptotische Verhalten von Xαn,δm fur m,n → ∞ zu bestimmen, folgt zunachst aus(1.2) eine asymptotische Entwicklung von EvD
svJn,m(v):
EvDsvJn,m(v) = s!
s∑
k=0
(
ns−k
)(
mk
)
(αδ− 1)k
k∑
i=0
(−1)k−i
(
ki
)
(m−k+i+αδ(s−i)
m−k
)
∼
∼s∑
k=0
(
s
k
)
ns−k
mαsδ−k
1
(αδ− 1)k
k∑
i=0
(−1)k−i
(
k
i
)
Γ(α
δ(s− i) + i+ 1
)
mi(αδ−1).
(3.29)
Weiters ist eine Fallunterscheidung zwischen α < δ und α > δ notwendig, wobei im zweiten Fallder Typ der Grenzverteilung vom asymptotischen Verhalten von n
mαδabhangt:
Satz 25: Im Fall αδ< 1, m→ ∞ und n = n(m) → ∞ mit beliebigem Wachstum konvergiert die
normalisierte ZufallsvariableXαn,δm
αgn,mmit gn,m =
n+m δδ−α
mαδ
in der Verteilung gegen eine Weibull-
verteilte Zufallsvariable mit Parametern 1 und δα:
Xαn,δm
αgn,m
(D)−−→W1, δα.
Im Fall αδ> 1 und n,m → ∞ mussen die drei verschiedenen Falle fur das asymptotische
Verhalten von n
mαδunterschieden werden:
1. n
mαδ
→ ∞: Die Zufallsvariable mαδ
n
Xαn,δm
αkonvergiert fur α
δ≤ 2 in der Verteilung gegen
eine Weibull-verteilte Zufallsvariable mit Parametern 1 und δα:
mαδ
n
Xαn,δm
α
(D)−−→W1, δα.
2. n
mαδ→ 0: Die Momente von Xαn,δm konvergieren gegen
E(Xsαn,δm) ∼ αs+1
δ
s∑
k=0
{
s
k
}
Γ(k + 1)
(αδ− 1)k
.
84 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
3. n
mαδ→ ρ mit 0 ≤ ρ ≤ ∞: Es konvergieren die faktoriellen Momente von
Xαn,δm
αgegen
s∑
k=0
(
s
k
)
ρs−k
(αδ− 1)k
Γ(α
δ(s− k) + k + 1
)
+ss−1∑
k=0
(
s− 1
k
)
ρs−1−k
(αδ− 1)k
Γ(α
δ(s− 1− k) + k + 1
)
.
Beweis. Im Fall αδ< 1 wird das Wachstum der inneren Summe in (3.29) durch den Summanden
mit i = 0 dominiert. Es folgt aus (3.29) bzw. dem binomischen Lehrsatz:
EvDsvJn,m(v) ∼ Γ
(
1 +α
δs)
s∑
k=0
(
s
k
)
ns−k
mαsδ−k
1
(1− αδ)k
= Γ(
1 +α
δs) (n+m δ
δ−α)s
mαsδ
.
Daraus folgt weiters
limm→∞
EvDs−1v Jn,m
EvDsvJn,m
=Γ(1 + α
δ(s− 1))
Γ(1 + αδs)
limm→∞
mαδ
n+m δδ−α
= 0
und somit aus (3.27)
E(Ysαn,δm) ∼ Γ
(
1 +α
δs) (n+m δ
δ−α)s
mαsδ
= Γ(
1 +α
δs)
gsn,m.
Dagkn,m
gsn,m→ 0 fur k < s erfullen die gewohnlichen Momente
E(Y sαn,δm) =
s∑
k=0
{
s
k
}
E(Ykαn,δm) ∼ Γ
(
1 +α
δs)
gsn,m.
Aus Lemma 11 und dem Satz von Frechet und Shohat folgt daher die behauptete Grenzvertei-lung.
Im Fall αδ> 1 wird das Verhalten der inneren Summe von EvD
svJn,m(v) in (3.29) durch den
Summanden i = k dominiert. Es folgt die asymptotische Entwicklung
EvDsvJn,m(v) ∼
s∑
k=0
(
s
k
)
ns−k
mαδ(s−k)
1
(αδ− 1)k
Γ(α
δ(s− k) + k + 1
)
. (3.30)
Im Fall n
mαδ→ ∞ ist der Summand k = 0 in (3.30) dominant:
EvDsvJn,m(v) ∼ ns
mαδsΓ(α
δs+ 1
)
.
WegenEvD
s−1v Jn,m(v)
EvDsvJn,m(v)
∼ mαδ
n
Γ(αδ(s− 1) + 1)
Γ(αδs+ 1)
→ 0
folgt
E(Ysαn,δm) ∼ ns
mαδsΓ(α
δs+ 1
)
3.6. VERALLGEMEINERTES PILLEN-PROBLEM 85
und daraus
E(Y sαn,δm) =
s∑
k=0
{
s
k
}
E(Ykαn,δm) ∼ ns
mαδsΓ(α
δs+ 1
)
.
Anwendung von Lemma 11 und dem Satz von Frechet und Shohat liefert die behauptete Grenz-verteilung.
Im Fall n
mαδ→ 0 konvergiert nur der Summand k = s in (3.30) nicht gegen Null:
EvDsvJn,m(v) ∼ 1
(αδ− 1)s
Γ (s+ 1) .
Mit (3.27) erhalt man
E(Ysαn,δm) ∼ 1
(αδ− 1)s
Γ (s+ 1) + s1
(αδ− 1)s−1
Γ (s) =α
δ
Γ(s+ 1)
(αδ− 1)s
und somit
E(Xsαn,δm) = αsE(Y s
αn,δm) =αs+1
δ
s∑
k=0
{
s
k
}
Γ(k + 1)
(αδ− 1)k
.
Im Fall n
mαδ→ ρ folgt aus (3.30) die Entwicklung
EvDsvJn,m(v) ∼
s∑
k=0
(
s
k
)
ρs−k
(αδ− 1)k
Γ(α
δ(s− k) + k + 1
)
und somit
E
((
Xαn,δm
α
)s)
= E(Ysαn,δm) ∼
∼s∑
k=0
(
s
k
)
ρs−k
(αδ− 1)k
Γ(α
δ(s− k) + k + 1
)
+ s
s−1∑
k=0
(
s− 1
k
)
ρs−1−k
(αδ− 1)k
Γ(α
δ(s− 1− k) + k + 1
)
.
Mit den Parametern α = 1, δ = 2 und anfangs 50 Pillen der Große 1 und 5000 Pillen derGroße 2 wurde eine Simulation mit 10000 Evolutionen durchgefuhrt. Gemaß Satz 25 konvergiertdie skalierte Zufallsvariable
Xαn,δm
αgn,mfur m → ∞ gegen eine Weibull-verteilte Zufallsvariable mit
Parametern 1 und δα. Die aus der Simulation erhaltene Haufigkeitsverteilung fur die Endanzahl
an Pillen der Große 1 und die skalierte Grenzverteilung sind in Abbildung 3.11 dargestellt.
86 KAPITEL 3. LOSUNG UBER METHODE DER CHARAKTERISTIKEN
Abbildung 3.11: Grenzverteilung der verbleibenden Pillen der Große 1 beim verallgemeinertenPillen-Problem (α = 1, δ = 2) fur m → ∞. MATLAB-Aufruf: histogramPlotEndConfig([-1 0; 1-2], 100000, [50 10000], 10000, 1, 3)
Anhang A
MATLAB-Code
Die Funktion urnEvolution ist der zentrale Baustein des Programms. Es wird eine Evolutionsimuliert:
function [results] = urnEvolution(M, maxDraws, D, zeroStop)
% urnEvolution: Simulation einer Evolution bis Abbruchbedingung (zeroStop)
% erfullt ist
%
% Input:
% Matrix M (n x n): Ubergangsmatrix
% Integer maxDraws: Anzahl Kugeln, die maximal gezogen werden
% Vektor D (1 x n): Anfangskonfiguration
% Boolean zeroStop:
% 1 <-> Abbruch, falls eine Kugelsorte nicht mehr
% vorhanden
% 2 <-> Abbruch, falls keine Kugel der ersten Sorte mehr vorhanden
% 3 <-> Abbruch, falls keine Kugel der zweiten Sorte mehr vorhanden
% 4 <-> Abbruch nach maxDraws Ziehungen
%
% Output:
% Matrix results ((Anzahl Ziehungen) x n+2):
% Zeile i, 1.Spalte: i
% 2.Spalte: gezogene Farbe
% 3.Spalte: Urnenkonfiguration nach Veranderung durch i.Ziehung
numberDraws = 0;
breakCond = 1;
n = size(M,1);
results = zeros(1,1);
while((numberDraws < maxDraws) && breakCond)
s = sum(D);
87
88 ANHANG A. MATLAB-CODE
x = ceil(rand(1)*s); % x.te Kugel wird gezogen (nach Farben sortiert)
numberDraws = numberDraws + 1;
colour = 0;
while(x > 0)
colour = colour + 1;
x = x - D(colour);
end
D(1:n) = D(1:n) + M(colour,1:n);
results(numberDraws,1) = numberDraws;
results(numberDraws,2) = colour;
results(numberDraws,3:(n+2)) = D(1:n);
if(sum(D) <= 0 || min(D) < 0)
breakCond = 0;
end
if(zeroStop == 1 && min(D) <= 0)
breakCond = 0;
end
if(zeroStop == 2 && D(1) == 0)
breakCond = 0;
end
if(zeroStop == 3 && D(2) == 0)
breakCond = 0;
end
end
end
Der Funktion iterEvolution wird als zusatzlicher Parameter die Anzahl der Evolutionen ubergeben,die unabhangig voneinander simuliert werden sollen:
function [endResults] = iterEvolution(M, maxDraws, D,
numberIterations, zeroStop)
% iterEvolution: simuliert unabhangige Evolutionen
%
% Input:
% Matrix M (n x n): Ubergangsmatrix
% Integer maxDraws: Anzahl Kugeln, die maximal gezogen werden
% Vektor D (1 x n): Anfangskonfiguration
% Integer numberIterations: Anzahl Evolutionen
% Boolean zeroStop:
% 1 <-> Abbruch, falls eine Kugelsorte nicht mehr
% vorhanden
% 2 <-> Abbruch, falls keine Kugel der ersten Sorte mehr vorhanden
89
% 3 <-> Abbruch, falls keine Kugel der zweiten Sorte mehr vorhanden
% 4 <-> Abbruch nach maxDraws Ziehungen
%
% Output:
% Matrix endResults (numberIterations x n): Zeile i enthalt
% Endkonfiguration der Urne in i.Evolution
n = size(M,1);
endResults = zeros(numberIterations, n);
for k = 1:numberIterations
tempResults = urnEvolution(M, maxDraws, D, zeroStop);
tempN = size(tempResults,1); % Anzahl Ziehungen in k.Evolution
endResults(k,1:n) = tempResults(tempN,3:(n+2));
Fortschritt = strcat(num2str(100*k/numberIterations),’ %’)
end
end
Als Benutzer startet man das Programm mit der Funktion histogramPlotEndConfig. Es werdenzusatzlich eine Abbruchbedingung und die untersuchte Kugelsorte als Parameter ubergeben:
function [result] = histogramPlotEndConfig(M, maxDraws, D,
numberIterations, colour, zeroStop)
% histogramPlotEndConfig: simuliert unabhangige Evolutionen und
% gibt ein Histogramm uber die Endanzahl der Kugeln von Farbe colour zuruck
%
% Input:
% Matrix M (n x n): Ubergangsmatrix
% Integer maxDraws: Anzahl Kugeln, die maximal gezogen werden
% Vektor D (1 x n): Anfangskonfiguration
% Integer numberIterations: Anzahl Evolutionen
% Integer colour: untersuchte Farbe (1..n)
% Boolean zeroStop:
% 1 <-> Abbruch, falls eine Kugelsorte nicht mehr
% vorhanden
% 2 <-> Abbruch, falls keine Kugel der ersten Sorte mehr vorhanden
% 3 <-> Abbruch, falls keine Kugel der zweiten Sorte mehr vorhanden
% 4 <-> Abbruch nach maxDraws Ziehungen
%
% Output:
% Histogramm,
% Matrix result: i.Zeile = Anzahl Evolutionen, bei denen sich von Kugelsorte
% colour genau (i-1) Kugeln in der Endkonfiguration befinden
endResults = iterEvolution(M, maxDraws, D, numberIterations, zeroStop);
90 ANHANG A. MATLAB-CODE
n = size(M,1);
m = size(endResults, 1);
plotVector = transpose(endResults(1:m, colour));
% Schranken fur Anzahl Kugeln
% untere Schranke: 0 (Teilbarkeitsbedingung)
% obere Schranke: maximale Anzahl einer Kugelsorte zu Beginn + betragsmaßig
% großte Zahl der Ubergangsmatrix * maximale Anzahl Ziehungen
result = transpose(histc(plotVector,-0.5:(max(D)+max(max(abs(M)))*maxDraws+1)));
% Histogramm-Ausgabe
hist(plotVector, min(floor(numberIterations/10), max(plotVector)));
titleString = {’Ubergangsmatrix: [ ’};
for i = 1:n
for j = 1:n
titleString = strcat(titleString, num2str(M(i,j)), {blanks(1)});
end
if(i ~= n)
titleString = strcat(titleString, {’; ’});
end
end
titleString = strcat(titleString,’] \newline’);
titleString = strcat(titleString, {’Initialkonfiguration: [ ’});
for i = 1:n
titleString = strcat(titleString, num2str(D(i)), {blanks(1)});
end
titleString = strcat(titleString, ’] \newline’);
titleString = strcat(titleString, ’Anzahl Iterationen: ’,
num2str(numberIterations), ’\newline’);
titleString = strcat(titleString, {’maxDraws: ’}, num2str(maxDraws), ’\newline’);
titleString = strcat(titleString, {’Untersuchte Kugelsorte: ’},
num2str(colour), ’\newline’);
title(titleString);
xlim([0 max(plotVector)]);
end
Die Parameter der Funktion urnEvolutionPlot stimmen mit jenen der Funktion histogramPlo-tEndConfig uberein. Der Output ist bei urnEvolutionPlot eine Graphik, die alle Evolutioneneiner Kugelsorte darstellt. Es ist daher im Gegensatz zu histogramPlotEndConfig ein kleinerParameter numberIterations empfehlenswert (1 ≤ numberIterations ≤ 100):
function [] = urnEvolutionPlot(M, maxDraws, D, numberIterations, colour, zeroStop)
% urnEvolutionPlot: simuliert unabhangige Evolutionen und gibt Kugelanzahl
% einer Farbe als Funktion der Anzahl durchgefuhrter Ziehungen zuruck
91
%
% Input:
% Matrix M (n x n): Ubergangsmatrix
% Integer maxDraws: Anzahl Kugeln, die maximal gezogen werden
% Vektor D (1 x n): Anfangskonfiguration
% Integer numberIterations: Anzahl Evolutionen
% Integer colour: untersuchte Farbe (1..n)
% Boolean zeroStop:
% 1 <-> Abbruch, falls eine Kugelsorte nicht mehr
% vorhanden
% 2 <-> Abbruch, falls keine Kugel der ersten Sorte mehr vorhanden
% 3 <-> Abbruch, falls keine Kugel der zweiten Sorte mehr vorhanden
% 4 <-> Abbruch nach maxDraws Ziehungen
%
% Output:
% plot: Ein Graph entspricht einer Evolution,
% x-Achse: Anzahl durchgefuhrter Ziehungen
% y-Achse: Anzahl Kugeln der Farbe colour
n = size(M,1);
plotMatrix = zeros(maxDraws, numberIterations);
for k = 1:numberIterations
tempResults = urnEvolution(M, maxDraws, D, zeroStop);
tempN = size(tempResults,1); % Gesamtanzahl Ziehungen in Evolution k
plotMatrix(1:tempN, k) = tempResults(1:tempN, colour + 2);
if(tempN < maxDraws)
for j = (tempN+1):maxDraws
% keine Veranderung nach Abbruchbedingung
plotMatrix(j,k) = tempResults(tempN, colour + 2);
end
end
end
plot(plotMatrix);
titleString = {’Ubergangsmatrix: [ ’};
for i = 1:n
for j = 1:n
titleString = strcat(titleString, num2str(M(i,j)), {blanks(1)});
end
if(i ~= n)
titleString = strcat(titleString, {’; ’});
end
end
titleString = strcat(titleString,’] \newline’);
92 ANHANG A. MATLAB-CODE
titleString = strcat(titleString, {’Initialkonfiguration: [ ’});
for i = 1:n
titleString = strcat(titleString, num2str(D(i)), {blanks(1)});
end
titleString = strcat(titleString, ’] \newline’);
titleString = strcat(titleString, ’Anzahl Iterationen: ’,
num2str(numberIterations), ’\newline’);
titleString = strcat(titleString, {’maxDraws: ’}, num2str(maxDraws), ’\newline’);
titleString = strcat(titleString, {’Untersuchte Kugelsorte: ’},
num2str(colour), ’\newline’);
title(titleString);
xlim([0 maxDraws]);
ylim([0 max(max(plotMatrix))]);
end
Literaturverzeichnis
[1] P. Flajolet, P. Dumas, V. Puyhaubert: Some exactly solvable models of urn process theory,Discrete Mathematics and Theoretical Computer Science, vol. AG, 59-118, 2006, in
”Procee-
dings of Fourth Colloquium on Mathematics and Computer Science“, P. Chassaing Editor.
[2] H.-K. Hwang, M. Kuba, A. Panholzer: Analysis of some exactly solvable diminishing urn
models, The 19th International Conference on Formal Power Series and Algebraic Combina-torics”, Nankai University, Tianjin, 2007.
[3] H.-K. Hwang, M. Kuba, A. Panholzer: Diminishing Urn Models: Analysis of exactly solvable
models, preprint.
[4] R. Graham, D. Knuth, O.Patashnik: Concrete Mathematics, Addison-Wesley PublishingCompany, Reading, MA, 1994.
[5] M. Drmota, B. Gittenberger, G. Karigl, A. Panholzer: Mathematik fur Informatik, 2008,Heldermann Verlag.
[6] M. Frechet, J. Shohat: A proof of the generalized second-limit theorem in the theory of pro-
bability, 1931, Trans. Amer. Soc. 33 533-543.
[7] P. Billingsley: Probability and Measure, Second Edition, 1986, John Wiley.
[8] T. Carleman: Sur le probleme des moments, 1922, Acad. Sci. Paris 174 1680-1682.
[9] A. Gut: On the moment problem, 2002, Uppsala University, Bernoulli Vol.8 Nr.3, 407-421.
[10] Michael E. Taylor: Partial Differential Equations I - Basic Theory, Applied MathematicalSciences, vol. 115, Springer-Verlag, New York, 1996.
93
