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

标签：

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

Author

zephyr, 祭音Myyura

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$).

题目描述

随机序列 $\{x_t\mid t=0,1,2,\ldots\}$ 取非负整数值，并按下列规则演化：

• 若 $x_t>0$，则以概率 $p$ 令 $x_{t+1}=x_t+1$，以概率 $q=1-p$ 令 $x_{t+1}=x_t-1$；
• 若 $x_t=0$，则以概率 1 保持 $x_{t+1}=0$。

以下假设 $p\ne q$。对非负整数初值 $x_0=k$，定义

$$u_k^{(T)}=P(x_T=0\mid x_0=k).$$

回答下列问题：

1. 求 $P(x_3=2\mid x_0=1)$。

2. 求 $P(x_4=0\mid x_0=2)$。

3. 对 $k>0,T\ge1$，用 $u_{k+1}^{(T-1)}$ 与 $u_{k-1}^{(T-1)}$ 表示 $u_k^{(T)}$。

4. 令

   $$u_k=\lim_{T\to\infty}u_k^{(T)},$$

   由第 3 问推出 $\{u_k\}$ 满足的方程及边界条件。

5. 求使上述方程存在满足 $\lim_{k\to\infty}u_k=0$ 的解时 $p$ 的条件，并求相应 $u_k$；可尝试代入 $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 0 \to 0$: probability $q^2$ (state $0$ is absorbing)
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 + 2pq^3 = q^2(1+2pq)$$

(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}$$

Also, $u_0=1$ because state $0$ is absorbing.

(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 = pz^2 + (1-p)$$

This is a quadratic equation in $z$:

$$pz^2-z+q=0=(z-1)(pz-q)$$

The roots of this equation are:

$$z=1,\qquad z=\frac{q}{p}$$

Thus the general solution is $u_k=C_1+C_2(q/p)^k$. The conditions $u_0=1$ and $\lim_{k\to\infty}u_k=0$ can hold exactly when $q/p<1$, i.e. $p>1/2$. They then give $C_1=0$, $C_2=1$, so

$$u_k=\left(\frac{q}{p}\right)^k$$

When $p<1/2$, the absorption probability is $u_k=1$, which does not tend to $0$ as $k\to\infty$.

Knowledge

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

难点解题思路

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

解题技巧和信息

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

重点词汇

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

参考资料

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