Wege in leiterartigem Gitter < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:59 Fr 30.11.2012 | | Autor: | Studi91 |
| Aufgabe | In einem leiterartigen Gitter besteht für jede Position die Wahrscheinlichkeit 1/3, zu einem der benachbarten 3 Punkte zu springen. Dabei ist die Leiter unendlich weit nach links und rechts ausgedehnt ![[]](/images/popup.gif) (Skizze).
Gesucht ist die Wahrscheinlichkeit, dass eine im Punkt a gestartete "Irrfahrt" den Punkt z erreicht, bevor sie zum Punkt a zurückkehrt. |
Hallo,
ich habe Probleme die obigen Aufgabe zu lösen.
Mein erster Ansatz war, dass ich mir zuerst die ersten paar Wahrscheinlichkeiten aufgeschrieben habe und daraus eine Formel herleiten wollte.
Hier sind die Wahrscheinlichkeiten [mm] P_{k}(z), [/mm] dass die Irrfahrt nach k Schritten im Punkt z endet (ich hoffe, ich habe mich beim 7. Schritt nicht verzählt):
1: [mm] P_{1}(z) [/mm] = [mm] \bruch{1}{3}
[/mm]
2: [mm] P_{2}(z) [/mm] = [mm] \bruch{1}{3}
[/mm]
3: [mm] P_{3}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3
[/mm]
4: [mm] P_{4}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3
[/mm]
5: [mm] P_{5}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3 [/mm] + [mm] 8*(\bruch{1}{3})^5
[/mm]
6: [mm] P_{6}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3 [/mm] + [mm] 8*(\bruch{1}{3})^5
[/mm]
7: [mm] P_{7}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3 [/mm] + [mm] 8*(\bruch{1}{3})^5 [/mm] + [mm] 42*(\bruch{1}{3})^7
[/mm]
8: [mm] P_{8}(z) [/mm] = [mm] \bruch{1}{3} [/mm] + [mm] 2*(\bruch{1}{3})^3 [/mm] + [mm] 8*(\bruch{1}{3})^5 [/mm] + [mm] 42*(\bruch{1}{3})^7
[/mm]
Was auffällt ist, dass sich die WK nur nach jedem zweiten Schritt, also bei einer ungeraden Zahl ändert. Dies ist auch logisch, denn für jede Anzahl von Schritten nach links oder rechts muss die selbe Anzahl ja wieder zurück gemacht werden. Dies ergibt eine gerade Zahl. Zusätzlich kommen noch die Schritte nach unten/oben hinzu, aber da diese auch immer unten enden, muss die Gesamtanzahl von Schritten die in z enden ungerade sein.
Außerdem gibt es natürlich auch die selben Kombinationen im Schritt [mm] P_{k}(z) [/mm] wie in [mm] P_{k-2}(z), [/mm] weshalb in jeder neuen Wahrscheinlichkeit nur ein neuer Summand hinzukommt. Dieser neue Summand hat dann im k-ten Schritt den Faktor [mm] (\bruch{1}{3})^{k}.
[/mm]
Meine abschließende Idee ist nun eine Formel für die Folge 1, 2, 8, 42, ... herzuleiten, damit ich dann die Reihe gegen unendlich laufen lassen kann und den Grenzwert bilden kann. Jedoch habe ich auf anhieb keine Idee, wie ich auf die Formel für die Folge kommen könnte.
Gesucht sind also letztendlich die Anzahl der Kombinationen in der Leiter nach k Schritten vom Punkt a zum Punkt z zu kommen, was eben meiner gesuchten Folge entspricht. Kann mir da jemand helfen?
Viele Grüße & Danke
|
|
| |
|
Hallo Studi91,
da hast Du Dich verzählt.
> In einem leiterartigen Gitter besteht für jede Position
> die Wahrscheinlichkeit 1/3, zu einem der benachbarten 3
> Punkte zu springen. Dabei ist die Leiter unendlich weit
> nach links und rechts ausgedehnt
> (Skizze).
Du kannst solche Skizzen hier auch direkt einbinden:
[Dateianhang nicht öffentlich]
> Gesucht ist die Wahrscheinlichkeit, dass eine im Punkt a
> gestartete "Irrfahrt" den Punkt z erreicht, bevor sie zum
> Punkt a zurückkehrt.
>
> Hallo,
>
> ich habe Probleme die obigen Aufgabe zu lösen.
> Mein erster Ansatz war, dass ich mir zuerst die ersten paar
> Wahrscheinlichkeiten aufgeschrieben habe und daraus eine
> Formel herleiten wollte.
> Hier sind die Wahrscheinlichkeiten [mm]P_{k}(z),[/mm] dass die
> Irrfahrt nach k Schritten im Punkt z endet (ich hoffe, ich
> habe mich beim 7. Schritt nicht verzählt):
Besser wäre, auch die Wahrscheinlichkeiten zu bestimmen, dass die Fahrt im Punkt a endet.
> 1: [mm]P_{1}(z)[/mm] = [mm]\bruch{1}{3}[/mm]
> 2: [mm]P_{2}(z)[/mm] = [mm]\bruch{1}{3}[/mm]
Wie Du weiter unten feststellst, kann die Fahrt nicht nach einer geraden Schrittzahl in z enden. Es ist aber
[mm] P_2(a)=\bruch{2}{9}
[/mm]
> 3: [mm]P_{3}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm]
> 4: [mm]P_{4}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm]
[mm] P_4(a)=\bruch{2}{9}+4*\left(\bruch{1}{3}\right)^4
[/mm]
> 5: [mm]P_{5}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm] + [mm]8*(\bruch{1}{3})^5[/mm]
> 6: [mm]P_{6}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm] + [mm]8*(\bruch{1}{3})^5[/mm]
[mm] P_6(a)=\bruch{2}{9}+4*\left(\bruch{1}{3}\right)^4+16*\left(\bruch{1}{3}\right)^6
[/mm]
> 7: [mm]P_{7}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm] + [mm]8*(\bruch{1}{3})^5[/mm] + [mm]38*(\bruch{1}{3})^7[/mm]
Nein, da gibt es nur 32 Wege, die nach 7 Schritten in z enden.
> 8: [mm]P_{8}(z)[/mm] = [mm]\bruch{1}{3}[/mm] + [mm]2*(\bruch{1}{3})^3[/mm] + [mm]8*(\bruch{1}{3})^5[/mm] + [mm]38*(\bruch{1}{3})^7[/mm]
[mm] P_8(a)=\bruch{2}{9}+4*\left(\bruch{1}{3}\right)^4+16*\left(\bruch{1}{3}\right)^6+64*\left(\bruch{1}{3}\right)^8
[/mm]
> Was auffällt ist, dass sich die WK nur nach jedem zweiten
> Schritt, also bei einer ungeraden Zahl ändert. Dies ist
> auch logisch, denn für jede Anzahl von Schritten nach
> links oder rechts muss die selbe Anzahl ja wieder zurück
> gemacht werden. Dies ergibt eine gerade Zahl. Zusätzlich
> kommen noch die Schritte nach unten/oben hinzu, aber da
> diese auch immer unten enden, muss die Gesamtanzahl von
> Schritten die in z enden ungerade sein.
> Außerdem gibt es natürlich auch die selben Kombinationen
> im Schritt [mm]P_{k}(z)[/mm] wie in [mm]P_{k-2}(z),[/mm] weshalb in jeder
> neuen Wahrscheinlichkeit nur ein neuer Summand hinzukommt.
> Dieser neue Summand hat dann im k-ten Schritt den Faktor
> [mm](\bruch{1}{3})^{k}.[/mm]
> Meine abschließende Idee ist nun eine Formel für die
> Folge 1, 2, 8, 38, ... herzuleiten, damit ich dann die
> Reihe gegen unendlich laufen lassen kann und den Grenzwert
> bilden kann. Jedoch habe ich auf anhieb keine Idee, wie ich
> auf die Formel für die Folge kommen könnte.
> Gesucht sind also letztendlich die Anzahl der
> Kombinationen in der Leiter nach k Schritten vom Punkt a
> zum Punkt z zu kommen, was eben meiner gesuchten Folge
> entspricht. Kann mir da jemand helfen?
[mm] P(a)=\bruch{2}{9}+\summe_{k=1}^{\infty}2^{2k}*\left(\bruch{1}{3}\right)^{2k+2}=\bruch{14}{45}
[/mm]
[mm] P(z)=\bruch{1}{3}+\summe_{k=1}^{\infty}2^{2k-1}*\left(\bruch{1}{3}\right)^{2k+1}=\bruch{7}{15}
[/mm]
Die Wahrscheinlichkeiten addieren sich nicht zu 1, da es noch die Möglichkeit gibt, dass weder a noch z jemals wieder erreicht werden. Ich nenne dieses "Ereignis" u.
[mm] P(u)=\bruch{2}{9}
[/mm]
Die Summenbestimmung ist nun nicht so schwierig, weswegen ich die Ergebnisse schonmal mit notiert habe.
Schwieriger ist der Nachweis, dass eben gerade diese Wahrscheinlichkeiten summiert werden sollen. Wieso gibt es nach je zwei Schritten mehr gerade viermal so viele Wege, aber nicht von Anfang an?
Wege mit 6 Schritten, die zu a zurückführen (und vorher weder a noch z "besuchen"), sind folgende:
LLLRRR RRRLLL
LLUORR RRUOLL
LLUROR RRULOL
LLRLRR RRLRLL
LUOLRR RUORLL
LULROR RURLOL
LULORR RUROLL
LUOUOR RUOUOL
..., wobei die Notation Links, Rechts, Oben, Unten bedeutet.
Nun gibt es doppelt so viele Wege mit 7 Schritten, die in z enden. Wie konstruiert man die?
Grüße
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:27 Sa 01.12.2012 | | Autor: | Studi91 |
Hallo!
Erst einmal vielen Dank für deine Antwort.
Ich habe das ganze mal in einem Computerprogramm simulieren lassen und bin bei 7 Schritten auf insgesammt 42 Möglichkeiten gekommen. Hier sind die verschiedenen Möglichkeiten, wobei hier nur die "rechte" Seite von a bzw. z betrachtet ist, für die linke Seite ist ja alles symmetrisch:
(0,1) (1,1) (2,1) (2,0) (1,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (1,0) (1,1) (1,0) (1,1) (1,0) (0,0)
(0,1) (1,1) (2,1) (3,1) (3,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (2,0) (3,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (3,1) (2,1) (1,1) (1,0) (0,0)
(0,1) (1,1) (2,1) (1,1) (1,0) (1,1) (1,0) (0,0)
(0,1) (1,1) (1,0) (2,0) (1,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (2,0) (2,1) (1,1) (1,0) (0,0)
(0,1) (1,1) (2,1) (2,0) (2,1) (2,0) (1,0) (0,0)
(0,1) (1,1) (1,0) (2,0) (2,1) (2,0) (1,0) (0,0)
(0,1) (1,1) (1,0) (2,0) (3,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (1,1) (2,1) (2,0) (1,0) (0,0)
(0,1) (1,1) (1,0) (2,0) (1,0) (1,1) (1,0) (0,0)
(0,1) (1,1) (2,1) (1,1) (2,1) (1,1) (1,0) (0,0)
(0,1) (1,1) (1,0) (2,0) (2,1) (1,1) (1,0) (0,0)
(0,1) (1,1) (2,1) (1,1) (1,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (1,0) (1,1) (2,1) (1,1) (1,0) (0,0)
(0,1) (1,1) (1,0) (1,1) (1,0) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (3,1) (2,1) (2,0) (1,0) (0,0)
(0,1) (1,1) (2,1) (2,0) (1,0) (1,1) (1,0) (0,0)
(0,1) (1,1) (1,0) (1,1) (2,1) (2,0) (1,0) (0,0)
Dabei ist a=(0,1) und z=(0,0).
Habe die Kombinationen auch überprüft und sie stimmen.
Demnach stimmt auch leider dein P(z) nicht.
Hier einmal die anderen Kombinationen auf die ich gekommen bin:
1: 1
3: 2
5: 8
7: 42
9: 254
11: 1670
13: 11596
Für die geraden Schritte mit Endung in a erhalte ich:
2: 2
4: 4
6: 18
8: 102
10: 646
12: 4376
Erkenne da leider keinen Zusammenhang.
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:07 Sa 01.12.2012 | | Autor: | reverend |
Hallo nochmal,
ich sehe gerade, welche Komplikation ich vorhin übersehen habe. Das ist nicht so leicht reparabel... Ich habe auch erst heute Abend wieder Zeit. Mal sehen, ob bis dahin jemand eine vollständige Lösung hat.
Erstaunlicherweise kommen in meinem derzeitigen Ansatz auf einmal Fibonaccizahlen vor.
Ganz kurz: ich fange damit an, L-R Kombinationen zu listen, bis man wieder am gleichen Punkt ist.
LR: 1 Möglichkeit
LLRR: 1 Möglichkeit
LLLRRR, LLRLRR: 2 Möglichkeiten
etc.
(probiers weiter, hier kommen die Fibonaccizahlen, wenn auch nur jede zweite)
Um jetzt eine 6-Schritt-Folge zurück zu a zu finden, können kürzere L-R-Ketten mit U-O-Folgen "durchsetzt" werden.
Also: die 2 reinen L-R-Kombis plus 6 Kombis mit LLRR durchsetzt mit UO (also LUOLRR, LLUORR, LLRUOR, LULORR, LULROR, LLUROR) plus 1 LR mit UOUO (alos LUOUOR), macht 9.
Hier sind gerade nur die linksseitigen Schrittfolgen berücksichtigt, natürlich verdoppelt sich die Zahl durch die Folgen, die mit einem Rechtsschritt beginnen.
Das ist aber auch noch nicht so leicht zusammenzufassen.
Mehr also vielleicht später.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Mi 05.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](https://dl.dropbox.com/u/61662712/leiter.jpg){kind=small}
(Skizze)
