IS Math-2018-03

题目来源：Problem 3 日期：2024-07-22 题目主题：Math-概率论-马尔可夫链

具体题目

Let $z_n$ and $w_n$ $(n=0,1,2,\dots )$ be complex numbers. Consider a bag that contains two red cards and one white card. First, take one card from the bag and return it to the bag. $z_{k+1}$ $(k=0,1,2,\dots )$ is generated in the following manner based on the color of the card taken.

$$z_{k+1}=\{\begin{array}{ll}i{z}_k& \text{if a red card was taken,}\\ -i{z}_k& \text{if a white card was taken.}\end{array}$$

Next, take one card from the bag again and return it to the bag. $w_{k+1}$ is generated in the following manner based on the color of the card taken.

$$w_{k+1}=\{\begin{array}{ll}-i{w}_k& \text{if a red card was taken,}\\ i{w}_k& \text{if a white card was taken.}\end{array}$$

Here, each card is independently taken with equal probability. The initial state is $z_0=1$ and $w_0=1$. Thus, $z_n,w_n$ are the values after repeating the series of the above two operations $n$ times starting from the state of $z_0=1$ and $w_0=1$. Here, $i$ is the imaginary unit.

Answer the following questions.

1. Show that $\mathrm{Re}(z_n)=0$ if $n$ is odd, and that $\mathrm{Im}(z_n)=0$ if $n$ is even. Here, $\mathrm{Re}(z)$ and $\mathrm{Im}(z)$ represent the real part and the imaginary part of $z$ respectively.

2. Let $P_n$ be the probability of $z_n=1$, and $Q_n$ be the probability of $z_n=i$. Find recurrence equations for $P_n$ and $Q_n$.

3. Find the probabilities of $z_n=1$, $z_n=i$, $z_n=-1$, and $z_n=-i$ respectively.

4. Show that the expected value of $z_n$ is ${\left(\frac{i}{3}\right)}^n$.

5. Find the probability of $z_n=w_n$.

6. Find the expected value of $z_n+w_n$.

7. Find the expected value of $z_n{w}_n$.

正确解答

Question 1

Prove that $\mathrm{Re}(z_n)=0$ if $n$ is odd, and that $\mathrm{Im}(z_n)=0$ if $n$ is even.

Proof: We can prove this by mathematical induction.

Base cases:

• When $n=0$, $z_0=1$, so $\mathrm{Re}(z_0)=1$ and $\mathrm{Im}(z_0)=0$, which satisfies the condition for even $n$.
• When $n=1$, $z_1$ can be either $i$ or $-i$, both of which have $\mathrm{Re}(z_1)=0$, satisfying the condition for odd $n$.

Inductive step: Assume that for some $k\ge 1$, $\mathrm{Re}(z_k)=0$ if $k$ is odd and $\mathrm{Im}(z_k)=0$ if $k$ is even.

Consider the case for $k+1$:

• If $k$ is odd, then $z_k=bi$ (where $b$ is real). Then $z_{k+1}$ is either $i(bi)=-b$ or $-i(bi)=b$. In either case, $z_{k+1}$ is real, so $\mathrm{Im}(z_{k+1})=0$.
• If $k$ is even, then $z_k=a$ (where $a$ is real). Then $z_{k+1}$ is either $ia$ or $-ia$. In either case, $z_{k+1}$ is purely imaginary, so $\mathrm{Re}(z_{k+1})=0$.

Therefore, by induction, the statement holds for all $n\ge 0$.

Question 2

To find the recurrence equations for $P_n$ and $Q_n$, we need to determine how the probabilities transition from one state to the next.

Let $P_n$ be the probability that $z_n=1$, and $Q_n$ be the probability that $z_n=i$. We will analyze the transitions for both even and odd $n$.

For even $n$:

• If $z_n=1$, then $z_{n+1}$ can be either $i$ or $-i$.
• If $z_n=-1$, then $z_{n+1}$ can be either $i$ or $-i$.

Therefore,

$$P_{n+1}=\mathbb{P}(z_{n+1}=1)=0$$ $$Q_{n+1}=\mathbb{P}(z_{n+1}=i)=\frac{2}{3}{P}_n+\frac{1}{3}(1-P_n)=\frac{1}{3}+\frac{1}{3}{P}_n$$

For odd $n$:

• If $z_n=i$, then $z_{n+1}$ can be either $1$ or $-1$.
• If $z_n=-i$, then $z_{n+1}$ can be either $1$ or $-1$.

Therefore,

$$P_{n+1}=\mathbb{P}(z_{n+1}=1)=\frac{1}{3}{Q}_n+\frac{2}{3}(1-Q_n)=\frac{2}{3}-\frac{1}{3}{Q}_n$$ $$Q_{n+1}=\mathbb{P}(z_{n+1}=i)=0$$

We will first express $P_{n+2}$ in terms of $P_n$:

• For even $n$, consider the step from $P_n$ to $Q_{n+1}$:

$$Q_{n+1}=\frac{1}{3}(1+P_n)$$

Then from $Q_{n+1}$ to $P_{n+2}$ (since $n+1$ is odd and $n+2$ is even):

$$P_{n+2}=\frac{2}{3}-\frac{1}{3}{Q}_{n+1}$$

Substituting $Q_{n+1}$ in terms of $P_n$ and simplifying, we get:

$$P_{n+2}=\frac{2}{3}-\frac{1}{9}-\frac{1}{9}{P}_n=\frac{6}{9}-\frac{1}{9}-\frac{1}{9}{P}_n=\frac{5}{9}-\frac{1}{9}{P}_n$$

So the recurrence relation for $P_n$ is:

$$P_{n+2}=\frac{5}{9}-\frac{1}{9}{P}_n$$

Next, we express $Q_{n+2}$ in terms of $Q_n$:

• For odd $n$, consider the step from $Q_n$ to $P_{n+1}$:

$$P_{n+1}=\frac{2}{3}-\frac{1}{3}{Q}_n$$

Then from $P_{n+1}$ to $Q_{n+2}$ (since $n+1$ is even and $n+2$ is odd):

$$Q_{n+2}=\frac{1}{3}(1+P_{n+1})$$

Substituting $P_{n+1}$ in terms of $Q_n$ and simplifying, we get:

$$Q_{n+2}=\frac{5}{9}-\frac{1}{9}{Q}_n$$

So the recurrence relation for $Q_n$ is:

$$Q_{n+2}=\frac{5}{9}-\frac{1}{9}{Q}_n$$

In summary, the recurrence relations for $P_n$ and $Q_n$ are:

$$P_{n+2}=\frac{5}{9}-\frac{1}{9}{P}_n,Q_n=0\text{when}n\text{is even,}$$ $$P_n=0,Q_{n+2}=\frac{5}{9}-\frac{1}{9}{Q}_n\text{when}n\text{is odd.}$$

Question 3

Find the probabilities of $z_n=1$, $z_n=i$, $z_n=-1$, and $z_n=-i$ respectively.

Let’s denote:

• $P_n=\mathbb{P}(z_n=1)$
• $Q_n=\mathbb{P}(z_n=i)$
• $R_n=\mathbb{P}(z_n=-1)$
• $S_n=\mathbb{P}(z_n=-i)$

From the conclusions of Questions 1 and 2, we know that:

• For even $n$: $Q_n=S_n=0$
• For odd $n$: $P_n=R_n=0$

We’ll solve for $P_n$ (even $n$) and $Q_n$ (odd $n$) separately:

For $P_n$ (even $n$): We have the recurrence relation: $P_{n+2}=\frac{5}{9}-\frac{1}{9}{P}_n$

Let’s find the general term. Assume $P_n=a{\left(-\frac{1}{9}\right)}^{n/2}+b$ for some constants $a$ and $b$.

Substituting into the recurrence relation:

$a{\left(-\frac{1}{9}\right)}^{(n+2)/2}+b=\frac{5}{9}-\frac{1}{9}\left(a{\left(-\frac{1}{9}\right)}^{n/2}+b\right)$

Simplifying:

$-\frac{1}{9}a{\left(-\frac{1}{9}\right)}^{n/2}+b=\frac{5}{9}-\frac{1}{9}a{\left(-\frac{1}{9}\right)}^{n/2}-\frac{1}{9}b$

Equating coefficients:

$b=\frac{5}{9}-\frac{1}{9}b⟹b=\frac{1}{2}$

Using the initial condition $P_0=1$:

$1=a+\frac{1}{2}⟹a=\frac{1}{2}$

Therefore, for even $n$:

$P_n=\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}$

$R_n=\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}$

