重拾「概率論」

Content

隨機變量與期望
- 分析幾何分布
- 分析快速排序
經(jīng)典概率論問題
- 匹配問題(Match Problem)
- 生日問題(Birthday Problem)
- 秘書問題(Secretary Problem)

這個學(xué)期上了Prof. Sheldon Ross的<Elements of Stochastic Processes>稳析，總算是把本科階段時曾經(jīng)粗淺地接觸過企孩、但是現(xiàn)在早已忘掉絕大部分的概率論知識給重新?lián)炱饋砹耸渭啊Ｗ晕腋杏X概率論的水平有不小的提高徽缚，于是決定趁熱打鐵整理一下筆記哲鸳，寫下這篇小文章霜幼。

隨機變量與期望

隨機變量是一座橋梁瘾婿，它的一端是這個世界上的各種或復(fù)雜或簡單的隨機現(xiàn)象(不確定性是這個世界的本質(zhì)之一)恬惯，另一端是包括代數(shù)計算在內(nèi)的各種數(shù)學(xué)工具向拆。對于隨機現(xiàn)象，我們可以定義一個隨機變量 $X$ 酪耳，針對每一種可能出現(xiàn)的結(jié)果浓恳，我們都可以給這個隨機變量賦予一個取值，這樣一來碗暗，我們就能夠運用數(shù)學(xué)的力量來對這個世界的隨機性進行分析颈将。很多時候，我們關(guān)心的是平均值言疗，我們有下面四種方法來計算隨機變量 $X$ 的期望值(均值)：

$\begin{eqnarray*} E(X) &=& \sum_k k\ P(X=k) \tag{1} \\ E(X) &=& E(\sum_i X_i) = \sum_i E(X_i) \tag{2} \\ E(X) &=& \sum_k E(X\ |\ Y=k)\ P(\ Y=k) \tag{3} \\ E(X) &=& E[E(X\ |\ Y)] \tag{4} \end{eqnarray*}$

(1)式是隨機變量期望值的定義式晴圾。由于使用這一公式需要知道該隨機變量的概率質(zhì)量函數(shù)——當(dāng)你已知其概率質(zhì)量函數(shù)時，你可以求出包括期望噪奄、方差等在內(nèi)的所有統(tǒng)計值——而在復(fù)雜的現(xiàn)實世界中我們很難得到一個變量的分布表達式（甚至很多時候連求出均值都顯得困難）死姚，因此該式使用相對較少。

(2)式表明勤篮，當(dāng)一個隨機變量可以表示成若干個隨機變量之和的形式時都毒，它的期望即為這些變量的期望之和。當(dāng)一個隨機事件可以拆解成具有先后順序的子事件時碰缔，這一表達式很有效账劲。

(3)式是計算期望值最常用的式子，實際上金抡，「條件于(conditioning on )」是概率論體系中最為核心的技術(shù)之一瀑焦。在分析現(xiàn)實世界的隨機現(xiàn)象時，如果你能夠獲取額外的信息，這便意味著一些本是未知且隨機的元素不再隨機，而是成為了確定性因素墓懂，這將影響你原本的分析計算結(jié)果。

(4)式又叫條件恒等式(Conditioning Identity)榆芦，是同時應(yīng)用了(1)(3)兩式得到的柄粹，根據(jù)求隨機變量函數(shù)值的期望值的公式，我們有

$E(h(X)) = \sum_x h(x) P(X=x) \implies E[E(X|Y)] = \sum_y E(X|Y = y) P(Y=y)= E(X) \tag{5}$

注意到 $E(X\ |\ Y)$ 是隨機變量 $Y$ 的函數(shù)值(仍舊是一個隨機變量)匆绣，它表示驻右，當(dāng)變量 $Y$ 取不同的值(這是隨機事件)時，變量 $X$ 的期望值(這是一個數(shù)值)也隨之變化崎淳，這正是隨機變量的定義(由某一隨機現(xiàn)象得到某一對應(yīng)的數(shù)值)堪夭，因此， $E(X\ |\ Y)$ 是一個隨機變量拣凹。

下面我們通過一些例子來展示這四個式子的運用森爽。

分析幾何分布

