Markov 链的基本概念

一个 Markov 链是概率空间上的一个以 \(E\) (至多可数) 为状态空间的随机序列 \(\{X_n: n\ge 0\}\), 它满足 Markov 性 (和时齐性). 在 Markov 链的情形下, Markov 性与强 Markov 性等价.

记 \(p^{(n)}_{x,y} = \mathbb P^x(X_n=y)\), 转移概率 \(p^{(1)}_{x,y}\) 简记为 \(p_{x,y}\). 转移概率满足 Chapman-Kolmogorov 方程.
记首中时 \(\tau_y = \inf\{n\ge1:X_n=y\}\), 约定 \(\inf\varnothing=\infty\). 令首达概率 \(f^{(n)}_{x,y} = \mathbb P^x(\tau_y=n)\).
若存在 \(n\ge 0\), 使得 \(p^{(n)}(x,y)>0\), 则称 \(x\) 可达 \(y\); 若互相可达则称互达. 若任意两状态互达, 则称 \(X\) 不可约 (irreducible).

状态 \(x\) 是常返的, if 满足下列条件 (这些条件是等价的).

• \(f_{x,x} = 1\);
• \(\mathbb P^x(\limsup\{X_n=x\})=1\);
• \(\sum_n p^{(n)}_{x,y}=\infty\).

否则称为暂留. 在一个互达等价类中, 要么所有状态常返, 要么所有状态暂留.

状态 \(x\) 的周期记为 \(d(x)\), 为 \(\{n\ge1:p^{(n)}_{x,x}>0 \}\) 的最大公因数, 约定空集时 \(d(x)=0\). 若 \(d(x)=1\), 则称 \(x\) 是非周期的 (aperiodic).

若 \(X\) 是不可约非周期的 Markov 链, 则

• 若 \(x\), \(y\) 互达, 则 \(d(x)=d(y)\).
• 对任意 \(x\), \(y\), 存在 \(N\), 对任意 \(n>N\), 有 \(p^{(n)}_{x,y}>0\).

若 \(\mathbb E^x \tau_x<\infty\), 则称 \(x\) 正常返, 否则称为零常返.
若 \(x\) 常返, 且 \(\lim_n p^{(n)}_{x,x}\) 存在, 则它等于 \(1/\mathbb E^x \tau_x\).

\(E\) 上一个概率分布 \((\pi_x:x\in E)\) 是转移矩阵 \(P\) 的平稳分布, if \(\pi P=\pi\) (把 \(\pi\) 看作行向量).

一个不可约非周期 Markov 链 \(X\) 有平稳分布 \(\pi\), 则

• \(X\) 常返;
• 对任意 \(x\), \(y\), \(\lim_n p^{(n)}_{x,y}=\pi_y\);
• 对任意 \(x\), \(\pi_x>0\).

例题. 来自 [1] p. 116 第 11 题, 原题可能是来自 Dimitri P. Bertsekas 的那本 Introduction to Probability.

An absent-minded professor has \(r\) umbrellas, used when commuting from home to work and back. If it rains and an umbrella is available, the professor takes it. If no umbrella is available, the professor gets wet. If it does not rain, the professor does not take the umbrella. It rains on a given commute with probability \(p\), independently for all days.

(1) What is the steady-state probability that the professor will get wet on a given day?

(2) Show that for any \(p\), 5 umbrellas can make sure that the professor does not get wet with probability greater than 0.95.

Solution. 用 \(X_n\) 表示他第 \(n\) 次出门时手边的伞的数目, 则这是一个 (时齐) 不可约 Markov 链.

\(p_{0,r}=1\).
\(p_{x,r-x} = 1-p\), \(p_{x,r+1-x} = p\), for \(x=1,\dots,r\).

\(\pi_0=(1-p)\pi_r\),
\(\pi_x=(1-p)\pi_{r-x}+p\pi_{r+1-x}\), for \(x=1,\dots,r-1\)
\(\pi_r=\pi_0+p\pi_1\).

可得平稳分布
\(\pi_0 = (1-p)/(1+r-p)\),
\(\pi_x = 1/(1+r-p)\) for \(x = 1,\dots,r\).

故淋湿的极限为 \(p(1-p)/(1+r-p)\).
5 把伞淋湿概率最大约为 0.0455.

References

[1] 应坚刚, 金蒙伟. (2017). 随机过程基础 (第二版) (pp. 98-116). 复旦大学出版社.

Markov 链的基本概念

原文：https://www.cnblogs.com/shiina922/p/10458890.html