For $Q_n$ (odd $n$): We have the recurrence relation: $Q_{n+2}=\frac{5}{9}-\frac{1}{9}{Q}_n$

From Question 2, we know that $Q_1=\frac{2}{3}$.

Using the same method as for $P_n$, we assume $Q_n=c{\left(-\frac{1}{9}\right)}^{(n-1)/2}+d$ for odd $n$.

Substituting into the recurrence relation and solving, we get:

$d=\frac{1}{2}$ and $c=\frac{1}{6}$

Therefore, for odd $n$:

$Q_n=\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}$

$S_n=\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}$

In summary:

• For even $n$: $P_n=\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}$ $R_n=\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}$ $Q_n=S_n=0$

• For odd $n$: $Q_n=\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}$ $S_n=\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}$ $P_n=R_n=0$

These formulas give the probabilities of $z_n$ being 1, i, -1, and -i for any non-negative integer $n$.

Summary

The probabilities for $z_n$ taking each possible value are as follows:

For even $n$:

$$\begin{array}{rl}\mathbb{P}(z_n=1)& =\frac{1}{2}{\left(\frac{i}{3}\right)}^n+\frac{1}{2}\\ \mathbb{P}(z_n=-1)& =\frac{1}{2}-\frac{1}{2}{\left(\frac{i}{3}\right)}^n\\ \mathbb{P}(z_n=i)& =0\\ \mathbb{P}(z_n=-i)& =0\end{array}$$

