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

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. random3d.png

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 ... result.png

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.)

Recommended Posts

Parlez de la probabilité d'évasion d'une marche aléatoire sur une grille entière
Calculer la probabilité de valeurs aberrantes sur les moustaches de la boîte
L'histoire de l'exportation d'un programme
L'histoire d'une erreur dans PyOCR
L'histoire de la fabrication d'un moule immuable
L'histoire du traitement A du blackjack (python)
L'histoire de la création d'un générateur d'icônes mel
Une histoire sur un ingénieur venu uniquement du côté serveur a créé un portfolio
Faire du répertoire initial de JupyterLab un Google Drive monté sur un disque dur externe
L'histoire du lancement d'un serveur Minecraft depuis Discord
Une histoire qui réduit l'effort de fonctionnement / maintenance
L'histoire de la création d'un réseau neuronal de génération musicale
Créer un nombre aléatoire avec une densité de probabilité arbitraire
Une histoire sur le changement du nom principal de BlueZ
Le problème Zip 4 Gbyte est une histoire du passé
Une histoire qui a analysé la livraison de Nico Nama.
Une réflexion sur la visualisation du champ d'application du modèle de prédiction
L'histoire de sys.path.append ()
VisibleDeprecation Avertissement: l'utilisation d'un nombre non entier au lieu d'un entier entraînera une erreur dans le futur
L'histoire de la création d'un canal VIP dans le chatwork en interne
Remarque sur le comportement par défaut de collate_fn dans PyTorch
Mesurer l'importance des entités avec un outil de forêt aléatoire
Sakura L'histoire du fonctionnement de la bouteille Python sur Internet
L'histoire du champ de modèle Django disparaissant de la classe
L'histoire de la création d'une base de données à l'aide de l'API Google Analytics
L'histoire de la création d'un bot de boîte à questions avec discord.py
L'histoire de la sortie d'un outil de vérification de texte créé par Python sur GitHub x CircleCI pour la première fois
Une histoire postée sur Kaggle par un amateur qui ne connaît pas le terminal depuis 3 semaines
L'histoire de la création d'un outil qui fonctionne sur Mac et Windows sur le site de développement de jeux
L'histoire de la construction de Zabbix 4.4
Une méthode de conversion du style d'une image tout en préservant la couleur
Une histoire coincée avec l'installation de la bibliothèque de machine learning JAX
Sous Linux, l'horodatage d'un fichier est un peu dépassé.
Compter la partie concaténée maximale d'un graphe aléatoire avec NetworkX
L'histoire de la création d'un site qui répertorie les dates de sortie des livres
Trouvez le rang de la matrice dans le monde XOR (rang de la matrice sur F2)
[Pythonista] L'histoire de la réalisation d'une action pour copier le texte sélectionné
[Windows] L'histoire d'un débutant qui tombe sur le décor de PATH d'Anaconda.
L'histoire de la création d'un module qui ignore le courrier avec python
Obtenez le nombre de lecteurs d'articles sur Mendeley en Python
Créez un programme de jugement de compatibilité avec le module aléatoire de python.
L'histoire de l'échec de la mise à jour de "calendar.day_abbr" sur l'écran d'administration de django
L'histoire de la création d'un outil pour charger une image avec Python ⇒ l'enregistrer sous un autre nom