UA MATH564 概率論 QE練習題 信封問題

• 2015年1月的第二題
• 2015年5月的第一題

這一篇介紹QE理論中出現了兩個信封問題相關的題目：2015年1月的第二題和2015年5月的第一題。信封問題最原始的設定是有$n$個信封和$n$個信件，把$n$個信件隨機裝入$n$個信封中。關于這個問題有個非常重要的結論，用$P_m$表示恰好有$m$個信件被放入了正確的信封的概率，則
$$P_m=\frac{1}{m!}\sum _{j=0}^{n?m}\frac{(?1{)}^j}{j!}$$

這個式子的推導也非常容易，根據Waring公式（參考UA MATH564 概率論 計算至少有一個發生的概率：Waring公式）
$$P_m=\sum _{k=m}^n(?1{)}^{k?m}{C}_k^m{S}_k$$

假設事件$A_i$表示第$i$個信件被裝在正確的信封中，則記號$S_k$表示
$$S_k=\sum _{1\le i_1<i_2<?<i_k\le n}P(A_{i_1}\cap A_{i_2}\cap ?\cap A_{i_k})=C_n^k\frac{(n?k)!}{n!}=\frac{1}{k!}$$

這個概率的計算比較簡單，從$n$個信件中抽$k$個，這$k$個的位置是確定的，所以基本事件數目等于另外$(n?k)$個的全排列，基本事件總數等于$n$的全排列。因此
$$P_m=\sum _{k=m}^n(?1{)}^{k?m}{C}_k^m{S}_k=\sum _{k=m}^n(?1{)}^{k?m}\frac{k!}{m!(k?m)!}\frac{1}{k!}=\frac{1}{m!}\sum _{j=0}^{n?m}\frac{(?1{)}^j}{j!}$$

2015年1月的第二題

Part a
這一問比較簡單，不限制每個袋子容納的球的數目，則基本事件總數為$n^n$，每個球都不在對應編號的袋子里的基本事件數目為$(n?1{)}^n$，因此概率為
$$\frac{n^n?(n?1{)}^n}{n^n}$$

Part b
這一問就是典型的信封問題，每個袋子只能容納一個球，每個球都不在對應編號的袋子里的概率，根據信封問題的公式，就是
$$P_0=\sum _{j=0}^n\frac{(?1{)}^j}{j!}$$

但！考試的時候是不能這樣寫的。這里提供兩種推導的思路，分別從概率論與組合學的角度入手，概率論方法的核心是用示性函數的期望表示事件的概率，把復雜概率化歸為簡單概率計算；組合學方法的核心是容斥原理。

概率論方法
引入Bernoulli隨機變量$X_i$，$X_i=1$表示編號為$i$的球被放在對應編號的袋子中，則
$$\begin{gathered} P_0=E\left[\prod _{i=1}^n(1?X_i)\right] \\ =E\left[1?\sum _{i=1}^n{X}_i+(?1{)}^m\sum _{1\le i_1<?<i_m\le n}{X}_{i_1}?X_{i_m}?+(?1{)}^n{X}_1?X_n\right] \end{gathered}$$

假設事件$A_i$表示編號為$i$的球被裝在對應編號的袋子中
$$E[X_{i_1}?X_{i_m}]=P(A_{i_1}\cap A_{i_2}\cap ?\cap A_{i_m})=\frac{(n?m)!}{n!}$$

帶入可得
$$P_0=\sum _{j=0}^n\frac{(?1{)}^j}{j!}$$

組合學方法
沿用上述記號，根據容斥原理，至少有一個球在對應編號的袋子里的基本事件總數為
$$\#\underset{i=1}{\overset{n}{?}}{A}_i=\sum _{i=1}^n\#A_i+(?1{)}^{m+1}\sum _{1\le i_1<?<i_m\le n}\#\underset{j=1}{\overset{m}{?}}{A}_{i_j}+(?1{)}^{n+1}\#\underset{i=1}{\overset{n}{?}}{A}_i$$

其中
$$\#\underset{j=1}{\overset{m}{?}}{A}_{i_j}=(n?m)!$$

基本事件總數為$n!$，因此概率為
$$P_0=\frac{n!?\#{?}_{i=1}^n{A}_i}{n!}=\sum _{j=0}^n\frac{(?1{)}^j}{j!}$$

2015年5月的第一題

這道題其實就是對上一題中概率論方法定義的Bernoulli隨機變量的深入討論。注意到$X_i～Ber(1/n)$，因此
$$E[X_i^2]=1^2\times \frac{1}{n}+0^2\times \frac{n?1}{n}=\frac{1}{n}$$

$X_i{X}_j$也服從Bernoulli分布，
$$\begin{gathered} P(X_i{X}_j=1)=P(X_i=1,X_j=1)=\frac{(n?2)!}{n!}=\frac{1}{n(n?1)} \\ E[X_1{X}_j]=\frac{1}{n(n?1)} \end{gathered}$$

有了這兩個結論，剩下兩個計算就十分容易了
$$\begin{gathered} E[S_n^2]=E{\left(\sum _{i=1}^n{X}_i\right)}^2=\sum _{i=1}^{n}E{X}_i^2+2\sum _{1\le i<j\le n}E{X}_i{X}_j=1+2\times C_n^2\frac{1}{n(n?1)}=2 \\ E[S_n]=\sum _{i=1}^{n}E{X}_i=1 \\ Var(S_n)=E[S_n^2]?(E[S_n]{)}^2=1 \end{gathered}$$

總結

以上是生活随笔為你收集整理的UA MATH564 概率论 QE练习题 信封问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。