08 抛硬币中某个固定字串会无穷次出现：用「不重叠的块」换来独立性 · 第3讲

这一页在讲什么

人话版一句话版

一直独立地抛公平硬币，任意给定的 0/1 字串 $w$ （长度 $ℓ ）$ 以概率 1 会出现无穷多次。证明的诀窍：把抛掷结果切成互不重叠的长度为 $ℓ$ 的块，「第 $j$ 块恰好是 $w 」$ 这些事件相互独立、概率都是 $2^{- ℓ} ，$ 于是第二 Borel–Cantelli 引理直接给出结论。

这是第 1 部分的最后一页，也是第二 Borel–Cantelli 引理（第 7 页）的第一个正式应用。它展示了使用第二引理时最常见的难点和对策：

难点：我们真正关心的事件（「 $w$ 从第 $n$ 位开始出现」）彼此重叠，因而不独立，第二引理不能直接用。
对策：主动扔掉一部分信息，只看互不重叠的块，换来独立性。我们只需要证明「出现无穷多次」，少数一些出现不影响结论。

先补基础

基础补课0/1 字串（binary word）

长度为 $ℓ$ 的二进制字串就是 $ℓ$ 个 0 或 1 排成的一列： $w = (w_{1}, w_{2}, \dots, w_{ℓ}) ，$ 每个 $w_{r} \in {0, 1} 。$ 例如 $w = 101$ （ $ℓ = 3 ）。$
长度为 $ℓ$ 的字串一共有 $2^{ℓ}$ 个：每一位有 2 种选法， $ℓ$ 位相乘。 $ℓ = 3$ 时是 $000, 001, \dots, 111$ 共 8 个。
符号 $ℓ$ 是小写字母 l 的花体写法，读作「ell」，这里表示字串长度。

基础补课独立的公平抛硬币 (ξ_n)

$ξ_{n}$ （希腊字母，读作「克西」）表示第 $n$ 次抛掷的结果：正面记 1，反面记 0， $P (ξ_{n} = 1) = P (ξ_{n} = 0) = \frac{1}{2} 。$
「独立」按第 6 页的补充定义：由不同次抛掷分别决定的事件相互独立。
直接推论：指定 $k$ 个不同的位置、规定每个位置上的值，这件事的概率是 $2^{- k}$ 。理由：它是 $k$ 个事件 ${ξ_{n} = c_{n}}$ 的交，由独立性等于 $k$ 个 $\frac{1}{2}$ 相乘。例： $P (ξ_{2} = 1, ξ_{5} = 0, ξ_{7} = 1) = \frac{1}{8} 。$
这样一列随机变量确实存在，例如第 6 页例 4：在 $(0, 1)$ 上均匀取点，它的二进制各位就是。

基础补课「w 在第 n 位出现」

我们说字串 $w$ 从第 $n$ 位开始出现，如果 $ξ_{n} = w_{1}, ξ_{n + 1} = w_{2}, \dots, ξ_{n + ℓ - 1} = w_{ℓ} 。$ 记这个事件为

C_{n} = {ξ_{n} = w_{1}, ξ_{n + 1} = w_{2}, \dots, ξ_{n + ℓ - 1} = w_{ℓ}} .

「 $w$ 出现无穷多次」就是 ${C_{n} i.o.} 。$

课件原文逐句精读

课件原文Recurrence of a fixed word in coin tosses

Example 5 (Independent fair tosses $(ξ_{n})$ ) Fix a binary word $w$ of length $ℓ$ . We want infinitely many copies of $w$ .

中文翻译

例 5（独立的公平抛硬币 $(ξ_{n}) ）$ 固定一个长度为 $ℓ$ 的二进制字串 $w 。$ 我们想要 $w$ 出现无穷多次。

Recurrence of a fixed word（蓝条标题）：固定字串的「重复出现」。recurrence 就是目录页第 1 部分标题里的那个词。
Independent fair tosses $(ξ_{n})$ ：设定是一列独立的公平抛硬币 $ξ_{1}, ξ_{2}, \dots 。$
Fix a binary word $w$ of length $ℓ$ ：先固定一个字串，它在整个论证中不变。比如 $w = 1101$ 或者「连续 20 个 1」。
We want infinitely many copies of $w$ ：copies 是「副本」，这里指 $w$ 在抛掷序列里的一次次出现。目标是证明：以概率 1， $w$ 出现无穷多次。

补全课件留白

补充说明

课件此处留白（课堂板书），以下内容由本站根据标准教材补写，记号与本课件保持一致；如与老师课堂写法不同，以老师为准。

Example 5 (Independent fair tosses (ξₙ))｜例 5（独立的公平抛硬币）

命题结论（例 5）