一系列相互獨立的試驗，每次試驗成功的概率都是 $p$ 嚣镜，用隨機變量 $X$ 表示出現(xiàn)第一次成功試驗時所需要的試驗次數(shù)爬迟，其概率質(zhì)量函數(shù)為 $P(X=k) = (1-p)^{k-1}p, \ k \ge 1$ 。這樣的一個隨機變量服從幾何分布菊匿。

使用(1)式來計算其期望值如下(在第二行運用了求導(dǎo)與求和運算次序的可交換性)

$E(X) = \sum_{k=1}^{\infty}{kP(X=k)} = \sum_{k=1}^{\infty}k(1-p)^{k-1}p \\ = p \sum_{k=1}^{\infty}{\fracmi01qqz{dp} (1-p)^{k}} = p \fract60f0ma{dp}[\sum_{k=1}^{\infty}{(1-p) ^k}]\ \\ = p \fraci0sx6pk{dp}[\frac{1-p}{p}] = p*\frac{1}{p^2} = \frac{1}{p}$

使用(2)式付呕，設(shè)隨機變量 $A$ 為第一次實驗過后仍需要幾次實驗才能出現(xiàn)第一次成功，即 $X=1+A$ 跌捆。因此徽职， $P(A=0) = p$ ，該式表示第一次試驗就成功了佩厚，所以不再需要額外的試驗姆钉； $P(A = n) = (1-p)^n\ p$ ，該式表示前n次試驗都失敗了抄瓦，在第 $n+1$ 次試驗時才終于成功潮瓶。于是有：

$E(A) = \sum_{n=1}^{\infty}{np(1-p)^n} = (1-p)\sum_{n=1}^{\infty}np(1-p)^{n-1} = (1-p)E(X) \\ E(X) = E(1+A) = E(A) + 1 \\ \implies E(X) = \frac{1}{p}$

使用(3)式，定義隨機變量 $Y$ 闺鲸，當(dāng)首次試驗成功時取值1筋讨，失敗時則取值0埃叭。條件于 $Y$ 來計算 $X$ 的期望值如下：

$E(X) = E(X\ | Y=0)P(Y=0) + E(X\ | Y=1)P(Y=1) \\ = E(X\ | Y=0)*(1-p) + E(X\ | Y=1)*p \\ = (E(X) + 1) * ( 1-p) + 1 * p \\ = E(X) * (1-p) + 1 \\ \implies E(X) = \frac{1}{p}$

如果我們定義隨機變量 $Z = E(X\ |\ Y)$ 如下摸恍， $Z=\begin{cases} 1, Y=1 \\ E(X) +1, Y=0 \\ \end{cases}?$ ，那么按照(4)式對變量 $Z$ 求期望便能求出 $E(X)$ 赤屋。對比(3)式的求解過程立镶，我們可以看到(4)式本質(zhì)上是在運用(3)式。

現(xiàn)在我們同時運用(2)(3)來計算方差类早。

$\begin{eqnarray*} E(X^2) &=& E(X^2|Y=1)P(Y=1) + E(X^2|Y=0)P(Y=0) \\ &=& 1 *p + (1-p) * E[A^2 + 2A +1\ | Y=0] \\ &=& p + (1-p) * [E(A^2\ |Y=0) + 2E(A\ | Y=0) + 1]\\ &=& p + (1-p) * (E(X^2) + 2E(X) + 1) \\ &=& p + (1-p) * (E(X^2) + \frac{2}{p} + 1) \\ &=& \frac{2-p}{p} + (1-p) E(X^2) \\ & \implies & E(X^2) = \frac{2-p}{p^2} \\ & \implies& Var(X) = E(X^2) - E^2(X) = \frac{2-p}{p^2} - \frac{1}{p^2} = \frac{1-p}{p^2} \tag{6} \end{eqnarray*}$

注意到媚媒，僅考慮 $X=1+A$ 時，變量 $A$ 是不服從幾何分布的涩僻，但是在引入「第一次實驗失敗了」這個條件后缭召，在得知這個原本未知的信息之后栈顷，隨機變量 $\{ A\ |\ Y=0 \}$ 成為了一個服從幾何分布的隨機變量，其參數(shù)和 $X$ 完全相同嵌巷，所以有 $E(A\ | Y=0) = E(X)$ 和 $E(A^2\ |Y=0) = E(X^2)$ 萄凤。

