首页 Stochastic Processes

Sheldon M. Ross "Stochastic Processes" 2nd Edition
随机过程（第二版）习题

# 4.2

对 Markov 链证明，只要 n1<⋯<nk<nn_1<\cdots<n_k<n, 就有

P(Xn=j∣Xn1=i1,⋯,Xnk=ik)=P(Xn=j∣Xnk=ik)P(X_n=j\mid X_{n_1}=i_1,\cdots,\,X_{n_k}=i_k)=P(X_n=j\mid X_{n_k}=i_k)

解：

归纳法证之.

① 当 n=nk+1n=n_k+1 时，由 Markov 性立即得

P(Xnk+1=j∣Xn1=i1,⋯,Xnk=ik)=P(Xnk+1=j∣Xnk=ik)P(X_{n_k+1}=j\mid X_{n_1}=i_1,\cdots,X_{n_k}=i_k)=P(X_{n_k+1}=j\mid X_{n_k}=i_k)

② 假设 n=m>nk+1n=m>n_k+1 时成立 P(Xm=s∣Xn1=i1,⋯,Xnk=ik)=P(Xm=s∣Xnk=ik)P(X_m=s\mid X_{n_1}=i_1,\cdots,X_{n_k}=i_k)=P(X_m=s\mid X_{n_k}=i_k). 考虑 n=m+1n=m+1，取条件于 XmX_m 的取值，由 Markov 性及归纳假设得

P(Xm+1=j∣Xn1=i1,⋯,Xnk=ik)=∑sP(Xm+1=j∣Xm=s,Xn1=i1,⋯,Xnk=ik)⋅P(Xm=s∣Xn1=i1,⋯,Xnk=ik)=∑sP(Xm+1=j∣Xm=s)⋅P(Xm=s∣Xnk=ik)=P(Xm+1=j∣Xnk=ik)(Chapman-Kolmogorov)\begin{aligned} &P(X_{m+1}=j\mid X_{n_1}=i_1,\cdots,X_{n_k}=i_k)\\ =\,&\textstyle\sum_{s} P(X_{m+1}=j\mid X_m=s,X_{n_1}=i_1,\cdots,X_{n_k}=i_k)\cdot P(X_m=s\mid X_{n_1}=i_1,\cdots,X_{n_k}=i_k)\\ =\,&\textstyle\sum_{s} P(X_{m+1}=j\mid X_m=s)\cdot P(X_m=s\mid X_{n_k}=i_k)\\ =\,&P(X_{m+1}=j\mid X_{n_k}=i_k)\quad(\text{Chapman-Kolmogorov}) \end{aligned}

于是原命题成立.

# 4.8

X1,X2,⋯X_1,\,X_2,\cdots 独立同分布，P(Xi=j)=αj(j≥0)P(X_i=j)=\alpha_j\ (j\geq0)，X0=−∞X_0=-\infty. 称 nn 时刻产生一个记录，若 XnX_n 比之前的所有值都大，并称 XnX_n 为其记录值。令 RiR_i 为第 ii 个记录值.

  1. 证明 {Ri}\left\{R_i\right\} 是 Markov 链，并计算转移概率.
  2. 记第 ii 个记录与第 i+1i+1 个记录之间的时间为 TiT_i. {Ti}\left\{T_i\right\} 是 Markov 链否？{(Ri,Ti)}\left\{(R_i,\,T_i)\right\} 是 Markov 链否？若是则计算转移概率.
  3. 令 Sn=∑1nTiS_n=\sum\limits_1^nT_i, 证明：当 XiX_i 都是连续随机变量时 {Sn}\left\{S_n\right\} 是 Markov 链，并计算转移概率.

解：

(1) 用 nkn_{k} 表示第 kk 次记录产生的时刻，则 Xnk=RkX_{n_k}=R_k. 于是 Rk=rR_k=r 即等价于 “nkn_k 时刻取值为 rr，且比上一个记录值要大，且两次记录时刻之间的取值均不比上一个记录值大”. 记第 kk 次记录与第 k+1k+1 次记录之间间隔 nk+1−nk=tn_{k+1}-n_k=t（也即两个记录中间夹 t−1t-1 个值），则取条件于 tt：

P(Rk+1=r∣Rk=r0)=∑t=1∞P(Xnk+1=r,Xnk+1>r0;X1+nk≤r0,X2+nk≤r0,⋯,Xt−1+nk≤r0)=∑t=1∞P(Xl=r,Xl>r0)⋅[P(Xn≤r0)]t−1\begin{aligned} P\left(R_{k+1}=r\mid R_k=r_0\right)&= \textstyle\sum\limits_{t=1}^\infty P\left(X_{n_{k+1} }=r,\,X_{n_{k+1} }>r_0\,;\,X_{1+{n_k} }\leq r_0,\,X_{2+{n_k} }\leq r_0,\,\cdots,\,X_{t-1+n_{k} }\leq r_0\right)\\ &= \textstyle\sum\limits_{t=1}^\infty P\left(X_l=r,\,X_{l}>r_0\right)\cdot\big[P\left(X_n\leq r_0\right)\big]^{t-1} \end{aligned}

