Random Walk & Urnenmodell < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei [mm] S_{n} [/mm] ein d-dimensionaler Random Walk und [mm] {R^{1}}_{n}, [/mm] .. , [mm] {R^{d}}_{n} [/mm] die Anzahl der Schritte in jede der d Komponenten. Zeige, dass für alle n > 0 die Wahrscheinlichkeit, dass [mm] {R^{1}}_{2n}, [/mm] .. , [mm] {R^{d}}_{2n} [/mm] alle gerade sind, [mm] 2^{-(d-1)} [/mm] ist. |
Hallo zusammen,
ich sitze seid einiger Zeit an obiger Aufgabe und mein Ansatz sieht bis jetzt wie folgt aus:
Ich möchte die Aufgabe gerne durch ein Urnenmodell formulieren. Wir verteilen 2n Kugel auf d Urnen und möchten die Wahrscheinlichkeit bestimmen, dass in jeder Urne eine gerade Anzahl an Kugeln liegt.
Die Kugel sind dabei ununterscheidbar (es ist ja egal, wann wir in welche Richtung gehen) und die Urnen sind auch ununterscheidbar (wir müssen ja nicht wissen, wie viele Schritte in eine bestimmte Richtung gegangen wird).
Als erstes kam mir jetzt die Multinomialverteilung in den Sinn, allerdings braucht man dafür ja nummerierte Kugeln und nummerierte Gruppen, was allerdings hier nicht der Fall ist.
Ich würde mich freuen, wenn jemand die Richtigkeit meines Ansatzes bestätigen kann und mir Tipps zur weiteren Lösung geben kann oder vielleicht einen alternativen Ansatz vorschlägt.
Vielen Dank schonmal
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Sei [mm]S_{n}[/mm] ein d-dimensionaler Random Walk und [mm]{R^{1}}_{n},[/mm]
> .. , [mm]{R^{d}}_{n}[/mm] die Anzahl der Schritte in jede der d
> Komponenten. Zeige, dass für alle n > 0 die
> Wahrscheinlichkeit, dass [mm]{R^{1}}_{2n},[/mm] .. , [mm]{R^{d}}_{2n}[/mm]
> alle gerade sind, [mm]2^{-(d-1)}[/mm] ist.
> Hallo zusammen,
>
> ich sitze seid einiger Zeit an obiger Aufgabe und mein
> Ansatz sieht bis jetzt wie folgt aus:
>
> Ich möchte die Aufgabe gerne durch ein Urnenmodell
> formulieren. Wir verteilen 2n Kugel auf d Urnen und
> möchten die Wahrscheinlichkeit bestimmen, dass in jeder
> Urne eine gerade Anzahl an Kugeln liegt.
>
> Die Kugel sind dabei ununterscheidbar (es ist ja egal, wann
> wir in welche Richtung gehen) und die Urnen sind auch
> ununterscheidbar (wir müssen ja nicht wissen, wie viele
> Schritte in eine bestimmte Richtung gegangen wird).
>
> Als erstes kam mir jetzt die Multinomialverteilung in den
> Sinn, allerdings braucht man dafür ja nummerierte Kugeln
> und nummerierte Gruppen, was allerdings hier nicht der Fall
> ist.
>
> Ich würde mich freuen, wenn jemand die Richtigkeit meines
> Ansatzes bestätigen kann und mir Tipps zur weiteren
> Lösung geben kann oder vielleicht einen alternativen
> Ansatz vorschlägt.
>
> Vielen Dank schonmal
Hallo cassini90
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
ich denke, dass du zuerst klar angeben solltest, was hier
unter einem d-dimensionalen Random Walk genau zu
verstehen ist. Welche Schritte in jeder der d Dimensionen
sind bei jedem Schritt möglich, und mit welcher Wahr-
scheinlichkeitsverteilung ?
(wären z.B. nur geradzahlige Schrittlängen zugelassen,
so hätte man stets nur geradzahlige Koordinaten bzw.
Kugelanzahlen)
Ob du dann in einem allfälligen Urnenmodell mit
nummerierten oder mit unnummerierten Kugeln
arbeitest, ist wohl einerlei.
Beschreibe also bitte die Funktionsweise des
Random Walks und die Umsetzung in ein Urnen-
modell genauer !
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:41 Mo 18.03.2013 | | Autor: | cassini90 |
Hallo Al-Chwarizmi,
vielen Dank für deine Antwort.
Bei dem Random Walk handelt es sich um eine symmterischen Random Walk auf [mm] \IZ^{d}, [/mm] d.h. in jedem Schritt besitzt jede Richtung die Wahrscheinlichkeit [mm] \bruch{1}{d}. [/mm]
Dabei ist [mm] S_{2n} [/mm] = [mm] \summe_{i=1}^{2n} X_{i} [/mm] die Position nach 2n Schritten und [mm] X_{i} \in \IZ^{d} [/mm] kann Werte der d-dimensionalen Einheitsvektoren annehmen
> Ob du dann in einem allfälligen Urnenmodell mit
> nummerierten oder mit unnummerierten Kugeln
> arbeitest, ist wohl einerlei.
Was du damit meinst ist mir leider noch nicht klar.
LG cassini90
|
|
|
| |
|
Hallo,
Für den Fall, dass der Random-Walk in jedem Schritt nur in eine der d Richtungen gehen darf:
ich glaube, dass das mit der Multinomialverteilung funktionieren könnte. Die nummeriert ja nicht die Schritte, sondern nur die Richtungen!
Ich würde von der Verteilung:
[mm] $p(n_1,...,n_d) [/mm] = [mm] \begin{pmatrix}2n\\n_1\end{pmatrix}\cdot \begin{pmatrix}2n-n_1\\n_2\end{pmatrix}\cdot [/mm] ... [mm] \cdot \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\n_d\end{pmatrix}* \left(\frac{1}{2}\right)^{n_1} \cdot [/mm] ... [mm] \cdot \left(\frac{1}{2}\right)^{n_d}$
[/mm]
ausgehen und jetzt über alle Möglichkeiten summieren, d.h. alle Tupel [mm] $(n_1,...,n_d)$ [/mm] mit [mm] $n_1 [/mm] + ... + [mm] n_d [/mm] = 2n$ und [mm] $n_i$ [/mm] gerade ($i = 1,...,d$).
Dabei natürlich mit der Summation über [mm] $n_d$ [/mm] (von 0 bis $2n - [mm] n_1 [/mm] - ... - [mm] n_{d-1}$) [/mm] anfangen. Ich bin mir ziemlich sicher, dass du folgendes ausnutzen kannst:
[mm] $\sum_{k=0}^{N}\begin{pmatrix}N\\k\end{pmatrix} [/mm] = [mm] 2^{N}$, [/mm] wenn n gerade gilt evtl. wegen [mm] $\begin{pmatrix}N\\k\end{pmatrix} [/mm] = [mm] \begin{pmatrix}N\\N-k\end{pmatrix}$
[/mm]
[mm] $\sum_{k=0, \mbox{k gerade}}^{N}\begin{pmatrix}N\\k\end{pmatrix} [/mm] = [mm] 2^{N-1}$.
[/mm]
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:02 Mo 18.03.2013 | | Autor: | cassini90 |
Hallo Stefan,
vielen Dank für deine Antwort.
> Für den Fall, dass der Random-Walk in jedem Schritt nur in
> eine der d Richtungen gehen darf:
Ja das ist der Fall. Ich habe gerade genauere Angaben ergänzt.
>
> ich glaube, dass das mit der Multinomialverteilung
> funktionieren könnte. Die nummeriert ja nicht die
> Schritte, sondern nur die Richtungen!
>
> Ich würde von der Verteilung:
>
> [mm]p(n_1,...,n_d) = \begin{pmatrix}2n\\n_1\end{pmatrix}\cdot \begin{pmatrix}2n-n_1\\n_2\end{pmatrix}\cdot ... \cdot \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\n_d\end{pmatrix}* \left(\frac{1}{2}\right)^{n_1} \cdot ... \cdot \left(\frac{1}{2}\right)^{n_d}[/mm]
> ausgehen und jetzt über alle Möglichkeiten summieren,
> d.h. alle Tupel [mm](n_1,...,n_d)[/mm] mit [mm]n_1 + ... + n_d = 2n[/mm] und
> [mm]n_i[/mm] gerade ([mm]i = 1,...,d[/mm]).
Das verstehe ich soweit, aber woher kommt: [mm] \left(\frac{1}{2}\right)^{n_1} \cdot [/mm] ... [mm] \cdot \left(\frac{1}{2}\right)^{n_d}
[/mm]
Müsste dort nicht [mm] \left(\frac{1}{d}\right)^{n_1} \cdot [/mm] ... [mm] \cdot \left(\frac{1}{d}\right)^{n_d} [/mm] stehen, wenn wir als Wahrscheinlichkeit für eine Richtung [mm] \frac{1}{d} [/mm] haben?
>
> Dabei natürlich mit der Summation über [mm]n_d[/mm] (von 0 bis [mm]2n - n_1 - ... - n_{d-1}[/mm])
> anfangen. Ich bin mir ziemlich sicher, dass du folgendes
> ausnutzen kannst:
>
> [mm]\sum_{k=0}^{N}\begin{pmatrix}N\\k\end{pmatrix} = 2^{N}[/mm],
> wenn n gerade gilt evtl. wegen
> [mm]\begin{pmatrix}N\\k\end{pmatrix} = \begin{pmatrix}N\\N-k\end{pmatrix}[/mm]
>
> [mm]\sum_{k=0, \mbox{k gerade}}^{N}\begin{pmatrix}N\\k\end{pmatrix} = 2^{N-1}[/mm].
>
> Viele Grüße,
> Stefan
Also meinst du folgendes:
[mm] \sum_{n_{d}=0}^{2n - n_1 - ... - n_{d-1}} [/mm] ... [mm] \sum_{n_{2}=0}^{2n - n_1} \sum_{n_{1}=0}^{2n} \begin{pmatrix}2n\\n_1\end{pmatrix}\cdot \begin{pmatrix}2n-n_1\\n_2\end{pmatrix}\cdot [/mm] ... [mm] \cdot \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\n_d\end{pmatrix}
[/mm]
Und das noch mal der korrekten Wahrscheinlichkeit oder?
LG cassini90
|
|
|
| |
|
Hallo,
> Das verstehe ich soweit, aber woher kommt:
> [mm]\left(\frac{1}{2}\right)^{n_1} \cdot[/mm] ... [mm]\cdot \left(\frac{1}{2}\right)^{n_d}[/mm]
>
> Müsste dort nicht [mm]\left(\frac{1}{d}\right)^{n_1} \cdot[/mm]
> ... [mm]\cdot \left(\frac{1}{d}\right)^{n_d}[/mm] stehen, wenn wir
> als Wahrscheinlichkeit für eine Richtung [mm]\frac{1}{d}[/mm]
> haben?
Ja, da hast du recht.
Da habe ich nicht mitgedacht  Wollte nur schnell meinen Ansatz loswerden, weil ich nicht so viel Zeit hatte.
> Also meinst du folgendes:
>
> [mm]\sum_{n_{d}=0}^{2n - n_1 - ... - n_{d-1}}[/mm] ...
> [mm]\sum_{n_{2}=0}^{2n - n_1} \sum_{n_{1}=0}^{2n} \begin{pmatrix}2n\\
n_1\end{pmatrix}\cdot \begin{pmatrix}2n-n_1\\
n_2\end{pmatrix}\cdot[/mm]
> ... [mm]\cdot \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\
n_d\end{pmatrix}[/mm]
So in etwa. Allerdings müssen die Summen andersrum laufen (also erst [mm] n_1, [/mm] ...), du sollst die Summen eben nur von innen nach außen auswerten. Beachte, dass die Summation nur über gerade Zahlen läuft, das steht bei dir noch nicht.
Ich bin mir auch nicht sicher, ob der Ansatz funktioniert, aber du kannst es ja mal ausprobieren.
> Und das noch mal der korrekten Wahrscheinlichkeit oder?
Ja.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:38 Mo 18.03.2013 | | Autor: | cassini90 |
> > Also meinst du folgendes:
> >
> > [mm]\sum_{n_{d}=0}^{2n - n_1 - ... - n_{d-1}}[/mm] ...
> > [mm]\sum_{n_{2}=0}^{2n - n_1} \sum_{n_{1}=0}^{2n} \begin{pmatrix}2n\\
n_1\end{pmatrix}\cdot \begin{pmatrix}2n-n_1\\
n_2\end{pmatrix}\cdot[/mm]
> > ... [mm]\cdot \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\
n_d\end{pmatrix}[/mm]
>
> So in etwa. Allerdings müssen die Summen andersrum laufen
> (also erst [mm]n_1,[/mm] ...), du sollst die Summen eben nur von
> innen nach außen auswerten. Beachte, dass die Summation
> nur über gerade Zahlen läuft, das steht bei dir noch
> nicht.
Alles klar. Vielen Dank.
> Ich bin mir auch nicht sicher, ob der Ansatz funktioniert,
> aber du kannst es ja mal ausprobieren.
Ich werde es versuchen.
|
|
|
| |
|
Irgendwie habe ich noch Probleme die Summen auszuwerten.
Also alle [mm] n_{i} [/mm] sind gerade. Dann folgt mit [mm] \sum_{k=0, \mbox{k gerade}}^{N}\begin{pmatrix}N\\k\end{pmatrix} [/mm] = [mm] 2^{N-1}:
[/mm]
[mm] \sum_{n_{1}=0}^{2n} \sum_{n_{2}=0}^{2n - n_1} \cdot [/mm] ... [mm] \cdot \sum_{n_{d-1}=0}^{2n - n_1 - ... - n_{d-2}}\sum_{n_{d}=0}^{2n - n_1 - ... - n_{d-1}} \begin{pmatrix}2n - n_1 - ... - n_{d-1}\\
n_d\end{pmatrix}\begin{pmatrix}2n - n_1 - ... - n_{d-2}\\
n_{d-1}\end{pmatrix} \cdot [/mm] ... [mm] \cdot \begin{pmatrix}2n-n_1\\
n_2\end{pmatrix} \begin{pmatrix}2n\\
n_1\end{pmatrix} \left(\frac{1}{d}\right)^{n_1} \cdot [/mm] ... [mm] \cdot \left(\frac{1}{d}\right)^{n_d} \\ \\ [/mm] = [mm] \sum_{n_{1}=0}^{2n} \sum_{n_{2}=0}^{2n - n_1} \cdot [/mm] ... [mm] \cdot \sum_{n_{d-1}=0}^{2n - n_1 - ... - n_{d-2}} 2^{2n - n_1 - ... - n_{d-1}-1} \begin{pmatrix}2n - n_1 - ... - n_{d-2}\\
n_{d-1}\end{pmatrix} \cdot [/mm] ... [mm] \cdot \begin{pmatrix}2n-n_1\\
n_2\end{pmatrix} \begin{pmatrix}2n\\
n_1\end{pmatrix} d^{-2n}
[/mm]
Jetzt habe ich im Inneren aber ein [mm] n_{d-1} [/mm] im Binomialkoeffizent und im Expoent der 2 und ich weiß nicht genau wie ich das weiterverarbeiten soll?
|
|
|
| |
|
Hallo,
folgender Vorschlag für dich, wenn du noch interessiert bist: Entweder gibt es zu der Aufgabe eine "schlaue" kurze Lösung, oder man muss es vermutlich so durchrechnen wie du es jetzt machst.
Zum Auflösen der Summen würde ich folgende Formel benutzen:
[mm] $\sum_{k=0}^{N}\vektor{2N\\2k}\cdot a^{2(N-k)} [/mm] = [mm] \frac{1}{2}\cdot \Big((a+1)^{2n}+(a-1)^{2n}\Big)$
[/mm]
Warum das gilt? Keine Ahnungm spuckt WolframAlpha aus.
Bevor du das bei der riesigen Summe anwendest, probiere es doch erstmal in den Fällen d = 2 oder d = 3.
Bei d = 2 hab ich's durchprobiert und es geht, bei d = 3 bekomme ich aber scheinbar einen zusätzlichen Summanden der das Ergebnis kaputt macht - vielleicht habe ich mich auch verrechnet...
Daher würde ich raten, dass du im Falle d = 3 vielleicht mal 2n = 4 annimmst oder so und mal wirklich die Möglichkeiten mit Wahrscheinlichkeiten aufschreibst und so überprüfst, ob wirklich [mm] 2^{-(d-1)} [/mm] für die gesuchte Wahrscheinlichkeit rauskommt. Dann würde ich mir die Wahrscheinlichkeit bei der Multinomialverteilung anschauen und gucken, ob irgendwas schiefläuft.
Viele Grüße,
Stefan
|
|
|
|