下面我們考慮一個以幾何分布為基礎(chǔ)的問題。現(xiàn)在變量 $X$ 不再表示出現(xiàn)第一次成功試驗時所需要的試驗次數(shù)搪哪，而表示連續(xù)出現(xiàn)k次成功試驗時所需要的試驗次數(shù)靡努。試求變量 $X$ 的期望。

要想最大化條件期望這一工具的威力晓折，我們要找到合適的變量來作為條件』箅現(xiàn)定義變量 $Y$ 為出現(xiàn)第一次失敗時所需要的試驗次數(shù)，這個變量將幫助我們輕松求出 $X$ 的期望值漓概。

以 $k=10$ 為例漾月，獨立隨機試驗的設(shè)定在于，哪怕你已經(jīng)連續(xù)9次成功垛耳，你也不能確定下一次就會成功栅屏。不管在連續(xù)9次成功之后失敗了，還是在連續(xù)3次成功之后失敗了堂鲜，得到的結(jié)果都是一樣的栈雳，同樣是回到了游戲的起點，同樣是需要從頭再來缔莲。所以我們有：

$E(X\ |\ Y = n)=\begin{cases} n + E(X), \quad n \le k\\ k,\quad n \gt k \\ \end{cases}$

利用(3)式來求其期望值：

$\begin{eqnarray*} E(X) &=& \sum_{i=1}^{\infty} E(X\ |\ Y = i) * P(Y=i) = \sum_{i=1}^k(i+E(X))*(1-p)*p^{i-1} + \sum_{i=k+1}^{\infty}(1-p)*p^{i-1}*k \\ &=& \sum_{i=1}^ki*(1-p)*p^{i-1} + \sum_{i=1}^kE(X)*(1-p)*p^{i-1} + \sum_{i=k+1}^{\infty}(1-p)*p^{i-1}*k \\ &=& \frac{1-p^k}{1-p} - k*p^k + E(X)*(1-p^k) + k*p^k \\ &=& \frac{1-p^k}{1-p} + E(X) - p^k *E(X) \\ & \implies & E(X) = \frac{1-p^k}{(1-p)*p^k}= \frac{1/p^k - 1}{1-p} \tag{7} \end{eqnarray*}$

接著我們進一步拓展哥纫。幾何分布的試驗只有兩種結(jié)果，即成功與失敗〕兆啵現(xiàn)在我們對其推廣蛀骇，假設(shè)每次獨立隨機試驗都會有m種可能結(jié)果，每種結(jié)果出現(xiàn)的概率都是 $\frac{1}{m}$ 读拆，用隨機變量 $N$ 表示任意一種結(jié)果連續(xù)出現(xiàn)k次所需要的試驗次數(shù)擅憔。試求 $N$ 的期望值。

這又是一道初看很棘手檐晕，但使用條件期望就能輕松解決的問題暑诸。用 $N_i$ 表示任意一種結(jié)果連續(xù)出現(xiàn) $i$ 次所需要的的試驗次數(shù)，那么有 $E(N) = E(N_k)$

$E(N_i\ |\ N_{i-1}) = N_{i-1} + [\frac{1}{m} * 1 + (1 - \frac{1}{m}) * E(N_i)] \tag{8}$

對(8)式兩邊求期望：

$\begin{eqnarray*} E(E(N_i\ |\ N_{i-1})) = E(N_i) &=& E(N_{i-1}) + \frac{1}{m} + (1-\frac{1}{m}) E(N_i) \\ \implies E(N_i) &=& m E(N_{i-1}) + 1 \\ E(N_1) &=& 1 \\ \implies E(N_n) &=& \sum_{j=0}^{n-1} m^j \\ \implies E(N_k) &=& \sum_{j=0}^{k-1} m^j = \frac{m^k - 1}{m - 1}= E(N) \tag{9} \end{eqnarray*}$

在(7)式中辟灰，令 $p = 1/2$ 則有 $E(X) = 2*(2^k -1)$ 个榕；在(8)式中，令 $m=2$ 芥喇，則有 $E(N) = 2^k -1$ 西采。這兩個結(jié)果是一致的，之所以差了個倍數(shù)2继控，是因為在后一題里械馆，任意一種結(jié)果出現(xiàn)k次就行胖眷，而在前一題里，需要特定某個結(jié)果出現(xiàn)k次才行霹崎。

分析快速排序

