Erwartete Anzahl Schritte berechnen
-
Angenommen ich habe n Felder die nebeneinander aufgereiht sind. Ich stehe ganz links auf dem Feld. Mit einer wahrscheinlichkeit von 0.5 wechsle ich auf das linke und mit wahrscheinlichkeit 0.5 auf das rechte Feld (Wenn ich ganz links stehe wechsle ich immer nach rechts). Was ist die erwartete/durchschnittliche Anzahl an Schritten die ich benötige um von links nach rechts zu kommen?
-
Jetzt mal ganz dumm gefragt... aber wenn die wahrscheinlichkeit für beide seiten gleich ist, ist doch der erwartungswert nach unendlich schritten da wo du angefangen hast...
Naja. Aber wenn du n Schritte nach rechts gehen willst, ist die Wahrscheinlichkeit dafür 0.5^n (also alle hinternander)
-
Maxi schrieb:
Jetzt mal ganz dumm gefragt... aber wenn die wahrscheinlichkeit für beide seiten gleich ist, ist doch der erwartungswert nach unendlich schritten da wo du angefangen hast...
richtig.
Maxi schrieb:
Naja. Aber wenn du n Schritte nach rechts gehen willst, ist die Wahrscheinlichkeit dafür 0.5^n (also alle hinternander)
wenn ich n Schritte mache bin ich mit einer Wahrscheinlichkeit von 0.5^n auf dem letzten Feld, das ist auch richtig.
Danach hab ich aber nicht gefragt
Mich interessiert die durchschnittliche Anzahl von Schritten die benötigt werden um von links nach rechts zu kommen. Sowas wie in 95% der Fälle werden mehr als x Schritte benötigt wäre auch ok.
-
Eigentlich wäre es ziemlich einfach, wenn man über die Endfelder rauslaufen dürfte, dann wäre der Erwartungswert im wesentlichen eine Summe über eine Binominalverteilung*Weglänge, was, aus dem Bauch raus, auch konvergieren sollte. Aber das darf man ja nicht, man muß noch irgendwie die Randbedingungen verwurschteln.
Eigentlich haben wir so nur ein kombinatorisches Problem: wie viele verschiedene Pfade der Länge m (m>=n, bzw sogar: m_0=n, m_1=n+2, m_2=n+4, da man falsch gelaufene Felder ja wieder zurücklaufen muß) gibt es auf dem n Felder langen Spielfeld. Jemand Lust?
-
Daniel E. schrieb:
Eigentlich wäre es ziemlich einfach, wenn man über die Endfelder rauslaufen dürfte, dann wäre der Erwartungswert im wesentlichen eine Summe über eine Binominalverteilung*Weglänge, was, aus dem Bauch raus, auch konvergieren sollte. Aber das darf man ja nicht, man muß noch irgendwie die Randbedingungen verwurschteln.
Die Wahrscheinlichkeit das ich irgendwann mal im n-ten Feld ankomme ist 1, ja.
Daniel E. schrieb:
Eigentlich haben wir so nur ein kombinatorisches Problem: wie viele verschiedene Pfade der Länge m (m>=n, bzw sogar: m_0=n, m_1=n+2, m_2=n+4, da man falsch gelaufene Felder ja wieder zurücklaufen muß) gibt es auf dem n Felder langen Spielfeld. Jemand Lust?
naja, Unendlich viele natürlich. Ich kann ja am Anfang bel. oft zwischen Feld 1 und 2 hin und her gehen und dann aufs Ziel zu. Mit dieser Art Von Weg hab ich ja schon Unendlich viele.
Wahrscheinlich kann man aus dem Grund auch nich einen echten Durchschnittswert bestimmen. Aber sowas wie "In x% der Fälle werden mehr als m Schritte benötigt" geht auf jedenfall.
-
borg schrieb:
Daniel E. schrieb:
Eigentlich wäre es ziemlich einfach, wenn man über die Endfelder rauslaufen dürfte, dann wäre der Erwartungswert im wesentlichen eine Summe über eine Binominalverteilung*Weglänge, was, aus dem Bauch raus, auch konvergieren sollte. Aber das darf man ja nicht, man muß noch irgendwie die Randbedingungen verwurschteln.
Die Wahrscheinlichkeit das ich irgendwann mal im n-ten Feld ankomme ist 1, ja.
Das kommt auf "irgendwann". Daß der Grenzwert für t->oo 1 wird, ist richtig. Richtig ist aber auch, daß es kein t0 gibt, für das das Zielfeld erreicht worden sein muß (außer das Spielbrett besteht genau aus zwei Steinen). Ob es so ein "irgendwann" gibt, ist also diskutierbar, je nach Definition.
Daniel E. schrieb:
Eigentlich haben wir so nur ein kombinatorisches Problem: wie viele verschiedene Pfade der Länge m (m>=n, bzw sogar: m_0=n, m_1=n+2, m_2=n+4, da man falsch gelaufene Felder ja wieder zurücklaufen muß) gibt es auf dem n Felder langen Spielfeld. Jemand Lust?
naja, Unendlich viele natürlich.
Nein. Es gibt zB nur einen Pfad der Länge n, der zum Ziel führt. Daß es insgesamt unendlich viele Pfade gibt, bezweifelt niemand (die sind im Zweifelsfall beliebig lang und damit beliebig uninteressant), aber interessant ist, wie viele verschiedene Pfade der festen(!) Länge m es gibt, die zum Ziel führen und das ist ein ganz anderes, kombinatorisches Problem.
BTW: In 100% der Fälle werden mehr als n-1 Schritte benötigt.
-
Daniel E. schrieb:
Daniel E. schrieb:
Eigentlich haben wir so nur ein kombinatorisches Problem: wie viele verschiedene Pfade der Länge m (m>=n, bzw sogar: m_0=n, m_1=n+2, m_2=n+4, da man falsch gelaufene Felder ja wieder zurücklaufen muß) gibt es auf dem n Felder langen Spielfeld. Jemand Lust?
naja, Unendlich viele natürlich.
Nein. Es gibt zB nur einen Pfad der Länge n, der zum Ziel führt. Daß es insgesamt unendlich viele Pfade gibt, bezweifelt niemand (die sind im Zweifelsfall beliebig lang und damit beliebig uninteressant), aber interessant ist, wie viele verschiedene Pfade der festen(!) Länge m es gibt, die zum Ziel führen und das ist ein ganz anderes, kombinatorisches Problem.
BTW: In 100% der Fälle werden mehr als n-1 Schritte benötigt.
oh, ja. Ich hab das was du geschrieben hast falsch Interpretiert.
-
hm, das klingt nach nem Problem, das bestimmt schonmal jemand betrachtet hat. "random walk" ist ein guter suchbegriff. und markov-ketten auch. keine ahnung ob's was hilft.
-
http://de.wikipedia.org/wiki/Zufallsbewegung schrieb:
Oft interessiert man sich speziell für den ungerichteten Random Walk mit p=q=1/2. Dann ist die Wahrscheinlichkeitsverteilung der zurückgelegten Strecke symmetrisch um X=0, und auch der Erwartungswert ist E(X)=0. Das Vorankommen des Fußgängers kann man dann nur durch den mittleren quadratischen Abstand vom Ausgangspunkt, also die Varianz der Binomialverteilung beschreiben: E(X^2) = n. Das ist ein nichttriviales Ergebnis, mit dem eine charakteristische Eigenschaft von Diffusionsprozessen und Brownscher Molekularbewegung wiedergefunden wird: das mittlere Quadrat des Abstands eines diffundierenden Teilchens von seinem Ausgangsort wächst proportional zur Zeit.
uuuhm.. bedeutet dass, die Anzahl der durchschnittlich benötigten Schritte wächst quadratisch mit n?
edit: Ja, das heißt es (In der englischen Wikipedia stehts genauer).
OK, das ist erheblich besser als ich vermutet hätte.