CBMS-2023-11

题目来源：Problem 11 日期：2024-07-11 题目主题：Math-概率论-随机过程

具体题目

Let $\{x_t|t=0,1,2,\dots \}$ 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\ne 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\ge 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$).

正确解答

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^{2}q+p^{2}q=2p^{2}q=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+p{q}^2+p{q}^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\ge 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$$

知识点

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

难点解题思路

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

解题技巧和信息

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

重点词汇

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

参考资料

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