马尔可夫相依伯努利试验

在许多应用概率论问题中，随机现象状态随时间的演变是一个关注点。例如，假设有两个瓮（I和II），每个瓮中装有一个白球和一个黑球。同时从每个瓮中抽取一个球，并将其放入另一个瓮中。人们常常关心这样的问题：经过100次这样的操作后，瓮I中有两个白球的概率是多少？马尔可夫¹链理论适用于这类问题。

马尔可夫链理论涉及物理和社会科学的每一个领域（参见A. T. Bharucha-Reid即将出版的著作《马尔可夫过程理论及其应用导论》；关于马尔可夫链理论在社会或心理现象描述中的应用，请参阅下一段引用的Kemeny和Snell的著作）。关于马尔可夫链理论有大量的文献。在本节和下一节中，我们只能提供一个简要的介绍。

该理论的优秀基础性阐述可见于W. Feller的著作《概率论及其应用导论》（第二版，Wiley，纽约，1957年）以及J. G. Kemeny和J. L. Snell的著作《有限马尔可夫链》（Van Nostrand，普林斯顿，新泽西，1959年）。关于第6节中所作断言的证明，读者可参考这些书籍。

独立伯努利试验概念的自然推广是马尔可夫相依伯努利试验的概念。给定一个只有两种可能结果（用 $s$ 或 $f$ 表示，分别代表“成功”或“失败”）的实验的 $n$ 次试验，我们记得，如果对于任何整数 $k (1$ 到 $n - 1)$ 以及分别依赖于第一次、第二次、…、第 $(k + 1)$ 次试验的 $k + 1$ 个事件 $A_{1}$ 、 $A_{2}, \dots, A_{k + 1}$ ，有则称这些试验为独立伯努利试验。如果代替(5.1)，下式成立则我们将这些试验定义为马尔可夫相依伯努利试验。用语言来说，(5.2)表明，在第 $k$ 次试验时，任何依赖于下一次试验的事件 $A_{k + 1}$ 的条件概率，不依赖于过去试验中发生的情况，而只依赖于当前发生的情况。有时人们会说这些试验没有记忆。

假设量 $在第次试验成功的条件下，第次试验成功的概率，在第次试验失败的条件下，第次试验成功的概率，在第次试验失败的条件下，第次试验失败的概率，在第次试验成功的条件下，第次试验失败的概率，$ 与 $k$ 无关。那么我们称这些试验为马尔可夫相依重复伯努利试验。

例5A。设对 $n$ 个连续日子的天气进行观测。令 $s$ 描述下雨的日子，令 $f$ 描述不下雨的日子。假设天气观测构成一系列马尔可夫相依伯努利试验（或者，用第6节的术语来说，一个具有两个状态的马尔可夫链）。那么 $P (s, s)$ 是在今天下雨的条件下，明天下雨的概率； $P (s, f)$ 是在今天下雨的条件下，明天不下雨的概率； $P (f, f)$ 是在今天不下雨的条件下，明天不下雨的概率；而 $P (f, s)$ 是在今天不下雨的条件下，明天下雨的概率。现在很自然地会问，比如，在今天不下雨的条件下，后天下雨的概率是多少；我们将这个概率记为 $P_{2} (f, s)$ ，并推导出它的公式。

在独立重复伯努利试验的情况下，一旦我们知道了每次试验成功的概率 $p$ ， $n$ 次试验的样本描述空间上的概率函数 $P [\cdot]$ 就完全确定了。在马尔可夫相依重复伯努利试验的情况下，只需指定量 $第一次试验成功的概率，第一次试验失败的概率，$ 以及(5.3)中的条件概率就足够了。任何事件的概率都可以用这些量来计算。例如，对于 $k = 1, 2, \dots, n$ ，令 $第次试验成功的概率，第次试验失败的概率。$

对于 $k = 2, 3, \dots, n$ ，量 $p_{k} (s)$ 满足以下方程：

