Wahrscheinlichkeitsfrage zu einem fiktiven Spiel
Pascal
In dem Spiel dreht es sich um die natï¿œrliche Zahl k, welche zu Begin 0
ist und welche man als Spieler erhï¿œhen mï¿œchte.
In jeder Runde wird jetzt:
- mit einer Wahrscheinlichkeit von p=1/3 der Wert von k um eins erhï¿œht.
- ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0 bleibt
es 0.
Beispiel:
1. Runde: k=0
2. Runde: k=0
3. Runde: k=1
4. Runde: k=0
5. Runde: k=1
6. Runde: k=2
Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
z.B. k=6 zu erreichen (Erwartungswert?). Wie wï¿œrde man soetwas rechnen?
Ich habe bereits mit einem Programm ein paar Tausend Durchgï¿œnge
simuliert und dabei auch einheitliche Zahlen herausbekommen. Mich wï¿œrde
aber interessieren, ob jemand eine Idee fï¿œr einen mathematischen Ansatz hat.
Wenn niemand darauf Lust hat, verstehe ich das natï¿œrlich. ;-)
Alfred Heiligenbrunner
> Hallo =)
>
> In dem Spiel dreht es sich um die natï¿œrliche Zahl k, welche zu Begin 0
> ist und welche man als Spieler erhï¿œhen mï¿œchte.
> In jeder Runde wird jetzt:
> - mit einer Wahrscheinlichkeit von p=1/3 der Wert von k um eins erhï¿œht.
> - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0 bleibt
> es 0.
>
> Beispiel:
> 1. Runde: k=0
> 2. Runde: k=0
> 3. Runde: k=1
> 4. Runde: k=0
> 5. Runde: k=1
> 6. Runde: k=2
>
> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
> z.B. k=6 zu erreichen (Erwartungswert?). Wie wï¿œrde man soetwas rechnen?
>
http://de.wikipedia.org/wiki/Markow-Kette
Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
(Mit etwas Eigenwerbung: http://www.heiligenbrunner.at/main/ahstoch.htm.)
Alfred
The Dust of Time
<alfred.heiligenbrunner_nos...@gmx.at> wrote:
> Pascal schrieb am 28.10.2009 20:55:
>
>
>
>
>
> > Hallo =)
>
> > ist und welche man als Spieler erhöhen möchte.
> > In jeder Runde wird jetzt:
> > - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0 bleibt
> > es 0.
>
> > Beispiel:
> > 1. Runde: k=0
> > 2. Runde: k=0
> > 3. Runde: k=1
> > 4. Runde: k=0
> > 5. Runde: k=1
> > 6. Runde: k=2
>
> > Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>
> http://de.wikipedia.org/wiki/Markow-Kette
>
> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> (Mit etwas Eigenwerbung:http://www.heiligenbrunner.at/main/ahstoch.htm.)
>
>
> - Zitierten Text anzeigen -
Alfred, wenn alle flapsig sind dann bin ich es auch, weil Außenseiter
ist noch schlimmer ( siehe NSdAP in Österreich ! ).
Error: 222222222222222 is too big! ???????????????
Und noch eine Aufgabe für dich : Ich will von München aus mit meinem
VW Käfer alle Städte Österreichs besuchen und photographieren - mit
welcher Stadt soll ich anfangen ?
Thomas Plehn
"Alfred Heiligenbrunner" <alfred.heilige...@gmx.at> schrieb im
Newsbeitrag news:7ksossF...@mid.individual.net...
>> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>> z.B. k=6 zu erreichen (Erwartungswert?). Wie wï¿œrde man soetwas rechnen?
>>
>
> http://de.wikipedia.org/wiki/Markow-Kette
>
> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> (Mit etwas Eigenwerbung: http://www.heiligenbrunner.at/main/ahstoch.htm.)
>
ï¿œbergangsmatrix, wie man die aus diesen Angaben aufstellt ist mir noch
bekannt, nicht aber, wie man allgemein aus einer ï¿œbergangsmatrix den
Erwartungswert fï¿œr den Zeitpunkt des ersten Erreichens eines Zustandes
berechnet. Kann mich da vieleicht jemand erhellen?
Jan Fricke
> Pascal schrieb am 28.10.2009 20:55:
>> Hallo =)
>>
>> ist und welche man als Spieler erhöhen möchte.
>> In jeder Runde wird jetzt:
>> - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0
>> bleibt es 0.
>>
>> Beispiel:
>> 1. Runde: k=0
>> 2. Runde: k=0
>> 3. Runde: k=1
>> 4. Runde: k=0
>> 5. Runde: k=1
>> 6. Runde: k=2
>>
>> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>>
>
> http://de.wikipedia.org/wiki/Markow-Kette
>
> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> (Mit etwas Eigenwerbung: http://www.heiligenbrunner.at/main/ahstoch.htm.)
>
> Alfred
Was erhält man eigentlich für allgemeines k und p?
Ich habe mal versucht, das mit Markow-Ketten durchzurechnen, und komme
darauf, dass der Erwartungswert T_k(p) der Quotient der Determinanten
der beiden k-reihigen Matrizen A_k und b_k ist, wobei
/ p -p \
| p-1 1 -p |
A = | p-1 1 -p | (leere Stellen sind Nullen)
k | ... ... ... |
| p-1 1 -p |
\ p-1 1 /
und B_k aus A_k entsteht, in dem die erste Spalte durch Einsen ersetzt wird.
Mit Induktion kann man det(A_k)=p^k recht schnell nachweisen, für
det(B_k) habe ich heuristisch die Formel
k+1 k
(1-p) - ((1-p) +k*(1-2p)) * p
---------------------------------
(1 - 2p)^2
gefunden, kann sie aber (noch?) nicht beweisen.
Viele Grüße Jan
Thomas Plehn
news:52beb3c7-0934-4078...@a21g2000yqc.googlegroups.com...
>Alfred, wenn alle flapsig sind dann bin ich es auch, weil Au�enseiter
>ist noch schlimmer ( siehe NSdAP in �sterreich ! ).
>Error: 222222222222222 is too big! ???????????????
>Und noch eine Aufgabe f�r dich : Ich will von M�nchen aus mit meinem
>VW K�fer alle St�dte �sterreichs besuchen und photographieren - mit
>welcher Stadt soll ich anfangen ?
ich finde es absolut bescheuert von dir, sich �ber Menschen, die helfen
anderer Leute Probleme zu l�sen, auch noch deswegen lustig zu machen und
anzudeuten, ob er denn nichts besseres zutun h�tte.
Rainer Willis
[...]
> Und noch eine Aufgabe f�r dich : Ich will von M�nchen aus mit meinem
> VW K�fer alle St�dte �sterreichs besuchen und photographieren - mit
> welcher Stadt soll ich anfangen ?
Geh alphabetisch vor, Bl�dmann, dann hast du wenigstens was zu tun.
Rainer
Stephan Gerlach
> Pascal schrieb am 28.10.2009 20:55:
>> In dem Spiel dreht es sich um die natï¿œrliche Zahl k, welche zu Begin 0
>> ist und welche man als Spieler erhï¿œhen mï¿œchte.
>> In jeder Runde wird jetzt:
>> - mit einer Wahrscheinlichkeit von p=1/3 der Wert von k um eins erhï¿œht.
>> - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0
>> bleibt es 0.
>>
>> Beispiel:
>> 1. Runde: k=0
>> 2. Runde: k=0
>> 3. Runde: k=1
>> 4. Runde: k=0
>> 5. Runde: k=1
>> 6. Runde: k=2
>>
>> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>> z.B. k=6 zu erreichen (Erwartungswert?). Wie wï¿œrde man soetwas rechnen?
[...]
> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> (Mit etwas Eigenwerbung: http://www.heiligenbrunner.at/main/ahstoch.htm.)
Was nimmt man als korrekte Eingabe im Programm, folgendes?
Null Null 2/3
Null Eins 1/3
Eins Null 2/3
Eins Zwei 1/3
Zwei Eins 2/3
Zwei Drei 1/3
Drei Zwei 2/3
Drei Vier 1/3
Vier Drei 2/3
Vier Fï¿œnf 1/3
Fï¿œnf Vier 2/3
Fï¿œnf Sechs 1/3
Sechs Fï¿œnf 0
Sechs Sechs 1
Scheint zu funktionieren; es erscheint die ï¿œbergangsmatrix, die man
"erwartet", und sogar sï¿œmtliche nicht angegebenen Wahrscheinlichkeiten
werden automatisch auf 0 gesetzt. Wobei es fast einfacher wï¿œre, wenn man
die ï¿œbergangsmatrix
/ 2/3 1/3 0 0 0 0 0 \
| 2/3 0 1/3 0 0 0 0 |
| 0 2/3 0 1/3 0 0 0 |
A = | 0 0 2/3 0 1/3 0 0 |
| 0 0 0 2/3 0 1/3 0 |
| 0 0 0 0 2/3 0 1/3 |
\ 0 0 0 0 0 0 1 /
direkt eingeben kï¿œnnte, aber ich will ja nicht meckern...
Aber eine Frage bleibt: Wie berechnet das Programm den Erwartungswert
E(X) = 360
fï¿œr
X = "Anzahl der Schritte bis zum erstmaligen Erreichen des Zustandes 6"?
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Dieter Kadelka
Sei m(s) die mittlere Zeit, die man braucht um von s aus 6 oder grￜￜer
zu erreichen. Dann m(s) = 0 fï¿œr s >= 6.
Fï¿œr s = 0: m(0) = 1 + Wahrs., dass man wieder nach 0 kommt * m(0) +
Wahrsch., dass man nach 1 kommt * m(1) = 1 + 2/3 * m(0) + 1/3 * m(1),
also m(0 = 3 + m(1)
Fï¿œr 0 < s < 6:
m(s) = 1 + 2/3 * m(s-1) + 1/3 * m(s+1)
So erhï¿œlt man m(1) = 1 + 2/3 * m(0) + 1/3 * m(2) = 3 + 2/3 * m(1) + 1/3
* m(2), also m(1) = 3*(2/3 * 3 +1) + m(2) = 9 + m(2), genauso
m(2) = 3*(2/3 * 9 + 1) + m(3) = 21 + m(3)
m(3) = 45 + m(4)
m(4) = 93 + m(5)
m(5) = 189 + m(6) = 189
und damit m(0) = 3 + 9 + 21 + 45 + 93 + 189 = 360
Viele Grￜￜe
Dieter Kadelka
--
Dr. Dieter Kadelka
Karlsruher Institut fï¿œr Technologie (KIT)
Institut fï¿œr Stochastik
Kaiserstr. 89-93
D 76133 Karlsruhe
Tel.: 0721 608 3271
Fax : 0721 608 6066
Alfred Heiligenbrunner
Danke f�r deine Verteidigung und (f�r mich) Klarstellung, um welche
Kategorie von Postern es sich da handelt.
Ich h�tte dem Herren (oder der Dame) ohnehin nichts antworten k�nnen.
Alfred Heiligenbrunner
Ja.
Oder auch folgendes:
-- Dies ist die Beschreibung eines stochastischen Automaten
--
-- von_Knoten zu_Knoten ï¿œbergangswahrscheinlichkeit
-- ---------- --------- ---------------------------
k0 k0 2/3
k0 k1 1/3
k1 k0 2/3
k1 k2 1/3
k2 k1 2/3
k2 k3 1/3
k3 k2 2/3
k3 k4 1/3
k4 k3 2/3
k4 k5 1/3
k5 k4 2/3
k5 k6 1/3
-- Ende
(Zeilen, die mit "--" beginnen, werden als Kommentar ignoriert.)
(Da "k6" nicht als "von_Knoten" auftaucht, wird er als Endknoten
behandelt; die ï¿œbergangswahrscheinlichkeit "von k6 zu k6" wird auf 1
gesetzt.)
>
> Scheint zu funktionieren; es erscheint die ï¿œbergangsmatrix, die man
> "erwartet", und sogar sï¿œmtliche nicht angegebenen Wahrscheinlichkeiten
> werden automatisch auf 0 gesetzt. Wobei es fast einfacher wï¿œre, wenn man
> die ï¿œbergangsmatrix
>
> / 2/3 1/3 0 0 0 0 0 \
> | 2/3 0 1/3 0 0 0 0 |
> | 0 2/3 0 1/3 0 0 0 |
> A = | 0 0 2/3 0 1/3 0 0 |
> | 0 0 0 2/3 0 1/3 0 |
> | 0 0 0 0 2/3 0 1/3 |
> \ 0 0 0 0 0 0 1 /
>
> direkt eingeben kï¿œnnte, aber ich will ja nicht meckern...
Nun ja, die ï¿œbergangsmatrix wï¿œchst schnell in's Unï¿œbersichtliche,
besonders in einem beschrï¿œnkten Eingabefeld im Browser, die Beziehungen
zwischen Knoten bleiben relativ ï¿œbersichtlich. In der Praxis hat jeder
Knoten nur wenige Verbindungen zu anderen Knoten.
>
> Aber eine Frage bleibt: Wie berechnet das Programm den Erwartungswert
> E(X) = 360
> fï¿œr
> X = "Anzahl der Schritte bis zum erstmaligen Erreichen des Zustandes 6"?
>
>
Hier kann ich nur wiedergeben, was ich aus Stochastik-Vorlesungen vor
ca. 20 Jahren mitgenommen habe:
Das Programm teilt die Knoten in transiente und absorbierend rekurrente
Knoten ein.
Absorbierend rekurrent ist ein Knoten, wenn er mit Wahrscheinlichkeit 1
in sich selbst ï¿œbergeht, wenn er also gewissermaï¿œen eine Falltï¿œr ist. Es
kann in einem Modell mehrere davon geben.
Transient sind (fï¿œr das Programm) alle anderen.
Gibt es transiente [t1, t2, ...] und absorbierende rekurrente (= End-)
Zustï¿œnde [r1, r2, ...] mit einer ï¿œbergangsmatrix
t1 t2 t3 r1 r2
t1 |
t2 T | R
t3 |
---------------- ,
r1 |
r2 0 | E
so erhï¿œlt man
- die Ws., bei Start in tx in ry zu landen als (E-T)^(-1) . R
- die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
- die mittlere Anzahl der Besuche in ty bei Start in tx als
(E-T)^(-1) - E.
Dabei ist E die Einheitsmatrix, 1 die Matrix aus lauter 1-en.
Fï¿œr Begrï¿œndungen und weitere Details mï¿œsste ich ein bisschen
nachgrï¿œbeln. Ich habe, wie erwï¿œhnt, die Sachen vor 20 Jahren gehï¿œrt, vor
15 Jahren programmiert, vor 10 Jahren fï¿œr's Internet adaptiert.
Der Sourcecode ist frei zugï¿œnglich:
http://www.heiligenbrunner.at/main/ahstoch.js.
The Dust of Time
<alfred.heiligenbrunner_nos...@gmx.at> wrote:
> Stephan Gerlach schrieb am 29.10.2009 13:00:
>
>
>
>
>
> > Alfred Heiligenbrunner schrieb:
> >> Pascal schrieb am 28.10.2009 20:55:
>
> >>> 0 ist und welche man als Spieler erhöhen möchte.
> >>> In jeder Runde wird jetzt:
> >>> - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0
> >>> bleibt es 0.
>
> >>> Beispiel:
> >>> 1. Runde: k=0
> >>> 2. Runde: k=0
> >>> 3. Runde: k=1
> >>> 4. Runde: k=0
> >>> 5. Runde: k=1
> >>> 6. Runde: k=2
>
> >>> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht
> >>> rechnen?
>
> > [...]
>
> >> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> >> (Mit etwas Eigenwerbung:http://www.heiligenbrunner.at/main/ahstoch.htm.)
>
> > Was nimmt man als korrekte Eingabe im Programm, folgendes?
>
> > Null Null 2/3
> > Null Eins 1/3
> > Eins Null 2/3
> > Eins Zwei 1/3
> > Zwei Eins 2/3
> > Zwei Drei 1/3
> > Drei Zwei 2/3
> > Drei Vier 1/3
> > Vier Drei 2/3
> > Fünf Vier 2/3
> > Fünf Sechs 1/3
> > Sechs Fünf 0
> > Sechs Sechs 1
>
> Ja.
> Oder auch folgendes:
>
> -- Dies ist die Beschreibung eines stochastischen Automaten
> --
> -- ---------- --------- ---------------------------
> k0 k0 2/3
> k0 k1 1/3
> k1 k0 2/3
> k1 k2 1/3
> k2 k1 2/3
> k2 k3 1/3
> k3 k2 2/3
> k3 k4 1/3
> k4 k3 2/3
> k4 k5 1/3
> k5 k4 2/3
> k5 k6 1/3
> -- Ende
>
> (Zeilen, die mit "--" beginnen, werden als Kommentar ignoriert.)
> (Da "k6" nicht als "von_Knoten" auftaucht, wird er als Endknoten
> gesetzt.)
>
>
>
> > Scheint zu funktionieren; es erscheint die Übergangsmatrix, die man
> > "erwartet", und sogar sämtliche nicht angegebenen Wahrscheinlichkeiten
> > werden automatisch auf 0 gesetzt. Wobei es fast einfacher wäre, wenn man
> > die Übergangsmatrix
>
> > / 2/3 1/3 0 0 0 0 0 \
> > | 2/3 0 1/3 0 0 0 0 |
> > | 0 2/3 0 1/3 0 0 0 |
> > A = | 0 0 2/3 0 1/3 0 0 |
> > | 0 0 0 2/3 0 1/3 0 |
> > | 0 0 0 0 2/3 0 1/3 |
> > \ 0 0 0 0 0 0 1 /
>
>
> Nun ja, die Übergangsmatrix wächst schnell in's Unübersichtliche,
> besonders in einem beschränkten Eingabefeld im Browser, die Beziehungen
> zwischen Knoten bleiben relativ übersichtlich. In der Praxis hat jeder
> Knoten nur wenige Verbindungen zu anderen Knoten.
>
>
>
> > Aber eine Frage bleibt: Wie berechnet das Programm den Erwartungswert
> > E(X) = 360
> > X = "Anzahl der Schritte bis zum erstmaligen Erreichen des Zustandes 6"?
>
> Hier kann ich nur wiedergeben, was ich aus Stochastik-Vorlesungen vor
> ca. 20 Jahren mitgenommen habe:
>
> Das Programm teilt die Knoten in transiente und absorbierend rekurrente
> Knoten ein.
> Absorbierend rekurrent ist ein Knoten, wenn er mit Wahrscheinlichkeit 1
> kann in einem Modell mehrere davon geben.
>
> Gibt es transiente [t1, t2, ...] und absorbierende rekurrente (= End-)
>
> t1 t2 t3 r1 r2
> t1 |
> t2 T | R
> t3 |
> ---------------- ,
> r1 |
> r2 0 | E
>
> - die Ws., bei Start in tx in ry zu landen als (E-T)^(-1) . R
> - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
> - die mittlere Anzahl der Besuche in ty bei Start in tx als
> (E-T)^(-1) - E.
>
> Dabei ist E die Einheitsmatrix, 1 die Matrix aus lauter 1-en.
>
> nachgrübeln. Ich habe, wie erwähnt, die Sachen vor 20 Jahren gehört, vor
> 15 Jahren programmiert, vor 10 Jahren für's Internet adaptiert.
>
> Der Sourcecode ist frei zugänglich:http://www.heiligenbrunner.at/main/ahstoch.js.- Zitierten Text ausblenden -
>
> - Zitierten Text anzeigen -
Also, was ist jetzt die Lösung vom Travelling Salesman Problem der
Städte in Ö. ?
Antworten !
Stephan Gerlach
>> In dem Spiel dreht es sich um die natï¿œrliche Zahl k, welche zu Begin 0
>> ist und welche man als Spieler erhï¿œhen mï¿œchte.
>> In jeder Runde wird jetzt:
>> - mit einer Wahrscheinlichkeit von p=1/3 der Wert von k um eins erhï¿œht.
>> - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0
>> bleibt es 0.
>>
>> Beispiel:
>> 1. Runde: k=0
>> 2. Runde: k=0
>> 3. Runde: k=1
>> 4. Runde: k=0
>> 5. Runde: k=1
>> 6. Runde: k=2
>>
>> Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>> z.B. k=6 zu erreichen (Erwartungswert?). Wie wï¿œrde man soetwas rechnen?
>>
>> Ich habe bereits mit einem Programm ein paar Tausend Durchgï¿œnge
>> simuliert und dabei auch einheitliche Zahlen herausbekommen. Mich
>> wï¿œrde aber interessieren, ob jemand eine Idee fï¿œr einen mathematischen
>> Ansatz hat.
>> Wenn niemand darauf Lust hat, verstehe ich das natï¿œrlich. ;-)
>
> Sei m(s) die mittlere Zeit, die man braucht um von s aus 6 oder grￜￜer
> zu erreichen. Dann m(s) = 0 fï¿œr s >= 6.
>
> Fï¿œr s = 0: m(0) = 1 + Wahrs., dass man wieder nach 0 kommt * m(0) +
> Wahrsch., dass man nach 1 kommt * m(1) = 1 + 2/3 * m(0) + 1/3 * m(1),
Ich versuche mir gerade zu ï¿œberlegen: Wie kommt wohl diese Formel zustande?
> also m(0 = 3 + m(1)
>
> Fï¿œr 0 < s < 6:
> m(s) = 1 + 2/3 * m(s-1) + 1/3 * m(s+1)
Und analog dazu diese?
Sind das irgendwelche "bekannten" Sï¿œtze (irgendwas mit bedingten
Wahrscheinlichkeiten im Zusammenhang mit Erwartungswert-Berechnung)?
Stephan Gerlach
> Gibt es transiente [t1, t2, ...] und absorbierende rekurrente (= End-)
> Zustï¿œnde [r1, r2, ...] mit einer ï¿œbergangsmatrix
>
> t1 t2 t3 r1 r2
> t1 |
> t2 T | R
> t3 |
> ---------------- ,
> r1 |
> r2 0 | E
>
> so erhï¿œlt man
> - die Ws., bei Start in tx in ry zu landen als (E-T)^(-1) . R
Wobei der Punkt vor dem R wohl als "mal" zu deuten ist, sowie die
Dimension der Einheitsmatrix E (s.u.) passend zu wï¿œhlen ist.
Und mit "Ws., bei Start in tx in ry zu landen" ist offensichtlich kein
Skalar, sondern eine Matrix
/p_{11} p_{12}\
| p_{21} p_{22} |
\p_{31} p_{32}/
gemeint. Und ein einzelner Matrix-Eintrag p_{jk} beschreibt anscheinend
dann die Wahrscheinlichkeit, bei Start in tj nach unendlich langer
Zeit(!) in rk zu landen.
(In 'irgendeinem' der beiden Zustï¿œnde r1 oder r2 wird frï¿œher oder spï¿œter
sowieso mit Wahrscheinlichkeit 1 gelandet.)
Hier kann ich mir sogar noch vorstellen, wie man darauf kommt:
Beschreibe A_{j->k,n} das Ereignis
A_{j->k,n} := "Bei Start in t_j landet man nach genau n Schritten (erst-
und gleichzeitig letztmalig) in r_k".
Wenn man fï¿œr beliebiges n e N_0 die Matrix T^n * R, oder in
elementeweiser Schreibweise
/a_{11,n} a_{12,n}\
T^n * R = | a_{21,n} a_{22,n} |
\a_{31,n} a_{32,n}/
betrachtet, so gibt hierbei z.B. der Matrix-Eintrag a_{12,n} die
Wahrscheinlichkeit fï¿œr das oben definierte Ereignis A_{1->2,n+1} an,
P[A_{1->2,n+1}] = a_{12,n}.
Mￜchte man nun das Ereignis betrachten, daￜ man bei Start in j ￜberhaupt
irgendwann mal in r_k landet, so entspricht das gerade dem Ereignis
Vereinigung_{n=1 bis unendlich} A_{j->k,n}.
Da die A_{j->k,n} fï¿œr verschiedene n paarweise disjunkt sind, berechnet
sich die Wahrscheinlichkeit fￜr die Vereinigung gemￜￜ
P(Vereinigung...) = Summe_{n=1 bis unendlich} P[A_{j->k,n}]
= Summe_{n=0 bis unendlich} P[A_{j->k,n+1}]
= Summe_{n=0 bis unendlich} a_{jk,n}.
Diese einzelnen Summen (3*2 Stï¿œck) in einer Matrix zusammengefaï¿œt
ergeben aber gerade die Matrix
/a_{11,n} a_{12,n}\
Summe_{n=0 bis unendlich} | a_{21,n} a_{22,n} |
\a_{31,n} a_{32,n}/
= Summe_{n=0 bis unendlich} (T^n * R)
= (Summe_{n=0 bis unendlich} T^n) * R
= (E-T)^-1 * R.
Beim letzten Gleichheitszeichen wurde die Formel fï¿œr die Neumann'sche
Reihe fï¿œr Matrizen angewendet. Dies geht, weil die Norm von T kleiner
als 1 ist.
> - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
> - die mittlere Anzahl der Besuche in ty bei Start in tx als
> (E-T)^(-1) - E.
Hierzu ist mir momentan noch nix eingefallen; vermutlich geht die
Begrï¿œndung aber jeweils wieder ï¿œber die Neumann'scher Reihe
Summe_{n=0 bis unendlich} T^n = (E-T)^-1.
> Dabei ist E die Einheitsmatrix, 1 die Matrix aus lauter 1-en.
--
The Dust of Time
wrote:
> Alfred Heiligenbrunner schrieb:
>
> > Gibt es transiente [t1, t2, ...] und absorbierende rekurrente (= End-)
>
> > t1 t2 t3 r1 r2
> > t1 |
> > t2 T | R
> > t3 |
> > ---------------- ,
> > r1 |
> > r2 0 | E
>
> > - die Ws., bei Start in tx in ry zu landen als (E-T)^(-1) . R
>
> Wobei der Punkt vor dem R wohl als "mal" zu deuten ist, sowie die
> Und mit "Ws., bei Start in tx in ry zu landen" ist offensichtlich kein
> Skalar, sondern eine Matrix
> /p_{11} p_{12}\
> | p_{21} p_{22} |
> \p_{31} p_{32}/
> gemeint. Und ein einzelner Matrix-Eintrag p_{jk} beschreibt anscheinend
> dann die Wahrscheinlichkeit, bei Start in tj nach unendlich langer
> Zeit(!) in rk zu landen.
> sowieso mit Wahrscheinlichkeit 1 gelandet.)
>
> Hier kann ich mir sogar noch vorstellen, wie man darauf kommt:
> Beschreibe A_{j->k,n} das Ereignis
>
> A_{j->k,n} := "Bei Start in t_j landet man nach genau n Schritten (erst-
> und gleichzeitig letztmalig) in r_k".
>
> elementeweiser Schreibweise
> /a_{11,n} a_{12,n}\
> T^n * R = | a_{21,n} a_{22,n} |
> \a_{31,n} a_{32,n}/
> betrachtet, so gibt hierbei z.B. der Matrix-Eintrag a_{12,n} die
> P[A_{1->2,n+1}] = a_{12,n}.
> irgendwann mal in r_k landet, so entspricht das gerade dem Ereignis
>
> Vereinigung_{n=1 bis unendlich} A_{j->k,n}.
>
> sich die Wahrscheinlichkeit für die Vereinigung gemäß
>
> P(Vereinigung...) = Summe_{n=1 bis unendlich} P[A_{j->k,n}]
> = Summe_{n=0 bis unendlich} P[A_{j->k,n+1}]
> = Summe_{n=0 bis unendlich} a_{jk,n}.
>
> ergeben aber gerade die Matrix
>
> /a_{11,n} a_{12,n}\
> Summe_{n=0 bis unendlich} | a_{21,n} a_{22,n} |
> \a_{31,n} a_{32,n}/
>
> = Summe_{n=0 bis unendlich} (T^n * R)
> = (Summe_{n=0 bis unendlich} T^n) * R
> = (E-T)^-1 * R.
>
> Reihe für Matrizen angewendet. Dies geht, weil die Norm von T kleiner
> als 1 ist.
>
> > - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
> > - die mittlere Anzahl der Besuche in ty bei Start in tx als
> > (E-T)^(-1) - E.
>
> Hierzu ist mir momentan noch nix eingefallen; vermutlich geht die
> Summe_{n=0 bis unendlich} T^n = (E-T)^-1.
>
> > Dabei ist E die Einheitsmatrix, 1 die Matrix aus lauter 1-en.
>
> --> Eigentlich sollte Brain 1.0 laufen.
>
> gut, dann werde ich mir das morgen mal besorgen...
> (...Dialog aus m.p.d.g.w.a.)
Warum steht auf der Startseite meiner Homepage "Diese Domain ist
bereits registriert"?
Diese Seite wurde automatisch erstellt, als Sie Ihr 1&1 Domain-Paket
oder Hosting-Paket registriert haben. Es handelt sich dabei um eine
vorübergehende Seite, die Sie allerdings jederzeit ersetzen können -
entweder mit einer anderen Seite Ihrer Wahl, oder mit einer Homepage.
Dazu müssen Sie lediglich die Datei "index.html" überschreiben oder
ersetzen. Um eine Homepage zu erstellen und einzufügen, können Sie
eines unserer Homepage-Tools benutzen, mit denen Sie schnell und
einfach Ihre eigene Homepage einrichten können - oder Sie nutzen eine
Homepage-Software Ihrer Wahl.
Warum haben wir für Sie diese vorübergehende Seite eingerichtet?
Wir haben diese Seite für Sie eingerichtet, damit Ihre Domain von
anderen Nutzern aufgerufen werden kann - ohne diese Seite würden Ihre
Besucher nichts weiter erhalten als die Fehlermeldung "Seite nicht
gefunden". Solange diese Seite jedoch angezeigt wird, sehen Ihre
Besucher, dass Ihre Domain gültig ist.
Hinweis: Die erste Seite, die angezeigt wird, wenn jemand Ihre Domain
aufruft, muss unter "index.html" abgespeichert werden.
Was ist jetzt zu tun?
Um Ihren Besuchern die richtige Reihenfolge Ihrer Homepage unter Ihrer
Domain anzuzeigen, muss sie eine Datei namens "index.html" besitzen.
Dateien mit anderen Namen wie beispielsweise "seite1.html" oder
"home.html" werden NICHT als Startseite erwartet. Sie sollten daher
eine entsprechende Datei in "index.html" umbenennen, um anzuzeigen,
dass sie die Startseite Ihrer Homepage ist.
Hinweis: Beachten Sie bitte die Groß- und Kleinschreibung: Die erste
Seite muss unbedingt "index.html" heißen - andere Schreibweisen wie
"Index.html" oder "INDEX.html" können nicht angezeigt werden! Beachten
Sie auch bitte die Schreibweise der Dateinendung "html" - Dateien mit
der Endung "htm" sollten Sie daher unter der Endung "html"
abspeichern.
??????????????????????? Wer bei 1 und 1 registriert ist, ist in
Berlin beim Schäuble registriert !!!!
Der Bulle will mich also wieder mal verhören - wielange soll das noch
weitergehen ?
Bewiesen ist wohl nun : Jeder der in Deutschland Steuern zahlt ist
Mittäter von Kriminellen !
The Dust of Time
In CNBC kam heute ein Bericht über soziale Netzwerke - Twitter,
Facebook, Scype und Co., aber Google ist ja wohl ein asoziales
Netzwerk !
The Dust of Time
>
>
>
>
>
> > Hallo =)
>
> > ist und welche man als Spieler erhöhen möchte.
> > In jeder Runde wird jetzt:
> > - ansonsten (p=2/3) wird k um eins erniedrigt, ist allerdings k=0 bleibt
> > es 0.
>
> > Beispiel:
> > 1. Runde: k=0
> > 2. Runde: k=0
> > 3. Runde: k=1
> > 4. Runde: k=0
> > 5. Runde: k=1
> > 6. Runde: k=2
>
> > Die Frage lautet jetzt, wieviele Runden man im Durchschnitt braucht um
>
> http://de.wikipedia.org/wiki/Markow-Kette
>
> Von 'k=0' kommt man im Mittel nach 360 Schritten zu 'k=6'.
> (Mit etwas Eigenwerbung:http://www.heiligenbrunner.at/main/ahstoch.htm.)
>
>
> - Zitierten Text anzeigen -
Tolle homepage - wie lautet deine Telefonnummer, Alfred ?
( ich stelle meine übrigens auch ganz cool ins Internet ...... )
Dieter Kadelka
die prï¿œzise Begrï¿œndung setzt einiges an Kenntnissen ï¿œber homogene
Markovketten voraus. Vieles davon kann man aber auch auf ziemlich
inituitive Weise herleiten, wenn man die Begriffe Erwartungswert EX,
bedingte Wahrscheinlichkeit P(A | B) und bedingter Erwartungswert
E[X|Y=i] (X und Y Zufallsvariablen) als bekannt voraussetzt (wie auch
oben schon vermutet).
Sei X_n der zufï¿œllige Spielstand nach n durchgefï¿œhrten Spielen (hier ist
X_0 = 0, aber die gleichen ï¿œberlegungen gelten auch fï¿œr andere
Spielstï¿œnde s zu Beginn) und tau die zufï¿œllige Zeit, die man braucht, um
zum Spielstand 6 zu gelangen. Es ist dann m(s) = E[tau | X_0 = s]. Es
gilt dann auch (fï¿œr s < 6)
m(s) = sum_t E[tau | X_0 = s,X_1 = t] * P(X_1 = t | X_0 = s) =
(Markov-Eigenschaft)
sum_{t:t >= 6) 1 * P(X_1 = t | X_0 = s) + sum_{t: t < 6} E[1+tau | X_1 =
t] * P(X_1 = t | X_0 = s)
Setzt man hier die vorgegebenen ï¿œbergangswahrscheinlichkeiten ein,
erhï¿œlt man die oben angegebene Formeln.
Ich hoffe ein klein wenig zur Erhellung beigetragen zu haben.
Einiges an Theorie dazu (fï¿œr die Schule leider wohl zu kompliziert)
findet man z.B. in J.R. Norris, Markov Chains, Cambridge University
Press, 1997 auf den Seiten 12 - 19.
Alfred Heiligenbrunner
Sehr gut.
>
>> - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
Das geht mit folgender Begrï¿œndung.
Angenommen, es gibt nur einen Endzustand E (= ry = r1).
Die transienten Zustï¿œnde seien t_1, t_2, ..., t_n.
p_{i,j} sei die Wahrscheinlichkeit, in einem Schritt von t_i nach t_j zu
kommen.
Sei s_i die mittlere Anzahl von Schritte, die notwendig ist, um von
Zustand t_i zum Endzustand E zu kommen.
Es gilt dann:
s_1 = 1 + p_{1,1} s_1 + p_{1,2} s_2 + ... + p_{1,n} s_n.
In Worten: Um von t_1 nach E zu kommen brauche ich mindestens 1 Schritt
sowie Anteile p_{1,j} an den Weglï¿œngen s_j (s_j = Weglï¿œnge von t_j nach
E), je nachdem, wohin ich nach dem einen Schritt gelangt bin.
Genauso gilt:
s_2 = 1 + p_{2,1} s_1 + p_{2,2} s_2 + ... + p_{2,n} s_n.
...
s_n = 1 + p_{n,1} s_1 + p_{n,2} s_2 + ... + p_{n,n} s_n.
In Matrix-Schreibweise:
S = 1 + T . S
Das lï¿œsst sich umformen zu
(E - T) . S = 1
oder
S = (E - T)^(-1) . 1.
(1 ist dabei ein Vektor der Lï¿œnge n aus lauter "1"-en.)
(T ist die Matrix der ï¿œbergangswahrscheinlichkeiten p_{i,j}.)
Inwieweit man damit Aussagen ï¿œber mehrere Endzustï¿œnde machen kann, muss
ich mir noch ï¿œberlegen.
Immerhin kann man den Workaround verwenden, von jedem "ursprï¿œnglichen"
Endzustand r_j einen ï¿œbergang zu einem neuen Endzustand E dazu zu geben.
Jedes r_j erreicht E mit Wahrscheinlichkeit 1 in genau 1 Schritt.
Aus der Aussage t_i erreicht E in durchschnittlich s_i Schritten kann
man dann schlieï¿œen, dass t_i in s_i - 1 Schritten in einem der r_j war.
Ein anderer Weg der Berechnung ist folgender.
Der Erwartungswert der Anzahl der Schritte von Zustand z_i nach Zustand
z_j steht in Element (i,j) der Matrix
1 * P + 2 * P . P + 3 * P . P . P + ... = P . (E-P)^(-2).
(Das Gleichheitszeichen gilt auf Grund von Matrizen-Arithmetik und
natï¿œrlich nur im Fall, dass der rechte Ausdruck existiert.)
Dabei ist P die ï¿œbergangsmatrix, wobei die Zeile j durch lauter 0-en
ersetzt wurde. (Von Zustand z_j mï¿œchte man ja nicht mehr weg.)
Zumindest im Fall von nur 1 Endzustand kann man
P . (E-P)^(-2)
ersetzen durch
(E - T)^(-1) . 1.
>> - die mittlere Anzahl der Besuche in ty bei Start in tx als
>> (E-T)^(-1) - E.
Das ist ein relativ tief liegendes Resultat aus der Theorie der
Markoff-Ketten. Nï¿œheres sollte sich im Dunstkreis "Ergodensatz" und "K.
L. Chung" finden lassen.
Stephan Gerlach
> Sei X_n der zufï¿œllige Spielstand nach n durchgefï¿œhrten Spielen (hier ist
> X_0 = 0, aber die gleichen ï¿œberlegungen gelten auch fï¿œr andere
> Spielstï¿œnde s zu Beginn) und tau die zufï¿œllige Zeit, die man braucht, um
> zum Spielstand 6 zu gelangen.
Und tau wird vom Zeitpunkt t=0 aus gemessen, nehme ich an?
> Es ist dann m(s) = E[tau | X_0 = s].
Ja, das ist klar. Ich finde die Bezeichnung E[tau | X_0 = s] sogar
leichter verstￜndlich als m(s), da deutlich wird, daￜ es sich um den
Erwartungswert einer Zufallsvariable handelt.
> Es
> gilt dann auch (fï¿œr s < 6)
> m(s) = sum_t E[tau | X_0 = s,X_1 = t] * P(X_1 = t | X_0 = s) =
Sieht bei genauem Hinsehen doch recht intuitiv aus; fast aus wie der
sogenannte "Satz von der totalen Wahrscheinlichkeit".
Hat der hier aufgefï¿œhrte Satz auch einen ï¿œhnlichen Namen; "Satz vom
totalen Erwartungswert" oder so?
Was ist, wenn t einen kontinuierlichen Bereich durchlï¿œuft; ich nehme an,
die Summe wird dann ein Integral ï¿œber dt (oder so ungefï¿œhr)?
> (Markov-Eigenschaft)
> sum_{t:t >= 6) 1 * P(X_1 = t | X_0 = s) + sum_{t: t < 6} E[1+tau | X_1 =
> t] * P(X_1 = t | X_0 = s)
>
> Setzt man hier die vorgegebenen ï¿œbergangswahrscheinlichkeiten ein,
> erhï¿œlt man die oben angegebene Formeln.
Das ist dann klar.
Man zerlegt auch die Zufallsvariable tau gewissermaï¿œen in
tau = 1 + (Zeit bis Spielstand 6 vom Zeitpunkt t=1 gemessen)
wenn ich das richtig verstanden habe.
Alfred Heiligenbrunner
> Ein anderer Weg der Berechnung [der mittleren Anzahl der Schritte bis zum Endzustand] ist folgender.
> Der Erwartungswert der Anzahl der Schritte von Zustand z_i nach Zustand
> z_j steht in Element (i,j) der Matrix
>
Das war falsch. Tut leid.
Die Aussage stimmt nur dann, wenn jede der Matrizen P, P.P, P.P.P, ...,
P^n, ... als Element (i,j) die BEDINGTE Wahrscheinlichkeit enthï¿œlt, nach
n Schritten in in z_j zu enden, unter der _Bedingung_, dass das Ende
ï¿œberhaupt in z_j ist. Wenn also Summe(n = 1, 2, ...: p_(i,j)(n)) = 1
ist. Das ist dann der Fall, wenn es nur 1 Endzustand gibt. Dieser Fall
ist aber schon mit einfacheren Mitteln berechenbar.
Alfred Heiligenbrunner
...
>
>>
>>> - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
>
> Das geht mit folgender Begrï¿œndung.
> Angenommen, es gibt nur einen Endzustand E (= ry = r1).
> Die transienten Zustï¿œnde seien t_1, t_2, ..., t_n.
> p_{i,j} sei die Wahrscheinlichkeit, in einem Schritt von t_i nach t_j zu
> kommen.
>
> Sei s_i die mittlere Anzahl von Schritte, die notwendig ist, um von
> Zustand t_i zum Endzustand E zu kommen.
>
> Es gilt dann:
...
> S = (E - T)^(-1) . 1.
>
> (1 ist dabei ein Vektor der Lï¿œnge n aus lauter "1"-en.)
> (T ist die Matrix der ï¿œbergangswahrscheinlichkeiten p_{i,j}.)
>
Die selbe Rechnung kann man auch durchfï¿œhren, wenn es mehrere
Endzustï¿œnde gibt.
s_i ist dann die mittlere Anzahl der Schritte, die notwendig ist, um von
Zustand t_i zu _einem_ (egal welchem) der Endzustï¿œnde zu kommen.
>
>
> Ein anderer Weg der Berechnung ist folgender.
> Der Erwartungswert der Anzahl der Schritte von Zustand z_i nach Zustand
> z_j steht in Element (i,j) der Matrix
>
...
> P . (E-P)^(-2).
>
> Dabei ist P die ï¿œbergangsmatrix, wobei die Zeile j durch lauter 0-en
> ersetzt wurde. (Von Zustand z_j mï¿œchte man ja nicht mehr weg.)
>
...
>
>
>>> - die mittlere Anzahl der Besuche in ty bei Start in tx als
>>> (E-T)^(-1) - E.
>
Beispiel:
Betrachten wir die 4 Zustï¿œnde t1, t2, r1, r2 mit der ï¿œbergangsmatrix
von\zu | t1 t2 r1 r2
-------------------------
t1 | 1/3 1/3 1/3 0
t2 | 0 1/2 0 1/2
r1 | 0 0 1 0
r2 | 0 0 0 1
Als ASCII-Grafik sehen die ï¿œbergï¿œnge so aus:
__ __
1/3 / \ 1/3 / \ 1
'-> t1 -----------> r1 <-'
|
__ | 1/3 __
1/2 / \ v 1/2 / \ 1
'-> t2 -----------> r2 <-'
Neben den absorbierenden Zustï¿œnden (d.h., Endzustï¿œnden) r1 und r2 gibt
es noch die Zustï¿œnde t1 und t2.
Es ist
/ 1/3 1/3 \
T = | |,
\ 0 1/2 /
/ 1/3 0 \
R = | |,
\ 0 1/2 /
/ 3/2 1 \
(E-T)^(-1) = | |.
\ 0 2 /
Ergebnisse:
1) die Ws., bei Start in tx in ry zu landen ist (E-T)^(-1) . R:
Wahrscheinlichkeit fï¿œr Endzustand:
von\zu | r1 r2
------------------
t1 | 1/2 1/2
t2 | 0 1
(Bei Start in t1 lande ich mit gleicher Wahrscheinlichkeit in r1 oder
r2. Bei Start in t2 lande ich mit Sicherheit nur in r2.)
2) die mittlere Anzahl der Schritte von tx zu ry ist (E-T)^(-1) . 1:
Schrittanzahl bis zu irgendeinem der Endzustï¿œnde:
von\zu | {r1 oder r2}
------------------
t1 | 5/2
t2 | 2
(Von t1 brauche ich im Mittel 2.5 Schritte, um irgendwo absorbiert zu
werden. Bei Start in t2 brauche ich im Mittel 2 Schritte.)
3) die mittlere Anzahl der Besuche in ty bei Start in tx ist
(E-T)^(-1) - E:
von\zu | t1 t2
------------------
t1 | 1/2 1
t2 | 0 1
(Bei Start in t1 besuche ich t1 im Durchschnitt 1/2 Mal, t2 1 Mal.
Bei Start in t2 komme ich nicht zu t1, und verweile in t2 im Durschnitt
1 Schritt lang.)
Stephan Gerlach
> Stephan Gerlach schrieb am 30.10.2009 22:22:
>> Alfred Heiligenbrunner schrieb:
>>> - die mittlere Anzahl der Schritte von tx zu ry als (E-T)^(-1) . 1
>
> Das geht mit folgender Begrï¿œndung.
> Angenommen, es gibt nur einen Endzustand E (= ry = r1).
> Die transienten Zustï¿œnde seien t_1, t_2, ..., t_n.
> p_{i,j} sei die Wahrscheinlichkeit, in einem Schritt von t_i nach t_j zu
> kommen.
>
> Sei s_i die mittlere Anzahl von Schritte, die notwendig ist, um von
> Zustand t_i zum Endzustand E zu kommen.
Ich wￜrd's ja eher E(s_i) nennen, um kenntlich zu machen, daￜ s_i eine
Zufallsvariable sowie E(s_i) deren Erwartungswert ist ;-) .
> Es gilt dann:
> s_1 = 1 + p_{1,1} s_1 + p_{1,2} s_2 + ... + p_{1,n} s_n.
Das ist die Formel, die auch Dieter Kadelka in ï¿œhnlicher Form gebracht hat.
> In Worten: Um von t_1 nach E zu kommen brauche ich mindestens 1 Schritt
> sowie Anteile p_{1,j} an den Weglï¿œngen s_j (s_j = Weglï¿œnge von t_j nach
> E), je nachdem, wohin ich nach dem einen Schritt gelangt bin.
Oder diese Summenformel noch anders begrï¿œndet:
Wir betrachten die folgenden Zufallsvariablen beim Start zum Zeitpunkt 0
und im Zustand t_i
S_{i,0} = [Anzahl Schritte vom Zeitpunkt 0 bis zum Erreichen von E]
S_{i,1} = [Anzahl Schritte vom Zeitpunkt 1 bis zum Erreichen von E]
Z_{01} = [Zustand, der beim ï¿œbergang vom Zeitpunkt 0 zum Zeitpunkt 1
erreicht wurde].
Dann gilt S_{i,0} = 1 + S_{i,1} (IMHO durchaus ein entscheidender Punkt
bei dieser ï¿œberlegung!) und damit fï¿œr den Erwartungswert
E[S_{i,0}]
= E[1 + S_{i,1}]
= 1 + E[S_{i,1}]
= 1 + Summe_{k=1 bis n} E[S_{i,1}|Z_{01}=t_k]*P[Z_{01}=t_k]
Die Begrï¿œndung fï¿œr das letzte Gleichheitszeichen soll die Formel fï¿œr
bedingten Erwartunswert sein. Und nun kann man sich noch gedanklich
davon ￜberzeugen, daￜ
E[S_{i,1}|Z_{01}=t_i] = E[S_{i,0}]
gilt und dieser Erwartungswert genau das ist, was du oben s_i genannt
hast. Und P[Z_{01}=t_k] ist dabei fï¿œr festes k natï¿œrlich nichts anderes
als die ï¿œbergangswahrscheinlichkeit p_{i,k}.
> Genauso gilt:
> s_2 = 1 + p_{2,1} s_1 + p_{2,2} s_2 + ... + p_{2,n} s_n.
> ...
> s_n = 1 + p_{n,1} s_1 + p_{n,2} s_2 + ... + p_{n,n} s_n.
>
> In Matrix-Schreibweise:
> S = 1 + T . S
Das erklï¿œrt, wo der 1-Vektor (bzw. bei mehr Endzustï¿œnden die 1-Matrix?)
herkommt.
> Das lï¿œsst sich umformen zu
> (E - T) . S = 1
> oder
> S = (E - T)^(-1) . 1.
>
> (1 ist dabei ein Vektor der Lï¿œnge n aus lauter "1"-en.)
> (T ist die Matrix der ï¿œbergangswahrscheinlichkeiten p_{i,j}.)
Insgesamt eine elegante Begrï¿œndung, die ohne unendliche Reihe
E[X] = Summe_{k=1 bis unendlich} k*P[X=k]
auskommt.
> Inwieweit man damit Aussagen ï¿œber mehrere Endzustï¿œnde machen kann, muss
> ich mir noch ï¿œberlegen.
Geht das nicht einfach analog? Evtl. mￜￜte man oben nur die Notation
geeignet anpassen, um "das zu sehen". Laut deiner Notation beschrieb ja
s_i den Erwartungswert
s_i = E[Anzahl Schritte von Zustand t_i zum (einzigen) Endzustand r_1].
Hat man nun mehrere Endzustï¿œnde r_1, ..., r_m, so definiert man eben
s_{ij} = E[Anzahl Schritte von Zustand t_i zum Endzustand r_j],
wobei j von 1 bis m lï¿œuft. Dann sehen die n Gleichungen, die du schon
hergeleitet hattest und die die ï¿œbergï¿œnge von t_1, t_2, ..., t_n nach
r_1 beschreiben, so aus:
s_{11} = 1 + p_{1,1} s_{11} + p_{1,2} s_{21} + ... + p_{1,n} s_{n1}
s_{21} = 1 + p_{2,1} s_{11} + p_{2,2} s_{21} + ... + p_{2,n} s_{n1}
...
s_{n1} = 1 + p_{n,1} s_{11} + p_{n,2} s_{21} + ... + p_{n,n} s_{n1}
Das war also der Fall j=1; die ï¿œbergï¿œnge in den (bis dato einzigen)
Endzustand r_1. Nun gibt es fï¿œr die Fï¿œlle j = 2, ..., m analoge
Gleichungssysteme
s_{12} = 1 + p_{1,1} s_{12} + p_{1,2} s_{21} + ... + p_{1,n} s_{n2}
s_{22} = 1 + p_{2,1} s_{12} + p_{2,2} s_{21} + ... + p_{2,n} s_{n2}
...
s_{n2} = 1 + p_{n,1} s_{12} + p_{n,2} s_{21} + ... + p_{n,n} s_{n2}
...
s_{1m} = 1 + p_{1,1} s_{1m} + p_{1,2} s_{2m} + ... + p_{1,n} s_{nm}
s_{2m} = 1 + p_{2,1} s_{1m} + p_{2,2} s_{2m} + ... + p_{2,n} s_{nm}
...
s_{nm} = 1 + p_{n,1} s_{1m} + p_{n,2} s_{2m} + ... + p_{n,n} s_{nm}.
Das erste Gleichungssystem sieht in Matrixschreibweise folgendermaï¿œen
aus (hattest du schon; ich habe nur S durch S_1 ersetzt):
S_1 = 1 + T . S_1
Analog nun die anderen Gleichungsssysteme:
S_2 = 1 + T . S_2
...
S_m = 1 + T . S_m
Wobei alle S_j hierbei Matrizen mit jeweils n Zeilen, aber nur 1 Spalte
sind. 'Baut' man nun aus diesen Matrizen S_j eine Blockmatrix mit m
Blockspalten (auch insgesamt m Spalten, da jeder Block nur aus 1 Spalte
besteht), so erhï¿œlt man
(S_1, S_2, ..., S_m) = (1 + T . S_1, 1 + T . S_2, ..., 1 + T . S_m)
= (1, 1, ...,1) + T.(S_1, S_2, ..., S_m)
Durch Umstellen nach (S_1, S_2, ..., S_m) ergibt sich, analog zum Fall
mit nur einer Spalte S_1, dann
(S_1, S_2, ..., S_m) = (E - T)^-1 . (1, 1, ...,1).
Ich hoffe mal, das geht so einfach - insbesondere die Gï¿œltigkeit der
Gleichungssysteme, von denen man dabei ausgeht?!
Alfred Heiligenbrunner
>
> (S_1, S_2, ..., S_m) = (E - T)^-1 . (1, 1, ...,1).
(Dabei ist jedes S_j ein Spaltenvektor, jedes "1" auch ein Spaltenvektor.)
Die Idee ist verlockend. Aber da bekommt jedes S_j die selben Werte.
Es steht letztlich nur der Vektor (E - T)^-1 . 1 mehrmals seitlich
versetzt nebeneinander. :-)
Bastian Erdnuess
> Dieter Kadelka schrieb:
>
> > [...]
> >
> > Es gilt dann auch (f�r s < 6)
> > m(s) = sum_t E[tau | X_0 = s,X_1 = t] * P(X_1 = t | X_0 = s) =
>
> Sieht bei genauem Hinsehen doch recht intuitiv aus; fast aus wie der
> sogenannte "Satz von der totalen Wahrscheinlichkeit".
> Hat der hier aufgef�hrte Satz auch einen �hnlichen Namen; "Satz vom
> totalen Erwartungswert" oder so?
Der "Satz vom iterierten Erwartungswert"?
E[X] = E[E[X|Y]]
Oder hier etwas speziefischer:
E[X|Z] = E[E[X|Y,Z]|Z]
Nach dem was bisher geschrieben wurde, scheint es als w�rde der Zustand
t im Mittel zum ersten Mal nach
3 [2 (2^t - 1) - t]
Schritten erreicht werden.
Die Idee:
Seit m(s,t) die Mittlere Anzahl an Schritten von Zustand s bis Zustand t
oder gr��er, dann ist
m(s,t) = 0 f�r s >= t
m(0,t) = 1 + 2/3 m(0,t) + 1/3 m(1,t) ==> m(0,t) = 3 + m(1,t)
m(s,t) = 1 + 2/3 m(s-1,t) + 1/3 m(s+1,t) ==>
==> 3 m(s,t) = 3 + 2 m(s-1,t) + m(s+1,t)
m(s,t) - m(s+1,t) = 3 + 2 (m(s-1,t) - m(s,t))
Mit n(s,t) = m(s,t) - m(s+1,t) wird daraus
n(s,t) = 0 f�r s >= t
n(0,t) = 3
n(s,t) = 3 + 2 n(s-1,t)
Offenbar l�st
n(s,t) = 3 (2^(s+1) - 1) f�r s < t
die Rekursion und somit ist
m(0,t) = m(0,t)-m(1,t) + m(1,t)-m(2,t) +...+ m(t-1,t)-m(t,t) + m(t,t)
= n(0,t) + n(1,t) + ... + n(t-1,t) + 0
= sum[s=0..t-1] n(s,t)
= 3 sum[s=0..t-1] (2^(s+1) - 1)
= 3 sum[s=1..t] (2^s - 1)
= 3 [(2^(t+1) - 2) / (2 - 1) - t]
= 3 [2 (2^t - 1) - t]
Das l�sst sich auch verallgemeinern:
Mit der W'kt p kommt man aus dem Zustand n in den Zustand n+1 und
anderenfalls f�llt man in Zustand n-1 zur�ck, bzw. bleibt in 0. Es gilt
dann (ohne alle Randbedingungen):
m(0,t) = 1 + p m(1,t) + (1-p) m(0,t) ==> m(0,t) = 1/p + m(1,t)
m(s,t) = 1 + p m(s+1,t) + (1-p) m(s-1,t)
==> p (m(s,t) - m(s+1,t)) = 1 + (1-p) (m(s-1,t) - m(s,t))
m(s,t) - m(s+1,t) = 1/p + (1-p)/p (m(s-1,t) - m(s,t))
und analog mit n(s,t) = m(s,t) - m(s+1,t)
n(0,t) = 1/p ,
n(s,t) = 1/p + (1-p)/p n(s-1,t) = 1/p + q n(s-1,t)
mit q = (1-p)/p.
Die Rekursion wird von
n(s,t) = 1/p (q^(s+1) - 1) / (q - 1)
gel�st und somit ist
m(0,t) = sum[s=1..t] 1/p (q^s - 1) / (q - 1)
= 1/p 1/(q-1) sum[s=1..t] (q^s - 1)
= 1/p 1/(q-1) [q (q^t - 1) / (q - 1) - t]
= 1/(1-2p) [(1-p)/(1-2p) (q^t - 1) - t] .
F�r p < 1/2 steigt m(0,t) also exponentiell an und f�r p > 1/2 steigt
m(0,t) linear an. F�r p = 1/2 ist n(s,t) = 2(s+1) und m(0,t) = t(t+1)
steigt quadratisch an.
Gr��e,
Bastian
Stephan Gerlach
ï¿œh, ja, stimmt :-) .
Mir stellt sich ohnehin die Frage, ob bei mehreren Endzustï¿œnden r_1,
..., r_n die Zufallsvariable (und damit deren Erwartungswert)
S_{0,r_i} = "Anzahl der Schritte vom Zustand 0 bis r_i"
ï¿œberhaupt sinnvoll definiert ist. Oder ob man nicht lieber definieren sollte
S_{0,r_i} = "Anzahl der Schritte vom Zustand 0 bis r_i unter der
Annahme, daￜ man ￜberhaupt in r_i landet".
Oder dann
S_{0,E} = "Anzahl der Schritte vom Zustand 0, bis einer der Endzustï¿œnde
erreicht wird".