快速排序是一種常用的排序算法瘦材，隨機從數(shù)列中選出一個數(shù)字，數(shù)列中剩余的所有數(shù)字和它進行比較仿畸，比它小的落入到左側(cè)的子數(shù)列中食棕，比它大的落入到右側(cè)的子數(shù)列中，然后對這兩個子數(shù)列分別進行同樣的操作错沽，重復(fù)下去簿晓，直到每個子數(shù)列只有1個或2個數(shù)字為止。最后我們將得到一個從左到右依照從小到大排列好的數(shù)列千埃。這是典型的分治法應(yīng)用憔儿，將一個復(fù)雜的大問題不斷地拆解成容易解決的小問題。

為了分析這一算法放可，我們先定義一些必要的變量谒臼。用 $X$ 表示完成對一個數(shù)列的排序所需要進行的大小比較的次數(shù)；用 $M_n$ 表示對一個長度為n的數(shù)列進行排序平均需要進行多少次大小比較耀里；用 $R$ 表示第一個隨機選取的數(shù)字在全體n個數(shù)字中的排名蜈缤，如果 $R=i$ ，那么有 $i-1$ 個數(shù)字比這個數(shù)小冯挎，落入它的左側(cè)底哥，有 $n-i$ 個數(shù)字比它大，落入它的右側(cè)房官。根據(jù)條件期望我們得到：

$\begin{eqnarray*}E(X) = M_n &=& \sum_{i=1}^nE(X\ |\ R=i)P(R = i) \\&=& \frac{1}{n} \sum_{i=1}^nE(X\ |\ R=i) \\ &=& \frac{1}{n}\sum_{i=1}^n[n-1+M_{i-1} + M_{n-i}] \\&=& n-1 + \frac{1}{n}[\sum_{i=1}^nM_{i-1}+\sum_{i=0}^{n-1}M_i]\\ &=& n-1 + \frac{2}{n} \sum_{i=0}^{n-1}M_i \\&=& n-1 + \frac{2}{n} \sum_{i=2}^{n-1}M_i \tag{10} \ (since \ M_0=M_1 = 0) \end{eqnarray*}$

用 $n-1$ 替換 $n$ 之后兩式相減：

$n*M_n =n(n-1)+2\sum_{i=2}^{n-1}M_i \\ (n-1)*M_{n-1} = (n-1)(n-2) + 2 \sum_{i=2}^{n-2} M_i \\ \implies n M_n - (n-1)M_{n-1} = 2 (n-1) + 2 M_{n-1} \\ \implies nM_n = 2(n-1) + (n+1)M_{n-1} \\ \implies \frac{M_n}{n+1} = \frac{2(n-1)}{n(n+1)} + \frac{M_{n-1}}{n} \\ \implies \frac{M_n}{n+1} = \frac{2(n-1)}{n(n+1)} + \frac{2(n-2)}{(n-1)n} + \frac{M_{n-2}}{n-1} = \cdots \\ \implies \frac{M_n}{n+1} = 2\sum_{k=0}^{n-2} \frac{n-1-k}{(n-k)(n+1-k)} \\$

兩邊同時乘以 $n+1$ 后我們便能得到 $M_n$ 的一般表示式：

$\begin{eqnarray*} M_n &=& 2(n+1)\sum_{k=0}^{n-2} \frac{n-1-k}{(n-k)(n+1-k)} \\ &=& 2(n+1)\sum_{i=1}^{n-1}\frac{i}{(i+1)(i+2)} \\ &=& 2(n+1)\sum_{i=1}^{n-1}(\frac{2}{i+2} - \frac{1}{i+1}) \\ &\approx& 2(n+1)[\int_3^{n+1}\frac{2}{x}dx - \int_2^n\frac{1}{x}dx] \\ &=& 2(n+1)[2log(n+1) - logn + log2 - 2log3] \\ &=& 2(n+1)[log(n+1) + log(\frac{n+1}{n})+ log2-2log3] \\ &\approx&2(n+1)log(n+1) \tag{11} \end{eqnarray*}$

由此可知趾徽，快速排序算法是平均復(fù)雜度為 $O(nlogn)$ 的排序算法。

經(jīng)典概率論問題

匹配問題(Match Problem)

