The story of the escape probability of a random walk on an integer grid

Problem setting

In a d-dimensional integer grid, a random walk (= randomly selected from 2d adjacent points and moved) is performed infinitely, starting from the origin. At this time, I am wondering if it may return to the origin again, or if it will go far and never come back.

In order to obtain this approximately by simulation, a random walk with a length of n steps is performed N times, and the empirical probability of returning to the origin at least once is calculated.

Image of experiment

I tried to visualize the state of the 3D random walk (100000 steps) with reference to [here] 2. In this example, it seems that it will not start from around the origin (upper left), go to the lower right, and return. Repeat this trial many times to find the probability that a trial will return to the origin. random3d.png

code

We have devised numpy array operation and Japanese display, but the explanation is omitted.


% 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):
    """Perform N random walks starting from the origin and moving n steps in the dim-dimensional grid.
    """
    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("Random walk length")
    if i==0:
        ax.set_ylabel("Probability of returning to the origin more than once")
    prob = ((ds == 0).cumsum(axis=1)>0).sum(axis=0) / N
    ax.plot(prob)

simulation result

If you continue the random walk, it will come back someday, so I would like the probability to converge to 1 ... result.png

In 1D and 2D, the probability of returning is 1, so if you continue for a long enough time, you will eventually return to the origin, but in 3D, "the probability of not returning is greater than 0", so if you continue for a long enough time It means that you will never come back (because even if you come back once or twice in the middle, if you repeat the restart, you will get a trial that will not come back eventually).

(Strictly speaking, it doesn't come back, but it goes to infinity before returning to the origin, so I don't understand the expression well.)

Background story

Mathematically, the value escape probability

p_ {escape} (i, j): = (Probability of starting from i and returning to i before reaching j)

Is defined as. In this lattice graph, $ i = origin $, $ j = $ {point } at a distance of n from the origin (Manhattan), and $ p_ {escape} $ when $ n \ to \ infinity $ was calculated. It is an image. When $ dim = 1,2 $, $ p_ {escape} = 0 $, and when $ dim = 3 $,

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

It is relatively easy to prove that. This proof shows that escape probablity is used in an electric circuit with a 1Ω resistor at each edge of the graph.

p_{escape} = c_{eff} / c_i

($ c_ {eff} $ is the combined conductance between i and j, $ c_i $ is the sum of the conductances of the edges connecting to $ i $) It is technically interesting to use what is expressed as, so if you are interested, please see [References] 1. In addition to escape probability, there are other topics such as the relationship between voltage, current and random walk, and the relationship between commute time and combined resistance, which is interesting. (By the way, the exercise "finding the escape probability in a computer experiment" is included in the exercise.)

Recommended Posts

The story of the escape probability of a random walk on an integer grid
Calculate the probability of outliers on a boxplot
Create a shape on the trajectory of an object
The story of writing a program
The story of an error in PyOCR
The story of making Python an exe
The story of making an immutable mold
The story of blackjack A processing (python)
The story of making a lie news generator
The story of making a mel icon generator
A story about an engineer who came only on the server side created a portfolio
Make the initial directory of JupyterLab a Google Drive mounted on an external HDD
The story of launching a Minecraft server from Discord
A story that reduces the effort of operation / maintenance
The story of making a music generation neural network
Create a random number with an arbitrary probability density
A story about changing the master name of BlueZ
Zip 4 Gbyte problem is a story of the past
A story that analyzed the delivery of Nico Nama.
A Study on Visualization of the Scope of Prediction Models
The story of sys.path.append ()
VisibleDeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
The story of creating a VIP channel for in-house chatwork
A note on the default behavior of collate_fn in PyTorch
Measure the importance of features with a random forest tool
The story of how the Python bottle worked on Sakura Internet
The story of a Django model field disappearing from a class
The story of creating a database using the Google Analytics API
The story of making a question box bot with discord.py
The story of releasing a Python text check tool on GitHub x CircleCI for the first time
A story posted on Kaggle by an amateur who doesn't even know the terminal over 3 weeks
The story of making a tool that runs on Mac and Windows at the game development site
A story about a person who uses Python addicted to the judgment of an empty JavaScript dictionary
The story of building Zabbix 4.4
[Apache] The story of prefork
A method of converting the style of an image while preserving the color
A story stuck with the installation of the machine learning library JAX
A story that struggled to handle the Python package of PocketSphinx
On Linux, the time stamp of a file is a little past.
Count the maximum concatenated part of a random graph with NetworkX
The story of creating a site that lists the release dates of books
Find the rank of a matrix in the XOR world (rank of a matrix on F2)
[Pythonista] The story of making an action to copy selected text
[Windows] A story of a beginner who stumbles on Anaconda's PATH setting.
The story of making a module that skips mail with python
Get the number of readers of a treatise on Mendeley in Python
Create a compatibility judgment program with the random module of python.
The story of failing to update "calendar.day_abbr" on the admin screen of django
The story of making a tool to load an image with Python ⇒ save it as another name