阿里巴巴筆試題集第23題及分析

題目： 一個骰子， 6 面， 1 個面是 1 ， 2 個面是 2 ， 3 個面是 3 ， 問平均擲多少次能使 1 、 2 、 3 都至少出現一次。

?方法： 面對面試概率題幾乎屢試不爽的分叉樹遞歸列方程法。

?這是一個求數學期望的問題，最終是求 1 ， 2 ， 3 出現至少一次的最短長度的期望。

?這樣分叉樹的每個節點是一個期望狀態，而每個分叉是一次投擲結果。將后續期望出現 1 、 2 、 3 各至少一次的情形記作 L 123 （即題目所求），將后續期望出現 1 、 2 各至少一次（ 3 無關）情形記作 L 12 ，而 1 至少一次（ 2 ， 3 無關）情形 L 1 ，其余數值符號類推，則樹結構如下（列出 4 級結構已經足夠）：

?

接下來，就是要排出方程，因為一共 7 個未知數，如果排出 7 個線性方程就能解決問題。
在此我向大家推薦一個架構學習交流圈。交流學習企鵝群號：948368769（里面有大量的面試題及答案）里面會分享一些資深架構師錄制的視頻錄像：有Spring，MyBatis，Netty源碼分析，高并發、高性能、分布式、微服務架構的原理，JVM性能優化、分布式架構等這些成為架構師必備的知識體系。還能領取免費的學習資源，目前受益良多

?這方程組里的未知數對應上述的狀態，而其數值則是一個對長度（投擲次數）的數學期望。

?根據這個樹狀結構和其中的遞歸關系，這個方程組就是：

L 123 ? = p 1 ? (L 23 + 1) + ? p 2 ? (L 13 +1) + p 3 ? (L 12 ? + 1) = p 1 ? L 23 ? + p 2 ? L 13 +? p 3 ? L 12 ? + 1

（以這個 L 123 為例，解釋，投擲 1 的概率是 p 1 而由此得到的結果是需要期待后續 2 和 3 各至少出現一次，于是長度期望是 L 23 + 1 ，加 1 是因為投擲了一次，亦即即增進一級）

L 23 ? = ? p 1 ? L 23 ? + p 2 ? L 3 +? p 3 ? L 2 ? + 1

L 13 ? = ? p 1 ? L 3 ? + p 2 ? L 13 +? p 3 ? L 1 ? + 1

L 12 ? = ? p 1 ? L 2 ? + p 2 ? L 1 +? p 3 ? L 12 ? + 1

L 1 ? = p 1 + p 2 ? L 1 +? p 3 ? L 1 ? + 1

（這里實際上是 ? L 1 ? =p 1 ? ·1 + p 2 ? (L 1 + 1) + p 3 ? (L 1 ? + 1) ? = p 2 ? L 1 +? p 3 ? L 1 ? + 1 ，因為對 L 1 情形，如果投了 1 就目的達到終止了）

L 2 ? = p 2 + ? p 1 ? L 2 ? +? ? p 3 ? L 2 ? + 1

L 3 ? = p 3 + ? p 1 ? L 3 ? + p 2 ? L 3 + 1

（以上一開始沒注意，多加了懸空的概率項，故計算有誤）

其中 ? p 1 ， p 2 ? 和 ? p 3 分別是擲出 1 ， 2 和 3 的概率，即 1/6 ， 1/3 ， 1/2 。

?于是求解這個方程，得到：

L 1 ? = 6 ， ? L 2 ? = 3 ， ? L 3 ? = 2

L 12 ? = 7 ， ? L 13 ? = 13/2 ， ? L 23 ? = 19/5 6

L 123 ? = ? 219/30 = 7.3 ? 259/36 ~= 7.14

?故以上如果沒有計算錯誤，該題結果是，平均擲 7.3 ? 約 7.14 次可出現這些面值各至少一次。

?【另一解法】感謝 4 樓 aaaxingruiaaa 同學提供的答案（指示器變量法），整理如下：

定義隨機變量 X n ，其可能值為 0 或 1 ，其值為 1 表示 “ 前 n 次擲骰子， 1 ， 2 ， 3 沒能都至少出現一次 ” 的事件，其值為 0 表示這個事件沒有發生，即 “ 前 n 次擲骰子， 1 ， 2 ， 3 各至少出現一次 ” 。

?令 p n 為 “ 擲 n 次骰子， 1 ， 2 ， 3 沒能都至少出現一次 ” 的概率，所以顯然 p n ? = Pr{ X n =1} ，于是 p n ? = 1·Pr{ X n =1} + 0·Pr{ X n =1}?= E[ X n ] ，即這個隨機變量的數學期望。