有n個人在一個房間里聚會翰守，每個人頭戴一頂帽子孵奶，現(xiàn)在大家都把帽子放到房間中心的一個箱子里，每個人依次上前去隨機抽取帽子蜡峰，如果他剛好抽到了他自己的那頂帽子了袁，我們說此時產(chǎn)生了一個匹配(match)。用隨機變量 $X$ 表示產(chǎn)生了多少個匹配事示。試求(a) $X$ 的期望值早像；(b) $X$ 的概率質(zhì)量函數(shù)僻肖。

對于 (a)問肖爵，利用(2)式可以輕松求出，令 $X=\sum_{i=1}^nX_i$ 臀脏，其中 $X_i$ 表示第i個人是否成功地拿到了自己的那頂帽子劝堪。

$P(X_1 = 1)= \frac{1}{n}$

$P(X_2=1) = \frac{n-1}{n} * \frac{1}{n-1} = \frac{1}{n}$ ,該式表示第一個人沒有拿走屬于第二個人的帽子冀自，然后第二個人順利地拿到了他的那頂帽子。于是有：

$P(X_i) = \frac{1}{n}, i=1,2, \ldots, n \\ \implies E(X) = \sum_{i=1}^n E(X_i)= n* \frac{1}{n}=1$

這一結(jié)果意味著秒啦，不管房間里有多少個人熬粗，平均而言只有一個人可以拿到屬于他的那頂帽子。

對于(b)問余境，為了求出 $p(X=k)$ 驻呐，我們需要先求出 $p(X=0)$ ，雖然這一項指的是所有人都沒有拿到自己的那一頂帽子芳来，但是不能簡單地用鏈?zhǔn)椒▌t來求解：

$p(X=0)=\frac{n-1}{n} *\frac{n-2}{n-1}*…* \frac{2}{3} * \frac{1}{2} = \frac{1}{n}$

上式是錯誤的計算方法含末，對于「第一個人沒有拿到他的帽子」這個事件，需要分類成「第一個人拿到了第二個人的帽子」和「第一個人拿到了既不屬于他也不屬于第二個人的帽子」這兩個子事件即舌，然后你才能去研究第二個人的匹配情況佣盒。

我們需要借助條件概率來求解，用 $Z$ 表示事件「產(chǎn)生匹配的數(shù)量為零」顽聂，用 $M$ 表示事件「第一個人拿到了他的那頂帽子」肥惭，用 $NM$ 表示事件「第一個人沒有拿到他的那頂帽子」，用變量 $P_n$ 表示「n個人中沒有產(chǎn)生匹配」的概率紊搪。則有：

$P_n = p(Z) = p(Z\ |\ M)p(M) + p(Z\ |\ NM)P(NM) = 0 + \frac{n-1}{n}p(Z\ |\ NM) = \frac{n-1}{n}p(Z\ |\ NM)$

若第一個人沒有選走他帽子蜜葱，則他的帽子留在了剩余的n-1頂帽子中，成為了「多余的帽子」(因為這頂帽子沒有被他的主人取走)耀石，而他所拿走的那頂帽子的主人則成了「多余的人」(因為他沒有機會取走他自己的帽子了)×ぃ現(xiàn)在我們來研究一下事件 $\{Z\ |\ NM \}$ 。這一事件分為兩個子事件：

剩余n-1個人里沒有產(chǎn)生匹配娶牌，并且多余的人拿走了那頂多余的帽子奔浅，將此稱為事件A
剩余n-1個人里沒有產(chǎn)生匹配，并且多余的人沒拿走那頂多余的帽子诗良，將此稱為事件B

$p(A) = \frac{1}{n-1}*p_{n-2}$

$p(B) = p_{n-1}$ ,把多余的帽子看做歸屬于多余的人汹桦，這樣一來，第一個人走后鉴裹，剩下的n-1個人都還有機會拿到自己的那頂帽子舞骆。

$\begin{eqnarray*} P_n &=& \frac{n-1}{n} * (P_A + P_B ) \\ &=& \frac{n-1}{n}*(\frac{1}{n-1}*p_{n-2} + p_{n-1}) \\ &=& \frac{n-1}{n}*p_{n-1} + \frac{1}{n}*p_{n-2} \\ \implies P_n - P_{n-1} &=& -\frac{1}{n}(P_{n-1} -P_{n-2}) \\ P_1 = 0 &,& P_2 = \frac{1}{2}\\ P_3-P_2 &=& -\frac{1}{3}(P_2 - P_1) = -\frac{1}{3!} \\ P_4 - P_3 &=& -\frac{1}{4}(P_3 - P_2) = \frac{1}{4!} \\ & \cdots \cdots& \\ P_n &=& P_2 +\sum_{i=3}^{n} \frac{(-1)^i}{i!} = \sum_{i=2}^{n} \frac{(-1)^i}{i!} = \sum_{i=0}^{n} \frac{(-1)^i}{i!} \tag{12} \end{eqnarray*}$