设 $ξ_{1}, ξ_{2}, \dots$ 是独立的公平抛硬币， $w \in {0, 1}^{ℓ}$ 是固定的字串。则

P (w 在 ξ_{1} ξ_{2} ξ_{3} \dots 中出现无穷多次) = P (C_{n} i.o.) = 1.

例子完整论证（四步）

第 1 步：切块。 把抛掷序列按长度 $ℓ$ 切成互不重叠的块：

第 1 块 ξ_{1} \dots ξ_{ℓ} 第 2 块 ξ_{ℓ + 1} \dots ξ_{2 ℓ} 第 3 块 ξ_{2 ℓ + 1} \dots ξ_{3 ℓ} \dots

第 $j$ 块由位置 $(j - 1) ℓ + 1, \dots, j ℓ$ 组成。令

B_{j} = {第 j 块恰好是 w} = r = 1 ⋂ ℓ {ξ_{(j - 1) ℓ + r} = w_{r}} = C_{(j - 1) ℓ + 1} .

第 2 步：每块的概率。 $B_{j}$ 规定了 $ℓ$ 个不同位置上的值，所以 $P (B_{j}) = 2^{- ℓ}$ （见基础补课）。

第 3 步：各块相互独立。 任取有限个不同的块号 $j_{1} < \dots < j_{k} 。$ 因为块互不重叠， $B_{j_{1}} \cap \dots \cap B_{j_{k}}$ 恰好规定了 $k ℓ$ 个不同位置上的值，所以

P (B_{j_{1}} \cap \dots \cap B_{j_{k}}) = 2^{- k ℓ} = k 个 2^{- ℓ} \dots 2^{- ℓ} = P (B_{j_{1}}) \dots P (B_{j_{k}}) .

这正是定义 3（第 6 页）的乘法规则，所以 $B_{1}, B_{2}, \dots$ 相互独立。

第 4 步：用第二引理，再翻译回来。 $\sum_{j} P (B_{j}) = \sum_{j} 2^{- ℓ} = \infty$ （同一个正数加无穷多次）。由第二 Borel–Cantelli 引理， $P (B_{j} i.o.) = 1 。$

在 ${B_{j} i.o.}$ 上，有无穷多个块等于 $w ；$ 不同的块从不同的位置 $(j - 1) ℓ + 1$ 开始，所以 $w$ 至少出现了无穷多次。即 ${B_{j} i.o.} \subseteq {C_{n} i.o.} ，$ 由单调性

1 = P (B_{j} i.o.) \leq P (C_{n} i.o.) \leq 1,

所以 $P (C_{n} i.o.) = 1 。$

为什么不能直接对重叠的出现用第二引理

最自然的想法是直接看 $C_{1}, C_{2}, C_{3}, \dots$ （从每一位开始的出现）。它们的概率都是 $2^{- ℓ} ，$ 和也是无穷。但相邻的 $C_{n}$ 共用了一些位置，不独立，第二引理的条件不满足。

例子计算：重叠窗口之间的依赖

$w = 11$ （ $ℓ = 2 ）$ ： $C_{1} = {ξ_{1} = 1, ξ_{2} = 1} ，$ $C_{2} = {ξ_{2} = 1, ξ_{3} = 1} ，$ 都共用位置 2。

P (C_{1} \cap C_{2}) = P (ξ_{1} = ξ_{2} = ξ_{3} = 1) = \frac{1}{8} \neq = \frac{1}{16} = P (C_{1}) P (C_{2}) .

知道 $C_{1}$ 发生（第 2 位是 1）， $C_{2}$ 就更容易发生：正相关。

$w = 10$ ： $C_{1} = {ξ_{1} = 1, ξ_{2} = 0} ，$ $C_{2} = {ξ_{2} = 1, ξ_{3} = 0} 。$ $C_{1} \cap C_{2}$ 要求 $ξ_{2}$ 既是 0 又是 1，不可能，

P (C_{1} \cap C_{2}) = 0 \neq = \frac{1}{16} = P (C_{1}) P (C_{2}) .

知道 $C_{1}$ 发生， $C_{2}$ 就一定不发生：负相关。

不重叠的窗口，比如 $C_{1}$ 和 $C_{3}$ （位置 1–2 与 3–4），各自规定两个不同的位置，交集规定四个不同位置， $P (C_{1} \cap C_{3}) = \frac{1}{16} = P (C_{1}) P (C_{3}) ，$ 是独立的。切块正是只保留这样的窗口。

所以切块的代价是漏掉一些出现（跨越块边界的那些），好处是换来独立性。我们只需要证明「无穷多次」，漏掉一部分无所谓：只要块里就已经有无穷多次，总的出现次数只会更多。

图解

图解：切块只数到一部分出现

取 $ℓ = 3 ，$ $w = 101 ，$ 一段抛掷结果如下（竖线是块的边界）：