?令隨機變量 X 表示 1 ， 2 ， 3 剛好全部出現過需要的投擲次數。可見題目要求的就是 E[X] 。

關鍵等式： X = ? Sigma (n=0 to ? Inf; ?X n )??? （這里 Sigma 是求和號，求和范圍是 n 從 0 到無窮大）

?說明一下，等式兩邊都是隨機變量，假設對于某個隨機實例（例如，這里指一次具體的投擲序列），其對應事件是： “ 投了 K 次恰好 1 ， 2 ， 3 都出現了 ” ，于是等式左邊顯然等于 K ；而等式右邊，對于 n < K ，由于這些項的對應定義事件發生了（即 1 ， 2 ， 3 沒能出現），所以他們的實例值是 1 ，而對于 n?K ，則由于對應定義事件都沒發生，實例值為 0 ，可見這個和也是 K 。故兩側相等。（為了達到這個相等關系，可以看出需要把 X 0 包含在內的必要性）

值得注意的是（但對于解這道題也可以不去注意，但注意一下有利于比較深入地理解），對 n < 3 ， X n 顯然恒為 1 。而對于 n?3 ，這些隨機變量不是獨立的。他們的相關性是不容易求出的，唯一容易知道的是，當序列中一個項為 0 時，其后的項均為 0 。好在對于這題我們不需要擔憂這個相關性。

?由于數學期望的加性與隨機變量的相關性無關（這是數學期望一個很令人高興的性質），所以即便這樣， E[X] 也能容易求出：

?E[X] = ? Sigma (n=0 to Inf; E[ X n ] ) =? Sigma (n=0 to ? Inf; ? p n )

?p n 的比較直觀的求法也由 aaaxingruiaaa 同學 提供了，即所謂容斥原理。稍微解釋一下，由于 p n 考慮的是 n 次投擲三者沒有全部出現，于是就是其中兩者出現或僅一者出現。假設單次投擲 1 ， 2 和 3 出現的概率分別為： r 1 ， r 2 和 r 3 。于是 ( r 1 + r 2 ) n 表征 n 次投擲只出現 1 或 2 的概率，這其中包括了出現全 1 和全 2 的情形，于是求 p n 可由這樣的項求和并剔除重復計算的單面值情形，于是：

?p n ? = ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n ，當 n > 0 ； ? 而 p 0 ? = 1 （由定義；同時也可以檢驗看出，這個 p n 在 n 為 1 和 2 的時候都是 1 ）

于是由等比級數（等比數列求和）公式：

E[X] = ? 1 + Sigma (n=1 to Inf; ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n = 1 + (1 - ? r 3 ) /? r 3 ? + (1 - ? r 2 ) / ? r 2 ? + (1 - ? r 1 ) / ? r 1 ? - ? r 1 ? /?(1 - ? r 1 ) - ? r 2 ? /?(1 - ? r 2 ) - r 3 ? /?(1 - ? r 3 ) = 7.3

?【程序仿真】

以下程序進行一千萬輪投擲的仿真，結果基本在 7.3 周圍。至此此題答案 7.3 毫無疑問了。

[csharp]?view plaincopy

 static ? void ?Main( string []?args)?? 
{??
????Random?rand?=?new ?Random();?? 
????int []?diceSurfaces?=? new ? int [6]?{?1,?2,?2,?3,?3,?3?};??? //?6個面 ?? 
????int ?nRounds?=?10000000;? //?投擲輪數 ?? 
????long ?totalTimes?=?0;???? //?所有輪中投擲數加起來的總投擲次數 ?? 
????for ?( int ?iRounds?=?0;?iRounds?<?nRounds;?iRounds++)?? 
????{??
????????bool []?occurred?=? new ? bool [3]?{? false ,? false ,? false ?};?? //?各面值出現標記 ?? 
????????int ?sumPicked?=?0;?? //?出現不同面值個數 ?? 
????????int ?times?=?0;?? 
????????for ?(;?;?)?? 
????????{??
????????????int ?iSurface?=?rand.Next(6);?? 
????????????int ?value?=?diceSurfaces[iSurface]?-?1;?? 
????????????times++;??
????????????if ?(!occurred[value])?? 
????????????{???//?出現新面值 ?? 
????????????????occurred[value]?=?true ;?? 
????????????????sumPicked++;??
????????????????if ?(sumPicked?==?occurred.Length)?? 
????????????????{???//?全部出現，結束此輪 ?? 
????????????????????break ;?? 
????????????????}??
????????????}??
????????}??
????????totalTimes?+=?times;??
????}??
????Console.WriteLine("average?number?of?times?=?{0}" ,?(( double )totalTimes)?/?nRounds);?? 
}??