李斯儒 譚靜

DOI：10.19850/j.cnki.2096-4706.2021.08.004

摘? 要：眾所周知，隨機游動作為一種特殊的馬爾科夫鏈在諸多領域有著廣泛的應用，而研究系統(tǒng)的閾值狀態(tài)的首達概率則是重中之重。文章首先對對稱一維隨機游動某狀態(tài)的首達概率、首達時進行計算分析;然后采用了對遞推公式求母函數(shù)的方法求解對稱一維隨機游動的首次返回概率，最后通過蒙特卡洛方法求其首次返回概率的模擬值與理論值對照，通過大樣本容量的計算證實理論解的精確性。

關鍵詞：隨機游動;首達時間;首達概率;馬爾科夫鏈

中圖分類號：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）。隨機游走是一種數(shù)學統(tǒng)計模型，由一連串的軌跡組成，其中的每一步都是隨機的。隨機游走的理論最早在1905年由Karl Pearson提出^[2]，就像一個人喝醉了之后酒后漫步一樣，一定時間中所記錄的軌跡就是隨機游動。

一維隨機游走作為一種特殊的馬爾科夫鏈，可以有如下定義：假設游走者在一維坐標軸上從起始點x處出發(fā)，與時間無關以概率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，輸?shù)糍€局的概率為1-p。你一開始身上帶了k元錢，贏一場加一元錢，輸一場少一元錢，在不能借錢賭博的情況下問你輸光所有賭錢的概率是多少，還有平均賭博幾場會輸光所有本錢?；蚴羌僭O一個只會向前或者向后移動的醉鬼站在一個一邊是懸崖的道路上，他再向前跨一步就會跌入懸崖，每秒醉鬼向前一步或者是向后一步的概率都是50%，問醉鬼掉下懸崖的概率是多少。

1? 一維隨機游走的首次返回問題求解

1.1? 游動點返回原點的理論概率

在這個特殊的一維對稱隨機游動中，假設游動點從0點出發(fā)經過m步返回0點，顯然m必須是偶數(shù)才有可能返回，所以我們可以只計算游動點經過2n步之后返回0點的概率^[1]。計算2n步之后首次返回0點的概率雖然有些難度，但我們很容易就能寫出2n步之后游動點停在0點的概率：

我們以此為計算的起始點，來分析2n步之后游動點首次回到0點的概率^[3]。

2? 數(shù)軸上的隨機游動仿真與蒙特卡洛方法

2.1? 蒙特卡洛方法

蒙特卡洛方法是一種一般使用偽隨機數(shù)，通過模擬的方式抽取系統(tǒng)狀態(tài)來解決很多計算問題的方法，與之對應的是確定性算法。

事實上很早以前布豐通過投針實驗^[7]來計算π就算是一種蒙特卡洛方法，目前在計算復雜的積分時經常會先選擇一個能完全包含積分曲線的長方形區(qū)域，再在區(qū)域內大量平均撒點將落在積分區(qū)域內點數(shù)比上全部的撒點次數(shù)就可以得到曲線與x軸包圍的面積與長方形區(qū)域的面積之比，從而求得積分數(shù)值解。

2.2? 蒙特卡洛模擬首達概率

在MATLAB環(huán)境中我用蒙特卡洛方法模擬了1.1中對稱隨機游走中游動點從0點出發(fā)經過2k次游動是否首次返回0點的問題，MATLAB蒙特卡洛實驗代碼為：

1n1=10000000;? ? ? ? ? ? ? ? %每次中層嵌套的蒙特卡洛要模擬一千萬次

i0=1;? ? ? ? ? ? ? ? ? ? ? ? %初始化i0=1

A=zeros（2，200）;? ? ? ? ? ? ? ? %創(chuàng)造一個2行200列的矩陣

neighbour=[-1 1];? ? ? ? ? ? ? ?%游動點游動矩陣，數(shù)軸坐標+1或者是-1

for n=2：2：400? ? ? ? ? ? %最外層循環(huán)確定在一千萬次模擬中游動的步數(shù)（n為偶數(shù)）

z=0;? ? ? ? ? ? ? %初始化z，z為一千萬次實驗中成功經過n步首次返回原點的次數(shù)

