马尔可夫链的期望击中时间

Expected Hitting Time in a Markov Chain

专题: Probability / 概率
难度: L4
来源: QuantQuestion

个人笔记

题目详情

考虑状态空间 $\Omega=\{0,1,2,3,4\}$ 的马尔可夫链，其转移矩阵为

P=\begin{bmatrix} 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{bmatrix}.

从状态 0 出发，求首次到达集合 $\{1,2,4\}$ 中任一状态的期望击中时间（步数）。

英文原题

Consider a Markov chain with state space $\Omega = \{0, 1, 2, 3, 4\}$ and the transition probability matrix
$P = \begin{bmatrix} 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{bmatrix}$
Starting from state 0, find the expected hitting time to any of the states $\{1, 2, 4\}$ .

解析

设 $h(i)$ 为从状态 $i$ 出发到达集合 $A=\{1,2,4\}$ 的期望步数。

边界： $h(1)=h(2)=h(4)=0$ 。

对 0 与 3 建方程：

从 0：下一步以 $1/3$ 到 1、2、3，因此

h(0)=1+\frac{1}{3}h(3).

从 3：下一步以 $1/2$ 到 0、以 $1/2$ 到 4，因此

h(3)=1+\frac{1}{2}h(0).

联立：

h(0)=1+\frac{1}{3}\left(1+\frac{1}{2}h(0)\right)=\frac{4}{3}+\frac{1}{6}h(0) \Rightarrow \frac{5}{6}h(0)=\frac{4}{3} \Rightarrow h(0)=\frac{8}{5}.

因此期望击中时间为 $\boxed{\frac{8}{5}}$ 。

英文解析

Set $h(i)$ to the expected number of steps to reach the set $A=\{1,2,4\}$ from the state $i$ .

Boundary: $h(1)=h(2)=h(4)=0$ .

Build equation for 0 and 3:

From 0: The next step is $1/3$ to 1, 2, 3, so

h(0)=1+\frac{1}{3}h(3).

From 3: The next step is $1/2$ to 0, and $1/2$ to 4, so

h(3)=1+\frac{1}{2}h(0).

United:

h(0)=1+\frac{1}{3}\left(1+\frac{1}{2}h(0)\right)=\frac{4}{3}+\frac{1}{6}h(0) \Rightarrow \frac{5}{6}h(0)=\frac{4}{3} \Rightarrow h(0)=\frac{8}{5}.

Therefore, the expected hit time is $\boxed{\frac{8}{5}}$ .