Blitzstein and Hwang条件期望问题39完整求解咨询
嘿，这是Blitzstein and Hwang里那道信用卡轮盘概率题的完整解答，我给你一步步拆解清楚：
问题背景：一群n个朋友经常一起出去吃晚餐，他们玩“信用卡轮盘”来决定谁买单。规则是每次晚餐随机均匀选一个人付全部账单，且每次选择独立于其他晚餐。
(a) 求在k次晚餐中，没有人需要买单超过一次的概率（k ≤ n时不用化简，k > n时完全化简）。
(b) 求每个人至少买单一次所需的晚餐次数的期望（可以保留为简单项的有限和）。
(c) Alice和Bob是其中两个朋友，求k次晚餐中Alice买单次数和Bob买单次数的协方差（完全化简）。
解答
(a) 无人重复买单的概率计算
当 ( k \leq n ) 时：
第一次随便选一个人买单，概率为1；第二次要选之前没买过单的人，概率是 ( \frac{n-1}{n} )；第三次选还没买过的，概率是 ( \frac{n-2}{n} )……以此类推，第k次的概率是 ( \frac{n-k+1}{n} )。把这些独立事件的概率相乘，得到总概率：
[
1 \times \frac{n-1}{n} \times \frac{n-2}{n} \times \dots \times \frac{n-k+1}{n}
]
也可以用排列数简化表示为 ( \frac{P(n,k)}{n^k} )（其中 ( P(n,k) = \frac{n!}{(n-k)!} ) 是从n个元素中选k个的排列数）。当 ( k > n ) 时：
根据鸽巢原理，n个人要承担k次买单（k>n），必然至少有一个人要买单超过一次，所以这个概率直接是 0。
(b) 全员至少买单一次的期望晚餐次数
这是经典的优惠券收集问题，我们用指示变量法来计算期望会更清晰：
设 ( T ) 表示每个人至少买单一次所需的晚餐次数，把 ( T ) 拆成一系列阶段的时间和：
[
T = T_1 + T_2 + \dots + T_n
]
其中：
- ( T_1 )：第一个人买单需要的次数，显然 ( T_1 = 1 )，期望 ( E[T_1] = 1 )；
- ( T_2 )：已经有1个人买过单后，等到第2个新的人买单需要的次数。此时每次选到新的人的概率是 ( \frac{n-1}{n} )，这是几何分布，期望为 ( \frac{n}{n-1} )；
- ( T_i )：已经有 ( i-1 ) 个人买过单后，等到第i个新的人买单需要的次数。此时每次选到新的人的概率是 ( \frac{n - (i-1)}{n} = \frac{n-i+1}{n} )，几何分布的期望为 ( \frac{n}{n-i+1} )；
根据期望的线性性，总期望就是各个阶段期望的和：
[
E[T] = E[T_1] + E[T_2] + \dots + E[T_n] = 1 + \frac{n}{n-1} + \frac{n}{n-2} + \dots + \frac{n}{1} = n \sum_{i=1}^n \frac{1}{i}
]
(c) Alice与Bob买单次数的协方差计算
设 ( X ) 为k次晚餐中Alice买单的次数，( Y ) 为Bob买单的次数，协方差公式为：
[
\text{Cov}(X,Y) = E[XY] - E[X]E[Y]
]
第一步：计算期望 ( E[X] ) 和 ( E[Y] )
( X ) 服从二项分布 ( Binomial(k, \frac{1}{n}) )，所以 ( E[X] = k \times \frac{1}{n} = \frac{k}{n} )；同理 ( E[Y] = \frac{k}{n} )，因此 ( E[X]E[Y] = \frac{k2}{n2} )。
第二步：计算 ( E[XY] )
每次晚餐只能有一个人买单，所以对于任意一次晚餐，Alice和Bob不可能同时买单。设 ( I_j ) 为第j次Alice买单的指示变量（买单则为1，否则为0），( J_l ) 为第l次Bob买单的指示变量，那么 ( I_jJ_j = 0 )（同一晚餐两人不能同时买单）。
而 ( X = \sum_{j=1}^k I_j )，( Y = \sum_{l=1}^k J_l )，展开乘积：
[
XY = \left( \sum_{j=1}^k I_j \right)\left( \sum_{l=1}^k J_l \right) = \sum_{j=1}^k I_jJ_j + \sum_{j \neq l} I_jJ_l
]
因为 ( I_jJ_j = 0 )，所以 ( XY = \sum_{j \neq l} I_jJ_l )，取期望：
[
E[XY] = \sum_{j \neq l} E[I_jJ_l]
]
当 ( j \neq l ) 时，两次晚餐的选择是独立的，所以 ( E[I_jJ_l] = E[I_j]E[J_l] = \frac{1}{n} \times \frac{1}{n} = \frac{1}{n^2} )。( j \neq l ) 的项一共有 ( k(k-1) ) 个，因此：
[
E[XY] = k(k-1) \times \frac{1}{n^2}
]
第三步：代入协方差公式
[
\text{Cov}(X,Y) = \frac{k(k-1)}{n^2} - \frac{k2}{n2} = \frac{k(k-1) - k2}{n2} = \frac{-k}{n^2}
]
备注：内容来源于stack exchange，提问作者Apex345