为了证明(5.6)，我们推理如下：如果 $A_{k}$ 是第 $k$ 次试验成功的事件，那么

由(5.7)以及事实(5.8) $P (s, f) = 1 - P (s, s) P (f, s) = 1 - P (f, f), p_{k} (f) = 1 - p_{k} (s)$ ，即可得到(5.6)。

方程(5.6)构成了 $p_{k} (s)$ 的一个递推关系，称为差分方程。在本节中，我们假设

利用理论练习4.5，由(5.6)和(5.9)可得，对于 $k = 1, 2, \dots, n$ ，

通过在(5.10)中交换 $s$ 和 $f$ 的角色，我们类似地得到，对于 $k = 1, 2, \dots, n$ ，

容易验证，(5.10)和(5.11)中的表达式之和为1，正如它们应该的那样。

在许多涉及马尔可夫相依重复伯努利试验的问题中，我们不知道第一次试验成功的概率 $p_{1} (s)$ 。我们只能计算以下量

$在第一次试验成功的条件下，第次试验成功的条件概率，在第一次试验成功的条件下，第次试验失败的条件概率，在第一次试验失败的条件下，第次试验失败的条件概率，在第一次试验失败的条件下，第次试验成功的条件概率。$

由于因此只需得到 $P_{k} (s, s)$ 和 $P_{k} (f, f)$ 的公式。

用我们得到(5.6)的同样方法，我们得到

利用理论练习4.5，由(5.14)和(5.9)可得，对于 $k = 1, 2, \dots, n$ ，这可以简化为

通过交换 $s$ 和 $f$ 的角色，我们类似地得到利用(5.13)，我们得到方程(5.16)到(5.19)代表了马尔可夫相依伯努利试验理论中的基本结论（在(5.9)成立的情况下）。

例5B。考虑一个传输数字0和1的通信系统。每个传输的数字必须经过几个阶段，在每个阶段，进入的数字离开时保持不变的概率为 $p$ 。假设该系统由三个阶段组成。一个以0进入系统的数字被（i）第三阶段传输为0，（ii）每个阶段都传输为0（即从未从0改变）的概率是多少？对 $p = \frac{1}{3}$ 计算这些概率。

解

在观察数字通过通信系统的过程中，我们观察的是一个4元组 $(z_{1}, z_{2}, z_{3}, z_{4})$ ，其第一个分量 $z_{1}$ 为1或0，取决于进入系统的数字是1还是0。对于 $i = 2, 3, 4$ ，分量 $z_{i}$ 等于1或0，取决于离开第 $i$ 阶段的数字是1还是0。我们现在使用前面的公式，将 $s$ 等同于1，将0等同于 $f$ 。我们的基本假设是

一个以0进入系统的数字被第三阶段传输为0的概率由下式给出如果 $p = \frac{1}{3}$ ，那么 $P_{3} (0, 0) = \frac{1}{2} [1 - {(\frac{1}{3})}^{3}] = \frac{13}{27}$ 。一个以0进入系统的数字被每个阶段都传输为0的概率由乘积给出 $P (0, 0) P (0, 0) P (0, 0) = p^{3} = {(\frac{1}{3})}^{3} = \frac{1}{27} .$

例5C。假设通过例5B中描述的通信系统（其中 $p = \frac{1}{3}$ ）传输的数字是由一个随机机制选择的；数字0被选中的概率为 $\frac{1}{3}$ ，数字1被选中的概率为 $\frac{2}{3}$ 。一个由第三阶段传输为0的数字实际上是以0进入系统的条件概率是多少？

解

一个由第三阶段传输为0的数字实际上是以0进入系统的条件概率由下式给出

为了证明(5.22)，注意 $p_{1} (0) P_{3} (0, 0)$ 是第一个数字为0且第四个数字为0的概率，而 $p_{4} (0)$ 是第四个数字为0的概率。现在，在假设 $P (1, 1) = P (0, 0) = \frac{1}{3}, p_{1} (0) = \frac{1}{3}, p_{1} (1) = \frac{2}{3},$ 下，由(5.10)可得

