随机过程题型总结

By Z.H. Fu https://fuzihaofzh.github.io/blog/

本文将总结一些与随机过程相关的重要题型和概念，涵盖了Markov链、可数Markov链、连续Markov链、Martingale以及一些常见模型。这些内容将有助于理解和解决与随机过程相关的问题。
在随机过程中，Markov链是一个关键的概念，我们讨论了如何根据给定的转移矩阵求稳态分布、计算状态转移概率、计算从特定状态出发到达目标状态的概率等问题。此外，我们还探讨了与Markov链相关的一些概念，如吸收态、recurrent态以及首次到达和改变的期望时间。
在可数Markov链方面，我们介绍了如何判定一个Markov链是transient或positive recurrent，以及如何求解极限概率。我们还讨论了Gambler’s Ruin问题、Alarm Clock问题等经典模型，并提供了相应的解决方法。
对于连续Markov链，我们研究了生成矩阵的构建、转移矩阵的计算以及稳态分布的求解方法。此外，我们还探讨了首次改变和到达的期望时间的计算。
最后，我们提到了Martingale概念，以及如何判断一个随机过程是否满足Martingale性质。

Markov

给定转移矩阵求稳态分布

直接解方程$\pi P=\pi$,或者$\pi (I-P)=0$。注意是左特征向量！！！

给定转移概率求稳态分布

建立差分方程，带入边界条件。$f_i=pf_{i+1}+qf_{i-1}$ $\Rightarrow f_{i+1}-f_i=q/p(f_i-f_{i-1}),\ldots, f_N-f_{N-1}=(q/p)^{N-1}f_1$

给定转移矩阵求$j\rightarrow i$次数

把i当做吸收态。去掉第i行，第i列得到剩余矩阵Q，则其余状态k访问状态j的次数期望为$I+Q+Q^2+\ldots+Q^\infty=(I-Q)^{-1}=M$。计算出M后把第j行求和就相当于到达i前在其他状态的停留次数，而这个和就是到达i的期望次数。如果$i=j$则要用稳态分布$1/\pi(i)$来计算。

进入吸收态前的步数期望

如果从第i个节点出发，则把$M=(I-Q)^{-1}$的第i行加起来；

recurrent

从A出发，返回A的步数$1/\pi(A)$

给定转移矩阵求$j\rightarrow i$概率

把目标状态改为absorb，这样矩阵就成了$[[I,0],[S,Q]]$。计算$A=(I-Q)^{-1}S=MS$，这样$A_{ij}$表示从i出发被j吸收的概率。

从k出发，到达$i$前先到$j$的概率

把i，j改为吸收态，然后构造上面那个矩阵，求$A=(I-Q)^{-1}S=MS$，$A_{kj}$即是所求。

验证sequence是否是Markov

$P(X_i=0)=0.5,P(X_i=1)=0.5$ $Y_i=X_i+X_{i-1}$ 。
不是Markov，因为如果$Y_{n-1}=1$，对于不同的$Y_{n-2},\ldots,Y_{1}$，可以得到不同的$X_{n-1}$。而不同的$X_{n-1}$能导致不同的$P(Y_n|Y_{n-1})$，所以不是Markov。
例如：$P(Y_3=2|Y_2=1,Y_1=0)$我们得出$X_0=0,X_1=0,X_2=1$，这种情况下$P(Y_3=2|...)=1/2$。另一方面，考虑$P(Y_3=2|Y_2=1,Y_1=2)$，我们有$X_0=1,X_1=1,X_2=0$，这种情况下$P(Y_3=2|...)=0$。

可数Markov

判定Markov链是transient

任意选定一个状态z（可以直接选0状态），令$\alpha(x)$表示从x出发能到达z的概率。Markov链是transient的iff (1) $0\le \alpha(x) \le 1$ (2) $\alpha(z)=1,\inf \{\alpha(x), x\in S\}=0$ (3)$\alpha(x)=\sum_{y\in S}p(x,y)\alpha(y),x\ne z$。对每一个状态x列出(3)得到recursive equation解出$\alpha(x),x\in S$的表达式，然后去带入其他条件，得到参数的具体值。

判断Markov链是positive recurrent

解稳态分布$\pi(x)=\sum_{y\in S} \pi(y)p(y,x)$,解出$\pi(n)=x_n \pi(0)$,$\because \sum_{n=1}^\infty \pi(n)=1$ 所以级数$\{x_n\}$收敛级数收敛来确定$\{x_n\}$中的系数。

例：求极限概率（limiting probability）