for i1=1：n1? ? ? ? ? ? ? ? ?%中層循環(huán)蒙特卡洛實驗開始

x=0;? ? ? ? ? ? ? ? ? ? ?%x代表坐標

y=0;? ? ? ? ? ? ? ? ? ? ? %y表示在本次游動中一共返回0點的次數(shù)

for i2=1：n

r=floor（1+2*rand（））;? ? ?%偽隨機數(shù)來判定x是向左游動一個單位還是向右移動一個單位

x=x+neighbour（1，r）;

if x==0? ? ? ? ? ? ? ?%游動過程中x每返回一次原點y自增1

y=y+1;

else end

end? ? ? ? ? ? ? ? ? ? ? %內層循環(huán)結束，一次n步的隨機游走完成

if （x==0）&（y==1）? ? ? ? ? ? ? ?%一次蒙特卡洛模擬結束，當且僅當%

z=z+1;? ? ? ? ? ? ? ? ? ? ? %x停在0點且只有這次停在0點時z自增1

else end

end? ? ? ? ? ? ? ? ? ? ? ? ? %記錄完一千萬次實驗中有幾次符合要求

A（：，i0）=[n;z];? ? ? ? ? ? ? ? ? ? ?%將實驗數(shù)據(jù)放置在矩陣A中

i0=i0+1;

end? ? ? ? ? ? ? ? ? ? ? ? ? ? ?%外層循環(huán)結束蒙特卡洛實驗完成

xlswrite（'A.xlsx'， A）;? ? ? ? ? ? ? ?%將實驗數(shù)據(jù)導出到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為底數(shù)的對數(shù)儲存

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

end

y1=y1./10000000;? ? ?%求出蒙特卡洛法從0點出發(fā)經過n次游動首次返回0點的概率

for i1=1：200

q=y1（：，i1）;

y1（：，i1）=log10（q）;? ? %同理將蒙特卡洛方法求得的概率的數(shù)值解去對數(shù)儲存

end

y2=B（2，：）;

x0=A（1，：）;

plot（x0，y2）? ? ? ? ? ? ? ? ? ?%繪制出橫坐標為游走步數(shù)縱坐標為從0點出發(fā)經過

hold on;? ? ? ? ? ? ? % n次游動首次返回0點的概率的對數(shù)的理論值和模擬實驗值

plot（x0，y1）? ? ? %理論值為光滑曲線，蒙特卡洛實驗值為震蕩曲線

運行結果如圖1、圖2所示。

3? 結? 論

綜合全文，本文使用遞推和母函數(shù)性質的方法著重研究了一維對稱隨機游動中粒子的首次返回原點的概率分布，給出MATLAB蒙特卡洛方法的具體代碼，經過多次試驗將理論精確解與模擬數(shù)值解進行比對。

在一維對稱隨機游動的狀態(tài)首達概率的理論計算時，由于使用的遞推公式較為繁瑣導致后面不得不使用數(shù)學歸納法證明f（x）的通項公式。

另外在進行一維對稱隨機游動蒙特卡洛方法的仿真中，若實驗次數(shù)稍少就會出現(xiàn)理論解與實際解不匹配，震蕩嚴重的情況。本文的代碼運行用時過長超過8小時，今后應采取效率更高的算法進行仿真。

參考文獻：

[1] 陸大絟.隨機過程及其應用 [M].北京：清華大學出版社，1986.

[2] 何聲武.隨機過程導論 [M].上海：華東師范大學出版社，1989.

[3] 李林海，常建平.隨機信號分析 [M].北京：科學出版社，2006.

[4] 陳懷琛，吳大正，高西全.MATLAB及在電子信息課程中的應用：第4版 [M].北京：電子工業(yè)出版社，2013.

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

[6] 陳紀修.數(shù)學分析：第2版 [M].北京：高等教育出版社，2004.

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

作者簡介：李斯儒（1999—），男，漢族，江蘇揚州人，本科在讀，研究方向：信息與信號處理;通訊作者：譚靜（1978—），女，漢族，江蘇南通人，副教授，碩士，研究方向：雷達信號處理。

收稿日期：2021-03-02