随机过程题型总结

By Z.H. Fu
切问录 www.fuzihao.org

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)\), $_{i=1}^(i)=1 $ \(\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}\). $$ 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求和)