由(5.21)和(5.23)可知，离开系统为0的数字实际上是以0进入系统的条件概率为 $\frac{1}{3} \cdot \frac{13}{27} / \frac{41}{81} = \frac{13}{41}$

Example 5D . Let us use the considerations of examples 5B and 5C to solve the following problem, first proposed by the celebrated cosmologist A. S. Eddington (see W. Feller, “The Problem of $n$ liars and Markov chains”, American Mathematical Monthly , Vol. 58 (1951), pp. 606–608). “If $A, B$ , $C, D$ each speak the truth once in 3 times (independently), and $A$ affirms that $B$ denies that $C$ declares that $D$ is a liar, what is the probability that $D$ was telling the truth”?

Solution

We consider a sample description space of 4-tuples $(z_{1}, z_{2}, z_{3}, z_{4})$ in which $z_{1}$ equals 0 or 1, depending on whether $D$ is truthful or a liar, $z_{2}$ equals 0 or 1, depending on whether the statement made by $C$ implies that $D$ is truthful or a liar, $z_{3}$ equals 0 or 1, depending on whether the statement made by $B$ implies that $D$ is truthful or a liar, and $z_{4}$ equals 0 or 1, depending on whether the statement made by $A$ implies that $D$ is truthful or a liar. The sample description space thus defined constitutes a series of Markov dependent repeated Bernoulli trials with $P (0, 0) = P (1, 1) = \frac{1}{3}, p_{1} (0) = \frac{1}{3}, p_{1} (1) = \frac{2}{3} .$

The persons $A, B, C$ , and $D$ can be regarded as forming a communications system. We are seeking the conditional probability that the digit entering the system was 0 (which is equivalent to $D$ being truthful), given that the digit transmitted by the third stage was 0 (if $A$ affirms that $B$ denies that $C$ declares that $D$ is a liar, then $A$ is asserting that $D$ is truthful). In view of example $5 C$ , the required probability is $\frac{13}{41}$ .

Statistical Equilibrium. For large values of $k$ the values of $p_{k} (s)$ and $p_{k} (f)$ are approximately given by

To justify (5.24) , use (5.10) and (5.11) and the fact that (5.9) implies that $lim_{k \to \infty} [P (s, s) + P (f, f) - 1]^{k - 1} = 0.$

Equation (5.24) has the following significant interpretation: After a large number of Markov dependent repeated Bernoulli trials has been performed, one is in a state of statistical equilibrium, in the sense that the probability $p_{k} (s)$ of success on the kth trial is the same for all large values of $k$ and indeed is functionally independent of the initial conditions, represented $b y$ $p_{1} (s)$ .

From (5.24) one sees that the trials are asymptotically fair in the sense that approximately for large values of $k$ if and only if

Example 5E . If the communications system described in example 5B consists of a very large number of stages, then half the digits transmitted by the system will be 0’s, irrespective of the proportion of 0’s among the digits entering the system.

Exercises

5.1 . Consider a series of Markov dependent Bernoulli trials such that $P (s, s) = \frac{1}{3}, P (f, f) = \frac{1}{2}$ . Find $P_{3} (s, f), P_{3} (f, s)$ .

Answer

$P_{3} (s, f) = \frac{31}{5}, P_{3} (f, s) = \frac{3}{7} \frac{1}{2}$ .

5.2 . Consider a series of Markov dependent Bernoulli trials such that $P (s, s) = \frac{1}{4}, P (f, f) = \frac{1}{2}, p_{1} (s) = \frac{1}{3}$ . Find $p_{3} (s), p_{3} (f)$ .

