drunken man in New York

14.02.2011, 20:00

Dopap

drunken man in New York

Hallo zusammen!
bin in den letzten 30 Jahren ( ABI ´70 ! )ein wenig eingerostet. Die folgende Aufgabe ist mir aber noch in Erinnerung, aber nicht gelöst:
Im quadratischen schachbrettartigen Straßenmeer von New York verläßt ein Betrunkener seine Eckkneipe und beschliesst, ab sofort die 4 jeweils möglichen Wege an jeder Kreuzung als Laplace Versuch zur nächsten Blockkreuzung zu wählen.
Welchen Erwartungswert hat seine Luftlinienentfernung zur Kneipe nach n Versuchen, wenn die Blocklänge a ist ?
Idee:
Sei die Kneipe im Ursprung eines X-Y Koordinatensystems.
Dann der Reihe nach die Wahrscheinlichkeitsfunktionen W(1), W(2) ...( Tabellen) bestimmen, wobei aus Symmetriegründen der momentante Ort im ersten Quadranten
belassen werden kann ( nach entsprechenden Spiegelungen). Die Erwartungswerte E(1), E(2) ... sind dann kein Problem. Das funktioniert so einigermaßen bis n=5. Aber nicht allgemein.
Idee: Annahme , dass eine unabhängige Überlagerungen von 2 BinomialWahrscheinlichkeitsfunktionen
BIN(n;1/2;x) in X- und in Y-Richtung vorliegt...
Ist die Aufgabe ist unmissverständlich und eineindeutig formuliert?

14.02.2011, 20:29

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Idee: Annahme , dass eine unabhängige Überlagerungen von 2 BinomialWahrscheinlichkeitsfunktionen BIN(n;1/2;x) in X- und in Y-Richtung vorliegt...

Hmm, ich würde allenfalls sagen bedingt unabhängig. Im einzelnen:

Das ganze passiert ja wohl zweistufig:

Sei $\begin{eqnarray*} H \end{eqnarray*}$ die zufällige Anzahl der horizontalen Schritte (also in X-Richtung) bei insgesamt $\begin{eqnarray*} n \end{eqnarray*}$ Schritten. Dann ist $\begin{eqnarray*} H\sim B\left(n, \frac{1}{2} \right) \end{eqnarray*}$ , also $\begin{eqnarray*} P(H=h) = \binom{n}{h}2^{-n} \end{eqnarray*}$ .

Gehen nun von den $\begin{eqnarray*} h \end{eqnarray*}$ horizontalen Schritten genau $\begin{eqnarray*} k \end{eqnarray*}$ in positive X-Richtung, und parallel dazu von den $\begin{eqnarray*} n-h \end{eqnarray*}$ vertikalen Schritten genau $\begin{eqnarray*} l \end{eqnarray*}$ in positive $\begin{eqnarray*} Y \end{eqnarray*}$ -Richtung, dann folgt für die Position $\begin{eqnarray*} (X,Y) \end{eqnarray*}$ nach $\begin{eqnarray*} n \end{eqnarray*}$ Schritten:

$\begin{eqnarray*} P(X=(2k-h)a,Y=(2l-n+h)a \bigm| H=h) &=& P(X=(2k-h)a \bigm| H=h)\cdot P(Y=(2l-n+h)a \bigm| H=h)\\ &=& \begin{cases} \binom{h}{k}2^{-h} \cdot \binom{n-h}{l}2^{-n+h} = \binom{h}{k}\binom{n-h}{l}2^{-n} & \textrm{für $0\leq k\leq h$ und $0\leq l\leq n-h$} \\ 0 & \textrm{sonst} \end{cases} \end{eqnarray*}$

Weiterhin ergibt sich für beliebige ganze Zahlen $\begin{eqnarray*} r,s \end{eqnarray*}$ gemäß Formel der totalen Wkt

$\begin{eqnarray*} P(X=ra,Y=sa) = \sum_{h=0}^n P(H=h)\cdot P(X=ra,Y=sa \bigm| H=h) = 2^{-n} \cdot \sum_{h=0}^n \binom{n}{h}\cdot P(X=ra,Y=sa \bigm| H=h) \end{eqnarray*}$ .

Irgendwelche Erwartungswerte von Funktionalen $\begin{eqnarray*} g(X,Y) \end{eqnarray*}$ berechnen sich dann natürlich als

$\begin{eqnarray*} E(g(X,Y)) = \sum_{r,s\in\mathbb{Z}} g(ra,sa)\cdot P(X=ra,Y=sa) \end{eqnarray*}$

also etwa bei der "mittleren Entfernung" mit $\begin{eqnarray*} g(X,Y) = \sqrt{X^2+Y^2} \end{eqnarray*}$ .

