Skip to content

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2022年8月実施 問題11

Author

zephyr

Description

Let \(\{x_t | t = 0, 1, 2, \ldots\}\) be a random sequence of non-negative integers generated by the following rules.

(i) If \(x_t > 0\), \(x_{t+1} = x_t + 1\) with probability \(p\), and \(x_{t+1} = x_t - 1\) with probability \(q = (1 - p)\).

(ii) If \(x_t = 0\), \(x_{t+1} = 0\) with probability 1.

In the following, \(p \neq q\) is assumed. Further, we define \(u_k^{(T)}\) as the probability that \(x_T = 0\) at time \(t = T\) with initial value \(x_0 = k\) (\(k\): a nonnegative integer). Answer the following questions.

(1) Answer the probability that \(x_3 = 2\) given \(x_0 = 1\).

(2) Answer the probability that \(x_4 = 0\) given \(x_0 = 2\).

(3) Express \(u_k^{(T)}\) using \(u_{k+1}^{(T-1)}\) and \(u_{k-1}^{(T-1)}\) (\(k > 0\), \(T \geq 1\)).

(4) Let \(u_k = \lim_{T \to \infty} u_k^{(T)}\). Derive the equations that the \(u_k\)s satisfy using (3).

(5) Answer the condition for \(p\) that the equations of (4) have a solution \(u_k\) with \(\lim_{k \to \infty} u_k = 0\), as well as the solution \(u_k\) (Examine the case: \(u_k = z^k\)).

Kai

(1) The probability that \(x_3 = 2\) given \(x_0 = 1\)

To find the probability that \(x_3 = 2\) given \(x_0 = 1\), we need to consider the different paths the process can take to reach from 1 to 2 in three steps.

The paths and their probabilities are:

  1. \(1 \to 2 \to 3 \to 2\): probability \(p \cdot p \cdot q\)
  2. \(1 \to 2 \to 1 \to 2\): probability \(p \cdot q \cdot p\)

Adding these probabilities together, we get:

\[ P(x_3 = 2 | x_0 = 1) = p^2q + p^2q = 2p^2q = 2p^2(1-p) = 2p^2 - 2p^3 \]

(2) The probability that \(x_4 = 0\) given \(x_0 = 2\)

To find the probability that \(x_4 = 0\) given \(x_0 = 2\), we consider the paths to reach 0 from 2 in four steps.

The paths and their probabilities are:

  1. \(2 \to 1 \to 0 \to 1 \to 0\): probability \(q \cdot q \cdot p \cdot q\)
  2. \(2 \to 1 \to 2 \to 1 \to 0\): probability \(q \cdot p \cdot q \cdot q\)
  3. \(2 \to 3 \to 2 \to 1 \to 0\): probability \(p \cdot q \cdot q \cdot q\)

Adding these probabilities together, we get:

\[ P(x_4 = 0 | x_0 = 2) = q^2 + pq^2 + pq^3 = q^2(1 + p + p^2) = (1-p)^2(1+p+p^2) = 1 - p - p^3 + p^4 \]

(3) Express \(u_k^{(T)}\) using \(u_{k+1}^{(T-1)}\) and \(u_{k-1}^{(T-1)}\) (\(k > 0\), \(T \geq 1\))

For \(k > 0\), the probability that \(x_T = 0\) given \(x_0 = k\) can be written in terms of the probabilities at \(T-1\):

\[ u_k^{(T)} = p \cdot u_{k+1}^{(T-1)} + q \cdot u_{k-1}^{(T-1)} = p \cdot u_{k+1}^{(T-1)} + (1-p) \cdot u_{k-1}^{(T-1)} \]

(4) Let \(u_k = \lim_{T \to \infty} u_k^{(T)}\). Derive the equations that the \(u_k\)s satisfy using (3)

As \(T \to \infty\), \(u_k\) becomes time-independent. Thus,

\[ u_k = p \cdot u_{k+1} + q \cdot u_{k-1} = p \cdot u_{k+1} + (1-p) \cdot u_{k-1} \]

(5) The condition for \(p\) that the equations of (4) have a solution \(u_k\) with \(\lim_{k \to \infty} u_k = 0\), as well as the solution \(u_k\) (Examine the case: \(u_k = z^k\))

Assume a solution of the form \(u_k = z^k\):

\[ z^k = p \cdot z^{k+1} + (1-p) \cdot z^{k-1} \]

Dividing by \(z^{k-1}\), we get:

\[ z^2 = p \cdot z + (1-p) \]

This is a quadratic equation in \(z\):

\[ z^2 - p \cdot z - (1-p) = 0 \]

The roots of this equation are:

\[ z = \frac{p \pm \sqrt{p^2 + 4p(1-p)}}{2} = \frac{p \pm \sqrt{p}}{2} \]

For the solution to converge to 0 as \(k \to \infty\), we need the root with the negative sign:

\[ z = \frac{p - \sqrt{p}}{2} \]

Therefore, the solution \(u_k\) is:

\[ u_k = \left(\frac{p - \sqrt{p}}{2}\right)^k \]

Knowledge

随机过程 马尔可夫链 概率计算

难点解题思路

  • 分析每个时间步的状态变化及其概率。
  • 考虑随机过程的限制条件如 \(x_t = 0\) 时的吸收状态。

解题技巧和信息

  • 分步计算状态转移概率。
  • 利用马尔可夫链的平稳状态来解答长时间行为问题。

重点词汇

  • random sequence 随机序列
  • probability 概率
  • Markov chain 马尔可夫链
  • absorbing state 吸收状态

参考资料

  1. Ross, S. M. (2007). Introduction to Probability Models. Chapter 4: Markov Chains.