CS70 Disc 11A

1 Student Life

问题背景

马库斯为了避免频繁洗衣服，设计了一个系统。每晚，他会选择一件衬衫作为“最脏的衬衫”。第二天早晨，他随机挑选一件衬衫。如果他挑选到“最脏的衬衫”，他就会把它放入脏衣堆，直到洗衣完成。这个过程会不断重复。

(a) 预期天数计算

设定:

设马库斯有 $ n $ 件衬衫。

过程分析:

把将一件衬衫放入脏衣堆的天数视为几何随机变量。对于第一件衬衫，这个几何随机变量的成功概率 $ p = $。
定义 $ X_i $ 为抛出第 $ i $ 件衬衫到脏衣堆所需的天数。对于第 $ i $ 件衬衫，剩下的衬衫数量为 $ n - i + 1 $，因此 $ X_i ( ) $。

计算预期值:

总的洗衣天数是这些变量之和： $ E[X] = E= _{i=1}^{n} E[X_i] $
每件衬衫的预期值为： $ E[X_i] = n - i + 1 $
因此， $ E[X] = {i=1}^{n} (n - i + 1) = {i=1}^{n} i = $

结论

在 $ n $ 件衬衫的情况下，马库斯在每次洗衣之间的预期天数为： $ E[X] = $

(b) 更懒的系统设计

设定:

马库斯随机把衬衫扔到 $ n $ 个不同的位置，每个位置只放一件衬衫。选择一件衬衫作为“最脏的衬衫”，并选择一个位置作为“最脏的位置”。

过程分析:

如果他挑选到“最脏的衬衫”，且这件衬衫在“最脏的位置”，那么这件衬衫会被放入脏衣堆，并且他不会再把其他衬衫放到该位置。该位置也不会再被考虑为将来的“最脏的位置”。

概率计算:

对于第 $ i $ 件衬衫，挑选到“最脏的衬衫”且它在“最脏的位置”的概率为 $ $。

计算预期值:

总的洗衣天数是这些变量之和： $ E[X] = E= _{i=1}^{n} E[X_i] $
每件衬衫的预期值为： $ E[X_i] = $
因此，总预期值为： $ E[X] = {i=1}^{n} = {i=1}^{n} i^2 = $

结论

在懒惰设计的情况下，马库斯在每次洗衣之间的预期天数为： $ E[X] = $

2 Elevator Variance

问题背景

在一栋有 $ n $ 层楼的建筑中，地面楼层标记为 G。在地面上，有 $ m $ 个人一起进入电梯，每个人独立且均匀地选择一层 $ n $ 上楼层下车。我们需要计算电梯不停止的楼层数量的方差。

解决方案

设定变量：

设 $ N $ 为电梯不停止的楼层数量。
用指示变量 $ I_i $ 表示在第 $ i $ 层是否有人下车：
- 如果没有人下车，则 $ I_i = 1 $；否则 $ I_i = 0 $。

**构造 $ N $：**$ N = I_1 + I_2 + + I_n $

1. 计算期望值 $ E[N] $

$ E[I_i] $ 为在第 $ i $ 层没有人下车的概率： $ E[I_i] = P[I_i = 1] = ( )^m $
利用期望的线性性质： $ E[N] = _{i=1}^{n} E[I_i] = n ( )^m $

2. 计算 $ E[N^2] $

利用 $ N $ 的定义展开： $ E[N^2] = E$
展开平方： $ E[N^2] = E= _{i,j} E[I_i I_j] $
这可以分为两部分：
- 当 $ i = j $ 时： $ _{i} E[I_i^2] = n E[I_i] = n ( )^m $
- 当 $ i j $ 时： $ _{i j} E[I_i I_j] = n(n-1) P[I_i = I_j = 1] = n(n-1) ( )^m $
综合上述两部分： $ E[N^2] = n ( )^m + n(n-1) ( )^m $

3. 计算方差 $ (N) $

使用方差的定义： $ (N) = E[N^2] - (E[N])^2 $
将计算得到的期望值代入： $ (N) = - ^2 $

总结

期望不停止楼层数量的计算： $ E[N] = n ( )^m $
方差的计算公式： $ (N) = E[N^2] - (E[N])^2 $
最终的方差表达式： $ (N) = n ( )^m + n(n-1) ( )^m - n^2 ( )^{2m} $

3 Covariance

问题背景

我们有两种情况来计算两个指示随机变量 $ X_1 $ 和 $ X_2 $ 之间的协方差。

情况 (a): 一个袋子中有 5 个红球和 5 个蓝球，不放回地随机抽取两个球。
情况 (b): 有两个袋子 A 和 B，每个袋子中都有 5 个红球和 5 个蓝球。首先从 A 中抽取一个球并记录其颜色，然后将其放入 B 中，再从 B 中抽取一个球并记录其颜色。

我们需要计算 $ (X_1, X_2) $，即两次抽取的球都是红球的事件之间的协方差。

解决方案

(a) 计算 $ (X_1, X_2) $

定义指示变量：

$ X_1 $ 表示第一个球是红球的事件。
$ X_2 $ 表示第二个球是红球的事件。

计算期望值：

计算 $ E[X_1] $：
- 抽到红球的概率为： $ E[X_1] = P() = = $
计算 $ E[X_2] $：
- 由于是没有放回抽取，第二个球是红球的概率为： $ E[X_2] = P() = + = = $
计算 $ E[X_1 X_2] $：
- 当第一个球是红球时，第二个球是红球的概率为： $ E[X_1 X_2] = P( ) = P(X_1 = 1 X_2 = 1) = = $
计算协方差：
- 使用协方差公式： $ (X_1, X_2) = E[X_1 X_2] - E[X_1] E[X_2] $
- 代入计算得到： $ (X_1, X_2) = - ( ) = - = - $

(b) 计算 $ (X_1, X_2) $

定义指示变量：

$ X_1 $: 从袋 A 中抽取的球是红球的事件。
$ X_2 $: 从袋 B 中抽取的球是红球的事件。

计算期望值：

计算 $ E[X_1] $：
- 仍然是： $ E[X_1] = P() = = $
计算 $ E[X_2] $：
- 取决于第一个球的颜色： $ E[X_2] = + = ( + ) = = $
计算 $ E[X_1 X_2] $：
- 如果第一个球是红球，袋 B 中有 6 个红球： $ E[X_1 X_2] = = $
计算协方差：
- 使用协方差公式： $ (X_1, X_2) = E[X_1 X_2] - E[X_1] E[X_2] $
- 代入计算得到： $ (X_1, X_2) = - ( ) = - = $