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

标签：

• Tokyo-University
• Absorbing-Random-Walk
• Gamblers-Ruin-and-Hitting-Probability

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.