Erwartungswert für zufällig hüpfenden Floh



  • Ein Floh sitzt auf einem regulären Polygon mit n Ecken nummeriert von 0 bis n-1. Jede Sekunde hüpft er entweder von Position i auf (i+1)mod n oder (i-1)mod n. Wie lange braucht er im Erwartungswert, um von der Ecke 0 bis zur Ecke x zu gelangen?

    Es sieht so aus, als ob die Lösung (n-x)*x wäre, aber wieso?



  • Die Idee die ich habe, lautet wie folgt:
    Die Anzahl der Sprünge zum Punkt hin modulo n minus die Anzahl der Sprünge entgegengesetzter Richtung modulo muss genau x sein.

    Nehmen wir eine feste Sprungzahl xt<nx \leq t < n an, wobei x und t dieselbe Parität haben müssen damit die Wahrscheinlichkeit ungleich 0 ist - wie hoch ist die Wahrscheinlichkeit, auf x zu kommen?
    In anderen Worten, wieviele von den 2t2^t möglichen Sprung-Kombinationen führen zu x?

    Die Antwort ist (ttx2)\binom {t}{\frac{t - x}{2}}. Die durchschnittliche Anzahl der benötigten Schritte ist dann das Maximum der Wahrscheinlichkeit (also der Binominalkoeffizient geteilt durch t).
    Edit: Hmm, nein, letzteres stimmt so nicht, oder?



  • Arcoth schrieb:

    In anderen Worten, wieviele von den 2t2^t möglichen Sprung-Kombinationen führen zu x?

    Du musst berücksichtigen, sobald der Floh angekommen ist, ist er da. Das heisst die Kombination "0...x,x+1,x" gibt es nicht.

    Arcoth schrieb:

    Die durchschnittliche Anzahl der benötigten Schritte ist dann das Maximum der Wahrscheinlichkeit (also der Binominalkoeffizient geteilt durch t).

    Der Erwartungswert ist die (unendliche) Summe aller Sprungkombinationen mal der jeweiligen Wahrscheinlichkeit.



  • Hi,

    das ist eine Markow-Kette und entspricht dem Beispiel der eindimensionalen zufälligen Irrfahrt.

    Siehe
    https://de.wikipedia.org/wiki/Markow-Kette
    und
    https://de.wikipedia.org/wiki/Zufallsbewegung



  • herrfloh schrieb:

    Arcoth schrieb:

    In anderen Worten, wieviele von den 2t2^t möglichen Sprung-Kombinationen führen zu x?

    Du musst berücksichtigen, sobald der Floh angekommen ist, ist er da. Das heisst die Kombination "0...x,x+1,x" gibt es nicht.

    Stimmt! Das habe ich nicht berücksichtigt.

    herrfloh schrieb:

    Der Erwartungswert ist die (unendliche) Summe aller Sprungkombinationen mal der jeweiligen Wahrscheinlichkeit.

    Danke, das wusste ich nicht.

    @µ: Da hol mich der Teufel. Jetzt erinnere ich mich haargenau, dass ich Markow-Ketten in der Schule durchgenommen habe, zusammen mit Übergangsmatrizen.



  • Arcoth schrieb:

    @µ: Da hol mich der Teufel. Jetzt erinnere ich mich haargenau, dass ich Markow-Ketten in der Schule durchgenommen habe, zusammen mit Übergangsmatrizen.

    In welcher Schule nimmt man bitteschön Markow-Ketten und irgendwelche Matrizen durch? 😮

    Bist Du nicht Österreicher? Ich glaube wir sollten in Deutschland mal das Niveau der Oberstufe anheben.



  • Nein, ich komme aus Hamburg. Und nein, ich bin nicht Pi. 😉

    Das haben wir im zweiten Semester der Oberstufe durchgenommen, Mathe Leistungskurs.



  • Also ich habe es bewiesen, aber der Beweis ist relativ umständlich und es leuchtet nicht ein, wieso das Resultat so schön ist.

    Der Beweis:
    Sei pi die erwartete Anzahl Schritte, von (i mod n) nach x zu gelangen (in beide Richtungen). Es gelten die folgenden Gleichungen:

    p\_i=\frac 12(p\_{i-1}+p_{i+1})+1 \,\forall i\neq x\\ p_{x-i}=p_{x+i}\\ p_x=0

    Wir erhalten eine Rekursionsgleichung (p_i=p_i+xp\_i'=p\_{i+x}):

    p'_0=0\\ p'_1=a\\ p'_{j+1}=2p\_j'-p\_{j-1}'-2

    Vermutung: pi=ia(i1)ip_i' = i\cdot a-(i-1)\cdot i. Beweis durch Induktion.
    Wegen Symmetrie gilt pn1=p1=ap'_{n-1}=p'_1=a woraus folgt (n1)a(n1)(n2)=aa=n1(n-1)a-(n-1)(n-2)=a \Leftrightarrow a=n-1

    Damit erhalten wir p_0=p_x=x(n1)x(x1)=x(nx)p\_0=p'\_x=x\cdot (n-1)-x(x-1)=x(n-x)

    Kann mir jemand zeigen, wie man das elegant mit den Markov-Ketten machen würde? Und was ist die intuitive Erklärung für x*(n-x)?



  • Arcoth schrieb:

    Nein, ich komme aus Hamburg. Und nein, ich bin nicht Pi. 😉

    Das haben wir im zweiten Semester der Oberstufe durchgenommen, Mathe Leistungskurs.

    Darf man fragen, an welcher Schule und in welchem Semester du im Moment bist?



  • Arcoth schrieb:

    Jetzt erinnere ich mich [...], dass ich Markow-Ketten in der Schule durchgenommen habe, zusammen mit Übergangsmatrizen.

    Na, viel hat es ja nicht gebracht.



  • unqualified inspector schrieb:

    Arcoth schrieb:

    Jetzt erinnere ich mich [...], dass ich Markow-Ketten in der Schule durchgenommen habe, zusammen mit Übergangsmatrizen.

    Na, viel hat es ja nicht gebracht.

    Die Erinnerungen kommen zurück: Wir haben sie gar nicht richtig durchgenommen, diese Markov-Ketten. Übergangsmatrizen schon eher. Mein Büchlein war der Lambacher Schweizer.

    Ist aber auch schon ein Jahr her, ich erinnere mich nur bröckelig.



  • Arcoth schrieb:

    Da hol mich der Teufel. Jetzt erinnere ich mich haargenau, dass ich Markow-Ketten in der Schule durchgenommen habe, zusammen mit Übergangsmatrizen.

    Arcoth schrieb:

    Die Erinnerungen kommen zurück: Wir haben sie gar nicht richtig durchgenommen, diese Markov-Ketten. (...)

    Ist aber auch schon ein Jahr her, ich erinnere mich nur bröckelig.

    Soviel zur Glaubwürdigkeit des Herrn Arcoth aka Sone aka Hacker aka Pi's Erzfeind.



  • Nein, ich erinnere mich haargenau dass wir sie durchgenommen haben.

    Nicht daran, wie, wie lange oder wie intensiv. Je weiter ich mich erinnere, kommt es mir vor, als hätten wir sie nur nebenbei angeschaut und uns nicht tiefer damit beschäftigt.

    Unterschied festgestellt? Gut!



  • OK, nochmal für den Doofen:

    Arcoth schrieb:

    Jetzt erinnere ich mich haargenau, dass ich Markow-Ketten in der Schule durchgenommen habe

    Arcoth schrieb:

    Wir haben sie gar nicht richtig durchgenommen, diese Markov-Ketten.

    Fällt dir der Widerspruch auf? Nein? Wieso wundert mich das nicht...



  • Man kann Dinge flüchtig bzw. nicht richtig durchnehmen. Sie sind dann trotzdem durchgenommen. Da existiert kein Widerspruch. Wenn ich mich daran erinnere, dass wir in der Schule zu diesem Stichwort einige Aufgabenblätter hatten (und ein Buchkapitel), dann haben wir Markow-Ketten durchgenommen.

    Gib einfach zu, dass du im Unrecht bist, es ist doch offensichtlich.

    P.S.: Du willst doch hier niemandem weiss machen, dass ich doofer bin als du? lol?



  • Bitte nicht meinen Thread zuspammen, ich will das gelöst haben!



  • Arcoth schrieb:

    P.S.: Du willst doch hier niemandem weiss machen, dass ich doofer bin als du? lol?

    Wozu? scnr


Log in to reply