現(xiàn)在我們可以求出 $P(X=k)$ 了，將所有人分成兩隊(一共有 $C_n^k$ 種分法)径荔，一隊有k個人督禽，他們中的每個人都拿到了自己的帽子；另一隊有n-k個人总处，每個人都沒有拿到自己的帽子狈惫。

$\begin{eqnarray*} P(X=k) &=& C_n^k* \frac{1}{n} \frac{1}{n-1} \frac{1}{n-2} \cdots \frac{1}{n-(k-1)} P_{n-k} \\ &=& C_n^k *\frac{(n-k)!}{n!} P_{n-k} \\ &=& \frac{n!}{k! (n-k)!} \frac{(n-k)!}{n!} P_{n-k} \\ &=& \frac{1}{k!} P_{n-k} = (\sum_{i=0}^{n-k} \frac{(-1)^i}{i!} ) / k! \tag{13} \end{eqnarray*}$

有了概率質(zhì)量函數(shù)之后，我們可以用期望的定義式即(1)式來驗證(a)問的結(jié)果：

$E(X) = \sum_{k=1}^n k* P(X=k) = \sum_{k=1}^n [k* (\sum_{i=0}^{n-k} \frac{(-1)^i}{i!} ) / k!] = \sum_{k=1}^n [(\sum_{i=0}^{n-k} \frac{(-1)^i}{i!} ) / (k-1)!]$

利用 $\sum_{i=1}^n \frac{x^i}{i!} = e^x, n \to \infty$ 可以化簡這一結(jié)果：

$E(X) = \sum_{k=1}^n [e^{-1}/ (k-1)!] = e^{-1} \sum_{k=1}^n \frac{1}{(k-1)!} = e^{-1} * e^{1} = 1 \tag{14}$

結(jié)果與(a)問的答案一致鹦马。下面我們拓展原問題胧谈，現(xiàn)在規(guī)定忆肾，在第一輪里拿到了自己帽子的人離開房間，剩下的人把拿錯的帽子放回箱子里菱肖，繼續(xù)隨機抽取客冈，重復(fù)進行下去直到所有的人都拿回自己的帽子為止。用變量 $R$ 表示需要經(jīng)過多少輪才能讓所有人都拿回帽子稳强。試求 $R$ 的期望场仲。

從(a)題的結(jié)果我們知道，不管房間里有多少人退疫，平均而言燎窘，一輪中只有一個人能夠拿回自己的帽子，于是我們直觀猜測 $E(R)=n$ √憧В現(xiàn)在我們用數(shù)學(xué)歸納法來證明這個結(jié)論褐健。

用 $R_n$ 表示當(dāng)房間里有n個人時需要經(jīng)過多少輪才能使所有人拿到自己的帽子，有 $E(R)=E(R_n)$ 澜汤；用變量 $X$ 表示第一輪里有多少人拿到了自己的帽子(即匹配的數(shù)量)蚜迅。顯然， $E(R_1)=1$ 成立俊抵，現(xiàn)在我們假設(shè)有 $E(R_{n-1}) = n-1$ 谁不，可以得到：

$\begin{eqnarray*} E(R_n) &=& \sum_{i=0}^n E(R_n\ |\ X=i) P(X=i) \\ &=& \sum_{i=0}^n (1 +E(R_{n-i})) *P(X=i) \\ &=& 1 + E(R_n) P(X=0) + \sum_{i=1}^n E(R_{n-i})P(X=i) \\ &=& 1 + E(R_n) P(X=0) + \sum_{i=1}^n (n-i) P(X=i) \\ &=& 1 + E(R_n) P(X=0) + n \sum_{i=1}^n P(X=i) - \sum_{i=1}^n i P(X=i) \\ &=& 1 + E(R_n) P(X=0) + n(1-P(X=0)) - E(X) \\ &=& E(R_n) P(X=0) + n(1-P(X=0)) \\ \implies & & (1-P(X=0))*E(R_n) = (1-P(X=0))*n \\ \implies & & E(R_n) = n \tag{15} \end{eqnarray*}$