$p(n,n+1)=2/3,p(n,0)=1/3$。
解：带入$\pi(x)=\sum_{y\in S} \pi(y)p(y,x)$有$\pi(n)=2/3\pi(n-1) \Rightarrow \pi(n)=(2/3)^n\pi(0)$, $\because \sum_{i=1}^\infty \pi(i)=1 \Rightarrow $ $\pi(n)=1/3(2/3)^n$

例：证明recurrent

$p(n,n+1)=p,p(n,0)=1-p$，证明是recurrent。
首先证明0是recurrent的。第一次返回0的次数记为$N_j=\min\{n>0:X_n=j\}$，则如果是recurrent，则$P(N_0<\infty)=1$,$P(N_0=n|X_0=0)=p^{n-1}(1-p)$ $\therefore f_0=\sum_k P(N_0=k|X_0=0)=P(N_0<\infty|X_0=0)=\sum_{n=1}^\infty p^{n-1}(1-p)=1/(1-p)(1-p)=1$
法2：利用recurrent的定义$\sum_{n=1}^\infty P_{jj}^n=\infty$. 见2D random walk。

连续Markov

求生成矩阵

$a(x,y)$表示单位时间内，从$x$转移到$y$的速率，矩阵A为生成矩阵，其中$A_{ij}=a(i,j),(i\ne j)$，对角线上的元素使得每行和为0，表示从状态x离开的总速率。

求转移矩阵

$P_t=e^{tA}$，就是先分解成特征值（一般都会有一个0特征值）$PDP^{-1}$，然后做指数运算$P diag\{e^{d_1t},\ldots,e^{d_nt}\}P^{-1}$

求稳态分布

可以让$P_t$中$t\rightarrow \infty$，也可以根据生成矩阵和状态概率分布的关系$p'(t)=p(t)A$直接求解$\pi A=0$。

首次改变期望时间

从状态1出发，求首次改变期望的时间。由生成矩阵$A_{11}$表示离开1的速率，所以期望时间为$1/3$。

首次到达期望时间

从状态1出发，求首次到达状态4的时间的期望。从状态1到达状态4的速率是$A_{14}$，因此期望的时间是$1/A_{14}$

泊松过程和离散马尔科夫组成连续马尔科夫

Markov:$X_n$, Poisson:$N(t)$,证$Z(t)=X_{N(t)}$ CTMC.
证明: $P\{Z(s+t)=j|Z(s)=i,Z(u)=k,0\le u\le s\}$ $=P\{X_{N(s+t)}=j|X_{N(s)}=i,X_{N(u)}=k,0\le u\le s\}$ $=P\{X_{N(s+t)}=j|X_{N(s)}=i,0\le u\le s\}$ ($\because N(s) \ge N(u)$, then, by property of DTMC) $=P\{Z(s+t)=j|Z(s)=i\}$

Martingale

判断是否是Martingale

计算$E[Y_{n+1}|X_1,\ldots,X_n]$看是否等于$Y_n$. 注意加上$E[|Z_n|]<\infty$

常见模型

M/G/1 Queue

Interarrival times is exponential. let $X_n$ denote the number of customers left behind by the $n$th depar­ture. Also, let $Y_n$ denote the number of customers arriving during the service period of the $(n + 1)$st customer. We have $X_{n+1}=X_n-1+Y_n (X_n > 0);=Y_n (X_n=0)$. $P\{Y_n=j\}=\int_0^\infty e^{-\lambda x}(\lambda x)^j/j!dG(x)$. $\Rightarrow$ $P_{0j}=\int_0^\infty e^{-\lambda x}(\lambda x)^j/j!dG(x)$. $P_{ij}=\int_0^\infty e^{-\lambda x}(\lambda x)^{j-i+1}/(j-i+1)!dG(x)$,$(j\ge i-1, i\ge 1)$, $P_{ij}=0 $(otherwise).

G/M/1 Queue

Let $X_n$ denote the number of customers in the system as seen by the $n$th arrival. $P_{i,i+1-j}=\int_0^\infty e^{-\mu t}(\mu t)^j/j!dG(x)$, $j=0,\cdots,i$. $P_{i0}=\int_0^\infty \sum_{k=i+1}^\infty e^{-\mu t}(\mu t)^k/k!dG(x), i\ge 0$

Gambler’s Ruin Problem

$p_{0,0}=p_{N,N}=1,p_{i,i+1}=p=1-p_{i,i-1}$ 解：Let $f_i$ denote the probability that starting with i, the fortune will eventually reach N. We obtain: $f_i=pf_{i+1}+qf_{i-1}$ $\Rightarrow f_{i+1}-f_i=q/p(f_i-f_{i-1}),\ldots, f_N-f_{N-1}=(q/p)^{N-1}f_1$ $\Rightarrow f_i-f_1=f_1[q/p+(q/p)^2+\cdots+(q/p)^{i-1}]$ $\Rightarrow f_i=(1-(q/p)^i)/(1-(q/p)^N),if p\ne 1/2;=i/N elif p=1/2$.终止为0的概率为$1-f_i$

