CS70 Disc 09B

1 Linearity

线性期望是指若 $ X $ 和 $ Y $ 是两个随机变量，则有： $ E[X + Y] = E[X] + E[Y] $ 这对于任意数量的随机变量均适用。

(a) 游戏A和游戏B的期望票数

假设你在一个游戏厅中玩游戏A 10次，游戏B 20次。

游戏A：

每次获胜的概率为 $ $。
如果获胜，获得3张票；如果失败，获得0张票。
定义指示变量 $ A_i $，表示第 $ i $ 次玩游戏A时是否获胜（1表示获胜，0表示失败）。

**计算 $ E[A_i] $：**$ E[A_i] = 1 + 0 = $

在玩10次游戏A时，期望票数为： $ E[] = 3 E[A_1 + A_2 + + A_{10}] = 3 (10 E[A_i]) = 10 = 10 $

游戏B：

每次获胜的概率为 $ $。
如果获胜，获得4张票；如果失败，获得0张票。
定义指示变量 $ B_i $，表示第 $ i $ 次玩游戏B时是否获胜。

**计算 $ E[B_i] $：**$ E[B_i] = 1 + 0 = $

在玩20次游戏B时，期望票数为： $ E[] = 4 E[B_1 + B_2 + + B_{20}] = 4 (20 E[B_i]) = 20 = 16 $

总期望票数： $ E[] = E[] + E[] = 10 + 16 = 26 $

(b) 猴子打字序列“book”的期望出现次数

设猴子独立地从26个字母中随机打字1,000,000次。

计算“book”出现的期望次数：

字符串“book”有4个字母，因此可以在字符串的 $ 1,000,000 - 4 + 1 = 999,997 $ 个位置出现。
定义随机变量 $ A $ 为“book”出现的总次数，定义指示变量 $ A_i $ 表示在第 $ i $ 个字母开始时“book”是否出现（1表示出现，0表示未出现）。

计算期望： $ E[A] = E[A_1 + A_2 + + A_{999,997}] = E[A_1] + E[A_2] + + E[A_{999,997}] $

计算 $ E[A_i] $：

“book”出现的概率为 $ ()^4 = $。

因此： $ E[A_i] = $

最终的期望次数为： $ E[A] = 999,997 $

## 2 Head Count II

考虑一个硬币，正面概率为 $ P[] = $。假设你翻硬币直到第一次出现正面，并定义 $ X $ 为你翻硬币的次数。

(a) $ P[X = k] $ 的计算

如果我们翻了 $ k $ 次硬币，则在前 $ k-1 $ 次为反面，最后一次为正面。可以得出： $ P[X = k] = P[]^{k-1} P[] = ( )^{k-1} $ 因此： $ P[X = k] = ( )^{k-1} $

(b) $ X $ 的分布及参数

随机变量 $ X $ 服从几何分布： $ X ( ) $

(c) $ P[X > k] $ 的计算

如果在第 $ k $ 次之前没有出现正面，那么前 $ k $ 次翻的硬币必须全部为反面。因此： $ P[X > k] = P[]^k = ( )^{k} $

(d) $ P[X < k] $ 的计算

注意到 $ P[X < k] = 1 - P[X k] = 1 - P[X > k-1] $，由于 $ X $ 只能取整数值，有： $ P[X < k] = 1 - P[X > k-1] = 1 - ( )^{k-1} $

(e) 条件概率 $ P[X > k | X > m] $

通过部分 (c)，我们有： $ P[X > k | X > m] = = $ 由此得出： $ P[X > k | X > m] = ( )^{k-m} $

这与 $ P[X > k - m] $ 是相同的。这个性质说明了几何分布的“无记忆性”，即如果我们知道第一次出现正面发生在第 $ m $ 次之后，那么接下来要再经过 $ k-m $ 次才能出现正面。

(f) 最小值分布 $ (X, Y) $

假设 $ X (p) $ 和 $ Y (q) $ 是独立的。求 $ (X,Y) $ 的分布。

设 $ X $ 为翻硬币直到出现正面（偏向 $ p $ 的硬币），而 $ Y $ 也为翻硬币直到出现正面（偏向 $ q $ 的硬币）。