For odd $n$:

$$\begin{array}{rl}\mathbb{P}(z_n=1)& =0\\ \mathbb{P}(z_n=-1)& =0\\ \mathbb{P}(z_n=i)& =\frac{1}{6}{\left(\frac{i}{3}\right)}^{n-1}+\frac{1}{2}\\ \mathbb{P}(z_n=-i)& =\frac{1}{2}-\frac{1}{6}{\left(\frac{i}{3}\right)}^{n-1}\end{array}$$

Question 4

Show that the expected value of $z_n$ is ${\left(\frac{i}{3}\right)}^n$.

Proof: We’ll prove this by induction.

Base case: When $n=0$, $\mathbb{E}[z_0]=1={\left(\frac{i}{3}\right)}^0$, which holds true.

Inductive step: Assume $\mathbb{E}[z_k]={\left(\frac{i}{3}\right)}^k$ for some $k\ge 0$. We need to prove that $\mathbb{E}[z_{k+1}]={\left(\frac{i}{3}\right)}^{k+1}$.

$$\begin{array}{rl}\mathbb{E}[z_{k+1}]& =\mathbb{P}(\text{red card})\cdot \mathbb{E}[i{z}_k]+\mathbb{P}(\text{white card})\cdot \mathbb{E}[-i{z}_k]\\ & =\frac{2}{3}\cdot i\mathbb{E}[z_k]+\frac{1}{3}\cdot (-i)\mathbb{E}[z_k]\\ & =\frac{2i}{3}\cdot {\left(\frac{i}{3}\right)}^k-\frac{i}{3}\cdot {\left(\frac{i}{3}\right)}^k\\ & =\frac{i}{3}\cdot {\left(\frac{i}{3}\right)}^k\\ & ={\left(\frac{i}{3}\right)}^{k+1}\end{array}$$

Thus, by the principle of mathematical induction, $\mathbb{E}[z_n]={\left(\frac{i}{3}\right)}^n$ for all non-negative integers $n$.

Question 5

Find the probability of $z_n=w_n$.

To solve this, we need to consider the possible values of $z_n$ and $w_n$ for both odd and even $n$.

For even $n$:

$z_n$ can be 1 or -1, while $w_n$ can be 1 or -1.

$\mathbb{P}(z_n=w_n)=\mathbb{P}(z_n=1)\cdot \mathbb{P}(w_n=1)+\mathbb{P}(z_n=-1)\cdot \mathbb{P}(w_n=-1)$

From Question 3, we know that for even $n$:

$\mathbb{P}(z_n=1)=\mathbb{P}(w_n=1)=\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}$

$\mathbb{P}(z_n=-1)=\mathbb{P}(w_n=-1)=\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}$

Therefore, for even $n$:

$$\begin{array}{rl}\mathbb{P}(z_n=w_n)& ={\left(\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}\right)}^2+{\left(\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}\right)}^2\\ & =\frac{1}{4}{\left(-\frac{1}{9}\right)}^n+\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{4}+\frac{1}{4}{\left(-\frac{1}{9}\right)}^n-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{4}\\ & =\frac{1}{2}{\left(-\frac{1}{9}\right)}^n+\frac{1}{2}\end{array}$$

For odd $n$:

$z_n$ can be $i$ or $-i$, while $w_n$ can be $-i$ or $i$ (note the opposite order).

$\mathbb{P}(z_n=w_n)=\mathbb{P}(z_n=i)\cdot \mathbb{P}(w_n=i)+\mathbb{P}(z_n=-i)\cdot \mathbb{P}(w_n=-i)$

From Question 3, we know that for odd $n$:

$\mathbb{P}(z_n=i)=\mathbb{P}(w_n=-i)=\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}$

$\mathbb{P}(z_n=-i)=\mathbb{P}(w_n=i)=\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}$

Therefore, for odd $n$:

$$\begin{array}{rl}\mathbb{P}(z_n=w_n)& =\left(\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}\right)\cdot \left(\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}\right)\\ & +\left(\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}\right)\cdot \left(\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}\right)\\ & =2\cdot \left(\frac{1}{4}-\frac{1}{36}{\left(-\frac{1}{9}\right)}^{n-1}\right)\\ & =\frac{1}{2}-\frac{1}{18}{\left(-\frac{1}{9}\right)}^{n-1}\\ & =\frac{1}{2}+\frac{1}{2}{\left(-\frac{1}{9}\right)}^n\end{array}$$

In conclusion, for all $n\ge 0$:

$$\mathbb{P}(z_n=w_n)=\frac{1}{2}{\left(-\frac{1}{9}\right)}^n+\frac{1}{2}$$

Certainly. I’ll continue answering questions 6 and 7 in English, based on the previous information and solutions.

Question 6

Find the expected value of $z_n+w_n$.

To solve this, we can use the linearity of expectation:

$\mathbb{E}[z_n+w_n]=\mathbb{E}[z_n]+\mathbb{E}[w_n]$

From Question 4, we know that $\mathbb{E}[z_n]={\left(\frac{i}{3}\right)}^n$.

For $w_n$, we can use a similar approach to prove that $\mathbb{E}[w_n]={\left(-\frac{i}{3}\right)}^n$. The proof would be almost identical to that for $z_n$, with the only difference being the sign of $i$ in the recurrence relation.

Therefore,

$$\begin{array}{rl}\mathbb{E}[z_n+w_n]& =\mathbb{E}[z_n]+\mathbb{E}[w_n]\\ & ={\left(\frac{i}{3}\right)}^n+{\left(-\frac{i}{3}\right)}^n\\ & ={\left(\frac{i}{3}\right)}^n+(-1{)}^n{\left(\frac{i}{3}\right)}^n\\ & =\{\begin{array}{ll}2{\left(\frac{i}{3}\right)}^n& \text{if }n\text{ is even}\\ 0& \text{if }n\text{ is odd}\end{array}\end{array}$$

Thus, the expected value of $z_n+w_n$ is $2{\left(\frac{i}{3}\right)}^n$ when $n$ is even, and 0 when $n$ is odd.

Question 7

Find the expected value of $z_n{w}_n$.

To solve this, we need to consider the possible values of $z_n$ and $w_n$ for both odd and even $n$.

For even $n$:

$z_n$ can be 1 or -1, and $w_n$ can be 1 or -1.

$$\begin{array}{rl}\mathbb{E}[z_n{w}_n]& =1\cdot \mathbb{P}(z_n=1,w_n=1)+(-1)\cdot \mathbb{P}(z_n=1,w_n=-1)\\ & +(-1)\cdot \mathbb{P}(z_n=-1,w_n=1)+1\cdot \mathbb{P}(z_n=-1,w_n=-1)\end{array}$$

From Question 3 and the independence of $z_n$ and $w_n$, we know:

$\mathbb{P}(z_n=1)=\mathbb{P}(w_n=1)=\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}$

$\mathbb{P}(z_n=-1)=\mathbb{P}(w_n=-1)=\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}$

Substituting these probabilities:

