返回题库

击中 {2

Expected Visits to State 1 Before Hitting {2, 4}

专题
Probability / 概率
难度
L6

题目详情

考虑一个马尔可夫链，状态空间为 Ω={0,1,2,3,4}\Omega = \{0, 1, 2, 3, 4\}，转移概率矩阵为

P=[0131313013013013121200012000120120120].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 出发，求在首次击中集合 {2,4}\{2,4\} 中任一状态之前，访问状态 1 的期望次数。

英文原题

Consider a Markov chain with state space Ω={0,1,2,3,4}\Omega = \{0, 1, 2, 3, 4\} and the transition probability matrix:

P=[0131313013013013121200012000120120120]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 number of times you will visit state 1 before hitting any of the states {2,4}\{2, 4\}.

解析

令 T=inf⁡{t≥0:Xt∈{2,4}}T=\inf\{t\ge 0: X_t\in\{2,4\}\}。我们要计算

N=#{t<T:Xt=1},E0[N].N=\#\{t<T: X_t=1\},\quad \mathbb{E}_0[N].

设 vi=Ei[N]v_i=\mathbb{E}_i[N]（从状态 ii 出发）。显然 v2=v4=0v_2=v_4=0。

对其他状态写一步递推：

  • 从 0：下一步以 1/31/3 到 1、2、3，因此
v0=13v1+13⋅0+13v3.v_0=\frac{1}{3}v_1+\frac{1}{3}\cdot 0+\frac{1}{3}v_3.
  • 从 1：当前已在 1，先计一次访问，然后以 1/31/3 到 0，1/31/3 到 2，1/31/3 到 4：
v1=1+13v0.v_1=1+\frac{1}{3}v_0.
  • 从 3：以 1/21/2 到 0，以 1/21/2 到 4：
v3=12v0.v_3=\frac{1}{2}v_0.

代回得

v0=13(1+13v0)+13⋅12v0=13+518v0.v_0=\frac{1}{3}\left(1+\frac{1}{3}v_0\right)+\frac{1}{3}\cdot\frac{1}{2}v_0 =\frac{1}{3}+\frac{5}{18}v_0.

因此

(1−518)v0=13⇒v0=613.\left(1-\frac{5}{18}\right)v_0=\frac{1}{3} \Rightarrow v_0=\frac{6}{13}.

答案：E0[N]=613\boxed{\mathbb{E}_0[N]=\frac{6}{13}}。

英文解析

to T=inf⁡{t≥0:Xt∈{2,4}}T=\inf\{t\ge 0: X_t\in\{2,4\}\}. We're going to calculate

N=#{t<T:Xt=1},E0[N].N=\#\{t<T: X_t=1\},\quad \mathbb{E}_0[N].

Set vi=Ei[N]v_i=\mathbb{E}_i[N] from status ii. Obviously v2=v4=0v_2=v_4=0.

Write a step-by-step recursion for other states:

  • From 0: the next step is 1/31/3 to 1, 2, 3, so
v0=13v1+13⋅0+13v3.v_0=\frac{1}{3}v_1+\frac{1}{3}\cdot 0+\frac{1}{3}v_3.
  • From 1: currently at 1, count the visits first, then use 1/31/3 to 0, 1/31/3 to 2, 1/31/3 to 4:
v1=1+13v0.v_1=1+\frac{1}{3}v_0.
  • From 3: from 1/21/2 to 0, from 1/21/2 to 4:
v3=12v0.v_3=\frac{1}{2}v_0.

Retrieved on behalf of

v0=13(1+13v0)+13⋅12v0=13+518v0.v_0=\frac{1}{3}\left(1+\frac{1}{3}v_0\right)+\frac{1}{3}\cdot\frac{1}{2}v_0 =\frac{1}{3}+\frac{5}{18}v_0.

Therefore,

(1−518)v0=13⇒v0=613.\left(1-\frac{5}{18}\right)v_0=\frac{1}{3} \Rightarrow v_0=\frac{6}{13}.

Answer: E0[N]=613\boxed{\mathbb{E}_0[N]=\frac{6}{13}}.