drunken man in New York |
14.02.2011, 20:00 | Dopap | Auf diesen Beitrag antworten » | ||||
drunken man in New York 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 » | ||||
Hmm, ich würde allenfalls sagen bedingt unabhängig. Im einzelnen: Das ganze passiert ja wohl zweistufig: Sei die zufällige Anzahl der horizontalen Schritte (also in X-Richtung) bei insgesamt Schritten. Dann ist , also . Gehen nun von den horizontalen Schritten genau in positive X-Richtung, und parallel dazu von den vertikalen Schritten genau in positive -Richtung, dann folgt für die Position nach Schritten: Weiterhin ergibt sich für beliebige ganze Zahlen gemäß Formel der totalen Wkt . Irgendwelche Erwartungswerte von Funktionalen berechnen sich dann natürlich als also etwa bei der "mittleren Entfernung" mit . Alles gut verrührt ergibt sich für diesen Erwartungswert eine Dreifachsumme, die man also mit Aufwand numerisch auswerten kann - eine theoretische Vereinfachung wird zumindest bei deiner euklidischen Distanzfunktion kaum drin sein: P.S.: Das Durchschleifen dieses 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 . EDIT: Formelumbruch wg. exzessiver Zeilenlänge... |
||||||
16.02.2011, 17:11 | Dopap | Auf diesen Beitrag antworten » | ||||
ja, sehr gut, das hilft mir weiter. 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 Summanden. Mit Betrachtung diverser Symmetrien lässt sich das ganze für große auf etwas mehr als ein Achtel reduzieren, wiewohl die entsprechende Programmierung dessen eine Reihe Fallunterscheidungen nötig macht ( bzw. 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 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 . |
||||||
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 |
||||||
Anzeige | ||||||
|
||||||
16.02.2011, 20:48 | René Gruber | Auf diesen Beitrag antworten » | ||||
@Huggy Hätte gern etwas früher kommen können, diese Anmerkung. Das reduziert den Berechnungsaufwand immerhin von auf . 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 statt . (Oder doch nicht ... muss ich nochmal drüber nachdenken. ) |
||||||
16.02.2011, 20:58 | Huggy | Auf diesen Beitrag antworten » | ||||
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 macht, landet man doch auf einem Punkt des Gitters, den man auch mit n Schritten mit Schriittweite 1 in Diagonalenrichtung erreichen könnte.
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. 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 » | ||||
Das kann nur daran liegen, dass du sie fehlerhaft implementiert hast. 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 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 » | ||||
Ich verstehe das mal so, dass du die Formel nicht kennst und auch nicht herleiten kannst? Ok, hier ist sie: hier natürlich wieder mit . |
||||||
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! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|