IS Math-2023-03

题目来源：Problem 3 日期：2024-08-13 题目主题：Math-概率论-生成函数与递推关系

解题思路

这道题目涉及到随机过程、生成函数（generating function）、递推关系（recurrence relation）以及期望值（expected value）的计算。题目描述了一个基于独立同分布（i.i.d.）的随机过程：我们在一条线上从左到右随机放置圆形石头和方形石头，直到出现连续的 $M$ 个方形石头时停止。要解决这一问题，我们需要通过以下步骤进行分析：

1. 递推关系的推导： 首先，基于概率转移分析，从一个状态转移到下一个状态的概率推导出对应的递推关系。这些递推关系可以帮助我们描述每个状态下达到停止条件的概率。

2. 生成函数的应用： 利用生成函数 $A_k(t)$ 来表示这些概率序列，将递推关系转换为生成函数形式，从而简化计算并最终求解。

3. 期望值的计算： 通过生成函数的导数，我们可以直接计算出随机变量 $L$ 的期望值 $\mathbb{E}[L]$，从而解决题目要求的期望值问题。

Solution

(1) Calculate the mean and variance of $L$ for $M=1$

When $M=1$, the stopping condition is to place the first square stone. The process stops immediately after the first square stone is placed. Thus, the number of stones placed, $L$, is a random variable representing the total number of stones when the first square stone appears.

Let $X_i$ be the indicator random variable that the $i$-th stone is square:

$$X_i=\{\begin{array}{ll}1& \text{if the i-th stone is □},\\ 0& \text{if the i-th stone is ◯}.\end{array}$$

The probability that the first square stone appears at the $n$-th position is:

$$P(L=n)=(1-q{)}^{n-1}q$$

The expected value (mean) of $L$ is:

$$\mathbb{E}[L]=\sum _{n=1}^{\infty }n\cdot P(L=n)=\sum _{n=1}^{\infty }n\cdot (1-q{)}^{n-1}q$$

We can use the identity:

$$\sum _{n=1}^{\infty }n{x}^{n-1}=\frac{1}{(1-x{)}^2}\text{ for }|x|<1$$

Substituting $x=1-q$, we get:

$$\mathbb{E}[L]=\frac{1}{q}$$

To calculate the variance of $L$, we first compute $\mathbb{E}[L^2]$:

$$\mathbb{E}[L^2]=\sum _{n=1}^{\infty }{n}^2\cdot P(L=n)=\sum _{n=1}^{\infty }{n}^2\cdot (1-q{)}^{n-1}q$$

Using the identity:

$$\sum _{n=1}^{\infty }{n}^2{x}^{n-1}=\frac{1+x}{(1-x{)}^3}\text{ for }|x|<1$$

We obtain:

$$\mathbb{E}[L^2]=\frac{1+q}{q^2}$$

Finally, the variance of $L$ is given by:

$$\mathrm{Var}(L)=\mathbb{E}[L^2]-(\mathbb{E}[L]{)}^2=\frac{1+q}{q^2}-\frac{1}{q^2}=\frac{1-q}{q^2}$$

(2) Obtain the recurrence relation that $A_k(t)$ satisfies

1. Recurrence Relation for $a_{kn}$

First, let’s start with the recurrence relation for the sequence $a_{kn}$. We know that $a_{kn}$ is the probability that, starting from state $C_k$ (with $k$ consecutive square stones at the right end), the stopping condition (i.e., achieving $M$ consecutive square stones) is met after placing exactly $n$ stones.

Let’s analyze the possible scenarios:

• Case 1: Placing a Circle Stone $◯$

  • If a circle stone is placed, the sequence of square stones is interrupted, and the system transitions to state $C_0$.
  • The probability of placing a circle stone is $1-q$.
  • Given that we are now in state $C_0$, the probability that the stopping condition is met after placing $n-1$ more stones is $a_{0,n-1}$.
  • Hence, the contribution to $a_{kn}$ from this scenario is $(1-q)\cdot a_{0,n-1}$.

• Case 2: Placing a Square Stone $\square$

  • If a square stone is placed, the system transitions to state $C_{k+1}$ with probability $q$, unless $k=M-1$, in which case the process stops.
  • If the process transitions to $C_{k+1}$, the probability that the stopping condition is met after placing $n-1$ more stones is $a_{k+1,n-1}$.
  • Hence, the contribution to $a_{kn}$ from this scenario is $q\cdot a_{k+1,n-1}$ for $k<M-1$.

Putting these cases together, we obtain the recurrence relation for $a_{kn}$ when $k<M-1$:

$$a_{kn}=(1-q)\cdot a_{0,n-1}+q\cdot a_{k+1,n-1}$$

And for $k=M-1$, since placing another square stone stops the process:

$$a_{M-1,n}=(1-q)\cdot a_{0,n-1}+q\cdot {\delta }_{n,1}$$

where ${\delta }_{n,1}$ is the Kronecker delta, which is 1 if $n=1$ (indicating the process stops with the placement of the final square stone) and 0 otherwise.

2. Transition from $a_{kn}$ to $A_k(t)$ via Generating Functions

Now, let’s see how this recurrence relation for $a_{kn}$ translates into a recurrence relation for the generating function $A_k(t)$.

The generating function $A_k(t)$ is defined as:

$$A_k(t)=\sum _{n=0}^{\infty }{t}^n{a}_{kn}$$

This generating function $A_k(t)$ encodes the entire sequence $a_{kn}$ into a single function of $t$, where each coefficient of $t^n$ corresponds to the probability $a_{kn}$.

To translate the recurrence relation for $a_{kn}$ into one for $A_k(t)$, we follow these steps:

• Substitute the recurrence relation for $a_{kn}$ into the definition of $A_k(t)$:

  Consider the generating function for $k<M-1$:

  $$A_k(t)=\sum _{n=0}^{\infty }{t}^n{a}_{kn}$$

  Using the recurrence relation for $a_{kn}$:

  $$A_k(t)=\sum _{n=0}^{\infty }{t}^n\left[(1-q)\cdot a_{0,n-1}+q\cdot a_{k+1,n-1}\right]$$

  This can be split into two sums:

  $$A_k(t)=(1-q)\sum _{n=0}^{\infty }{t}^n{a}_{0,n-1}+q\sum _{n=0}^{\infty }{t}^n{a}_{k+1,n-1}$$

• Shift the index of summation for each series:

  • For the first sum (involving $a_{0,n-1}$), shift the index by setting $m=n-1$:

    $$\sum _{n=0}^{\infty }{t}^n{a}_{0,n-1}=t\sum _{m=0}^{\infty }{t}^m{a}_{0,m}=t{A}_0(t)$$

  • For the second sum (involving $a_{k+1,n-1}$), shift the index similarly:

    $$\sum _{n=0}^{\infty }{t}^n{a}_{k+1,n-1}=t\sum _{m=0}^{\infty }{t}^m{a}_{k+1,m}=t{A}_{k+1}(t)$$

• Combine the terms:

  Substituting back into the expression for $A_k(t)$:

  $$A_k(t)=t\left[(1-q)A_0(t)+q{A}_{k+1}(t)\right]$$

  This gives us the recurrence relation for $A_k(t)$ when $k<M-1$.

• Special Case $k=M-1$:

  For $k=M-1$, since the system stops once another square stone is placed:

  $$A_{M-1}(t)=\sum _{n=0}^{\infty }{t}^n\left[(1-q)\cdot a_{0,n-1}+q\cdot {\delta }_{n,1}\right]$$

  The second sum simplifies to $qt$, since it corresponds to placing the final square stone and stopping:

  $$A_{M-1}(t)=t[(1-q)A_0(t)+q]$$

3. Summary

• The recurrence relation for $a_{kn}$ gives us a way to calculate each probability in the sequence.
• By converting this relation into a generating function $A_k(t)$, we leverage the power of generating functions to work with an entire sequence at once.
• The operations in the recurrence relation (like adding probabilities or multiplying by $t$) translate directly into operations on the generating function, giving us the recurrence relation for $A_k(t)$.

Thus, the final recurrence relations for the generating functions are:

• For $k<M-1$:

  $$A_k(t)=t[(1-q)A_0(t)+q{A}_{k+1}(t)]$$

• For $k=M-1$:

  $$A_{M-1}(t)=t[(1-q)A_0(t)+q]$$

(3) Obtain $A_k(t)$ as a function of $q$, $M$, $t$, and $k$ using an Iterative Expansion Method

Step 1: Express the Recurrence Relation

We are given the recurrence relation:

$$A_k(t)=t\left[q{A}_{k+1}(t)+(1-q)A_0(t)\right]$$

This equation shows that the generating function $A_k(t)$ depends on the next generating function $A_{k+1}(t)$ and the constant $A_0(t)$, scaled by $t$.

Step 2: Iteratively Expand the Recurrence

To solve for $A_k(t)$, we can expand the recurrence relation iteratively. Begin by substituting $A_{k+1}(t)$ back into the equation:

$$A_k(t)=t\left[q\left(t\left[q{A}_{k+2}(t)+(1-q)A_0(t)\right]\right)+(1-q)A_0(t)\right]$$

This expands to:

$$A_k(t)=t(1-q)A_0(t)+t^{2}q(1-q)A_0(t)+t^2{q}^2{A}_{k+2}(t)$$

Continuing this process $n$ times, we get:

$$A_k(t)=A_0(t)t(1-q)\sum _{i=0}^n(tq{)}^i+(tq{)}^{n+1}{A}_{k+n+1}(t)$$

Step 3: Use the Stopping Condition at $k=M$

We know that at $k=M$, the process stops, so $A_M(t)=1$. By choosing $n=M-k-1$, we stop at $k=M$:

$$A_k(t)=A_0(t)t(1-q)\sum _{i=0}^{M-k-1}(tq{)}^i+(tq{)}^{M-k}$$

Since the sum is a finite geometric series, we simplify it:

$$A_k(t)=A_0(t)t(1-q)\frac{1-(tq{)}^{M-k}}{1-tq}+(tq{)}^{M-k}$$

Step 4: Simplify $A_0(t)$

We have the equation for $A_0(t)$:

$$A_0(t)\left[1-t(1-q)\frac{1-(tq{)}^M}{1-tq}\right]=(tq{)}^M$$

Simplify the term in the brackets:

$$A_0(t)\left[\frac{1-t(1-q)+t(1-q)(tq{)}^M}{1-tq}\right]=(tq{)}^M$$

This simplifies to:

$$A_0(t)\cdot \frac{1-t(1-q)\left[1-(tq{)}^M\right]}{1-tq}=(tq{)}^M$$

Now, solve for $A_0(t)$:

$$A_0(t)=\frac{(tq{)}^M\cdot (1-tq)}{1-t(1-q)\left[1-(tq{)}^M\right]}$$

Thus, the simplified expression for $A_0(t)$ is:

$$A_0(t)=\frac{(tq{)}^M(1-tq)}{1-t(1-q)\left[1-(tq{)}^M\right]}$$

Step 5: Express $A_k(t)$

Now that we have $A_0(t)$, we can substitute it back into the formula for $A_k(t)$:

$$A_k(t)=t^{M-k}{q}^{M-k}+A_0(t)\cdot t(1-q)\cdot \frac{1-(tq{)}^{M-k}}{1-tq}$$

Substituting the expression for $A_0(t)$:

$$A_k(t)=t^{M-k}{q}^{M-k}+\frac{(tq{)}^M(1-tq)}{1-t(1-q)\left[1-(tq{)}^M\right]}\cdot t(1-q)\cdot \frac{1-(tq{)}^{M-k}}{1-tq}$$

This is the general expression for the generating function $A_k(t)$, now fully expressed as a function of $q$, $M$, $t$, and $k$.

(4) Calculate the Mean of $L$

Certainly! Let’s re-derive the expected value $\mathbb{E}[L]$ for the random variable $L$ by differentiating the generating function $A_0(t)$ and then evaluating at $t=1$.

Step 1: Restate the Generating Function $A_0(t)$

We start with the generating function for $A_0(t)$ derived earlier:

$$A_0(t)=\frac{(tq{)}^M(1-tq)}{1-t(1-q)\left[1-(tq{)}^M\right]}$$

Step 2: Differentiate $A_0(t)$

We want to find $A_0^{\prime }(t)$ by differentiating $A_0(t)$ with respect to $t$. We use the quotient rule for differentiation:

$$A_0^{\prime }(t)=\frac{g^{\prime }(t)h(t)-g(t)h^{\prime }(t)}{[h(t){]}^2}$$

where:

• $g(t)=(tq{)}^M(1-tq)$
• $h(t)=1-t(1-q)\left[1-(tq{)}^M\right]$

Differentiate $g(t)$

$$g^{\prime }(t)=M{q}^M{t}^{M-1}(1-tq)-q(tq{)}^M$$

Differentiate $h(t)$

$$h^{\prime }(t)=-(1-q)\left[1-(tq{)}^M\right]+tM(1-q)q^M{t}^{M-1}$$

Simplifying:

$$h^{\prime }(t)=-(1-q)\left[1-(tq{)}^M\right]+M(1-q)q^M{t}^M$$

Step 3: Evaluate $A_0^{\prime }(1)$

We substitute $t=1$ into the derivative to find $\mathbb{E}[L]=A_0^{\prime }(1)$.

First, let’s calculate $g(1)$ and $h(1)$:

• $g(1)=q^M(1-q)$
• $h(1)=1-(1-q)(1-q^M)=q+(1-q)q^M$

And their derivatives at $t=1$:

• $g^{\prime }(1)=q^M[M(1-q)-q]$
• $h^{\prime }(1)=(1-q)\left[M{q}^M-(1-q^M)\right]$

Now, substitute these into the quotient rule formula:

$$A_0^{\prime }(1)=\frac{q^M[M(1-q)-q]\cdot [q+(1-q)q^M]-q^M(1-q)\cdot \left[M{q}^M-(1-q^M)\right]}{[q+(1-q)q^M{]}^2}$$

Step 4: Evaluate $A_0^{\prime }(1)$ for $M=1$

For $M=1$:

• $g(1)=q(1-q)$
• $g^{\prime }(1)=q(1-q)-q^2=q(1-q-q)=q(1-2q)$
• $h(1)=q$
• $h^{\prime }(1)=(1-q)[q-(1-q)]=(1-q)(2q-1)$

The derivative becomes:

$$A_0^{\prime }(1)=\frac{q(1-2q)\cdot q-q(1-q)\cdot (2q-1)}{q^2}=\frac{q^2(1-2q)-q(1-q)(2q-1)}{q^2}$$

Simplify:

$$A_0^{\prime }(1)=\frac{q(1-2q)-(1-q)(2q-1)}{q}$$

Expanding:

$$A_0^{\prime }(1)=\frac{q-2q^2-2q+2q^2+q-1}{q}=\frac{q-1}{q}=\frac{1}{q}$$

So for $M=1$, $\mathbb{E}[L]=\frac{1}{q}$.

Conclusion

For $M=1$, the expected value $\mathbb{E}[L]$ simplifies to $\frac{1}{q}$, which matches the known result from geometric distributions. This confirms that the simplified expression $\mathbb{E}[L]=\frac{1}{q}$ is correct.

知识点

生成函数递推关系概率论期望

解题技巧和信息

1. 生成函数的技巧： 生成函数是处理序列和递推关系的强大工具，特别是在随机过程和组合问题中。它将一个序列编码为一个函数，通过函数的操作（如求导）可以直接得到序列的期望、方差等统计量。

2. 递推关系的建立： 递推关系的建立依赖于状态转移的分析，在处理与随机过程相关的问题时，明确状态转移的每一步及其对应的概率是至关重要的。

3. 求导计算期望： 当我们得到了生成函数后，通过对生成函数在 $t=1$ 处求导，能够快速计算出相关随机变量的期望值，这是一种非常有效的计算方法。

难点思路

1. 递推关系的推导： 在推导 $a_{kn}$ 的递推关系时，需要对状态之间的转移以及每种转移的概率进行细致的分析。特别是在理解和区分不同状态的转移路径时，容易产生混淆，需要特别注意每种转移的概率及其后续影响。

2. 生成函数的构建和化简： 生成函数的构建是从递推关系到最终解的一大步，这里需要细心地将每一步的递推关系正确地转换为生成函数的形式。生成函数的化简过程中，特别是在递推式的递归展开和合并时，需要耐心并确保每一项的正确性。

3. 最终期望值的计算： 虽然生成函数导数的计算理论上相对直接，但涉及到复杂的分数和多项式运算时，仍然需要小心处理符号和分母化简，确保最终结果的正确性。

这些步骤需要对概率论中的生成函数和递推关系有深入的理解，同时也需要在细节处理上保持耐心和准确性。

重点词汇

• Generating function 生成函数
• Recurrence relation 递推关系
• Expected value 期望
• Variance 方差

参考资料

1. Sheldon Ross, A First Course in Probability, Chapter 7, Generating Functions.
2. William Feller, An Introduction to Probability Theory and Its Applications, Chapter 13, Random Walks.