證明完成。

生日問題(Birthday Problem)

在一個教室里坐著n個學(xué)生徽诲，假設(shè)每個人在任意一天出生的概率相同刹帕，都為 $1 / 365$ ，那么這n個學(xué)生中谎替，有兩個人在同一天過生日的概率是多少偷溺？

用 $A$ 表示事件「至少有兩個人在同一天出生」，用 $A^{'}$ 表示事件「沒有人的生日相同」钱贯，由于這兩個事件互補挫掏，所以有 $P(A) + P(A^{'}) = 1$ 。我們從 $P(A^{'})$ 著手秩命，因為它比 $P(A)$ 的計算要簡單得多尉共。事件 $A^{'}$ 意味著，第一人在某一天出生了弃锐，第二個人的生日與他不同袄友；第三個人的生日既和第一個人不同，也和第二個人不同霹菊；第四個人的生日和前面三個人的生日都不相同剧蚣，以此類推，第n個人的生日和前n-1個人的生日都不相同。所以有：

$P(A^{'}) = 1 * (1 - \frac{1}{365}) * (1 - \frac{2}{365})*(1 - \frac{3}{365}) \cdots (1 - \frac{n-1}{365}) \\ = \frac{365 * 364 * 363 * \cdots (365- n+1)}{365^n} \\ = \frac{365!}{365^n (365-n)!} \\ \implies P(A) = 1 - P(A^{'}) = 1 - \frac{365!}{365^n (365-n)!} \tag{16}$

當(dāng)n=23時券敌， $P(A)=0.507297$ ；當(dāng)n=57時柳洋， $P(A) = 0.99012$ 待诅。這意味著，只需要有23個人熊镣，就有超過一半的幾率出現(xiàn)兩個人同一天過生日(對于概率論不熟悉的人可能會猜測至少需要157人)卑雁；只需要57個人，就能使這一概率值高達99%绪囱。以人數(shù)為橫軸测蹲，概率值為縱軸，繪圖如下：

Birthday Problem

秘書問題(Secretary Problem)

這個問題有各種版本的場景描述(最初的場景是要從眾多的候選者中選出綜合能力最好的那個秘書)鬼吵，而我個人傾向于這樣來描述：在你生日這天扣甲，你的n個好朋友排成一隊給你送紅包，但在這n份紅包中你只能接受一份齿椅。每次拿到紅包后琉挖，你可以拆開紅包來查看面額大小，如果滿意涣脚，你選擇接受這一紅包示辈，游戲結(jié)束；如果不滿意遣蚀，你拒絕這份紅包(事后不能反悔)矾麻，然后去拆下一份紅包。這個問題的目標(biāo)是拿到面額最大的那個紅包芭梯，它的難點在于险耀，每一份紅包的面額大小都是純粹隨機的，不管你已經(jīng)見過多少份紅包玖喘，下一份紅包對于你而言仍舊是完全未知的(雖然見過的紅包越多胰耗，對于面額的相對大小的判斷越準(zhǔn)確)。

直觀上來看芒涡，n越大柴灯，紅包數(shù)量越多，拿到最大的那一份紅包就越困難费尽。用數(shù)學(xué)的語言來說就是赠群， $W$ 表示事件「拿到最大的紅包」，有 $n \rightarrow \infty, P(W) \rightarrow 0$ 旱幼。但是查描，下面我們將看到，在采用適當(dāng)?shù)牟呗灾螅?img class="math-inline" src="https://math.jianshu.com/math?formula=P(W)%20%3D%201%2Fe" alt="P(W) = 1/e" mathimg="1">是一個恒定不變的常數(shù)，與n的大小無關(guān)冬三。

這樣的策略稱為k-policy匀油，它的做法是，不管最開始的k個紅包面額如何勾笆，都不要接受敌蚜，在這之后，如果遇到一個比前k個面額都大的紅包窝爪，就接受它弛车，如果一直沒有遇到比前k個面額大的紅包，那么就接受最后一個紅包(即第n個)蒲每。下面我們來求這種策略下的 $P(W)$ . 用隨機變量 $y$ 表示最大紅包所在的位置纷跛， $y \le n$ . 則有：

$P(W) = \sum_i^n P(W |\ y=i)P(y=i) = \frac{1}{n}\sum_i^n P(W |\ y=i)$

