Bernoulli序列与首中时
我们现在来研究简单随机游动，在一条直线上从0开始，每步有\(\rm{p}\)的概率向右，\(\rm{q}\)的概率向左，这其实是一直重复Bernoulli实验，即位置变化在每一步分别以\(\rm{p},q(p+q=1)\)的概率为1,-1,设第n次实验的结果为\(\xi_n\in\{1,-1\}\)，那么\(\{\xi_n\}\)是一个独立同分布的随机变量序列，称为Berboulli序列。上述描述看起来显然且直观，但严格的定义需要构造符合要求的概率空间使得其上有Bernoulli序列。事实上，取\(\xi\)是区间\([0,1]\)上均匀分布的随机变量，则考虑其无限二进制表示的第n位小数\(\eta_n\)，取值为0和1，不难验证\(\eta_n\)构成一个Bernoulli序列。我们进而给出简单随机游动的严格表述，在取值为1，-1的Bernoulli序列\(\{\eta_n\}\)中，我们设：
\[\rm{X}_0=0,X_n=\xi_1+\xi_2+\cdots+\xi_n,n\geq1\]
这样我们给出了简单随机游动的严格构造。简单随即游动通常分为三种：右偏\(\rm p\gt {1\over2}\)，左偏\(\rm p\lt {1\over2}\)，对称\(\rm p={1\over
2}\)；不难发现左右偏是对称的，所以只需分别研究右偏和对称的情况即可。
我们想要研究随机游动的样本轨道，从以下这个基本的问题开始讨论：设\(\rm a\)是整数，则随机游动\((\rm X_n)\)是否一定到达\(\rm a\)？从字面意义上来说，这就是事件\(\bigcup_{\rm n=1}^{\infty} \{\rm
X_n=a\}\)，但更重要的是引入如下随机时间： \[\rm T_a:=\inf\{n\geq1:X_n=a\}\]
这个随机时间称为\(\rm
a\)的首中时，即随机游动第一次到达\(\rm
a\)的时间。
注： 这里\(\rm n\geq1\)和\(\rm n\geq0\)在\(\rm
a=0\)时是有区别的，后者所给出的随机时间叫做进入时。另一方面，\(\rm
T=T_0\)代表起点的首中时，也因此被称为首次返回时。
那让我们在这个随机时间的帮助下重述之前研究的问题，自然地约定\(\inf \emptyset
=\infty\)，则随机游动在有限时间内经过\(\rm a\)这一事件即为\(\{\rm T_a\lt \infty\}\)
，其概率自然表示为\(\mathbb{P}(\rm T_a\lt
\infty)\)，当此概率为1时，我们才能考虑其期望与分布。换言之，接下来我们先研究这个概率何时为1。
随机游动地严格表述自然地和概率论中地大数定律联系在一起，我们根据\(\rm X_n\)满足大数定律，所以有： \[{\rm X_n \over \rm n}\rightarrow
\mathbb{E}[\xi_1]\]
这是Bernoulli300年前地结果，Borel在100年前进一步证明了上述收敛在几乎处处意义下也成立，也即几乎所有样本轨道具有此性质。于是在随机游动右偏地情况下，由\(\mathbb{E}[\xi_1]=\rm p-q\)，\(\rm X_n\)几乎处处趋于正无穷，进而当\(\rm a\gt 0\)时，自然有\(\mathbb{P}(\rm T_a\lt
\infty)=1\)，另一边，即当\(\rm a\leq
0\)时，也不难证明\(\mathbb{P}(\rm
T_a\lt \infty)\lt 1\)
接下来我们继续考察对称时的情况，这个时候强大数定律只能得到\(\rm {X_n\over n}\)趋于0，也即\(\rm |X_n|\)相比\(\rm
n\)很小，但不能得到更细致的结果。从直觉上来看，对称简单随机游动在两边到达的最远位置应该相同，自然猜测会到达所有点，即\(\forall \rm a \in \mathbb{Z},\mathbb{P}(T_a\lt
\infty)=1\)。要证明这一点实际上只需证明几乎所有轨道无界即可，即
\[\mathbb{P}(\rm \sup_nX_n=\infty)=1\]
这样结合简单随机游动自身性质证明了我们的猜测。具体证明过程如下：
首先该事件属于\(\{\xi_n\}\)的尾事件域，因为其与前有限个\(\{\xi_n\}\)无关。于是由Kolmogorov 01
律，它的概率非0即1.我们只需说明概率非0即可。而根据中心极限定理：
\[
\begin{align*}
\rm \mathbb{P}(\sup_n X_n=\infty)&\geq \mathbb{P}(\rm
\varlimsup_{n}\{X_n\gt \sqrt{n}\})\\
&\geq\rm \lim_n \mathbb{P}(X_n\gt\sqrt{n})=1-\Phi(1)\gt0
\end{align*}
\] 同理根据随机游动的对称性，进而得到\(\mathbb{P}(\rm \sup_n X_n=\infty,\inf_n
X_n=-\infty)=1\)，于是给出了我们猜测的证明。
反射原理
我们刚刚给出了对简单随机游动首中时的基本研究，但这一刻画似乎不够深刻，我们接下来从初等排列组合方法研究对称随机游动。事实上，以离散时间为横轴，所处位置为纵轴，我们可以很轻松地将对称简单随机游动的每条轨道以折线形式画出来。
我们称一条格点轨道为某个整数列\((\rm
s_m,s_{m+1},s_{m+3},\cdots s_n)\)满足\(\forall \rm m\lt k \leq n\)，\(\rm
s_k-s_{k-1}\)为1或-1。也即我们给出了一个随机游动样本轨道到格点轨道的一一对应，且每条轨道是等概率的。因此，我们只需研究格点轨道上的问题即可。若\(\rm W_n\)表示从0出发长为\(\rm n\)的格点轨道全体，\(\rm B\subset
W_n\)表示一个轨道性质，则显然有：
\[\mathbb{P}(\rm (X_j:0\leq j \leq n)\in
B)={|B|\over2^n}\] 我们想要研究的是首次返回时\(\rm
T\)的分布，即简单随机游动以何种方式返回起点，注意到格点轨道只能在\(2\rm n\)处与横轴相交，故只需考虑\(\mathbb{P}(\rm T=2n),\forall
n\in\mathbb{Z}^+\)即可。这个问题的核心在于与横轴不交，且大于0与小于0对称，故只需给出\(\mathbb{P}(\rm X_1\gt 0,X_2\gt 0,\cdots,X_{2n}\gt
0),\forall n\in
\mathbb{Z}^+\)的表达式，相邻两项乘2后做差即得结果。这一结论依赖于以下反射原理。
定理3.2.1（反射原理） 设\(\rm
a,b\gt 0,m\lt n\)则从格点\((\rm
m,a)\)到\((\rm
n,b)\)的且与横轴相交的格点轨道总数与从\((\rm m,a)\)到\((\rm n,-b)\)的格点轨道总数相同。
证明
直觉上通过翻折可以建立两者间的一一对应，我们将它写得严格一些。对任何从格点\((\rm m,a)\)到\((\rm n,b)\)的且与横轴相交的格点轨道\((\rm s_m,\cdots,s_n
)\)，设最迟与横轴相遇于\(\rm k(m\lt
k\lt n)\)时刻，将该轨道对应至轨道\((\rm
s_m,\cdots,s_k,-s_{k+1},\cdots,-s_n )\)不难验证这是从\((\rm m,a)\)到\((\rm
n,-b)\)的格点轨道且这个映射是一一映射，于是反射原理自然成立。
记\(\rm
u_{2n}=\mathbb{P}(X_{2n}=0)\)，运用反射原理来说明\(\mathbb{P}(\rm X_1\gt 0,X_2\gt 0,\cdots,X_{2n}\gt
0)={1 \over2}u_{2n}\)，下面的推导中\(\rm N_{n,x}\)表示\((0,0)\)到\((\rm
n,x)\)的格点轨道总数。 \[
\begin{align*}
\mathbb{P}(\rm X_1\gt 0,X_2\gt 0,\cdots,X_{2n}\gt 0)&=\rm
\sum^{n}_{k=1}\mathbb{P}(\rm X_1\gt 0,X_2\gt 0,\cdots,X_{2n}=2k) \\
&=\rm{1\over2^{2n}}\sum^{n}_{k=1}
(N_{2n-1,2k-1}-N_{2n-1,2k+1})\\
&=\rm{N_{2n-1,1}\over 2^{2n}}=\rm{1\over2}u_{2n}
\end{align*}
\] 于是我们有\(\mathbb{P}(\rm T=2n)=\rm
u_{2n-2}-u_{2n},\forall n\in\mathbb{Z}^+\)，进而也有
\[\mathbb{P}(\rm T\lt
\infty)=\lim_{n\to\infty}\sum^n_{k=1} \mathbb{P}(\rm
T=2k)=\lim_{n\to\infty}1-u_{2n}=1\]
首达概率公式
在上一节中我们利用对称随机游走在格点轨道上等概率的性质证明了\(\mathbb{P}(\rm T\lt
\infty)=1\)，但这一方法不能很平凡地推广到一般情况，我们还是希望能够更一般地解决这一问题。一个自然的想法是通过好算的\(\rm u_{2n}\)来推导\(\rm
f_{2n}\)。具体思路是先通过首达概率公式将\(\rm
f_{2n}:=\mathbb{P}(T=2n)\)与之前所说的\(\rm u_{2n}\)联系起来，进而通过\(\mathbb{P}(\rm T\lt \infty)=\sum_{\rm
n=1}^{\infty} f_{2n}\)得到结果。
首达概率公式证明的核心来自于一个直觉，可以从某一时刻开始将原随机游动视为起始点不同的新随机游动，也就是说随机序列\(\rm X_k'=X_{n+k}-X_n\)，\(k\geq 0\)是一个与\((\rm X_j :j\leq n)\)独立且与\((\rm
X_t)\)分布相同的随机序列。具体的证明细节验证起来并不复杂。
注： 这也就是之后会讲到的马尔可夫性。
有了上述性质以后，首达概率公式的证明就并不复杂。我们有
\[
\begin{align*}
\rm u_{2n}=\mathbb{P}(\rm X_{2n}=0)&=\rm
\sum^{n}_{r=1}\mathbb{P}(\rm X_{2n}=0,T=2r)\\
&=\rm \sum^{n}_{r=1}\mathbb{P}(\rm X_{2n-2r}'=0,T=2r)\\
&=\rm \sum^{n}_{r=1}f_{2r}u_{2n-2r}
\end{align*}
\] 这样就有了将\(\rm
u_{2n}\)和\(\rm
f_{2n}\)联系起来的桥梁。理论上从上述方程组可以解出\(\rm
f_{2n}\)。但这并不是一件容易的事，我们需要一个更简单的算法。母函数是一个不错的选择。公式两边乘\(\rm t^{2n}\)再对\(\rm n\)求和：
\[
\rm \sum_{n\geq 1} u_{2n}t^{2n}=\rm \sum_{n\geq
1}\sum^{n}_{r=1}f_{2r}t^{2r}\cdot u_{2n-2r}t^{2n-2r}=\rm \sum_{r\geq
1}f_{2r}t^{2r}\sum_{n\geq r}u_{2n-2r}t^{2n-2r}
\] 则记\(\rm
F(t),U(t)\)分别为\(\rm (u_n)_{n\geq
0},(f_n)_{n\geq0}\)的母函数，我们进而有\(\rm F(t)U(t)=U(t)-1\)而Taylor公式给出了
\[\rm U(t)=\sum_{n\geq 0}{(2n)!\over
(n!)^2}(pq)^nt^{2n}=(1-4pqt^2)^{-{1\over 2}}\] 故\(\rm F(t)=1-\sqrt{1-4pqt^2}\)，于是
\[\rm \mathbb{P}(T\lt \infty)=\lim_{t\uparrow
1}F(t)=1-|p-q| \] 这样即给出了我们希望研究的结果。
差分方程
差分方程是微分方程的离散形式，也是早期研究随机游动的一个重要方法。下面我们以输光问题为例讲述这一方法。
输光问题指的是两个赌资为\(\rm
a,b\)的赌徒甲乙进行简单的掷硬币赌博，直到一方输光为止，求甲输光的概率。将其抽象化为数学模型也就是一个简单随机游动的问题：即从\(\rm
a\)位置开始做简单随机游动，直到他触碰到\(\rm 0\)（输光）或\(\rm a+b\)（赢下所有），也就是求\(\mathbb{P}(\rm T_0\lt
T_{a+b})\)注意到若\(\rm
X=(X_n)\)为简单随机游动，则\(\rm
X_n^x=X_n+x\)是从\(\rm
x\)出发的简单随机游动。差分方程的基本思路就是利用从\(\rm
x\)开始的随机游动左走一步，右走一步后分别变为\(\rm x-1\)开始的随机游动和\(\rm
x+1\)开始的随机游动，通过边界条件和方程给出结果。在计算当中首中时和进入时无差别，不妨用进入时。
\(\rm g_x\)代表从\(\rm x\)开始的简单随机游动下的\(\mathbb{P}(\rm T_0\lt
T_{a+b})\)。根据进入时，我们有边界条件\(\rm g_0=1,g_{a+b}=0\)而当\(0\lt \rm x\lt
a+b\)，随机游动再走一步就变成\(\rm
g_{x-1},g_{x+1}\)，根据全概率公式我们给出差分方程：
\[\rm g_x=pg_{x+1}+qg_{x-1}\]
类似地考虑赌博地持续时间\(\rm T=T_0\wedge
T_{a+b}\)，他的期望（记作\(\rm
E_x\)）通过差分方程\(\rm
E_x=pE_{x+1}+qE_{x-1}+1\)及边界条件\(\rm E_0=E_{a+b}=0\)给出。
随机游动的马氏性
前面几节所用的方法都诉诸于简单随机游动本身的性质，也即只能用于简单随机游动，在这节中我们尝试考察简单随机游动中更一般的性质，Markov性及其应用，该性质可以推广至一般随机序列。所谓Markov性，或马氏性是指在已知现在的情况下，将来与过去独立。
刚刚的这个叙述略显抽象，让我们回到例子中看，在简单随机游动中，给定\(\rm X_k=x\)，将来的运动\(\rm (X_n,n\geq k)\)是一个从\(\rm x\)出发的简单随机游动，与过去\(\rm X_0,X_1,\cdots,X_{k-1}\)独立。
对\(\rm x\in \mathbb{Z}\)，令\(\rm X_n^x=x+X_n\)，\(\{\rm X_n^x\}\)称为从\(\rm
x\)出发的简单随机游动，即在概率空间\((\Omega,\mathcal{F},\mathbb{P})\)下，我们有一族随机序列\(\{(\rm X_n^x:n\geq
0):x\in\mathbb{Z}\}\)描述不同点开始的相同转移规律的随机游动。在这一思想的基础上，我们将随机游动\((\rm
X_n^x)\)映射到轨道空间上，变成轨道空间上依赖于\(\rm x\)的分布\(\rm
\mathbb{P}^x\)，然后只需关注坐标过程即可。也就是说，坐标过程Z在概率测度\(\rm \mathbb{P}^x\)下相当于从\(\rm x\)出发的随机游动。
具体来说，现在\(\rm
E\)是整数集，\(\rm
T\)是非负整数集，\(\rm
E^T\)是轨道空间，对\(\rm w\in
E^T\)，定义坐标过程\(\rm
Z_n(w)=w(n),n\geq0\)；\(\mathcal{E}^T\)表示\(E^T\)上使所有\(\rm
Z_n,n\geq0\)为随机变量的最小事件域，于是从\(\rm x\)出发的随机游动\((\rm X_n^x)\)在轨道空间\((\rm E^T,\mathcal{E}^T)\)上的分布用\(\rm\mathbb{P}^x\)表示。也就是说，坐标过程\((\rm Z_n)\)在概率\(\rm\mathbb{P}^x\)下与\((\rm X^n_x)\)在概率\(\mathbb{P}\)下同分布。自然有限维分布一致，于是我们可以通过直接计算确切地给出有限维分布
定理2.5.1 \(\rm \forall
n\geq0,x_0,\cdots,x_n\in\mathbb{Z}\)我们有
\[\rm \mathbb{P}^x(Z_i=x_i:0 \leq i\leq
n)=1_{\{x=x_0\}}p(x,x_1)p(x_1,x_2)\cdots p(x_{n-1},x_n)\]
又我们有\(\rm
\mathbb{P}^x(Z_0=x)=1\)故直接有
\[\rm \mathbb{P}^x(Z_i=x_i:0 \leq i\leq
n)=p(x,x_1)p(x_1,x_2)\cdots p(x_{n-1},x_n)\]
我们之后直接将轨道空间和坐标过程分别记作\(\Omega\)和\(\rm
(X_n)\)，也即是\(\forall
\omega\in\Omega\)都是一条轨道，且有一族概率\(\rm\mathbb{P}^x\)使\((\rm X_n)\)，取\(\mathcal{F}=\sigma(\{\rm X_n:n\geq
0\})\)在概率空间\(\rm(\Omega,\mathcal{F},\mathbb{P}^x)\)上为从\(\rm
x\)出发的简单随机游动。接下来我们重新认识马氏性引理中给出的有限维分布等价于
\[\rm \mathbb{P}^x(X_{n+1}=y|X_i=x_i,0\leq
i\leq n)=p(x_n,y)=\mathbb{P}^{x_n}(X_1=y)\]
再将这里的条件概率替换为更一般的概念，也就是其生成的\(\sigma\)-代数，我们得到
推论2.5.2 \(\rm\forall
n\geq0,x,y\in\mathbb{Z}\)我们有
\[\rm
\mathbb{P}^x(X_{n+1}=y|\mathcal{F}_n)=p(X_n,y)=\mathbb{P}^{X_n}(X_1=y)\]
我们接下来引入推移算子的语言。\(\forall \rm
k\geq
0,\omega\in\Omega,(\omega(k+n),n\geq0)\)也是一个轨道，记作\(\rm \theta_k\omega\)它满足\(\rm
X_n\circ\theta_k=X_{k+n},n\geq0\)也就是说退役\(\rm \theta_k\)相当于“从\(\rm
k\)时刻开始看”，于是我们之前的表示可写作
\[\rm
\mathbb{P}^{X_n}(X_1=y)=\mathbb{E}^x(1_{\{X_1=y\}}\circ
\theta_n|\mathcal{F}_n)\] 更一般地可将原命题推广至以下定理：
定理2.5.3 \(\rm\forall
n\geq0,x\in\mathbb{Z},\mathcal{F}\)可测的有界（或非负）随机变量\(\rm Y\)，有
\[\rm \mathbb{E}^x(Y\circ
\theta_n|\mathcal{F}_n)=\mathbb{E}^{X_n}(Y)\]
证明 由于\(\rm
\mathbb{E}^{X_n}(Y)\)是\(\rm
\mathcal{F}_n\)可测的随机变量，故只需验证对任何原子\(\rm \mathcal{A}\in\mathcal{F}_n\)有
\[\rm \mathbb{E}^x(Y\circ
\theta_n;\mathcal{A})=\mathbb{E}(\mathbb{E}^{X_n}(Y);\mathcal{A})\]
由单调类方法，只需证明其对于示性函数\(\rm
Y=1_B\)成立即可，其中\(\rm
B=\{X_0=x_0,\cdots,X_m=x_m\}\)于是根据定理2.5.1，我们自然得到这一命题。
停时与强马氏性
我们引入在生活中更常见的随机时间，强马氏性是指上述的性质对随机时间也是正确的，但这种表述离严格还很远，我们下面尝试严格给出强马氏性的定义。直观上来说一个合法的随机时间应该被“过去”所决定，因此我们有
定义 取值在\(\rm
\mathbb{Z}_+\cup\{+\infty\}\)上的（广义）随机变量被称为停时，如果\(\rm \forall n\geq 0,\{T\leq
n\}\in\mathcal{F}_n\)；以及\(\rm\mathcal{F}_T:=\{B\in\mathcal{F}:B\cap \{T\leq
n\}\in\mathcal{F}_n\}\)
不难证明\(\rm\mathcal{F}_T\)为事件域以及关于停时的一系列简单性质。
在事件\(\rm \{T=n\}\)上定义\(\rm X_T:=X_n\)，代表随机游动在\(\rm
T\)时刻的位置。我们说样本空间上的函数\(\rm X\)在事件\(\mathcal{A}\)上是\(\mathcal{F}\)随机变量，是指\(\rm \forall x\in\mathbb{R},\{X\leq x\}\cap
\mathcal{A}\in\mathcal{F}\)；我们进一步研究\(\rm X_T\)与事件域\(\rm \mathcal{F}_T\)的关系
引理2.6.1 设\(\rm
T\)是停时，则\(\rm X_T\)在\(\{\rm T\lt \infty\}\)上关于\(\rm\mathcal{F}_T\)可测。
证明 直接带入定义验证即可。
接下来考虑停时的推移，在\(\rm
T=n\)时定义\(\rm
\theta_T=\theta_n\)，是\((\Omega,\mathcal{F})\)到自身的随机映射。本节下面用\(\rm T_y,\tau_y\)表示\(\rm
y\)的首中时和进入时。接下来是一个常用的结果。
引理2.6.3 \(\rm\forall
n,\tau_y\circ\theta_n+n=\inf\{k\geq
n:X_k\circ\theta_n=y\}\)；于是在事件\(\rm \{\tau_y\geq n\}\)上有\(\rm\tau_y=\tau_y\circ\theta_n+n\)；首中时类似，只需将\(\geq\)修改为\(\gt\)
证明
按照定义有
\[
\begin{align*}
\rm \tau_y\circ\theta_n&=\rm \inf\{k\geq0:X_k\circ\theta_n=y\}\\
&=\rm\inf\{k\geq0:X_{k+n}=y\}\\
&=\rm\inf\{k\geq n:X_{k+n}=y\}-n
\end{align*}
\] 即证。
在建立了之前的一系列结果后，我们终于可以严格地给出强马氏性的证明了。
定理2.6.4 \(\rm\forall
n\geq0,x\in\mathbb{Z}\)，非负随机变量\(\rm Y\)，在事件\(\rm\{T\lt \infty\}\)上时有
\[\rm \mathbb{E}^x(Y\circ
\theta_T|\mathcal{F}_T)=\mathbb{E}^{X_T}(Y)\] 即\(\forall \mathcal{A}\in\mathcal{F}_T\)有
\[\rm \mathbb{E}^x(Y\circ
\theta_T;\mathcal{A},T\lt\infty)=\mathbb{E}(\mathbb{E}^{X_T}(Y);\mathcal{A},T\lt\infty)\]
证明
类似之前的证明，只需对示性函数验证即可。而由于\(\rm\mathcal{A}\cap\{T=n\}\in\mathcal{F}_n\)以及前面的结论，我们有
\[
\begin{align*}
\rm \mathbb{E}^x(Y\circ
\theta_T;\mathcal{A},T\lt\infty)&=\rm\sum_{n\geq
0}\mathbb{E}^x(1_B\circ \theta_T;\mathcal{A}\cap \{T=n\})\\
&=\rm\sum_{n\geq 0}\mathbb{E}^x(1_B\circ
\theta_n;\mathcal{A}\cap \{T=n\})\\
&=\rm\sum_{n\geq
0}\mathbb{E}^x(\mathbb{P}^{X_n}(B);\mathcal{A}\cap \{T=n\})\\
&=\rm\sum_{n\geq
0}\mathbb{E}^x(\mathbb{P}^{X_T}(B);\mathcal{A}\cap \{T=n\})\\
&=\rm\mathbb{E}(\mathbb{E}^{X_T}(Y);\mathcal{A},T\lt\infty)
\end{align*}
\] 这样就完成了强马氏性的建立。
马氏性的应用
我们应用新的符号体系来证明首达概率公式：
\[
\begin{align*}
\rm u_{2n}&=\rm
\mathbb{P}^0(X_{2n}=0)=\sum^n_{r=1}\mathbb{P}^0(X_{2n}=0,T=2r)\\
&=\rm\sum^n_{r=1}\mathbb{P}^0(X_{2n-2r}\circ\theta_{2r},T=2r)\\
&=\rm\sum^n_{r=1}\mathbb{E}^0(\mathbb{P}^{X_{2r}}(X_{2n-2r}=0),T=2r)=\sum_{r=1}^nf_{2r}u_{2n-2r}
\end{align*}
\]
在马氏性以外，简单随机游动还有一个重要的性质，即空间平移不变性，或空间齐性：从\(\rm x\)出发落在集合\(\rm B\)内的概率和从\(\rm x+y\)出发落入\(\rm
B+y\)的概率相同。我们来应用随机游动的强马氏性来计算首中时的母函数。我们从进入时开始，\(\rm\forall
x,y\in\mathbb{Z},\phi_{x,y}\)为\(\rm
\tau_y\)在概率\(\rm
\mathbb{P}^x\)下的母函数\(\rm
\phi_{x,y}(t):=\mathbb{E}^xt^{\tau_y}\)
\(\rm x\not =y\)时，我们有\(\rm\mathbb{P}^x(T_y=\tau_y)=1\)；于是由空间平移不变性：
\[\rm
\phi_{x,y}(t)=\mathbb{E}^xt^{\tau_y}=\mathbb{E}^0t^{\tau_{y-x}}=\phi_{0,y-x}(t)\]
\[\rm \phi_{x,x}(t)=1\] 设\(\rm x\gt
0\)因为随机游动每次移动一个单位，故从0出发时通过\(\rm x\)必须先通过1，即\(\rm \tau_x\geq\tau_1\)这时\(\rm\tau_x=\tau_x\circ\theta_{\tau_1}+\tau_1\)注意这个式子对\(\rm T_x\)不成立，因为\(\rm x=1\)时\(\rm
\tau_1\circ\theta_{\tau_1}\not=0\)；于是由强马氏性：
\[
\begin{align*}
\rm
\phi_{0,x}(t)&=\rm\mathbb{E}^0t^{\tau_x}=\mathbb{E}^0(t^{\tau_x\circ\theta_{\tau_1}+\tau_1})\\
&=\rm \mathbb{E}^0t^{\tau_1}\cdot
t^{\tau_x}\circ\theta_{\tau_1}=\mathbb{E}^0(t^{\tau_1}\cdot
\mathbb{E}^{X_{\tau_1}}t^{\tau_x})\\
&=\rm\mathbb{E}^0t^{\tau_1}\cdot\mathbb{E}^1t^{\tau_x}=\phi_{0,1}(t)\phi_{1,x}(t)
\end{align*}
\] 也就是说记\(\phi:=\phi_{0,1}\)，则\(\rm \phi_{0,x}=\phi^x\)
同样的，从0出发也有\(\rm \tau_x\geq
1\)，于是\(\rm\tau_x=\tau_x\circ\theta_1+1\)则同样由马氏性得到\(\rm
\phi_{0,x}(t)=tp\phi_{0,x-1}(t)+tq\phi_{0,x+1}(t)\)；令\(\rm x=1\)自然有\(\rm \phi(t)={1-\sqrt{1-4t^2pq}\over
2tq}\)同理得到\(\phi_{0,-1}(t)\)由此得到\(\{\tau_1\lt \infty\}\)的概率和期望。
最后再回来计算首次返回时\(\rm
T\)的母函数。根据\(\rm
T=1+T\circ\theta_1\)及马氏性结合之前的结论得到\(\mathbb{E}^0\rm
t^T=1-\sqrt{1-4t^2pq}\)；也就给出了我们想要的结论。