IS Math-2014-03

题目来源：Problem 3 日期：2024-08-09 题目主题: Math-概率论-随机变量序列&马尔科夫链

解题思路

这道题涉及一系列独立随机变量的分析，以及通过递推公式和极限分析来计算期望和方差。题目涉及到的知识点包括：随机变量的方差计算，独立事件的概率计算，马尔科夫链的状态转移概率，递推序列的解法，几何级数求和等。

Solution

Question 1.1

1. Variance of $x_i$:

   Given $x_i$ takes value 1 with probability $p$ and value 0 with probability $1-p$, the variance of $x_i$ is calculated as follows:

   $$\mathrm{Var}(x_i)=E[x_i^2]-(E[x_i]{)}^2$$

   Since $x_i$ is a Bernoulli random variable:

   $$E[x_i]=p$$ $$E[x_i^2]=E[x_i]=p$$

   Thus, the variance is:

   $$\mathrm{Var}(x_i)=p-p^2=p(1-p)$$

   Probability that $x_0 = x_1 = 1:

   Since $x_0$ and $x_1$ are independent:

   $$P(x_0=1\text{ and }{x}_1=1)=P(x_0=1)\cdot P(x_1=1)=p\cdot p=p^2$$

Question 1.2

We are given a sequence of independent random variables $\{x_i\}$, where each $x_i$ takes the value 1 with probability $p$ and the value 0 with probability $1-p$. The goal is to determine the probability that $x_k=1$, where $k$ is the smallest integer such that $x_k=x_{k+1}$.

To solve this problem, we use a state transition approach based on the following reasoning:

1. Independence and Identical Distribution:

   • Each random variable $x_i$ is independent and identically distributed (i.i.d.), with $P(x_i=1)=p$ and $P(x_i=0)=1-p$.
   • Due to this independence and identical distribution, the sequence starting from any index $n$, whether $x_0,x_1,\dots$ or $x_1,x_2,\dots$, is probabilistically identical. This means the statistical properties of the sequence do not change, regardless of where we start.

2. Recursive Nature:

   • Since $k$ is defined as the first index where $x_k=x_{k+1}$, the problem inherently has a recursive structure.
   • For example, if we know $x_0=0$ and $x_1=1$, we can treat the sequence starting from $x_1$ as a new sequence, similar to the original sequence, and ask the same question again: when do we first have $x_k=x_{k+1}$?

3. Probabilistic Equivalence:

   • Because the sequences starting from different indices $n$ are probabilistically equivalent, the probability $P(x_k=1)$ can be expressed using recurrence relations that relate the probabilities starting from different initial conditions.
   • Specifically, by analyzing the transitions between states (e.g., $x_0=0$ to $x_1=1$), we can express the desired probability in terms of itself, leading to a solvable set of recursive equations.

Step 1: Define Conditional Probabilities

Let:

• $\alpha =P(x_k=1\mid x_0=0)$
• $\beta =P(x_k=1\mid x_0=1)$

We need to compute these probabilities by considering the conditions for $x_k=x_{k+1}$.

Step 2: Set Up the Recurrence Relations

1. Case 1: $x_0=0$

   • If $x_1=1$, then the sequence $x_0,x_1$ cannot immediately satisfy $x_k=x_{k+1}$ for $k=0$. Therefore, the first $k$ satisfying $x_k=x_{k+1}$ must occur for some $k\ge 1$.
   • Since the sequence $x_1,x_2,\dots$ is probabilistically identical to the sequence starting from $x_0$, the probability $P(x_k=1\mid x_0=0)$ can be expressed in terms of $P(x_k=1\mid x_1=1)$, which we denote as $\beta$. Thus:
   $$\alpha =p\times \beta$$

   where $p$ is the probability that $x_1=1$.