Alles gut verrührt ergibt sich für diesen Erwartungswert eine Dreifachsumme, die man also mit Aufwand $\begin{eqnarray*} O(n^3) \end{eqnarray*}$ numerisch auswerten kann - eine theoretische Vereinfachung wird zumindest bei deiner euklidischen Distanzfunktion $\begin{eqnarray*} g \end{eqnarray*}$ kaum drin sein:

$\begin{eqnarray*} E(g(X,Y)) = 2^{-2n} \cdot \sum_{h=0}^n \binom{n}{h} \sum_{k=0}^h \binom{h}{k} \sum_{l=0}^{n-h} \binom{n-h}{l} g((2k-h)a,(2l-n+h)a) \end{eqnarray*}$

P.S.: Das Durchschleifen dieses $\begin{eqnarray*} a \end{eqnarray*}$ kann man sich eigentlich sparen und mit o.B.d.A. a=1 rechnen. Das Skalieren des Ergebnisses kann man hinterher vornehmen, ist ja offensichtlich linear in $\begin{eqnarray*} a \end{eqnarray*}$ .

EDIT: Formelumbruch wg. exzessiver Zeilenlänge...

16.02.2011, 17:11

Dopap

Auf diesen Beitrag antworten »

ja, sehr gut, das hilft mir weiter. Freude

Vor geraumer Zeit hab ich mal ein Programm zum Erwartungswert geschrieben, aber
die mehrfachen FOR j=k TO n STEP h Schleifen waren im Prinzip auch nur Summen und
das Ergebnis war noch suboptimal.

Ich versuch jetzt mal die vorgebene Summe für ein Beispiel zu berechnen.
Mein neuester Taschenrecher lässt im Prinzip eine grafische (!) Eingabe der
Dreifachsumme zu, nur abschnittsweis-definierte Funktionen bremsen stark.
Anschliessend noch einen Vergleich mit dem Wert nach Monte Carlo Methode ...

16.02.2011, 17:24

René Gruber

Auf diesen Beitrag antworten »

Die obige Summe umfasst genau $\begin{eqnarray*} \binom{n+3}{3} = \frac{(n+1)(n+2)(n+3)}{6} \end{eqnarray*}$ Summanden. Mit Betrachtung diverser Symmetrien lässt sich das ganze für große $\begin{eqnarray*} n \end{eqnarray*}$ auf etwas mehr als ein Achtel reduzieren, wiewohl die entsprechende Programmierung dessen eine Reihe Fallunterscheidungen nötig macht ( $\begin{eqnarray*} n \end{eqnarray*}$ bzw. $\begin{eqnarray*} h \end{eqnarray*}$ gerade oder ungerade ...).

16.02.2011, 20:07

Huggy

Auf diesen Beitrag antworten »

Kleine Anmerkung:

Ein 2-dimensionaler random walk mit n Schritten auf einem kartesischen Gitter mit Gitterabstand 1 lässt sich sich auf 2 voneinander unabhängige 1-dimensionale random walks mit jeweils n Schritten und einer einer Schrittweite $\begin{eqnarray*} \sqrt 2 /2 \end{eqnarray*}$ zurückführen.

Dazu legt man das Gitter mit Gitterabstand 1 in einem Winkel von 45° in ein xy-Koordinatensystem. Jeder Schritt ist dann ein Schritt mit Schrittweite 1 in eine der Richtungen NO, NW, SW, SO. Jeden dieser Schriitte kann man sich entstanden denken durch je einen Schritt in x- und in y-Richtung mit der Schrittweite $\begin{eqnarray*} \sqrt 2 /2 \end{eqnarray*}$ .

16.02.2011, 20:37

Dopap

Auf diesen Beitrag antworten »

@Huggy:
darf ich deinen Vorschlag dahingehen abändern, dass der rand-walk im System O'
in Wu(2)/2 Schritten erfolgt?
Hat für mich den gedanklichen Vorteil, dass er nach 2n Schritten wieder auf den
Original-Kreuzungen landet!
Aber wo ist jetzt der Fortschritt verwirrt

16.02.2011, 20:48

René Gruber

Auf diesen Beitrag antworten »

@Huggy

Hätte gern etwas früher kommen können, diese Anmerkung. Big Laugh

Das reduziert den Berechnungsaufwand immerhin von $\begin{eqnarray*} O(n^3) \end{eqnarray*}$ auf $\begin{eqnarray*} O(n^2) \end{eqnarray*}$ . Freude

