信封错装

Messing with Envelops

专题: Probability / 概率
难度: L6
来源: Brainstellar

个人笔记

题目详情

有 $n$ 封信与 $n$ 个信封。把 $n$ 封信随机放入信封（等价于对 $n$ 个编号做均匀随机排列）。

问：最终装对的信封数量的期望是多少？

提示：指示变量 + 期望线性性。

英文原题

There are $n$ letters and $n$ envelopes. You put the letters randomly in the envelopes so that each letter is in one envelope. (Effectively a random permutation of $n$ numbers chosen uniformly). Calculate the expected number of envelopes with the correct letter inside them.

Hint

Use Indicator variables and the Linearity of Expectation

解析

答案是 1。

令 $X_i$ 表示第 $i$ 个信封是否装对（装对为 1，否则为 0），则

E[X_i]=P(\text{第 }i\text{ 封信进第 }i\text{ 个信封})=\frac{1}{n}.

总装对数 $X=\sum_{i=1}^n X_i$ ，因此

E[X]=\sum_{i=1}^n E[X_i]=n\cdot\frac{1}{n}=1.

英文解析

Solution

Let $X_i$ be the indicator random variable such that:

$1$ if the $i$ th letter ends up in the $i$ th envelope.
$0$ otherwise

$E[X_i] = P(X_i = 1) = 1/n$ for any $i$

let $X$ be the number of letters that ended up in their respective envelopes.

Now, $X$ = $X_1 + X_2+ \ldots +X_n$

$E[X] = E[\sum_{i=1}^{n} X_i]$

$= \sum_{i=1}^{n} E[X_i]$ (Using Linearity of Expectations)

$=\sum_{i=1}^{n} (1/n) = 1$

Therefore, we expect on average one letter to be in the correct envelope.