$$\begin{array}{rl}\mathbb{E}[z_n{w}_n]& ={\left(\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}\right)}^2-\left(\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}\right)\left(\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}\right)\\ & -\left(\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}\right)\left(\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}+\frac{1}{2}\right)+{\left(\frac{1}{2}-\frac{1}{2}{\left(-\frac{1}{9}\right)}^{n/2}\right)}^2\\ & ={\left(-\frac{1}{9}\right)}^n\end{array}$$

For odd $n$:

$z_n$ can be $i$ or $-i$, and $w_n$ can be $-i$ or $i$.

$$\begin{array}{rl}\mathbb{E}[z_n{w}_n]& =(-1)\cdot \mathbb{P}(z_n=i,w_n=-i)+1\cdot \mathbb{P}(z_n=i,w_n=i)\\ & +1\cdot \mathbb{P}(z_n=-i,w_n=-i)+(-1)\cdot \mathbb{P}(z_n=-i,w_n=i)\end{array}$$

From Question 3 and the independence of $z_n$ and $w_n$, we know:

$\mathbb{P}(z_n=i)=\mathbb{P}(w_n=-i)=\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}$

$\mathbb{P}(z_n=-i)=\mathbb{P}(w_n=i)=\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}$

Substituting these probabilities:

$$\begin{array}{rl}\mathbb{E}[z_n{w}_n]& =-{\left(\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}\right)}^2+\left(\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}\right)\left(\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}\right)\\ & +\left(\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}\right)\left(\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}+\frac{1}{2}\right)-{\left(\frac{1}{2}-\frac{1}{6}{\left(-\frac{1}{9}\right)}^{(n-1)/2}\right)}^2\\ & =-{\left(-\frac{1}{9}\right)}^n\end{array}$$

Therefore, for all $n\ge 0$:

$$\mathbb{E}[z_n{w}_n]=(-1{)}^n{\left(-\frac{1}{9}\right)}^n={\left(\frac{1}{9}\right)}^n$$

In conclusion, the expected value of $z_n{w}_n$ is ${\left(\frac{1}{9}\right)}^n$ for all non-negative integers $n$.

知识点

概率论马尔可夫链复数期望值 递归数学归纳法

难点解题思路

这道题的主要难点在于理解复数的旋转性质和概率的递推关系，特别是要注意奇偶步数的区别以及所有可能的状态转移。关键是要认识到 $z_n$ 和 $w_n$ 的变化实际上是在复平面上的旋转，而且每次旋转的概率是固定的，但是奇偶步数会影响可能的状态。这样就可以建立起完整的递推关系，并利用数学归纳法来证明一些性质。

解题技巧和信息

1. 在处理复数序列时，考虑其实部和虚部的变化规律，特别注意奇偶步数的影响。
2. 在建立递推关系时，要仔细考虑所有可能的状态转移，注意奇偶步数可能导致的不同情况。
3. 在计算期望时，如果两个随机变量是独立的，那么它们的乘积的期望等于各自期望的乘积。
4. 对于周期性的问题，考虑分类讨论（如奇数步和偶数步）是很重要的。
5. 在解决马尔可夫链问题时，写出完整的状态转移方程可以帮助理清思路，但要注意可能存在的周期性。
6. 在处理复杂的递推关系时，尝试找出模式可以帮助我们得到一般形式的解。

重点词汇

• Markov chain 马尔可夫链
• recurrence equation 递推方程
• mathematical induction 数学归纳法
• expected value 期望值
• imaginary unit 虚数单位
• complex plane 复平面
• rotation 旋转
• state transition 状态转移
• independence (of random variables) （随机变量的）独立性
• parity (odd/even) 奇偶性
• pattern recognition 模式识别

参考资料

1. Probability and Random Processes by Geoffrey Grimmett and David Stirzaker, Chapter 6 (Markov Chains)
2. Complex Analysis by Elias M. Stein and Rami Shakarchi, Chapter 1 (Complex Numbers)
3. Introduction to Probability by Joseph K. Blitzstein and Jessica Hwang, Chapter 10 (Markov Chains)
4. Discrete-Time Markov Chains by J. R. Norris, Chapter 1 (Discrete-time Markov chains)
5. A First Course in Probability by Sheldon Ross, Chapter 4 (Conditional Probability)