Immerhin muss man die obigen Betrachtungen von mir nicht ganz wegwerfen, falls man etwa ein rechteckiges statt einem quadratischen Straßennetz betrachtet, d.h. mit Blockgröße $\begin{eqnarray*} a\times b \end{eqnarray*}$ statt $\begin{eqnarray*} a\times a \end{eqnarray*}$ . (Oder doch nicht ... muss ich nochmal drüber nachdenken. verwirrt

)

16.02.2011, 20:58

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
darf ich deinen Vorschlag dahingehen abändern, dass der rand-walk im System O'
in Wu(2)/2 Schritten erfolgt?
Hat für mich den gedanklichen Vorteil, dass er nach 2n Schritten wieder auf den
Original-Kreuzungen landet!

Ich verstehe nicht, wie du das meinst?
Die Zahl der Schritte muss doch eine natürliche Zahl sein. Und wenn mann man n Schritte in x-Richtung und n Schritte in y-Richtung mit Schrittweite $\begin{eqnarray*} \sqrt 2 /2 \end{eqnarray*}$ macht, landet man doch auf einem Punkt des Gitters, den man auch mit n Schritten mit Schriittweite 1 in Diagonalenrichtung erreichen könnte.

Zitat:

Aber wo ist jetzt der Fortschritt verwirrt

Siehe Anmerkung von René.

Ich bin im Moment anderweitig stark beschäftigt. Ich denke aber, falls man durch die Reduktion auf eine Doppelsumme noch weitere Fortschriitte erzielen kann, wird euch das auch ohne mich gelingen.

16.02.2011, 21:58

Dopap

Auf diesen Beitrag antworten »

mmh, der obere Index der 2. Variablen musste sich bisher nach dem
LaufIndex der 1. Variablen richten, (kleiner als n sein)
Fortschritt:
für beide Variable ist der obere Summenindex gleich, nämlich n.
Und dadurch ist die bisherige leichte Abhängigkeit aufgehoben.
Wenn's stimmt, dann hätt' ich es endlich auch kapiert!

Und nun noch zur Summenauswertung.
Leider hat der Taschenrechner gestreikt. Der kann zwar mehrfache Summen, aber
keine bedingten(!) oberen SummenIndexe. unglücklich

obiger Fortschritt könnte das Problem vielleicht beheben. Mal sehen...

19.02.2011, 00:48

Dopap

Auf diesen Beitrag antworten »

die Dreifachsumme liefert als Programm geschrieben extrem zu große Werte.
Vielleicht bringt die Doppelsumme bessere Werte!
Bei n=10 steps ist nach Monte-Carlo-Methode E(10) =3.25 mit SQR(Varianz)=1.68
Bei n=30 ist E(30)=5.60 mit Standardabweichung sigma=2.88.

Das sieht plausibel aus, es besteht also in beiden Fällen die realistische Möglichkeit auch wieder
vor der Kneipe zu landen.

19.02.2011, 01:10

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
die Dreifachsumme liefert als Programm geschrieben extrem zu große Werte.

Das kann nur daran liegen, dass du sie fehlerhaft implementiert hast. unglücklich

Ich hab beide Varianten (Doppel- und Dreifachsumme) ausprobiert, und sie lieferten bei Testvergleichen bis hin zu n=10000 immer dieselben Werte.

19.02.2011, 21:04

Dopap

Auf diesen Beitrag antworten »

ich hatte in der Eile am Ende per Hand mit (2*n)^2 statt mit 2^(2*n) dividiert Hammer

Nun siehts gleich besser aus. Mein taschenrechner braucht bei der Dreifachsumme
bei n=20 ca. 15 Minuten.
Ergebnis: E(10)=2.800 und E(20)=3.966
Wenn's richtig ist wäre das Thema erledigt.
@Rene´Gruber:die Doppelsummenformel würde mich schon noch interessieren!?

19.02.2011, 21:15

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
@Rene´Gruber:die Doppelsummenformel würde mich schon noch interessieren!?

Ich verstehe das mal so, dass du die Formel nicht kennst und auch nicht herleiten kannst? Ok, hier ist sie:

$\begin{eqnarray*} E(g(X,Y)) = 2^{-2n} \cdot \sum_{k=0}^n \binom{n}{k} \sum_{l=0}^n \binom{n}{l} g((k+l-n)a,(k-l)a) \end{eqnarray*}$

hier natürlich wieder mit $\begin{eqnarray*} g(x,y) = \sqrt{x^2+y^2} \end{eqnarray*}$ .

20.02.2011, 23:24

Dopap

Auf diesen Beitrag antworten »

sehr gut, die Formel ist schneller und liefert dieselben Ergebnisse.
Alles klar soweit und Danke an die Helfer!

Neue Frage »

Antworten »

drunken man in New York

Verwandte Themen