李斯儒 谭静

DOI：10.19850/j.cnki.2096-4706.2021.08.004

摘  要：众所周知，随机游动作为一种特殊的马尔科夫链在诸多领域有着广泛的应用，而研究系统的阈值状态的首达概率则是重中之重。文章首先对对称一维随机游动某状态的首达概率、首达时进行计算分析;然后采用了对递推公式求母函数的方法求解对称一维随机游动的首次返回概率，最后通过蒙特卡洛方法求其首次返回概率的模拟值与理论值对照，通过大样本容量的计算证实理论解的精确性。

关键词：随机游动;首达时间;首达概率;马尔科夫链

中图分类号：O211.1    文献标识码：A    文章编号：2096-4706（2021）08-0013-04

Research and Analysis on the First Arrival Probability in Random Walk

LI Siru，TAN Jing

（Nanhang Jincheng College，Nanjing  211156，China）

Abstract：As we all know，the random walk is a special Markov chain that has wide applications in many fields，and the research on the first arrival probability of the threshold state of the system is the most important thing. First，the paper calculates and analyzes the first arrival probability and first arrival time of a certain state of a symmetric one-dimensional random walk;then uses the method of finding the generating function of the recurrence formula to solve the first return probability of the symmetric one-dimensional random walk，and finally uses Monte Carlo method compares the simulated value of the probability of its first return with the theoretical value，and confirms the accuracy of the theoretical solution through the calculation of a large sample volume.

Keywords：random walk;first arrival time;first arrival probability;Markov chain

0  引  言

在马尔科夫链中有一类非常特殊的随机过程被称为随机游走^[1]（Random Walk，RW）。随机游走是一种数学统计模型，由一连串的轨迹组成，其中的每一步都是随机的。随机游走的理论最早在1905年由Karl Pearson提出^[2]，就像一个人喝醉了之后酒后漫步一样，一定时间中所记录的轨迹就是随机游动。

一维随机游走作为一種特殊的马尔科夫链，可以有如下定义：假设游走者在一维坐标轴上从起始点x处出发，与时间无关以概率p向左移动一个单位（以1-p的概率向右移动一个单位，很多时候取p=0.5）。不妨记第游走者的第k次游动为X_k，n时刻游走着的位置是L_n，于是有：

L_n=x+X₁+X₂+…+X_k+…+X_n

这里X₁，X₂，…，X_n要满足P（X_i=1）=p=1-P（X_i=-1）。

再列举两个常用的随机游走问题：假设你是一位赌徒，你在赌场赌博，与时间无关，你每一场赢的概率为p，输掉赌局的概率为1-p。你一开始身上带了k元钱，赢一场加一元钱，输一场少一元钱，在不能借钱赌博的情况下问你输光所有赌钱的概率是多少，还有平均赌博几场会输光所有本钱。……