当 r≤r0r\leq r_0 时，显然有 P(Xl=r,Xl>r0)=0P\left(X_l=r,\,X_l>r_0\right)=0；
当 r>r0r>r_0 时，原式 =∑t=0∞P(Xl=r)⋅[P(Xn≤r0)]t=P(Xl=r)⋅11−P(Xn≤r0)=αj∑m=r0+1∞αm=\textstyle\sum\limits_{t=0}^\infty P\left(X_l=r\right)\cdot\big[P\left(X_n\leq r_0\right)\big]^{t}=P\left(X_l=r\right)\cdot\dfrac{1}{1-P(X_n\leq r_0)}=\dfrac{\alpha_j}{\sum_{m=r_0+1}^{\infty}\alpha_m}

因此 {Rk}\left\{R_k\right\} 是 Markov 链，转移概率

P(Rk+1=r∣Rk=r0)={0,r≤r0αr∑m=r0+1∞αm,r>r0P\left(R_{k+1}=r\mid R_k=r_0\right)=\begin{cases}0&,\,r\leq r_0\\\dfrac{\alpha_r}{\sum_{m=r_0+1}^{\infty}\alpha_m}&,\,r>r_0\end{cases}

(2) 第 k+1k+1 次记录至第 k+2k+2 次记录的时间间隔显然与且只与第 k+1k+1 次记录的值有关，因此 {Tk}\left\{T_k\right\} 不是 Markov 链。结合 {Rk}\left\{R_k\right\} 的 Markov 性可得

P(Rk+1=r,Tk+1=t∣Rk=r0,Tk=t0)=P(Rk+1=r,Tk+1=t∣Rk=r0)=P(Rk+1=r,Tk+1=t,Tk=t0∣Rk=r0)P(Rk=r0)P(Tk=t0∣Rk=r0)P(Rk=r0)=P((t⁣−⁣1)个X≤r,Xl=r>r0,(t0⁣−⁣1)个X≤r0)P((t0⁣−⁣1)个X≤r0)=P((t⁣−⁣1)个X≤r,Xl=r>r0)\begin{aligned} &\quad\,\,P\left(R_{k+1}=r,\,T_{k+1}=t\mid R_k=r_0,\,T_k=t_0\right)\\ &= P\left(R_{k+1}=r,\,T_{k+1}=t\mid R_k=r_0\right)\\ &= \dfrac{P\left(R_{k+1}=r,\,T_{k+1}=t,\,T_k=t_0\mid R_k=r_0\right)\bcancel{P(R_k=r_0)} }{P\left(T_k=t_0\mid R_k=r_0\right)\bcancel{P(R_k=r_0)} }\\ &= \dfrac{P((t\!-\!1)个X\leq r,\,X_l=r>r_0,\,(t_0\!-\!1)个X\leq r_0)}{P((t_0\!-\!1)个X\leq r_0)}\\ &= P((t\!-\!1)个X\leq r,\,X_l=r>r_0) \end{aligned}

于是由 (1) 的结论，当 r≤r0r \leq r_0 时为 00，当 r>r0r>r_0 时 =P(Xl=r)⋅[P(Xn≤r0)]t−1=αr(∑m=0rαm)t−1=P\left(X_l=r\right)\cdot\big[P\left(X_n\leq r_0\right)\big]^{t-1}=\alpha_r\left(\sum\limits_{m=0}^{r}\alpha_m\right)^{t-1}{}

因此 {(Rk,Tk)}\left\{(R_k,\,T_k)\right\} 是 Markov 链，转移概率

P(Rk+1=r,Tk+1=t∣Rk=r0,Tk=t0)={0,r≤r0αr(∑m=0rαm)t−1,r>r0P\left(R_{k+1}=r,\,T_{k+1}=t\mid R_k=r_0,\,T_k=t_0\right)=\begin{cases}0&,\,r\leq r_0\\\alpha_r\left(\sum\limits_{m=0}^{r}\alpha_m\right)^{t-1}&,\,r>r_0\end{cases}

(3) 由题意，SkS_k 即第 kk 个记录出现的时刻。欲求 P(Sk+1=s∣Sk=s0)P(S_{k+1}=s\mid S_k=s_0)，这个事相当于：

  1. X1,⋯,Xs−1X_1,\cdots,X_{s-1} 的最大值出现在前 s0s_0 个中，即 max⁡(X1,…,Xs−1)=max⁡(X1,…,Xs0)\max(X_1,\dots,X_{s-1})=\max(X_1,\dots,X_{s_0}). 参考习题 1.6 可得，当变量为连续型时，右侧 max 括号内每一个数成为左侧最大值的可能性相同，均为 1s−1\dfrac{1}{s-1}，因此这部分的概率为 s0s−1\dfrac{s_0}{s-1}；
  2. XsX_s 是新的记录值，即 Xs=max⁡(X1,…,Xs)X_s=\max(X_1,\dots,X_s)，这里的概率为 1s\dfrac1s.

以上两事件独立，故 P(Sk+1=s∣Sk=s0)=s0s−11s(s>s0)P(S_{k+1}=s\mid S_k=s_0)=\dfrac{s_0}{s-1}\dfrac1s\ (s>s_0).

于是 {Sn}\left\{S_n\right\} 是 Markov 链，转移概率

P(Sk+1=s∣Sk=s0)={0,s≤s0s0s(s−1),s>s0P(S_{k+1}=s\mid S_k=s_0)=\begin{cases}0&,s\leq s_0 \\ \dfrac{s_0}{s(s-1)}&,s>s_0 \end{cases}

# 4.18

工作按速率 λ\lambda 的 Poisson 过程来到一个加工中心。加工中心只有 NN 个等待空间，因此若来到的工作发现有 NN 个工作在等待就不再进来。每天至多有一个工作得到加工，而加工此工作必须在每天的开始。于是若在每天开始时有任何工作等待加工，则其中之一就在这天被加工，否则这天就没有工作被加工。以 XnX_n 记第 nn 天的开始时处在该加工中心的工作个数（不含当天开始时被加工的工作）.

  1. 求 Markov 链 {Xn}\left\{X_n\right\} 的转移概率.
  2. 判断该链是否遍历.
  3. 写出平稳概率的方程.

解：

(1) XnX_n 可能的取值只能为 [0,N]\left[0,N\right] 中的整数。计算 P(Xn+1=x∣Xn=x0)P(X_{n+1}=x\mid X_n=x_0) 时，假设两次统计之间来了 kk 个工作（概率为 e−λλkλ!\dfrac{ {\rm e}^{-\lambda}\lambda^k}{\lambda!}），按 x0x_0 分两类讨论：
① x0=0x_0=0 时，当 0≤k<N0\leq k<N 时 Xn+1X_{n+1} 的取值 x=kx=k，当 k≥Nk\geq N 时 x=Nx=N；
② 0<x0≤N0< x_0\leq N 时，先从队列中扣除一个工作进行处理，当 0≤k<N−x00\leq k < N-x_0 时 Xn+1X_{n+1} 的取值 x=x0+k−1x=x_0+k-1，当 k≥N−x0+1k\geq N-x_0+1 时 x=Nx=N

将参数由 kk 代换为 xx 即得转移概率表达式

P(Xn+1=x∣Xn=x0)={e−λλxx!x0=0,0≤x<N∑k=N∞e−λλkk!x0=0,x=Ne−λλx−x0+1(x−x0+1)!0<x0≤N,x0−1≤x<N∑k=N−x0+1∞e−λλkk!0<x0≤N,x=NP(X_{n+1}=x\mid X_n=x_0)= \begin{cases} {\dfrac{ {\rm e}^{-\lambda}\lambda^x}{x!} } & x_0=0\,,\quad\quad\ 0\leq x<N \\ \sum\limits_{k=N}^{\infty} {\dfrac{ {\rm e}^{-\lambda}\lambda^k}{k!} } & x_0=0\,,\quad\quad\ x=N \\ {\dfrac{ {\rm e}^{-\lambda}\lambda^{x-x_0+1} }{(x-x_0+1)!} } & 0< x_0\leq N,\, x_0-1\leq x<N \\ \sum\limits_{k=N-x_0+1}^{\infty} \dfrac{ {\rm e}^{-\lambda}\lambda^k}{k!} & 0< x_0\leq N,\, x=N \end{cases}

(2) 先证明该链不可约且正常返：

若 Xn=0X_n=0，则新到达 kk 个工作后，Xn+1=min⁡(k,N)X_{n+1}=\min(k,N)，由于 Poisson 分布对任意 k∈Nk\in \mathbb{N} 都有正概率，故对任意 0≤x≤N0\leq x\leq N，P(Xn+1=x∣Xn=0)>0P(X_{n+1}=x\mid X_n=0)>0，即状态 00 可以到达所有状态。另一方面，对任意 x0>0x_0>0，每天加工一个工作，新到达 kk 个工作后，状态转移为Xn+1=min⁡(x0−1+k,N)X_{n+1}=\min(x_0-1+k,N)，特别地若连续有限天 k=0k=0，工作数会递减到达状态 00. 因此该链不可约，且状态间是正常返的.

再证明该链非周期：

P(Xn+1=0∣Xn=0)=e−λ>0P(X_{n+1}=0\mid X_n=0)={\rm e}^{-\lambda}>0，即状态 00 可以在一步内返回自身，因此周期为 1. 由互通状态周期一致，该链周期为 1，故该链非周期.

因此该链是遍历的.

(3) 平稳概率方程 {πj=∑iπiPij∑i=0Nπi=1\left\{\begin{aligned}\pi_j= \sum\limits_i&\pi_iP_{ij}\\\sum\limits_{i=0}^N \pi_i=&\,1\end{aligned}\right.. 由 (1) 中的分类，当 j<Nj<N 时

πj=∑i=0NπiPij=π0⋅e−λλjj!+∑i=1NπiPij=π0⋅e−λλjj!+∑i=1j+1πiPij=π0⋅e−λλjj!+∑i=1j+1πi⋅e−λλj−i+1(j−i+1)!\begin{aligned} \pi_j=\sum\limits_{i=0}^N \pi_i P_{ij}&= \pi_0 \cdot \frac{ {\rm e}^{-\lambda}\lambda^j}{j!}+\sum\limits_{i=1}^N \pi_i P_{ij} \\ &= \pi_0\cdot{ \frac{ {\rm e}^{-\lambda}\lambda^j}{j!}+\sum\limits_{i=1}^{j+1} \pi_i P_{ij} }\\ & =\pi_0 \cdot\frac{ {\rm e}^{-\lambda}\lambda^j}{j!}+\sum\limits_{i=1}^{j+1}\pi_i\cdot\frac{ {\rm e}^{-\lambda}\lambda^{j-i+1} }{(j-i+1)!} \end{aligned}

当 j=Nj=N 时，πN=∑i=0NπiPiN=π0∑i=N∞e−λλii!+∑i=1Nπi(∑i=N−i+1∞e−λλii!)\pi_N=\sum\limits_{i=0}^N \pi_i P_{i N}=\pi_0 \sum\limits_{i=N}^{\infty}\dfrac{ {\rm e}^{-\lambda}\lambda^i}{i!}+\sum\limits_{i=1}^N \pi_i\left(\sum\limits_{i=N-i+1}^{\infty} \dfrac{ {\rm e}^{-\lambda} \lambda^i}{i!}\right)

# 4.23

在赌徒破产问题中，证明

P(赢得下一次赌局∣当前资产为i,且迟早到N)={p[1−(q/p)i+1]/[1−(q/p)i],p≠1/2(i+1)/2i,p=1/2\begin{aligned}&\quad\ \ P(赢得下一次赌局\mid 当前资产为\ i\,, 且迟早到\ N)\\\\&=\begin{cases}p[1-(q/p)^{i+1}]/[1-(q/p)^{i}],\quad p\neq1/2\\\\(i+1)/2i,\quad p=1/2\end{cases}\end{aligned}

解：

由例题 4.4A，从本金 ii 出发最终赢到 NN 的概率 fi={1−(q/p)i1−(q/p)N,p≠12iN,p=12f_i=\begin{cases}\dfrac{1-(q/p)^i}{1-(q/p)^N}&,p\neq\dfrac12\\\dfrac iN&,p=\dfrac12\end{cases}{}

于是

P(下一局赢∣从i开始赢到N)=P(从i开始赢到N∣下一局赢)⋅P(下一局赢)P(从i开始赢到N)=P(从i+1开始赢到N)⋅P(下一局赢)P(从i开始赢到N)=p⋅fi+1fi\begin{aligned} P(\text{下一局赢} \mid 从\ i\ 开始赢到\ N)&= \dfrac{P(从\ i\ 开始赢到\ N\mid\text{下一局赢})\cdot P(下一局赢)}{P(从\ i\ 开始赢到\ N)}\\ &= \dfrac{P(从\ i+1\ 开始赢到\ N)\cdot P(下一局赢)}{P(从\ i\ 开始赢到\ N)}\\ &= \dfrac{p\cdot f_{i+1} }{f_i}\\ \end{aligned}

因此当 p≠12p\neq\dfrac12 时，p⋅fi+1fi=p(1−(q/p)i+1)1−(q/p)i\dfrac{p\cdot f_{i+1} }{f_i}= \dfrac{p{(1-(q/p)^{i+1})} }{ {1-(q/p)^i} }；当 p=12p=\dfrac12 时，p⋅fi+1fi=12i+1i=i+12i\dfrac{p\cdot f_{i+1} }{f_i}= \dfrac12\dfrac{i+1}{i}=\dfrac{i+1}{2i}{}