CS70Disc14
CS70 Disc 14
1 Short Tree Proofs
问题背景
给定一个无向图 $ G = (V, E) $，其中顶点数 $ |V| $。我们需要证明以下三点：
- (a) 在无环图中，每个连通分量都是一棵树。
- (b) 如果图 $ G $ 有 $ k $ 个连通分量，并且图是无环的，那么 $ |E| = |V| - k $。
- (c) 如果一个图有 $ |V| $ 条边，那么它包含一个环。
(a) 每个连通分量是树的证明
要证明的结论：每个连通分量在无环图中都是树。
- 连通性：由于我们考虑的是连通分量，因此每个分量都是连通的。
- 无环性：根据问题的条件，图是无环的。无环图意味着没有闭环存在。
- 树的定义：树是一个连通且无环的图。
因此，每个连通且无环的连通分量自然满足树的定义。因此可以得出结论：每个连通分量是树。
(b) $ |E| = |V| - k $ 的证明
已知条件：
- 图 $ G $ 是无环的，并且有 $ k $ 个连通分量。
- 每个连通分量都是一棵树（根据(a)的结论）。
步骤：
- 每个连通分量是树：根据树的性质，一棵包含 $ |V_i| $ 个顶点的树有 $ |V_i| - 1 $ 条边。
- 所有连通分量的边数之和：图中有 $ k $ 个连通分量，假设每个连通分量的顶点数分别为 $ |V_1|, |V_2|, , |V_k| $，则每个连通分量的边数为 $ |V_i| - 1 \(，总边数为：\) |E| = (|V_1| - 1) + (|V_2| - 1) + + (|V_k| - 1) $ 这可以写成： $ |E| = {i=1}^{k} (|V_i| - 1) = {i=1}^{k} |V_i| - k = |V| - k $ 其中 $ _{i=1}^{k} |V_i| = |V| $ 表示图中所有顶点的总数。
因此，无环图的边数 $ |E| = |V| - k $，其中 $ k $ 是连通分量的数量。
(c) 如果图有 $ |V| $ 条边，它包含一个环
要证明的结论：如果图中有 $ |V| $ 条边，则它包含一个环。
- 无环图的边数：从 (b) 的结论得知，无环图的边数最多为 $ |V| - k $，其中 $ k $ 是连通分量的数量。当图是连通的（即 $ k = 1 $）时，边数最多为 $ |V| - 1 $。
- 反证法：假设图中没有环，并且它有 $ |V| $ 条边。根据无环图的性质，这样的图应该有至多 $ |V| - 1 $ 条边，而不是 $ |V| $ 条。因此，假设成立的前提与无环图的边数限制相矛盾。
因此，如果一个图有 $ |V| $ 条边，它必然包含一个环。
2 Secret Sharing Practice
问题背景
我们探讨两种秘密共享方案，并针对问题中的要求解决相关变量：
- (a) 为了给 5 个 trick-or-treaters（讨糖的小孩）设计一个方案，确保至少 3 个小孩同意才能打开装有糖果的袋子，密码是介于 0 和某个整数 $ n $ 之间的值。
- (b) 设计一个方案，确保如果有 4 只猫和 3 只狗，只有当每类动物中的大多数感到饿时，它们才能拿到零食。零食被一个密码锁住，密码介于 0 和某个整数 $ n $ 之间。
(a) 方案设计：至少 3 人同意才能打开袋子
目标：设计一个秘密共享方案，确保至少 3 个 trick-or-treaters 同意才能打开糖果袋。
解决方案：
多项式选择：使用一个 2 次多项式。根据秘密共享原理，d 次多项式需要 $ d + 1 $ 个点才能唯一确定。因此，2 次多项式需要 3 个点才能唯一确定。
方案构建：
- 定义一个 2 次多项式 $ f(x) = a_0 + a_1 x + a_2 x^2 $。
- $ f(0) $ 是我们要隐藏的秘密，即糖果袋的密码。
- 每个 trick-or-treater 被分配多项式在某一点 $ f(x_i) $ 处的值。
- 至少需要 3 个人的份额（即 3 个点）来恢复多项式并得到密码。
总结：该方案使用一个 2 次多项式来保证至少 3 个人共同协作才能解锁密码。每个人被分配该多项式的一个特定值，至少需要 3 个人合作才能唯一确定多项式并解锁糖果袋。
(b) 方案设计：猫和狗的投票机制
目标：设计一个方案，确保至少有多数猫和多数狗同意才能获取零食。
解决方案：
- 多项式选择原则：
- d 次多项式需要 $ d + 1 $ 个点才能唯一确定。因此，假设猫需要 3 只同意，狗需要 2 只同意。
- 设定三个多项式：一个对应猫 $ c(x) $、一个对应狗 $ d(x) $，以及一个联合多项式 $ j(x) $（实际包含解锁零食的秘密）。
- 具体构建：
- 猫的多项式 $ c(x) $：
- $ c(x) $ 是一个 2 次多项式（因为需要至少 3 只猫同意），即 $ c(x) = c_0 + c_1 x + c_2 x^2 $。
- 只有 3 只猫合作才能唯一确定 $ c(x) $，从而获得猫的投票信息。
- 狗的多项式 $ d(x) $：
- $ d(x) $ 是一个 1 次多项式（因为需要至少 2 只狗同意），即 $ d(x) = d_0 + d_1 x $。
- 只有 2 只狗合作才能唯一确定 $ d(x) $，从而获得狗的投票信息。
- 联合多项式 $ j(x) $：
- $ j(x) $ 是一个 1 次多项式，且 $ j(0) $ 是最终的秘密（即零食的密码）。
- 设计 $ c(0) = j(1) $ 和 $ d(0) = j(2) $，确保只有获得猫的 $ c(0) $ 和狗的 $ d(0) $ 信息后，才能确定 $ j(x) $ 并获得最终的秘密。
- 猫的多项式 $ c(x) $：
3 Counting Subsets
问题背景
本节涉及集合 $ S $ 和函数集 $ T $，我们需要处理不同的子集计数问题：
- (a) 展示 $ S $（所有自然数 $ $ 的子集的集合）与 $ T = { f: {0,1} } $ 之间的双射。
- (b) 证明或反驳：集合 $ S $ 是可数的。
- (c) 定义函数 $ f: {0,1} $ 具有有限支撑，当且仅当 $ f $ 在有限个输入上非零。设 $ F $ 是所有具有有限支撑的函数集合，证明 $ F $ 是可数无穷的。
(a) 展示 $ S $ 和 $ T $ 之间的双射
目标：展示 $ S $ 和 $ T = { f : {0,1} } $ 之间存在双射关系。
解法：
- 映射定义：
- 定义一个从 $ S $ 到 $ T $ 的映射 $ f(x) $，其中如果 $ x X $ 则 $ f(x) = 1 $，否则 $ f(x) = 0 $。
- 对于任意一个子集 $ X $，我们可以通过该映射得到一个函数 $ f $，这个函数映射每个自然数到 $ {0,1} $。
- 证明双射：
- 满射性：对于每个函数 $ f T $，都存在一个子集 $ X = {x | f(x) = 1} $，这样可以得到与之对应的子集，因此是满射。
- 单射性：如果两个不同的子集 $ X $ 和 $ X' $ 在某个 $ x $ 处不同，即 $ x X $ 但 $ x X' $，那么它们对应的函数 $ f $ 和 $ f' $ 在 $ f(x) = 1 $ 和 $ f'(x) = 0 $ 处不同，因此 $ f f' $，所以是单射。
总结：我们已经证明了 $ S $ 和 $ T $ 之间存在双射关系，即每个子集 $ X $ 都唯一对应一个函数 $ f $，反之亦然。
(b) $ S $ 是可数的还是不可数的？
目标：确定 $ S $ 是否是可数的。
解法：
- 不可数性证明：可以将集合 $ S $ 中的每个函数 $ f T $ 视为一个将自然数映射到 $ {0,1} $ 的函数，这相当于一个实数的二进制编码。每个函数 $ f $ 可以编码为一个介于 0 和 1 之间的实数。因此，集合 $ S $ 与实数区间 $ [0,1] $ 存在满射关系，而 $ [0,1] $ 是不可数的。由此可知，$ S $ 也是不可数的。
总结：$ S $ 是不可数的。
(c) 证明 $ F $ 是可数无穷的
目标：证明有限支撑的函数集合 $ F $ 是可数无穷的。
解法：
- 定义有限支撑函数：
- $ f: {0,1} $ 的有限支撑意味着 $ f $ 在有限个输入上非零，即仅在有限个自然数上 $ f(x) = 1 $，在其他地方 $ f(x) = 0 $。
- 与自然数 $ $ 之间的双射：
我们将每个有限支撑的函数 $ f $ 编码为一个二进制数 $ y_f $，其第 $ i $ 位（从 0 开始）设为 1 当且仅当 $ f(i) = 1 $。由于 $ f $ 只有有限个位置为 1，因此该二进制编码有有限长度（排除前导 0）。这个编码可以唯一地表示为自然数中的一个元素。
一一对应：每个有限支撑函数 $ f $ 对应一个唯一的自然数二进制表示，反之亦然，因此我们建立了 $ F $ 与 $ $ 之间的双射。
由于自然数是可数的，因此 $ F $ 是可数无穷的。
- 另一种双射：
- 也可以使用素数分解来建立双射。令 $ {p_0 = 2, p_1 = 3, p_2 = 5, } $ 为所有素数的集合。对于每个有限支撑的函数 $ f $，它在有限个 $ x_1, x_2, , x_k $ 处为 1。
- 将 $ f $ 编码为自然数 $ p_{x1} p_{x2} p_{xk} $，即素数的乘积。由于素数分解的唯一性，这样的编码是唯一的，并且每个自然数对应一个有限支撑函数。因此 $ F $ 与自然数之间也有一个双射。
总结：通过二进制编码或素数分解的方式，我们证明了 $ F $ 是可数无穷的。
4 Strings
问题背景
我们需要解决的问题是：
- 计算只包含字母 $ A, B, C $ 的长度为 5 的不同字符串的数量。
- 计算至少包含每个字母 $ A, B, C $ 的字符串的数量。
第一部分：计算所有不同字符串的数量
目标：求出长度为 5 的字符串数量，字符集合为 $ {A, B, C} $。
解法：
- 选择方式：
- 对于长度为 5 的字符串，每个位置都可以选择 $ A, B, $ 或 $ C $，因此每个位置有 3 种选择。
- 总数量计算：
- 字符串的总数量 = $ 3^5 $。
- 计算结果为： $ 3^5 = 243 $
总结：只包含 $ A, B, C $ 的长度为 5 的字符串的数量为 243。
第二部分：计算至少包含每个字符的字符串数量
目标：求出至少包含 $ A, B, C $ 每个字符的字符串数量。
解法：
- 定义集合：
- 设 $ E_A $ 为不使用字符 $ A $ 的字符串集合，$ E_B $ 和 $ E_C $ 分别类似定义。
- 计算集合的大小：
- $ |E_A| $：仅使用 $ B, C $ 的字符串的数量： $ |E_A| = 2^5 = 32 $
- 由于集合 $ E_B $ 和 $ E_C $ 的大小相同： $ |E_B| = |E_C| = 32 $
- 交集的计算：
- $ |E_A E_B| $：只使用 $ C $ 的字符串数量（即仅有一个字符）： $ |E_A E_B| = 1 $
- 同理，$ |E_B E_C| = 1 $ 和 $ |E_C E_A| = 1 $。
- $ |E_A E_B E_C| = 0 $，因为不可能同时不使用 $ A, B, C $。
- 使用包含-排除原理：
- 根据包含-排除原理，计算 "坏字符串" 的数量： $ |E_A E_B E_C| = |E_A| + |E_B| + |E_C| - |E_A E_B| - |E_A E_C| - |E_B E_C| + |E_A E_B E_C| $
- 代入已知值： $ |E_A E_B E_C| = 32 + 32 + 32 - 1 - 1 - 1 + 0 = 93 $
- 计算有效字符串数量：
- 有效字符串数量 = 总字符串数量 - 坏字符串数量： $ = 243 - 93 = 150 $
总结：至少包含字符 $ A, B, C $ 的长度为 5 的字符串的数量为 150。
5 Mario’s Coins
问题背景
马里奥拥有三枚看似相同的硬币：
- 第一枚硬币显示正面的概率为 $ $。
- 第二枚硬币显示正面的概率为 $ $。
- 第三枚硬币显示正面的概率为 $ $。
部分 (a)：X1 和 X2 是否独立
定义：
- $ X_1 $：第一次翻转结果为正面。
- $ X_2 $：第二次翻转结果为正面。
直觉分析：
- $ X_1 $ 的发生会影响选择的第一枚硬币，进一步影响第二次翻转所选硬币的概率，因此 $ X_1 $ 和 $ X_2 $ 不是独立的。
数学证明：
**计算 $ P[X_1] \(**：\) P[X_1] = + + = + + = $
对称性： $ P[X_2] = P[X_1] = $
**计算 $ P[X_1] P[X_2] \(**：\) P[X_1] P[X_2] = = $
**计算 $ P[X_1 X_2] \(**：\) P[X_1 X_2] = + + + + + $ 计算得： $ P[X_1 X_2] = = $
结论： 因为 $ P[X_1 X_2] P[X_1] P[X_2] $，所以 $ X_1 $ 和 $ X_2 $ 不是独立事件。
部分 (b)：Y1 和 Y2 是否独立
定义：
- $ Y_1 $：第一次翻转结果为正面。
- $ Y_2 $：第二次翻转结果为正面。
直觉分析：
- $ Y_1 $ 的结果会影响所选硬币的概率，从而影响 $ Y_2 $。
数学证明：
**计算 $ P[Y_1] \(**：\) P[Y_1] = + + = $
对称性： $ P[Y_2] = P[Y_1] = $
**计算 $ P[Y_1] P[Y_2] \(**：\) P[Y_1] P[Y_2] = = $
**计算 $ P[Y_1 Y_2] \(**：\) P[Y_1 Y_2] = ()^2 + ()^2 + ()^2 $ 计算得： $ P[Y_1 Y_2] = = $
结论： 因为 $ P[Y_1 Y_2] P[Y_1] P[Y_2] $，所以 $ Y_1 $ 和 $ Y_2 $ 不是独立事件。
部分 (c)：第三枚硬币显示正面的概率
已知条件：
- 左边的硬币（A）显示正面。
- 中间的硬币（B）显示正面。
- 右边的硬币（C）尚未翻转。
目标：计算 $ P[C | A B ] $。
计算步骤：
定义事件：
- 设 $ A $ 为概率 $ \(，\) B $ 为概率 $ \(，\) C $ 为概率 $ $。
计算条件概率： $ P[] = P[A B C] = P[A] P[B] P[C] = () () () = $
已知前两个硬币显示正面的情况下： $ P[] = P[X_1 X_2] = $
使用贝叶斯定理： $ P[C | A B ] = = = $
结论： 第三枚硬币显示正面的概率为 $ $。
6 Sum of Poisson Variables
背景知识
Poisson随机变量是描述单位时间或单位空间内事件发生次数的随机变量，通常用于描述稀疏事件发生的情况。若一个随机变量$ X $服从参数为 $ $ 的Poisson分布，记作 $ X () \(，则其概率质量函数为：\) P[X = k] = , k = 0, 1, 2, $
题目要求
给定两个独立的Poisson随机变量 $ X_1 $ 和 $ X_2 $，其中 $ X_1 $ 的均值为 $ _1 \(，\) X_2 $ 的均值为 $ _2 $。我们需要证明 $ X_1 + X_2 $ 是一个均值为 $ _1 + _2 $ 的Poisson随机变量。
证明步骤
我们需要证明 $ P[X_1 + X_2 = i] $ 的形式符合Poisson分布的概率质量函数。
定义概率： $ P[X_1 + X_2 = i] = _{k=0}^{i} P[X_1 = k, X_2 = i - k] $
使用独立性： 根据 $ X_1 $ 和 $ X_2 $ 的独立性，我们可以将联合概率分解为： $ P[X_1 = k, X_2 = i - k] = P[X_1 = k] P[X_2 = i - k] $ 因此： $ P[X_1 + X_2 = i] = _{k=0}^{i} P[X_1 = k] P[X_2 = i - k] $
代入概率质量函数： 根据Poisson分布的概率质量函数： $ P[X_1 = k] = , P[X_2 = i - k] = $ 将这些代入得： $ P[X_1 + X_2 = i] = _{k=0}^{i} $ 进一步简化： $ P[X_1 + X_2 = i] = e^{-_1} e{-2} {k=0}{i} $ 这里，$ e^{-_1} e^{-_2} = e^{-(_1 + _2)} $。
应用二项式定理： 根据二项式定理： $ (x + y)^n = _{k=0}^{n} x^k y^{n-k} $ 在这里我们可以取 $ x = _1 \(，\) y = 2 $，并且 $ n = i \(：\) {k=0}^{i} _1^k _2^{i-k} = (_1 + _2)^i $ 于是，我们得到： $ P[X_1 + X_2 = i] = e^{-(_1 + _2)} $
结论： 我们可以看出： $ P[X_1 + X_2 = i] = $ 这正是均值为 $ _1 + _2 $ 的Poisson分布的形式，因此我们证明了 $ X_1 + X_2 $ 也是一个Poisson随机变量，均值为 $ _1 + _2 $。
7 Balls in Bins
问题描述
我们有 $ k $ 个球和 $ n $ 个箱子，定义 $ X_i $ 为投掷到箱子 $ i $ 中的球的数量。
(a) 计算 $ E[X_i] $
求解步骤：
- 使用线性期望法则（Linearity of Expectation），我们可以表示每个箱子中球的期望数量为每个球落入该箱子的概率的总和。
- 每个球落入箱子 $ i $ 的概率是 $ $。
- 因此，期望 $ E[X_i] $ 可以表示为： $ E[X_i] = P[ i] + P[ i] + + P[ k i] $ $ = + + + (k ) $ $ = $
(b) 计算空箱子的期望数量
求解步骤：
- 定义 $ I_i $ 为指示变量，表示箱子 $ i $ 是否为空。箱子 $ i $ 为空的条件是所有球都落入剩余的 $ n-1 $ 个箱子中。
- 箱子 $ i $ 为空的概率为： $ P[I_i = 1] = ( )^k $
- 因此，所有箱子为空的期望数量为： $ E[I_1 + I_2 + + I_n] = E[I_1] + E[I_2] + + E[I_n] $ $ = n ( )^k $
(c) 计算冲突的期望数量
定义：
- 冲突是指球落入一个非空箱子的情况。若某个箱子中有 $ n $ 个球，则冲突数为 $ n-1 $。
求解步骤：
- 冲突的数量可以表示为球的数量减去占用箱子的数量（因为每个占用箱子的第一个球不会造成冲突）。
- 定义已占用箱子的数量为 $ O \(，因此有：\) E[] = k - E[] $
- 已占用箱子的期望可以通过已知的空箱子的期望来计算： $ E[] = n - E[] $ 结合之前的结果： $ E[] = k - n + E[] $ $ = k - n + n (1 - )^k $ $ = k - n + n ( )^k $
8 Inequality Practic
问题描述
(a) 随机变量 $ X $
- 条件：$ X $ 且 $ E[X] = -3 $
- 目标：找到 $ P[X ] $ 的上界。
(b) 随机变量 $ Y $
- 条件：$ Y $ 且 $ E[Y] = 1 $
- 目标：找到 $ P[Y ] $ 的上界。
(c) 掷骰子
- 我们掷一个骰子 $ 100 $ 次，设 $ Z $ 为这 $ 100 $ 次投掷结果的总和。
- 目标：计算 $ (Z) $，然后使用切比雪夫不等式来界定 $ Z > 400 $ 或 $ Z < 300 $ 的概率。
(a) 随机变量 $ X $
转换随机变量： 定义新的随机变量 $ = X + 5 $，这样 $ $ 始终为非负值。
计算期望： $ E[] = E[X] + 5 = -3 + 5 = 2 $
应用马尔可夫不等式： 使用马尔可夫不等式，得出： $ P[ ] = = $
结论： $ P[X ] $
(b) 随机变量 $ Y $
转换随机变量： 定义新的随机变量 $ = -Y + 10 $。
计算期望： $ E[] = -E[Y] + 10 = -1 + 10 = 9 $
应用马尔可夫不等式： 利用马尔可夫不等式，得出： $ P[Y ] = P[-Y ] = P[-Y + 10 ] $
结论： $ P[Y ] $
(c) 掷骰子
定义随机变量： 设 $ Z_i $ 为第 $ i $ 次掷骰子的结果，$ Z = _{i=1}^{100} Z_i $。
计算期望： $ E[Z_i] = {j=1}^{6} j P[Z_i = j] = {j=1}^{6} j = _{j=1}^{6} j = = $ 因此： $ E[Z] = 100 E[Z_i] = 100 = 350 $
计算方差： 首先，计算单次掷骰子的方差： $ E[Z_i^2] = {j=1}^{6} j^2 P[Z_i = j] = {j=1}^{6} j^2 = _{j=1}^{6} j^2 = = $ 因此，方差为： $ (Z_i) = E[Z_i^2] - (E[Z_i])^2 = - ()^2 = - $ 通过通分，我们得： $ (Z_i) = - = = $ 因为 $ Z_i $ 是独立的，所以： $ (Z) = 100 (Z_i) = 100 = = $
使用切比雪夫不等式： 使用切比雪夫不等式来界定 $ Z $ 的偏离： $ P[|Z - 350| > 50] P[|Z - 350| ] = = = $
9 Exponential Distributions: Lightbulbs
问题描述
背景：一只全新的灯泡被安装在教室里，其寿命是以平均50天的指数分布进行描述。
(a) 电工检查灯泡的概率
电工定于30天后检查灯泡，如果灯泡坏了就会更换。求电工发现灯泡坏掉的概率。
(b) 新灯泡的概率
如果电工发现灯泡坏了，并更换为新灯泡，求新灯泡至少能持续30天的概率。
(c) 现有灯泡的概率
如果电工发现灯泡仍然在工作，那么它至少再持续30天的概率是多少？
解决方案
(a) 求电工发现灯泡坏掉的概率
定义随机变量： 设随机变量 $ X () $，其中 $ = $。这表示灯泡的寿命。
概率密度函数： 指数分布的概率密度函数为： $ f_X(x) = e^{-x} x > 0 $
计算概率： 我们需要计算灯泡在前30天内坏掉的概率，即 $ P[X < 30] \(：\) P[X < 30] = _0^{30} e^{-x} , dx $ 代入 $ = \(：\) P[X < 30] = _0^{30} e^{-x/50} , dx $ 计算得到： $ P[X < 30] = 1 - e^{-30/50} = 1 - e^{-3/5} $
(b) 求新灯泡至少能持续30天的概率
独立性： 新灯泡的寿命 $ Y $ 与旧灯泡的寿命 $ X $ 是独立同分布的。
计算概率： 因此，新灯泡至少持续30天的概率为： $ P[Y > 30] = 1 - P[Y < 30] = 1 - (1 - e^{-3/5}) = e^{-3/5} $
(c) 求现有灯泡再持续30天的概率
记忆无关性： 指数分布具有记忆无关性，即给定灯泡已经工作了30天的情况下，它继续工作的概率等于它从现在开始工作30天的概率： $ P[X > 60 | X > 30] = P[X - 30 > 30 | X > 30] = P[X > 30] $
计算概率： 因此，得到： $ P[X > 60 | X > 30] = P[X > 30] = e^{-3/5} $
10 Continuous Probability Continued
问题描述
(a) Bob的投币游戏
假设 Bob1, Bob2, …, Bobk 每个人都有一个公平的硬币，硬币的两面分别标有 $ i $ 和 $ -i $。每个人投掷他们的硬币 $ n $ 次，并求和，得出数字 $ X_i $。当 $ n $ 很大时，求 \((X_1 + \cdots + X_k) / \sqrt{n}\) 的分布近似于什么。
(b) 独立同分布随机变量的和
设 $ X_1, X_2, $ 是一系列独立同分布随机变量，其均值为 $ $，方差为 $ ^2 \(。求：\) _{n } P( ) $ 这个极限的值可能依赖于 $ $ 和标准正态分布的累积分布函数 $ $。
解决方案
(a) 分布的近似
随机变量的定义： 每个 Bob 的投币结果为 $ X_i $，每次投掷的结果为 $ i $ 或 $ -i \(。因此，每个 Bob 的投掷结果的期望为：\) E[X_i] = 0 $ 其方差为： $ (X_i) = E[X_i^2] - (E[X_i])^2 = = i^2 $
求和的分布： 根据中心极限定理，随着 $ n $ 的增大，随机变量的标准化和的分布会趋近于正态分布： $ N(0, _{i=1}^{k} i^2) $
因此，可以得出： $ N(0, _{i=1}^{k} i^2) $
这是因为每个 $ $ 都收敛到 $ N(0, ) $，所以它们的和也收敛到正态分布。
(b) 独立同分布随机变量的和的极限
极限的计算： 根据大数法则： $ N(0, 1) $ 我们需要考虑： $ P( ) $
三种情况：
当 $ > \(：\) P( ) $ 使用切比雪夫不等式可以证明。
当 $ = \(：\) P( ) (1) - (-1) $ 这是根据中心极限定理的直接结果。
当 $ < \(：\) P( ) $ 这个情况是通过将结果转化为正态分布的概率得到的。
11 Three Tails
问题描述
我们希望计算在抛掷硬币的过程中，直到看到三个连续的尾（T T T）时，平均看到的头（H）的数量。
状态定义
我们可以将整个过程定义为以下几个状态：
- S: 起始状态，表示我们还没有进行任何投掷。
- H: 当前看到一个“头”，即没有连续的“尾”。
- T: 当前看到一个“尾”，即有一个“尾”。
- T T: 当前看到两个连续的“尾”。
- T T T: 达成目标，看到三个连续的“尾”，停止投掷。
转移图
在这个模型中，转移图可以表示为：
- 从状态 S：
- 以概率 \(0.5\) 转移到状态 H（见到“头”）。
- 以概率 \(0.5\) 转移到状态 T（见到“尾”）。
- 从状态 H：
- 以概率 \(0.5\) 转移到状态 H（继续见到“头”）。
- 以概率 \(0.5\) 转移到状态 T（见到“尾”）。
- 从状态 T：
- 以概率 \(0.5\) 转移到状态 T T（见到第二个“尾”）。
- 以概率 \(0.5\) 转移到状态 H（见到“头”）。
- 从状态 T T：
- 以概率 \(0.5\) 转移到状态 H（见到“头”）。
- 以概率 \(0.5\) 转移到状态 T T T（见到第三个“尾”，结束）。
- 从状态 T T T：
- 这个状态是终止状态，期望值为 \(0\)。
方程建立
我们定义 $ (X) $ 为从状态 $ X $ 开始时，期望看到的“头”的数量。根据状态转移，我们可以建立以下方程：
从状态 S： $ (S) = 0.5 (T) + 0.5 (H) $
从状态 H： $ (H) = 1 + 0.5 (H) + 0.5 (T) $ 这里 \(1\) 是因为看到一个“头”。
从状态 T： $ (T) = 0.5 (T T) + 0.5 (H) $
从状态 T T： $ (T T) = 0.5 (H) + 0.5 (T T T) $
从状态 T T T： $ (T T T) = 0 $
解方程
首先，从方程 (5) 我们知道： $ (T T T) = 0 $
将其代入方程 (4)： $ (T T) = 0.5 (H) + 0 (T T) = 0.5 (H) $
然后，将 $ (T T) $ 代入方程 (3)： $ (T) = 0.5 (0.5 (H)) + 0.5 (H) = 0.25 (H) + 0.5 (H) = 0.75 (H) $
接着，我们将 $ (T) $ 的表达式代入方程 (2)： $ (H) = 1 + 0.5 (H) + 0.5 (0.75 (H)) $ $ (H) = 1 + 0.5 (H) + 0.375 (H) $ $ (H) = 1 + 0.875 (H) $ $ (H) - 0.875 (H) = 1 $ $ 0.125 (H) = 1 (H) = 8 $
得到 $ (H) = 8 $。
然后，将 $ (H) $ 代入求 $ (T) \(：\) (T) = 0.75 = 6 $
接着，再将 $ (T) $ 代入求 $ (S) \(：\) (S) = 0.5 + 0.5 = 3 + 4 = 7 $
