[PYTHON] Sprechen Sie über die Fluchtwahrscheinlichkeit eines zufälligen Gehens auf einem ganzzahligen Gitter

Es ist eine Geschichte, dass der zufällige Gang auf dem Ganzzahlgitter zum Startpunkt zurückkehrt, wenn es 2D oder weniger ist, aber nicht zurückkehrt, wenn es 3D ist.
Führen Sie eine Simulation mit Python durch, um zu sehen, wie die Fluchtwahrscheinlichkeit konvergiert (endet / endet nicht).
Es war interessant, dass Cahpter4 von [Foundation of Data Science] 1 über Markov-Kette ~ MCMC ~ Random Walk sprach.

Problemstellung

Beginnen Sie in einem d-dimensionalen ganzzahligen Raster am Ursprung und führen Sie einen zufälligen Spaziergang (= wählen Sie zufällig aus 2d benachbarten Punkten aus und bewegen Sie sich) unendlich oft aus. Zu diesem Zeitpunkt frage ich mich, ob ich vielleicht wieder zum Ursprung zurückkehren werde oder ob ich weit weg gehen und niemals zurückkehren werde.

Um dies ungefähr durch Simulation zu erhalten, führen Sie N zufällige Spaziergänge mit einer Länge von n Schritten N-mal durch und erhalten Sie die empirische Wahrscheinlichkeit, mehr als einmal zum Ursprung zurückzukehren.

Bild des Experiments

Ich habe versucht, den Zustand des 3D-Zufallslaufs (100.000 Schritte) anhand von [hier] 2 zu visualisieren. In diesem Beispiel scheint es nicht um den Ursprung (oben links) herum zu beginnen, nach rechts unten zu gehen und zurückzukehren. Wiederholen Sie diesen Versuch viele Male, um die Wahrscheinlichkeit zu ermitteln, mit der ein Versuch zum Ursprung zurückkehrt.

Code

Wir haben eine Numpy-Array-Berechnung und eine japanische Anzeige entwickelt, aber die Erklärung wird weggelassen.


% matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import seaborn as sns
sns.set()
matplotlib.rcParams['font.family'] = 'sans-serif'
matplotlib.rcParams['font.sans-serif'] = ['Hiragino Maru Gothic Pro', 'Yu Gothic', 
'Meirio', 'Takao', 'IPAexGothic', 'IPAPGothic', 'VL PGothic', 'Noto Sans CJK JP']

def try_mc(n, N, dim):
    """Führen Sie N zufällige Spaziergänge vom Ursprung aus durch und bewegen Sie n Schritte in einem dim-dimensionalen Gitter.
    """
    index = np.random.randint(dim, size=(N, n))
    sign = np.random.choice([-1,1], size=(N, n))
    ps = np.zeros((N, n,dim), dtype=int)
    ps[np.arange(N).reshape(N,1), np.arange(n), index] += sign
    ps = ps.cumsum(axis=1)
    return ps

n = 100000
N = 1000
dims = [1,2,3]

fig, axes = plt.subplots(1,3, sharey=True, sharex=True, figsize=(15,5))

for i, dim in enumerate(dims):
    ps = try_mc(n, N, dim)
    ds = np.abs(ps).sum(axis=2)
    ax = axes[i]
    ax.set_xlabel("Zufällige Gehlänge")
    if i==0:
        ax.set_ylabel("Wahrscheinlichkeit, mehr als einmal zum Ursprung zurückzukehren")
    prob = ((ds == 0).cumsum(axis=1)>0).sum(axis=0) / N
    ax.plot(prob)

Simulationsergebnis

Wenn Sie den zufälligen Spaziergang fortsetzen, wird er eines Tages wiederkommen, daher möchte ich, dass die Wahrscheinlichkeit auf 1 konvergiert ...

In einer Dimension konvergiert es sofort gegen 1.
2D sollte eigentlich gegen 1 konvergieren, aber es ist ziemlich langsam und es scheint, dass 100.000 Schritte noch weit entfernt sind. [Referenz] In 1 beträgt die eindimensionale Fluchtwahrscheinlichkeit $ O (1 / n) $ und kann von oben gebunden werden, während die zweidimensionale Fluchtwahrscheinlichkeit $ O (1 / \ log n) $ beträgt. Es scheint unvermeidlich, weil es nur unterdrückt wird ($ n $ bedeutet hier die Entfernung vom Ursprung).
Im Vergleich zu 2D liegt die Neigung von 3D näher bei 0 und es sieht so aus, als ob sie konvergiert. Die Wahrscheinlichkeit einer Rückkehr beträgt ungefähr 0,34 (die Fluchtwahrscheinlichkeit beträgt 0,66).

In der 1. und 2. Dimension beträgt die Wahrscheinlichkeit einer Rückkehr 1. Wenn Sie also ausreichend lange fortfahren, kehren Sie schließlich zum Ursprung zurück. In der 3. Dimension ist die Wahrscheinlichkeit, dass Sie nicht zurückkehren, größer als 0. Wenn Sie also ausreichend lange fortfahren, kehren Sie definitiv zurück. Dies bedeutet, dass Sie niemals zurückkehren werden (denn selbst wenn Sie ein- oder zweimal in der Mitte zurückkommen und den Neustart wiederholen, erhalten Sie eine Testversion, die irgendwann nicht mehr zurückkommt).

(Genau genommen kommt es nicht zurück, aber es geht bis ins Unendliche, bevor es zum Ursprung zurückkehrt, also verstehe ich den Ausdruck nicht wirklich.)

Hintergrundgeschichte

Mathematisch ist der Wert Fluchtwahrscheinlichkeit

p_ {Escape} (i, j): = (Wahrscheinlichkeit, von i zu beginnen und zu i zurückzukehren, bevor j erreicht wird)

Ist definiert als. In diesem Gitterdiagramm ist $ i = Ursprung $, $ j = $ {Punkt } mit n Abstand vom Ursprung (Manhattan) und $ p_ {Flucht} $, wenn $ n \ bis \ infty $ berechnet wurde. Es ist ein Bild. $ P_ {Escape} = 0 $ wenn $ dim = 1,2 $, $ dim = 3 $

1/6 <= p_{escape} <= 5/6

Es ist relativ einfach, das zu beweisen. Dieser Beweis zeigt, dass die Fluchtwahrscheinlichkeit in einem Stromkreis mit einem 1Ω-Widerstand an jeder Kante des Diagramms verwendet wird.

p_{escape} = c_{eff} / c_i

($ c_ {eff} $ ist die zusammengesetzte Leitfähigkeit zwischen i und j, $ c_i $ ist die Summe der Leitfähigkeiten der Kanten, die mit $ i $ verbunden sind) Es ist technisch interessant zu verwenden, was ausgedrückt wird. Wenn Sie interessiert sind, lesen Sie bitte [Referenzen] 1. Neben der Fluchtwahrscheinlichkeit gibt es noch andere Themen wie die Beziehung zwischen Spannung, Strom und Random Walk und die Beziehung zwischen Pendelzeit und kombiniertem Widerstand, was interessant ist. (Übrigens ist die Übung "Finden der Fluchtwahrscheinlichkeit in einem Computerexperiment" in der Übung enthalten.)