[PYTHON] Parlez de la probabilité d'évasion d'une marche aléatoire sur une grille entière

C'est une histoire que la marche aléatoire sur la grille entière revient au point de départ si elle est 2D ou moins, mais elle ne revient pas si elle est 3D.
Effectuez une simulation avec Python pour voir comment la probabilité d'échappement converge (se termine / ne se termine pas).
Cahpter4 de [Foundation of Data Science] 1 était intéressant car il s'agissait de Markov Chain ~ MCMC ~ Random Walk.

Problème de réglage

Dans une grille d'entiers en d dimensions, partez de l'origine et effectuez une marche aléatoire (= sélectionnez au hasard parmi 2d points adjacents et déplacez-vous) un nombre infini de fois. En ce moment, je me demande si je peux revenir à l'origine ou si je vais partir loin et ne jamais revenir.

Pour l'obtenir approximativement par simulation, effectuez N marches aléatoires d'une longueur de n pas N fois, et obtenez la probabilité empirique de revenir plus d'une fois à l'origine.

Image de l'expérience

J'ai essayé de visualiser l'état de la marche aléatoire en 3D (100 000 pas) en référence à [ici] 2. Dans cet exemple, il semble qu'il ne commencera pas autour de l'origine (en haut à gauche), n'ira pas en bas à droite et ne reviendra pas. Répétez cet essai plusieurs fois pour trouver la probabilité qu'un essai revienne à l'origine.

code

Nous avons conçu un calcul de tableau numpy et un affichage japonais, mais l'explication est omise.


% 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):
    """Effectuez N marches aléatoires en partant de l'origine et en déplaçant n étapes dans un réseau dimensionnel.
    """
    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("Longueur de marche aléatoire")
    if i==0:
        ax.set_ylabel("Probabilité de revenir à l'origine plus d'une fois")
    prob = ((ds == 0).cumsum(axis=1)>0).sum(axis=0) / N
    ax.plot(prob)

résultat de la simulation

Si vous continuez la marche aléatoire, elle reviendra un jour, alors j'aimerais que la probabilité converge vers 1 ...

Dans une dimension, il converge immédiatement vers 1.
La 2D devrait en fait converger vers 1, mais c'est assez lent, et il semble que 100 000 pas sont encore loin. [Référence] En regardant 1, la probabilité d'échappement unidimensionnelle est $ O (1 / n) $ et peut être liée par le haut, tandis que la probabilité d'échappement bidimensionnelle est $ O (1 / \ log n) . Cela semble inévitable car il est seulement supprimé ( n $ signifie ici la distance à l'origine).
Par rapport à la 2D, l'inclinaison de la 3D est plus proche de 0 et il semble qu'elle converge. La probabilité de retour est d'environ 0,34 (la probabilité de fuite est de 0,66).

Dans les 1ère et 2ème dimensions, la probabilité de retour est de 1, donc si vous continuez suffisamment longtemps, vous finirez par revenir à l'origine, mais dans la 3ème dimension, "la probabilité de ne pas revenir est supérieure à 0", donc si vous continuez suffisamment longtemps, vous reviendrez certainement. Cela signifie que vous ne reviendrez jamais (car même si vous revenez une ou deux fois au milieu, si vous répétez le redémarrage, vous obtiendrez un essai qui ne reviendra finalement pas).

(Strictement parlant, ça ne revient pas, mais ça va à l'infini avant de revenir à l'origine, donc je ne comprends pas vraiment l'expression.)

Histoire de fond

Mathématiquement, la valeur de probabilité d'échappement

p_ {escape} (i, j): = (Probabilité de partir de i et de revenir à i avant d'atteindre j)

Est défini comme. Dans ce quadrillage, $ i = origin $, $ j = $ {point } avec n distance de l'origine (Manhattan), et $ p_ {escape} $ lorsque $ n \ to \ infty $ a été calculé C'est une image. $ P_ {escape} = 0 $ quand $ dim = 1,2 $, $ dim = 3 $

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

Il est relativement facile de le prouver. Cette preuve montre que la probabilité d'échappement est utilisée dans un circuit électrique avec une résistance de 1Ω à chaque bord du graphe.

p_{escape} = c_{eff} / c_i

($ c_ {eff} $ est la conductance composite entre i et j, $ c_i $ est la somme des conductances des arêtes connectées à $ i $) Il est techniquement intéressant d'utiliser ce qui est exprimé comme, donc si vous êtes intéressé, veuillez consulter [Références] 1. En plus de la probabilité d'échapper, il existe d'autres sujets tels que la relation entre la tension, le courant et la marche aléatoire, et la relation entre le temps de trajet et la résistance combinée, ce qui est intéressant. (À propos, l'exercice "trouver la probabilité de fuite dans une expérience informatique" est inclus dans l'exercice.)