匹配问题：期望匹配数

Average Number of Matches

专题: Probability / 概率
难度: L4
来源: QuantQuestion

题目详情

The following are two versions of the matching problem: (a) From a shuffled deck, cards are laid out on a table one at a time, face up from left to right, and then another deck is laid out so that each of its cards is beneath a card of the first deck. What is the average number of matches of the card above and the card below in repetitions of this experiment?

(b) A typist types letters and envelopes to $\pmb{n}$ different persons. The letters are randomly put into the envelopes. On the average, how many letters are put into their own envelopes?

解析

把每个位置是否匹配记为指示变量 $X_i$ 。

对任意 $i$ ，两副随机排列下第 $i$ 位匹配的概率是 $1/n$ ，所以 $\mathbb{E}[X_i]=1/n$ 。

总匹配数 $X=\sum_{i=1}^n X_i$ ，由期望线性性

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