Alarm Clock Problem

n个闹钟服从$b_1,\ldots,b_n$的指数分布。$P(T_i>t)=\exp(-b_i t)$。随机变量$T=\min\{T_1,\ldots,T_n\}$ $P(T\ge t)=P(T_1\ge t)P(T_2\ge t)\cdots P(T_n\ge t)=\exp(-(b_1+\cdots+b_n)t)$// $T_1$先响概率：$P(T_1=T)=\int_0^\infty P(T_2>t,\cdots,T_n>t)P(T_1=t)dt$ $=\int_0^\infty \exp(-(b_2+\cdots+b_n)t)b_1\exp(-b_1 t)dt=b_1/(b_1+\cdots+b_n)$

Absolute Value of Simple Random Walk

$S_n=\sum_1^nX_n$, $P\{X_i =1\}=p$, $P\{X_i =-1\}=1-p=q$. Let $j=\max\{k:0\le k\le n,i_k=0\}$, $\therefore P\{S_n=i||S_n|=i,\cdots,|S_1|=i_1\}=$ $P\{S_n=i||S_n|=i,\cdots,|S_j|=0\}$, $\therefore P(S_n=i|...)=p^{(n-j)/2+i/2}q^{(n-j)/2-i/2}$ $\therefore P(S_n=-i|...)=p^{(n-j)/2-i/2}q^{(n-j)/2+i/2}$
$P(S_n=i|...)=P(S_n=i|...)/(P(S_n=i|...)+P(S_n=-i|...))$ $=p^i/(p^i+q^i)$ $\therefore P\{|S_{n+1}|=i+1||S_n|=i,|S_{n-1},\cdots,|S_1|\}$ $=P\{S_{n+1}=i+1|S_n=i\}p^i/(p^i+q^i)$ $+P\{S_{n+1}=-(i+1)|S_n=-i\}q^i/(p^i+q^i)$ $=(p^{i+1}+q^{i+1})/(p^i+q^i)$ $\therefore P_{i,i+1}=(p^{i+1}+q^{i+1})/(p^i+q^i)$ $=1-P_{i,i-1},i>0$ $P_{01}=1$

Simple Random Walk

$P_{i,i+1}=p=1-P_{i,i-1}$. Firstly, step number cannot be even, i.e. $P_{00}^{2n+1}=0$. $P_{00}^{2n}=\binom{2n}{n}p^n(1-p)^n$ $=\frac{(2n)!}{n!n!}(p(1-p))^n$. By Stirling, $P_{00}^{2n}\sim (4p(1-p))^n/\sqrt{\pi n}$. $\therefore $ if $\sum_{n=1}^\infty (4p(1-p))^n/\sqrt{\pi n}=\infty$ (only when $p=1/2$) it will be recurrent. otherwise transient.

Calculate steady state probabilities

联立两个方程$\pi=\pi P;\sum_j\pi_j=1$. 第一个方程有一个是冗余的，通过消元，将第一个方程化成如下形式

$$\begin{aligned} &\pi_0 = &0.080 &\pi_0 + &0.632 &\pi_1 + &0.264 &\pi_2 + &0.080 &\pi_3,\\ &\pi_1 = &0.184 &\pi_0 + &0.368 &\pi_1 + &0.368 &\pi_2 + &0.184 &\pi_3,\\ &\pi_2 = &0.368 &\pi_0 + & & &0.368 &\pi_2 + &0.368 &\pi_3,\\ &\pi_3 = &0.368 &\pi_0 + & & & & &0.368 &\pi_3,\\ &1 = & &\pi_0 + & &\pi_1 + & &\pi_2 + & &\pi_3. \end{aligned}$$

然后逐个用$\pi_0$去表示其他的，最后带入最后一个方程求出。

已知$p_{ij}$,求$\mu_{ij}$

利用$\mu_{ij}=1+\sum_{k\ne j}p_{ik}\mu_{kj}$

计算absorb概率

假设马氏链中存在absorb state记该状态为$k$，求从某点出发，被$k$吸住的概率。denote $f_{ik}$ as the probability of starting from $i$ and end in $k$. The recursive equation is $f_{ik}=\sum_j p_{ij}f_{jk}$(i到k的概率等于i先到j，再从j到k的概率对所有j求和)