位置 $n$	1	2	3	4	5	6	7	8	9	10	11	12
$ξ_{n}$	1	1	0	1	0	1	0	1	0	1	0	1
所在的块	第 1 块			第 2 块			第 3 块			第 4 块

按块看：第 1 块 $110 、$ 第 2 块 $101 、$ 第 3 块 $010 、$ 第 4 块 $101 。$ 所以 $B_{2} 、$ $B_{4}$ 发生，块的方法数到 2 次。
按所有起点看： $w = 101$ 从位置 $2, 4, 6, 8, 10$ 开始都出现了（例如位置 2–4 是 $1, 0, 1 ），$ 一共 5 次，其中从位置 2、6、8 开始的出现跨越了块边界，块的方法没有数到。
块的方法数得少，但它数到的每一次都是真实的出现。只要它数到无穷多次，真实次数就更是无穷。

例子

例 1：连续 10 次正面，要等多久？

取 $w = 10 11 \dots 1 ，$ $ℓ = 10 ，$ 每块等于 $w$ 的概率 $2^{- 10} = \frac{1}{1024} \approx 0.000977 。$

前 $K$ 块都不是 $w$ 的概率：由独立性（第 6 页命题 A），等于 $(1 - \frac{1}{1024})^{K} 。$
$K = 1000$ （抛 1 万次）： $(1 - \frac{1}{1024})^{1000} \approx e^{- 0.977} \approx 0.38 。$
$K = 10000$ （抛 10 万次）： $(1 - \frac{1}{1024})^{10000} \approx e^{- 9.77} \approx 5.7 \times 1 0^{- 5} 。$

所以抛 10 万次时，块里一次都没出现「连续 10 个正面」的概率约为十万分之六。随着 $K \to \infty ，$ 这个概率趋于 0；而第二引理说的更多：不仅会出现，还会出现无穷多次。

例 2：所有有限字串同时出现无穷多次

长度为 1 的字串有 2 个，长度为 2 的有 4 个……所有有限字串可以排成一列 $w^{(1)}, w^{(2)}, \dots ，$ 是可数多个。对每个 $w^{(i)} ，$ 事件 $E_{i} = {w^{(i)} 出现无穷多次}$ 的概率为 1。于是

P (i \geq 1 ⋂ E_{i}) = 1 - P (i \geq 1 ⋃ E_{i}^{c}) \geq 1 - i \geq 1 \sum P (E_{i}^{c}) = 1 - 0 = 1.

即以概率 1，每一个有限字串都出现无穷多次（俗称「猴子打字机」：随机敲键盘，任何一段文字终将出现，而且出现无穷多次）。这里关键是字串只有可数多个，才能用可数次可加性。

例 3：不公平的硬币也一样，但概率必须严格在 0 和 1 之间

若 $P (ξ_{n} = 1) = p ，$ $P (ξ_{n} = 0) = 1 - p ，$ $0 < p < 1 ，$ 各次独立。设 $w$ 里有 $a$ 个 1、 $ℓ - a$ 个 0，则 $P (B_{j}) = p^{a} (1 - p)^{ℓ - a} > 0 ，$ 它是一个固定的正数，和仍为无穷，结论不变。

但若 $p = 1$ （硬币永远正面），含有 0 的字串永远不会出现：此时 $P (B_{j}) = 0 ，$ $\sum_{j} P (B_{j}) = 0 < \infty ，$ 第一引理给出 $P (B_{j} i.o.) = 0 ，$ 与事实一致。

推导：一步一步来

第 3 步中「规定 $k ℓ$ 个不同位置」的严格写法。 设 $j_{1} < \dots < j_{k} ，$ 令

S = i = 1 ⋃ k {(j_{i} - 1) ℓ + 1, \dots, j_{i} ℓ}

为这些块覆盖的所有位置。块互不重叠，所以 $S$ 恰有 $k ℓ$ 个不同的元素。对 $n \in S ，$ 若 $n = (j_{i} - 1) ℓ + r$ （ $1 \leq r \leq ℓ ），$ 令 $c_{n} = w_{r}$ （位置 $n$ 上要求的值）。则

B_{j_{1}} \cap \dots \cap B_{j_{k}} = n \in S ⋂ {ξ_{n} = c_{n}} .

由 $ξ$ 的独立性（第 6 页的补充定义，取博雷尔集 ${c_{n}} ），$

P (n \in S ⋂ {ξ_{n} = c_{n}}) = n \in S \prod P (ξ_{n} = c_{n}) = (\frac{1}{2})^{k ℓ} .

取 $k = 1$ 就得到 $P (B_{j}) = 2^{- ℓ} 。$

常见疑问与易错点

易错点问：切块把很多出现丢掉了，这样证明还算数吗？