2. Case 2: $x_0=1$

   • If $x_1=0$, then $x_k=x_{k+1}$ cannot occur at $k=0$ because $x_0$ and $x_1$ are different. The sequence $x_1,x_2,\dots$ again has the same probabilistic structure as the original sequence, but now starting from $x_1=0$.
   • The probability $P(x_k=1\mid x_0=1)$ can thus be split into two scenarios:
     1. If $x_1=0$: The problem reduces to finding $x_k=1$ starting from $x_1=0$, which happens with probability $\alpha$.
     2. If $x_1=1$: In this case, $k=0$, and $x_k=x_0=1$, which happens with probability $p$.
   • Therefore:
   $$\beta =(1-p)\times \alpha +p$$

   The $p$ term corresponds to the immediate match $x_k=x_0=1$ when $x_1=1$.

Step 3: Solve the Recurrence Relations

Using the equations derived from the cases above:

$$\alpha =p\times \beta$$ $$\beta =(1-p)\times \alpha +p$$

Substitute $\alpha =p\times \beta$ into the second equation:

$$\beta =p(1-p)\beta +p$$

Expanding and simplifying:

$$\beta =p(1-p)\beta +p$$ $$\beta (1-p+p^2)=p$$ $$\beta =\frac{p}{1-p+p^2}$$

Using $\alpha =p\times \beta$, we find:

$$\alpha =\frac{p^2}{1-p+p^2}$$

Step 4: Compute $P(x_k=1)$

Finally, the probability that $x_k=1$ is given by:

$$P(x_k=1)=\alpha \times (1-p)+\beta \times p$$

Substitute the values of $\alpha$ and $\beta$:

$$P(x_k=1)=\frac{p^2}{1-p+p^2}\times (1-p)+\frac{p}{1-p+p^2}\times p$$

Simplifying:

$$P(x_k=1)=\frac{p^2(1-p)+p^2}{1-p+p^2}=\frac{p^2(1-p+1)}{1-p+p^2}=\frac{p^2(2-p)}{1-p+p^2}$$

This final result simplifies further:

$$P(x_k=1)=\frac{2p^2-p^3}{1-p+p^2}$$

Thus, the probability that $x_k=1$ when $x_k=x_{k+1}$ is:

$$\boxed{P(x_k=1)=\frac{2p^2-p^3}{1-p+p^2}}$$

This concludes the derivation and solution.

Question 2.1

We are given the recursive sequence:

$$y_{i+1}=y_i+\alpha (x_i-y_i)$$

Expanding this sequence iteratively, we obtain:

$$y_n=(1-\alpha )y_{n-1}+\alpha x_{n-1}$$

Using induction, it can be shown:

$$y_n=(1-\alpha {)}^n+\sum _{i=0}^{n-1}(1-\alpha {)}^{n-i-1}\alpha x_i$$

Question 2.2

Expected Value $E_n$:

Taking the expectation on both sides:

$$E_n=E[(1-\alpha {)}^n]+\sum _{i=0}^{n-1}E[(1-\alpha {)}^{n-i-1}\alpha x_i]$$

Since $E[x_i]=p$, we have:

$$E_n=(1-\alpha {)}^n+p(1-(1-\alpha {)}^n)$$

Variance $V_n$:

The variance $V_n$ can be computed as:

$$V_n=\mathrm{Var}\left(\sum _{i=0}^{n-1}\alpha (1-\alpha {)}^{n-i-1}{x}_i\right)$$

Given independence of $x_i$:

$$V_n={\alpha }^2\sum _{i=0}^{n-1}(1-\alpha {)}^{2(n-i-1)}\mathrm{Var}(x_i)={\alpha }^{2}p(1-p)\sum _{i=0}^{n-1}(1-\alpha {)}^{2(n-i-1)}$$

This is a geometric series:

$$V_n=p(1-p)\left[\frac{{\alpha }^2(1-(1-\alpha {)}^{2n})}{1-(1-\alpha {)}^2}\right]$$

Question 2.3

We are asked to find the maximum value of $\alpha$ such that the condition $E_{\infty }-\sqrt{V_{\infty }}\ge \frac{1}{2}$ holds, where $E_{\infty }={\lim }_{n\to \infty }{E}_n$ and $V_{\infty }={\lim }_{n\to \infty }{V}_n$. Given that $\frac{1}{2}<p<\frac{3}{4}$.

