李斯儒 谭静

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元钱，赢一场加一元钱，输一场少一元钱，在不能借钱赌博的情况下问你输光所有赌钱的概率是多少，还有平均赌博几场会输光所有本钱。或是假设一个只会向前或者向后移动的醉鬼站在一个一边是悬崖的道路上，他再向前跨一步就会跌入悬崖，每秒醉鬼向前一步或者是向后一步的概率都是50%，问醉鬼掉下悬崖的概率是多少。

1  一维随机游走的首次返回问题求解

1.1  游动点返回原点的理论概率

在这个特殊的一维对称随机游动中，假设游动点从0点出发经过m步返回0点，显然m必须是偶数才有可能返回，所以我们可以只计算游动点经过2n步之后返回0点的概率^[1]。计算2n步之后首次返回0点的概率虽然有些难度，但我们很容易就能写出2n步之后游动点停在0点的概率：

我们以此为计算的起始点，来分析2n步之后游动点首次回到0点的概率^[3]。

2  数轴上的随机游动仿真与蒙特卡洛方法

2.1  蒙特卡洛方法

蒙特卡洛方法是一种一般使用伪随机数，通过模拟的方式抽取系统状态来解决很多计算问题的方法，与之对应的是确定性算法。

事实上很早以前布丰通过投针实验^[7]来计算π就算是一种蒙特卡洛方法，目前在计算复杂的积分时经常会先选择一个能完全包含积分曲线的长方形区域，再在区域内大量平均撒點将落在积分区域内点数比上全部的撒点次数就可以得到曲线与x轴包围的面积与长方形区域的面积之比，从而求得积分数值解。

2.2  蒙特卡洛模拟首达概率

在MATLAB环境中我用蒙特卡洛方法模拟了1.1中对称随机游走中游动点从0点出发经过2k次游动是否首次返回0点的问题，MATLAB蒙特卡洛实验代码为：

1n1=10000000;                %每次中层嵌套的蒙特卡洛要模拟一千万次

i0=1;                        %初始化i0=1

A=zeros（2，200）;                %创造一个2行200列的矩阵

neighbour=[-1 1];               %游动点游动矩阵，数轴坐标+1或者是-1

for n=2：2：400            %最外层循环确定在一千万次模拟中游动的步数（n为偶数）

z=0;              %初始化z，z为一千万次实验中成功经过n步首次返回原点的次数

for i1=1：n1                 %中层循环蒙特卡洛实验开始

x=0;                     %x代表坐标

y=0;                      %y表示在本次游动中一共返回0点的次数

for i2=1：n

r=floor（1+2*rand（））;     %伪随机数来判定x是向左游动一个单位还是向右移动一个单位

x=x+neighbour（1，r）;

if x==0               %游动过程中x每返回一次原点y自增1

y=y+1;

else end

end                      %内层循环结束，一次n步的随机游走完成

if （x==0）&（y==1）               %一次蒙特卡洛模拟结束，当且仅当%

z=z+1;                      %x停在0点且只有这次停在0点时z自增1

else end

end                          %记录完一千万次实验中有几次符合要求

A（：，i0）=[n;z];                     %将实验数据放置在矩阵A中

i0=i0+1;

end                             %外层循环结束蒙特卡洛实验完成

xlswrite（'A.xlsx'， A）;               %将实验数据导出到Excel中防止丢失

B=zeros（2，200）;

B=A;

i0=1;

for n=2：2：400

w=（1./（n-1））.*nchoosek（n，n/2）.*（（1/2）^n）;   %将之前计算的概率分布的理论值付给w

B（：，i0）=[n;log10（w）];   %由于某些概率过低将理论值取以10为底数的对数储存

i0=i0+1; y1=A（2，：）;

end

y1=y1./10000000;     %求出蒙特卡洛法从0点出发经过n次游动首次返回0点的概率

for i1=1：200

q=y1（：，i1）;

y1（：，i1）=log10（q）;    %同理将蒙特卡洛方法求得的概率的数值解去对数储存

end

y2=B（2，：）;

x0=A（1，：）;

plot（x0，y2）                   %绘制出横坐标为游走步数纵坐标为从0点出发经过

hold on;              % n次游动首次返回0点的概率的对数的理论值和模拟实验值

plot（x0，y1）      %理论值为光滑曲线，蒙特卡洛实验值为震荡曲线

运行结果如图1、图2所示。

3  结  论

综合全文，本文使用递推和母函数性质的方法着重研究了一维对称随机游动中粒子的首次返回原点的概率分布，给出MATLAB蒙特卡洛方法的具体代码，经过多次试验将理论精确解与模拟数值解进行比对。

在一維对称随机游动的状态首达概率的理论计算时，由于使用的递推公式较为繁琐导致后面不得不使用数学归纳法证明f（x）的通项公式。

另外在进行一维对称随机游动蒙特卡洛方法的仿真中，若实验次数稍少就会出现理论解与实际解不匹配，震荡严重的情况。本文的代码运行用时过长超过8小时，今后应采取效率更高的算法进行仿真。

参考文献：

[1] 陆大絟.随机过程及其应用 [M].北京：清华大学出版社，1986.

[2] 何声武.随机过程导论 [M].上海：华东师范大学出版社，1989.

[3] 李林海，常建平.随机信号分析 [M].北京：科学出版社，2006.

[4] 陈怀琛，吴大正，高西全.MATLAB及在电子信息课程中的应用：第4版 [M].北京：电子工业出版社，2013.

[5] 何书元.概率引论 [M].北京：高等教育出版社，2011.

[6] 陈纪修.数学分析：第2版 [M].北京：高等教育出版社，2004.

[7] SPITZER F. Principles of RANDOM WALK [M].New York：Springer，2001.

作者简介：李斯儒（1999—），男，汉族，江苏扬州人，本科在读，研究方向：信息与信号处理;通讯作者：谭静（1978—），女，汉族，江苏南通人，副教授，硕士，研究方向：雷达信号处理。

收稿日期：2021-03-02