www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Wege in leiterartigem Gitter
Wege in leiterartigem Gitter < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Wege in leiterartigem Gitter: Idee
Status: (Frage) beantwortet Status 
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 [](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

        
Bezug
Wege in leiterartigem Gitter: Antwort
Status: (Antwort) fertig Status 
Datum: 10:39 Sa 01.12.2012
Autor: reverend

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]
Bezug
                
Bezug
Wege in leiterartigem Gitter: Frage (überfällig)
Status: (Frage) überfällig Status 
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

Bezug
                        
Bezug
Wege in leiterartigem Gitter: hast Recht
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
Wege in leiterartigem Gitter: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:20 Mi 05.12.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de