答：算数。我们要证的是「出现无穷多次」这种下界型结论。块的方法数到的出现是真实出现的一部分（ ${B_{j} i.o.} \subseteq {C_{n} i.o.} ），$ 部分已经无穷，整体当然无穷。如果要证的是「出现的次数恰好是多少」，丢掉信息就不行了。

易错点问：概率为 1，是不是说每一条抛掷序列里 w 都出现无穷多次？

答：不是每一条，是几乎每一条。例如全是 0 的序列 $000 \dots$ 在样本空间里， $w = 1$ 在其中一次都不出现。但这类「坏」序列合起来概率为 0。

易错点问：为什么一定要「固定」w？

答：因为第 2 步需要每块的概率是同一个正数 $2^{- ℓ} ，$ 这样和才是无穷。如果字串的长度随 $j$ 增长（比如第 $j$ 块要求 $j$ 个连续的 1），概率 $2^{- j}$ 之和有限，第一引理反而说以概率 1 只成功有限次。

小结与自测

小结本页小结

目标：独立公平抛硬币中，固定字串 $w$ （长度 $ℓ ）$ 以概率 1 出现无穷多次。
重叠的出现 $C_{n}$ 彼此不独立（ $w = 11$ 正相关， $w = 10$ 互斥），第二引理不能直接用。
诀窍：切成互不重叠的块， $B_{j} = {第 j 块 = w}$ 相互独立、 $P (B_{j}) = 2^{- ℓ} ，$ $\sum_{j} P (B_{j}) = \infty ，$ 第二引理给出 $P (B_{j} i.o.) = 1 。$
${B_{j} i.o.} \subseteq {w 出现无穷多次} ，$ 所以后者概率为 1；对可数多个字串取交，所有有限字串同时出现无穷多次。

自测

1. 取 $w = 01 。$ 块的方法中第 $j$ 块由哪两个位置组成？ $P (B_{j})$ 是多少？

点开看答案

$ℓ = 2 ，$ 第 $j$ 块是位置 $2 j - 1$ 和 $2 j 。$ $B_{j} = {ξ_{2 j - 1} = 0, ξ_{2 j} = 1} ，$ $P (B_{j}) = \frac{1}{4} 。$

2. 取 $w = 00 ，$ 计算 $P (C_{1} \cap C_{2}) ，$ 它和 $P (C_{1}) P (C_{2})$ 相等吗？

点开看答案

$C_{1} \cap C_{2} = {ξ_{1} = ξ_{2} = ξ_{3} = 0} ，$ 概率 $\frac{1}{8} ；$ 而 $P (C_{1}) P (C_{2}) = \frac{1}{16} 。$ 不相等，重叠窗口不独立（正相关）。

3. 如果把「块」换成「位置 $1, 1 + 2 ℓ, 1 + 4 ℓ, \dots$ 开始的窗口」（相邻窗口之间空出 $ℓ$ 位），论证还成立吗？

点开看答案

成立。这些窗口互不重叠，事件仍相互独立，每个概率仍是 $2^{- ℓ} ，$ 和为无穷，第二引理照样适用。只要窗口互不重叠、个数无穷，怎么选都可以。

本页术语中英对照（按出现顺序）

中文	English	白话解释
独立	independence	任意有限个事件同时发生的概率等于各自概率的乘积。
无穷多次	infinitely often (i.o.)	「Aₙ 发生无穷多次」就是集合 lim sup Aₙ。
事件	event	样本空间的（允许谈概率的）子集；实现的 ω 落在里面，就说事件发生。
Borel–Cantelli 引理	Borel–Cantelli lemma	概率之和有限 ⇒ 只发生有限次；独立且概率之和无穷 ⇒ 发生无穷多次。
随机变量	random variable	从样本空间到实数的（可测）函数，把结局翻译成数字；随机性来自「实现了哪个 ω」。
交集	intersection	同时属于两个集合的元素全体，A ∩ B 对应「A 且 B」。
可数	countable	元素能排成第 1 个、第 2 个、第 3 个……的一列（有限也算），例如自然数、有理数。
次可加性	subadditivity	并集的测度不超过各部分测度之和：μ(A ∪ B) ≤ μ(A) + μ(B)。
元素	element	集合里的对象。ω ∈ Ω 读作「ω 属于 Ω」。
博雷尔 σ-代数	Borel sigma-algebra	由实数轴上所有开区间生成的 σ-代数 𝓑(ℝ)，包含所有常见的集合。
下界	lower bound	数集 A 的下界是一个数 m，A 里每个数都 ≥ m。例如 0 和 −3 都是 (0,1] 的下界；所有下界中最大的那个叫下确界。
样本空间	sample space	一次试验所有可能的完整结局组成的集合，记作 Ω。