取错外套：轮数的期望与方差

n coats

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

There are $n$ coats in a coat check room, belonging to $n$ people, who make an attempt to leave by picking a coat at random. Those who pick their own coat leave, the rest return the coats and try again. Let $N$ be the number of rounds of attempts until everyone has left. Show that $\mathbb{E}[N] = n$ and $\operatorname {var}(N) = n$ .

解析

设第 $k$ 轮结束后剩余外套数为 $R_k$ ，停止时刻 $N$ 满足 $R_N=0$ 。

每一轮相当于在 $R_k$ 个元素的随机排列中统计“不动点”个数，其期望恒为 1，因此

\mathbb{E}[R_{k+1}\mid\mathcal{F}_k]=R_k-1.

于是 $X_k:=R_k+k$ 为鞅，且 $X_N=R_N+N=N$ ， $X_0=n$ 。可选停止给出

\boxed{\mathbb{E}[N]=n}.

类似地可构造二次型鞅（或用 $\mathbb{E}[R_{k+1}^2\mid\mathcal{F}_k]=R_k^2-2R_k+2$ ）得到

\mathbb{E}[N^2]=n^2+n\Rightarrow \boxed{\operatorname{Var}(N)=n}.