Step 1: Calculate $E_{\infty }$

From the previous part, we have the expression for $E_n$:

$$E_n=(1-\alpha {)}^n+p(1-(1-\alpha {)}^n)$$

Taking the limit as $n\to \infty$:

$$E_{\infty }=\underset{n\to \infty }{\lim }\left[(1-\alpha {)}^n+p(1-(1-\alpha {)}^n)\right]$$

Since $(1-\alpha {)}^n\to 0$ as $n\to \infty$ (for $0<\alpha <1$):

$$E_{\infty }=p$$

Step 2: Calculate $V_{\infty }$

We found earlier that the variance $V_n$ is:

$$V_n=p(1-p)\left[\frac{{\alpha }^2(1-(1-\alpha {)}^{2n})}{1-(1-\alpha {)}^2}\right]$$

Taking the limit as $n\to \infty$:

$$V_{\infty }=p(1-p)\left[\frac{{\alpha }^2}{1-(1-\alpha {)}^2}\right]$$

Simplifying the denominator:

$$V_{\infty }=p(1-p)\left[\frac{{\alpha }^2}{\alpha (2-\alpha )}\right]=\frac{p(1-p)\alpha }{2-\alpha }$$

Step 3: Solve the Inequality

We need to satisfy the inequality:

$$E_{\infty }-\sqrt{V_{\infty }}\ge \frac{1}{2}$$

Substituting $E_{\infty }=p$ and $V_{\infty }=\frac{p(1-p)\alpha }{2-\alpha }$:

$$p-\sqrt{\frac{p(1-p)\alpha }{2-\alpha }}\ge \frac{1}{2}$$

Rearranging the inequality:

$$\sqrt{\frac{p(1-p)\alpha }{2-\alpha }}\le p-\frac{1}{2}$$

Square both sides:

$$\frac{p(1-p)\alpha }{2-\alpha }\le {\left(p-\frac{1}{2}\right)}^2$$

Multiply both sides by $(2-\alpha )$ to eliminate the fraction:

$$p(1-p)\alpha \le {\left(p-\frac{1}{2}\right)}^2(2-\alpha )$$

Expanding and solving for $\alpha$:

$$\alpha \le \frac{(p-\frac{1}{2}{)}^2\cdot 2}{p(1-p)+(p-\frac{1}{2}{)}^2}=\frac{2(p-\frac{1}{2}{)}^2}{\frac{1}{4}}=8(p-\frac{1}{2}{)}^2$$

Expanding the quadratic expression:

$$\alpha \le 8(p^2-p+\frac{1}{4})=8p^2-8p+2$$

Thus, the maximum value of $\alpha$ that satisfies the condition is:

$$\boxed{{\alpha }_{\text{max}}=8p^2-8p+2}$$

Equality is achieved when $p=\frac{1}{2}$, but for $\frac{1}{2}<p<\frac{3}{4}$, the expression increases, indicating that the maximum value of $\alpha$ approaches $8p^2-8p+2$ as $p$ approaches $\frac{3}{4}$.

Question 3

Given a sequence of random variables $z_0,z_1,z_2,\dots$ defined using $x_0,x_1,x_2,\dots$ as follows: if $x_j,x_{j+1}$ is the $i$-th pair of adjacent variables in $x_0,x_1,x_2,\dots$ such that $x_j=x_{j+1}$, then $z_i$ is defined by $z_i=x_j$. The goal is to obtain ${\lim }_{i\to \infty }{q}_i$, where $q_i=P(z_i=1)$.

Step 1: Understanding the Problem

The random variable $z_i$ is defined based on the pairs $(x_j,x_{j+1})$ in the sequence $x_0,x_1,x_2,\dots$. Each $z_i$ corresponds to the value of the $i$-th occurrence where $x_j=x_{j+1}$. The task is to determine the long-term probability $q_i=P(z_i=1)$ as $i$ becomes large.

Step 2: Define Conditional Probabilities

To analyze the probability $q_{i+1}$ in terms of $q_i$, we define:

• $\alpha =P(z_i=1\mid z_{i-1}=0)$: the probability that $z_i=1$ given that the previous $z_{i-1}$ was 0.
• $\beta =P(z_i=1\mid z_{i-1}=1)$: the probability that $z_i=1$ given that the previous $z_{i-1}$ was 1.

Step 3: Recurrence Relations

Using a similar approach as in Question 1.2:

1. Case 1: $z_{i-1}=0$

   If $z_{i-1}=0$, then the previous pair was $(0,0)$. The probability that $z_i=1$ (the next pair is $(1,1)$) is:

   $$\alpha =p\times \beta$$

2. Case 2: $z_{i-1}=1$

   If $z_{i-1}=1$, then the previous pair was $(1,1)$. The next $z_i$ can remain 1 if the next pair is $(1,1)$, or it can transition to 0 if the next pair is $(0,0)$. Therefore:

   $$\beta =(1-p)\times \alpha +p$$

Step 4: Solve the Recurrence Relations

From the recurrence relations:

$$\alpha =p\times \beta$$ $$\beta =(1-p)\times \alpha +p$$

Substitute $\alpha =p\times \beta$ into the second equation:

$$\beta =p(1-p)\beta +p$$

Simplifying:

$$\beta (1-p+p^2)=p$$ $$\beta =\frac{p}{1-p+p^2}$$

Substituting this into $\alpha =p\times \beta$:

$$\alpha =\frac{p^2}{1-p+p^2}$$

Step 5: Express $q_{i+1}$ in Terms of $q_i$

The probability $q_{i+1}$ can now be expressed as:

$$q_{i+1}=(1-q_i)\times \alpha +q_i\times \beta$$

Substituting the values of $\alpha$ and $\beta$:

$$q_{i+1}=(1-q_i)\times \frac{p^2}{1-p+p^2}+q_i\times \frac{p}{1-p+p^2}$$

Step 6: Simplify the Recursive Formula

Factor out the common denominator:

$$q_{i+1}=\frac{1}{1-p+p^2}\left[(1-q_i)\times p^2+q_i\times p\right]$$

Simplifying further:

$$q_{i+1}=\frac{p^2+q_i\times (p-p^2)}{1-p+p^2}$$

Step 7: Calculate the Limit

To find the long-term behavior, take the limit as $i\to \infty$:

$$\underset{i\to \infty }{\lim }{q}_i=q_{\infty }$$

At equilibrium, $q_{i+1}=q_i=q_{\infty }$:

$$q_{\infty }=\frac{p^2+q_{\infty }\times (p-p^2)}{1-p+p^2}$$

Solving for $q_{\infty }$:

$$q_{\infty }\times (1-p+p^2-(p-p^2))=p^2$$ $$q_{\infty }=\frac{p^2}{1-2p+2p^2}$$

Final Answer

Thus, the limit of the probability that $z_i=1$ as $i\to \infty$ is:

$$\boxed{\underset{i\to \infty }{\lim }{q}_i=\frac{p^2}{1-2p+2p^2}}$$

This expression gives the long-term probability for $z_i=1$ in terms of the original probability $p$.

知识点

期望值方差极限分析递推关系几何级数

难点思路

在 2.3 和 3 的解答中，重点在于处理极限分析和递推关系，特别是 2.3 中的不等式求解，需要仔细考虑每个条件下的最优值。在第 3 问中，通过理解随机变量的独立性和 i.i.d.属性，明确了 $q_i$ 的极限。

解题技巧和信息

1. 在处理极限问题时，理解随机变量的长尾效应和趋近稳定状态的条件非常重要。
2. 递推关系中，通过逐步展开和递推得到一般解，然后进行极限分析，是处理复杂随机过程的重要技巧。
3. 通过独立性分析，计算序列中各部分的概率，最终求得问题的全局概率。

重点词汇

1. Limit 极限
2. Maximum Value 最大值
3. Independent Identically Distributed (i.i.d.) 独立同分布
4. Recurrence Relation 递推关系
5. Geometric Series 几何级数