Problem　I

Example (Expected Number of Matches)
N 個人將他們的帽子丟向房子的中央, 帽子經混合後, 每人隨機選取一頂帽子. 試求取到自己帽子之人數的期望值.
Solution:
令 X 表示取到自己帽子的人數, 則可將 X 寫成 $ X = X_1 + \cdots + X_N $ 其中
$X_i = \left \{ \begin{array}{ll} 1 & \mbox{ if the i}\mbox{th person selects his own hat} \\ \\ 0 & \mbox { otherwise } \end{array} \right .$
因對每一 i, 第 i 人選取任一頂帽子的機會是均等的, 所以
$ E[X_i] = P \{ X_i =1 \} = \displaystyle\frac{1}{N} $
故得
$E[X] = E[X_1] + \cdots + E[X_N] = \left ( \displaystyle\frac{1}{N} \right ) N = 1$
因此, 就平均而言, 恰有一人取到自己的帽子.          $\rule[0.02em]{1.0mm}{1.5mm}$

Example (Coupon-Collecting Problems)
假設有 N 種不同型的優待券, 且設每次所收集到的優待券是屬於任何一 型之優待券的機會是均等的.
(a) 試求在 n 張優待券中所含不同型式優待券的期望數.
(b) 試求要獲得每一種型式至少有一張之整套優待券所需收集之優待券張數的期望數.
Solution:
(a)
令 X 表示在 n 張優待中所含的不同型式之優待券的個數, 則 X 可寫成 $ X = X_1 + \cdots + X_N $ 其中
$ X_i = \left \{ \begin{array}{ll} 1 & \qquad \mbox { 若 n 張優待券中至少含有一張第 i 型的優待券} \\ \\ 0 & \qquad \mbox{ 其他 } \end{array} \right .$
因
$\begin{array}{rcl} E[X_i]&=&P\{X_i=1\} \\ \\ &=&1 - P\{ \mbox{n 張中不含有第 i... ...\} \\ \\ &=&1 - \left ( \displaystyle\frac{N-1}{N} \right )^n \end{array}$
所以
$\begin{array}{rcl} E[X]&=&E[X_1]+\cdots+E[X_N] \\ \\ &=&N \left [ 1 - \left ( \displaystyle\frac{N-1}{N} \right )^n \right ] \end{array}$

(b)
令 Y 表示收集到一整套之前所收集的優待券的張數. 我們利用與求負二項隨機變術同樣的技巧來求 E[Y]. 也就是說, 對 $i=0,1,\ldots,N-1$, 令 Yi 表示在收集 i種不同型式之優待券後直到另一種不同型式之優待券被收集到所需的張數, 且注意到

$ Y = Y_0 + Y_1 + \cdots + Y_{N-1} $
當 i 種不同型式之優待券被收集到後, 一新獲得之優待券為另一種不同型式之優待券的機率為 $ \displaystyle\frac{N-i}{N} $. 故得
$ P\{ Y_i = k \} = \displaystyle\frac{N-i}{N} \left ( \displaystyle\frac{i}{N} \right )^{k-1} \qquad k \geq 1 $
亦即, Yi 為參數是 $ \displaystyle\frac{N-i}{N} $ 的幾何隨機變數. 因此 $E[Y_i] = \displaystyle\frac{N}{N-i}$ 所以
$\begin{array}{rcl} E[Y]&=&1 + \displaystyle\frac{N}{N-1} + \frac{N}{N-2} + \cdo... ...e\frac{1}{N-1}+\frac{1}{N}\right ]\qquad\rule[0.02em]{1.0mm}{1.5mm} \end{array}$