$P(W |\ y=i ) =\begin{cases} 0, i \le k\\ P(best\ of\ first\ i ? 1\ is\ among\ the\ first\ k) = \frac{k}{i-1}, i >k \end{cases}$

好好品味一下 $i>k$ 時的這個表達式，如果前 $i-1$ 個紅包中最大的那個在前k個位置里邀杏，就能確保在此之后贫奠、在最大的紅包之前，不會有紅包被選走望蜡。
$P(W) = \frac{1}{n} \sum_{i=k+1}^n{\frac{k}{i-1}} \approx \frac{k}{n} \int_k^{n-1}{\frac{1}{x}dx} = \frac{k}{n} *ln{\frac{n-1}{k}} \approx \frac{k}{n}*ln{\frac{n}{k}}$

考慮關(guān)于x的函數(shù) $f(x) = \frac{x}{n} * ln{\frac{n}{x}}$ 叮阅，對其進行求導(dǎo)。

$f '(x) = \frac{1}{n}*ln{\frac{n}{x}} -\frac{x}{n} * \frac{x}{n} \frac{n}{x^2} = \frac{1}{n}*ln{\frac{n}{x}} -\frac{1}{n} = 0 \implies \frac{n}{x} =e \implies x^*=\frac{n}{e}$

$f''(x) = \frac{1}{n} \frac{x}{n} (-\frac{n}{x^2}) = -\frac{1}{nx} \lt 0 \implies \max f(x) = f(x^*) = f(\frac{n}{e}) = \frac{1}{e} \approx 0.367879$

這一結(jié)論是反直覺的(大概這就是概率論的魅力所在)泣特，它表明浩姥，不管有多少份紅包，我們拿到最大的那個紅包的概率都是個常數(shù)状您，并且這個概率還不小(接近四成了)勒叠。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市膏孟，隨后出現(xiàn)的幾起案子眯分，更是在濱河造成了極大的恐慌，老刑警劉巖柒桑，帶你破解...
沈念sama閱讀 217,406評論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件弊决，死亡現(xiàn)場離奇詭異，居然都是意外死亡魁淳，警方通過查閱死者的電腦和手機飘诗，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,732評論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來界逛，“玉大人昆稿，你說我怎么就攤上這事∠荩” “怎么了溉潭？”我有些...
開封第一講書人閱讀 163,711評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵净响，是天一觀的道長。經(jīng)常有香客問我喳瓣，道長馋贤，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,380評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任畏陕，我火速辦了婚禮配乓，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘蹭秋。我一直安慰自己扰付，他們只是感情好堤撵，可當(dāng)我...
茶點故事閱讀 67,432評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布仁讨。她就那樣靜靜地躺著，像睡著了一般实昨。火紅的嫁衣襯著肌膚如雪洞豁。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,301評論 1贊 301
城市分裂傳說
那天荒给，我揣著相機與錄音，去河邊找鬼。笑死闯割，一個胖子當(dāng)著我的面吹牛拉讯，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播挑辆，決...
沈念sama閱讀 40,145評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼例朱，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了鱼蝉？” 一聲冷哼從身側(cè)響起洒嗤，我...
開封第一講書人閱讀 39,008評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎魁亦，沒想到半個月后渔隶，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,443評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡洁奈，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,649評論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年间唉，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片利术。...
茶點故事閱讀 39,795評論 1贊 347
活死人
序言：一個原本活蹦亂跳的男人離奇死亡终吼，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出氯哮，到底是詐尸還是另有隱情际跪，我是刑警寧澤商佛，帶...
沈念sama閱讀 35,501評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站姆打，受9級特大地震影響良姆，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜幔戏，卻給世界環(huán)境...
茶點故事閱讀 41,119評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一玛追、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧闲延，春花似錦痊剖、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,731評論 0贊 22
一樁弒父案陆馁，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至合愈，卻和暖如春叮贩，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背佛析。一陣腳步聲響...
開封第一講書人閱讀 32,865評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工益老，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人寸莫。一個月前我還...
沈念sama閱讀 47,899評論 2贊 370
代替公主和親
正文我出身青樓捺萌，卻偏偏與公主長得像，于是被迫代替她去往敵國和親膘茎。傳聞我的和親對象是個殘疾皇子桃纯，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,724評論 2贊 354