5.3 . Consider a series of Markov dependent Bernoulli trials such that $P (s, s) = \frac{1}{2}, P (f, f) = \frac{3}{4}, p_{1} (s) = \frac{1}{2}$ . Find the conditional probability of a success at the first trial, given that there was a success at the fourth trial.

Answer

$\frac{2}{4} \frac{2}{3}$ .

5.4 . Consider a series of Markov dependent Bernoulli trials such that $P (s, s) = \frac{1}{2}, P (f, f) = \frac{3}{4}$ . Find $lim_{k \to \infty} p_{k} (s)$ .

5.5 . If $A, B, C$ , and $D$ each speak the truth once in 3 times (independently), and $A$ affirms that $B$ denies that $C$ denies that $D$ is a liar, what is the probability that $D$ was telling the truth?

Answer

0.35.

5.6 . Suppose the probability is equal to $p$ that the weather (rain or no rain) on any arbitrary day is the same as on the preceding day. Let $p_{1}$ be the probability of rain on the first day of the year. Find the probability $p_{n}$ of rain on the $n$ th day. Evaluate the limit of $p_{n}$ as $n$ tends to infinity.

5.7 . Consider a game played as follows: a group of $n$ persons is arranged in a line. The first person starts a rumor by telling his neighbor that the last person in line is a nonconformist. Each person in line then repeats this rumor to his neighbor; however, with probability $p > 0$ , he reverses the sense of the rumor as it is told to him. What is the probability that the last person in line will be told he is a nonconformist if (i) $n = 5$ , (ii) $n = 6$ , (iii) $n$ is very large?

Answer

(i) $\frac{1}{2} + \frac{1}{2} (1 - 2 p)^{3}$ ; (ii) $\frac{1}{2} + \frac{1}{2} (1 - 2 p)^{4}$ ; (iii) $\frac{1}{2}$ if $p < 1$ .

5.8 . Suppose you are confronted with 2 coins, $A$ and $B$ . You are to make $n$ tosses, using the coin you prefer at each toss. You will be paid 1 dollar for each time the coin falls heads. Coin $A$ has probability $\frac{1}{2}$ of falling heads, and coin $B$ has probability $\frac{1}{4}$ of falling heads. Unfortunately, you are not told which of the coins is coin $A$ . Consequently, you decide to toss the coins according to the following system. For the first toss you choose a coin at random. For all succeeding tosses you select the coin used on the preceding toss if it fell heads, and otherwise switch coins. What is the probability that coin $A$ will be the coin tossed on the $n$ th toss if (i) $n = 2$ , (ii) $n = 4$ , (iii) $n = 6$ , (iv) $n$ is very large? What is the probability that the coin tossed on the $n$ th toss will fall heads if (i) $n = 2$ , (ii) $n = 4$ , (iii) $n = 6$ , (iv) $n$ is very large? Hint: On each trial let $s$ denote the use of coin $A$ and $f$ denote the use of coin $B$ .

5.9 . A certain young lady is being wooed by a certain young man. The young lady tries not to be late for their dates too often. If she is late on 1 date, she is $90 %$ sure to be on time on the next date. If she is on time, then there is a $60 %$ chance of her being late on the next date. In the long run, how often is she late?

Answer

$\frac{2}{5}$ .

5.10 . Suppose that people in a certain group may be classified into 2 categories (say, city dwellers and country dwellers; Republicans and Democrats; Easterners and Westerners; skilled and unskilled workers, and so on). Let us consider a group of engineers, some of whom are Easterners and some of whom are Westerners. Suppose that each person has a certain probability of changing his status: The probability that an Easterner will become a Westerner is 0.04, whereas the probability that a Westerner will become an Easterner is 0.01. In the long run, what proportion of the group will be (i) Easterners, (ii) Westerners, (iii) will move from East to West in a given year, (iv) will move from West to East in a given year? Comment on your answers.

The theory of Markov chains derives its name from the celebrated Russian probabilist, A. A. Markov (1856–1922). ↩︎