Was ist der Bereich, der von einem Random Walk in einem 2D-Raster abgedeckt wird?

8

Ich bin Biologe und bewirb mich um einen Job, für den ich diese Frage lösen muss. Es ist ein Open-Book-Test, bei dem das Internet und andere Ressourcen ein faires Spiel sind. Hier ist die Frage - ich bin fest, wie man es angehen und würde gerne Hinweise zu schätzen wissen. Meine Intuition ist darunter veröffentlicht.

Hintergrund

Ihr Nachbar ist ein Bauer mit zwei Kühen, Clarabelle und Bernadette. Jede Kuh hat einen eigenen quadratischen Stift, der 11 m breit ist (siehe erste Abbildung). Der Bauer verlässt die Stadt für eine Reise und plant, die Kühe in ihren jeweiligen Pferchen zu lassen, die vollständig mit Gras gefüllt sind, um zu starten. Die Kühe beginnen in der Mitte des Pferchs und werden sich langsam um den Pferch herum bewegen und das Gras fressen. Sie bewegen sich sehr langsam um den Stift herum und halten immer nach jedem Schritt inne, um zu essen oder sich auszuruhen. Wenn Sie den Stift in Quadrate von 1 m teilen, können die Kühe in jedem Schritt ein Quadrat in jede Richtung bewegen (wie ein König auf einem Schachbrett), wie in der zweiten Abbildung gezeigt.

Nach jedem Zug wird die Kuh 20 Minuten auf dem neuen Platz verbringen und Gras fressen, wenn es verfügbar ist. Sobald das Gras auf einem Platz gegessen ist, ist es für immer weg. Bewegt sich die Kuh auf ein Feld, dessen Gras bereits gegessen wurde, dann ruht die Kuh 20 Minuten auf diesem Feld. Nach 20 Minuten, ob Pause oder Essen, bewegt sich die Kuh auf ein anderes Feld. Wenn sich eine Kuh in einem Feld neben dem Zaun befindet, wird sie niemals versuchen, sich in Richtung Zaun zu bewegen. Die Kühe bleiben nie zweimal hintereinander auf demselben Platz - sie bewegen sich immer zu einem anderen, nachdem sie sich ausgeruht oder gegessen haben. Die erste Abbildung zeigt ein Beispiel dafür, wie ein Stift nach einigen Stunden aussehen könnte, wobei die braunen Punkte auf abgegratete Quadrate hinweisen.

Die erste Kuh, Clarabelle, hat keine Vorliebe für die Richtung, wenn sie sich bewegt. Sie ist gleichermaßen wahrscheinlich in jede Richtung zu jeder Zeit bewegen. Sei p die Wahrscheinlichkeit, dass sie sich in eine Richtung bewegt, wie in der ersten Abbildung unten gezeigt.

Die zweite Kuh, Bernadette, zieht es vor, auf Plätze mit Gras zu ziehen. Es ist doppelt so wahrscheinlich, dass sie sich zu einem Raum mit Gras bewegt, während sie auf einen Raum zuläuft, den sie bereits gegessen hat, wie in der zweiten Abbildung unten gezeigt.

Fragen

  • Wenn der Bauer nach 48 Stunden zurückkehrt, welchen Prozentsatz des Grases in seinem Stall erwartest du von Clarabella?
  • Wie lange erwartest du, dass Bernadette 50% des Grases in ihrem Stall essen wird?
  • Nehmen wir an, wenn eine der Kühe 24 Stunden ohne Gras geht, stirbt sie. Welche Kuh soll länger überleben?

Meine Intuition

Dies scheint eine zufällige Wanderung durch ein zweidimensionales Gitter zu modellieren. Ich kann zum Beispiel die Wahrscheinlichkeit herausfinden, nach einer bestimmten Zeit an einem bestimmten Knoten im Gitter zu sein. Aber ich bin mir nicht sicher, wie ich über das Gebiet der Kuh denken soll, wenn sie durchgeht. Würde mich über Einsichten freuen.

Edit: Das Endziel hier wäre, dass ich eine Art von Programm dafür schreibe. Dies ist keine rein mathematische Frage und damit die Post hier.

    
mission1983 02.08.2015, 08:36
quelle

2 Antworten

3

Hier ist eine Möglichkeit, die Wahrscheinlichkeiten zu berechnen (für Clarabelle):

  1. Beginnen Sie mit einem Gitter von 0 , mit Ausnahme von 1 in der Zelle (6, 6) . Dies ist Ihr Wahrscheinlichkeitsraster für die Zeit t = 0 .

  2. Zur Zeit t + 1 wird die Wahrscheinlichkeit p(x, y, t + 1) der Zelle (x, y) gegeben durch: p(x, y, t + 1) = p1 * p(x + 1, y, t) + p2 * p(x + 1, y - 1, t) + ... (Sie haben acht Begriffe in der Summe).

Beachten Sie, dass alle pi nicht gleich sind: Die Wahrscheinlichkeit kann 1/3 (Ecke), 1/5 (Kante) oder 1/8 (jede andere Zelle) sein.

Sie können Ihr Raster dynamisch aktualisieren, indem Sie dieses für jeden Schritt t = 0 bis t = 144 (48h) ausführen.

Wenn Sie die Wahrscheinlichkeit für eine bereits gegessene Zelle wissen möchten, ist es einfach 1 - Pn wo Pn , wenn die Wahrscheinlichkeit der Zelle nie besucht wurde, nämlich:

%Vor%

Hier ist ein Code, der diese Wahrscheinlichkeit unter Verwendung von numpy in Python berechnet (im Grunde betrachtet dies eine Markov Chain ) wobei der Zustand X die Menge aller Zellen | X | = 121 und die Übergangsmatrix T = {T ij <} ist, wobei T ij die Beweglichkeitswahrscheinlichkeit ist von i bis j):

%Vor%

Der Algorithmus für Bernadette ist ein bisschen komplexer, weil Ihre p1, p2, ... probabilistisch sind, also erhalten Sie zwei Terme für jede benachbarte Zelle.

Sobald Sie alle diese Wahrscheinlichkeiten haben, können Sie leicht finden, was Sie wollen.

    
Holt 02.08.2015, 09:27
quelle
2

Es gibt zwei Möglichkeiten, solche Probleme zu lösen: analytisch oder über Simulation.

Wenn Sie den Prozess mit einer Monte-Carlo-basierten Methode simulieren, können Sie die Antworten leicht durch Mittelung finden die Ergebnisse vieler Wanderwege.

Ich würde annehmen, dass dies von Ihnen erwartet wird, es sei denn, Sie wurden anders geführt.

    
Lior Kogan 02.08.2015 10:34
quelle

Tags und Links