概率计算： 不出现正面的概率为 $ (1-p)(1-q) $，这对应于一次失败。因此，至少有一次成功的概率为：$ 1 - (1 - p)(1 - q) = p + q - pq $ 因此，$ (X,Y) $ 服从几何分布： $ (X,Y) (p + q - pq) $

替代方法： 我们也可以通过代数计算来求解。设 $ Z = (X,Y) $，那么：$ P[Z = k] = P[ k-1 ] P[ k ] $ 具体概率为： $ P[ k-1 ] = ((1 - p)(1 - q))^{k-1} $ 结合以上概率，可以得到： $ P[Z = k] = ((1 - p)(1 - q))^{k-1} (p + q - pq) $ 这也可以看作是一个几何随机变量，其参数为 $ p + q - pq $。

尾概率计算： 我们也可以用尾概率 $ P[Z k] $ 来求解： $ P[Z k] = P[X k] P[Y k] = (1 - p)^{k-1} (1 - q)^{k-1} = ((1 - p)(1 - q))^{k-1} $ 因此，$ Z $ 服从几何分布： $ Z (p + q - pq) $

总结

$ P[X = k] = ( )^{k-1} $
$ X ( ) $
$ P[X > k] = ( )^{k} $
$ P[X < k] = 1 - ( )^{k-1} $
$ P[X > k | X > m] = ( )^{k-m} $ (无记忆性)
$ (X,Y) (p + q - pq) $

3 Shuttles and Taxis at Airport

问题背景

在旧金山国际机场第3航站楼的接送区，班车和出租车的到达遵循泊松分布。班车到达的速率为 $\lambda_1 = \frac{1}{20}$（即每20分钟到达1辆班车），出租车到达的速率为 $\lambda_2 = \frac{1}{10}$（即每10分钟到达1辆出租车）。这两者的到达是独立的。

(a) 不同情况的分布

(i) 在00:00到00:20之间到达的出租车数量

设 $T([0,20])$ 表示在00:00到00:20之间到达的出租车数量。此区间长度为20分钟，因此出租车的到达服从以下泊松分布： $ T([0,20]) (_2 ) = (2) $ 即： $ P[T([0,20]) = t] = , t = 0, 1, 2, $

(ii) 在00:00到00:20之间到达的班车数量

设 $S([0,20])$ 表示在00:00到00:20之间到达的班车数量。此区间长度为20分钟，因此班车的到达服从以下泊松分布： $ S([0,20]) (_1 ) = (1) $ 即： $ P[S([0,20]) = s] = , s = 0, 1, 2, $

(iii) 在00:00到00:20之间到达的所有车辆数量

设 $N([0,20]) = S([0,20]) + T([0,20])$ 表示在00:00到00:20之间到达的所有车辆（出租车和班车）数量。由于独立泊松随机变量的和仍然服从泊松分布，我们有： $ N([0,20]) (3) $ 即： $ P[N([0,20]) = n] = , n = 0, 1, 2, $

(b) 恰好到达1辆班车和3辆出租车的概率

我们有： $ P[T([0,20]) = 3] = P[S([0,20]) = 1] = $ 因为班车和出租车的到达是独立的，所以恰好到达3辆出租车和1辆班车的概率为： $ P[T([0,20]) = 3] P[S([0,20]) = 1] = () () = = e^{-3} $

(c) 在00:00到00:20之间到达的恰好1辆车辆是出租车的条件概率

设事件 $A$ 为在00:00到00:20之间恰好到达1辆出租车，事件 $B$ 为恰好到达1辆车辆。我们有： $ P[B] = $ 事件 $A \cap B$ 表示在00:00到00:20之间恰好到达1辆出租车和0辆班车： $ P[A B] = $ 因此，条件概率为： $ P[A|B] = = = $

(d) 到达接送区时错过3辆出租车和1辆班车的情况下，等待超过10分钟的概率

你在00:20到达接送区，错过了3辆出租车和1辆班车。等待超过10分钟的事件等同于在00:20到00:30之间没有任何车辆到达。设 $N([20,30])$ 表示在00:20到00:30之间到达的车辆数量，此区间长度为10分钟，因此： $ N([20,30]) ((_1 + _2) ) = (1.5) $ 由于泊松过程在不重叠区间内是独立的，因此： $ P[N([20,30]) = 0] = = e^{-1.5} $