Content

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

這個(gè)學(xué)期上了Prof. Sheldon Ross的<Elements of Stochastic Processes>，總算是把本科階段時(shí)曾經(jīng)粗淺地接觸過、但是現(xiàn)在早已忘掉絕大部分的概率論知識(shí)給重新?lián)炱饋砹?。自我感覺概率論的水平有不小的提高，于是決定趁熱打鐵整理一下筆記，寫下這篇小文章。

隨機(jī)變量與期望

隨機(jī)變量是一座橋梁，它的一端是這個(gè)世界上的各種或復(fù)雜或簡(jiǎn)單的隨機(jī)現(xiàn)象(不確定性是這個(gè)世界的本質(zhì)之一)，另一端是包括代數(shù)計(jì)算在內(nèi)的各種數(shù)學(xué)工具。對(duì)于隨機(jī)現(xiàn)象，我們可以定義一個(gè)隨機(jī)變量 $X$ ，針對(duì)每一種可能出現(xiàn)的結(jié)果，我們都可以給這個(gè)隨機(jī)變量賦予一個(gè)取值，這樣一來，我們就能夠運(yùn)用數(shù)學(xué)的力量來對(duì)這個(gè)世界的隨機(jī)性進(jìn)行分析。很多時(shí)候，我們關(guān)心的是平均值，我們有下面四種方法來計(jì)算隨機(jī)變量 $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)式是隨機(jī)變量期望值的定義式。由于使用這一公式需要知道該隨機(jī)變量的概率質(zhì)量函數(shù)——當(dāng)你已知其概率質(zhì)量函數(shù)時(shí)，你可以求出包括期望、方差等在內(nèi)的所有統(tǒng)計(jì)值——而在復(fù)雜的現(xiàn)實(shí)世界中我們很難得到一個(gè)變量的分布表達(dá)式（甚至很多時(shí)候連求出均值都顯得困難），因此該式使用相對(duì)較少。

(2)式表明，當(dāng)一個(gè)隨機(jī)變量可以表示成若干個(gè)隨機(jī)變量之和的形式時(shí)，它的期望即為這些變量的期望之和。當(dāng)一個(gè)隨機(jī)事件可以拆解成具有先后順序的子事件時(shí)，這一表達(dá)式很有效。

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

(4)式又叫條件恒等式(Conditioning Identity)，是同時(shí)應(yīng)用了(1)(3)兩式得到的，根據(jù)求隨機(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)$ 是隨機(jī)變量 $Y$ 的函數(shù)值(仍舊是一個(gè)隨機(jī)變量)，它表示，當(dāng)變量 $Y$ 取不同的值(這是隨機(jī)事件)時(shí)，變量 $X$ 的期望值(這是一個(gè)數(shù)值)也隨之變化，這正是隨機(jī)變量的定義(由某一隨機(jī)現(xiàn)象得到某一對(duì)應(yīng)的數(shù)值)，因此， $E(X\ |\ Y)$ 是一個(gè)隨機(jī)變量。

下面我們通過一些例子來展示這四個(gè)式子的運(yùn)用。

分析幾何分布

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

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

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

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

$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)式，定義隨機(jī)變量 $Y$ ，當(dāng)首次試驗(yàn)成功時(shí)取值1，失敗時(shí)則取值0。條件于 $Y$ 來計(jì)算 $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}$

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

現(xiàn)在我們同時(shí)運(yùn)用(2)(3)來計(jì)算方差。

$\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$ 時(shí)，變量 $A$ 是不服從幾何分布的，但是在引入「第一次實(shí)驗(yàn)失敗了」這個(gè)條件后，在得知這個(gè)原本未知的信息之后，隨機(jī)變量 $\{ A\ |\ Y=0 \}$ 成為了一個(gè)服從幾何分布的隨機(jī)變量，其參數(shù)和 $X$ 完全相同，所以有 $E(A\ | Y=0) = E(X)$ 和 $E(A^2\ |Y=0) = E(X^2)$ 。

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

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

以 $k=10$ 為例，獨(dú)立隨機(jī)試驗(yàn)的設(shè)定在于，哪怕你已經(jīng)連續(xù)9次成功，你也不能確定下一次就會(huì)成功。不管在連續(xù)9次成功之后失敗了，還是在連續(xù)3次成功之后失敗了，得到的結(jié)果都是一樣的，同樣是回到了游戲的起點(diǎn)，同樣是需要從頭再來。所以我們有：

$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*}$

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

這又是一道初看很棘手，但使用條件期望就能輕松解決的問題。用 $N_i$ 表示任意一種結(jié)果連續(xù)出現(xiàn) $i$ 次所需要的的試驗(yàn)次數(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}$

對(duì)(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$ 。這兩個(gè)結(jié)果是一致的，之所以差了個(gè)倍數(shù)2，是因?yàn)樵诤笠活}里，任意一種結(jié)果出現(xiàn)k次就行，而在前一題里，需要特定某個(gè)結(jié)果出現(xiàn)k次才行。

分析快速排序

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

為了分析這一算法，我們先定義一些必要的變量。用 $X$ 表示完成對(duì)一個(gè)數(shù)列的排序所需要進(jìn)行的大小比較的次數(shù)；用 $M_n$ 表示對(duì)一個(gè)長(zhǎng)度為n的數(shù)列進(jìn)行排序平均需要進(jìn)行多少次大小比較；用 $R$ 表示第一個(gè)隨機(jī)選取的數(shù)字在全體n個(gè)數(shù)字中的排名，如果 $R=i$ ，那么有 $i-1$ 個(gè)數(shù)字比這個(gè)數(shù)小，落入它的左側(cè)，有 $n-i$ 個(gè)數(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)} \\$

兩邊同時(shí)乘以 $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個(gè)人在一個(gè)房間里聚會(huì)，每個(gè)人頭戴一頂帽子，現(xiàn)在大家都把帽子放到房間中心的一個(gè)箱子里，每個(gè)人依次上前去隨機(jī)抽取帽子，如果他剛好抽到了他自己的那頂帽子，我們說此時(shí)產(chǎn)生了一個(gè)匹配(match)。用隨機(jī)變量 $X$ 表示產(chǎn)生了多少個(gè)匹配。試求(a) $X$ 的期望值；(b) $X$ 的概率質(zhì)量函數(shù)。

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

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

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

$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é)果意味著，不管房間里有多少個(gè)人，平均而言只有一個(gè)人可以拿到屬于他的那頂帽子。

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

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

上式是錯(cuò)誤的計(jì)算方法，對(duì)于「第一個(gè)人沒有拿到他的帽子」這個(gè)事件，需要分類成「第一個(gè)人拿到了第二個(gè)人的帽子」和「第一個(gè)人拿到了既不屬于他也不屬于第二個(gè)人的帽子」這兩個(gè)子事件，然后你才能去研究第二個(gè)人的匹配情況。

我們需要借助條件概率來求解，用 $Z$ 表示事件「產(chǎn)生匹配的數(shù)量為零」，用 $M$ 表示事件「第一個(gè)人拿到了他的那頂帽子」，用 $NM$ 表示事件「第一個(gè)人沒有拿到他的那頂帽子」，用變量 $P_n$ 表示「n個(gè)人中沒有產(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)$

若第一個(gè)人沒有選走他帽子，則他的帽子留在了剩余的n-1頂帽子中，成為了「多余的帽子」(因?yàn)檫@頂帽子沒有被他的主人取走)，而他所拿走的那頂帽子的主人則成了「多余的人」(因?yàn)樗麤]有機(jī)會(huì)取走他自己的帽子了)。現(xiàn)在我們來研究一下事件 $\{Z\ |\ NM \}$ 。這一事件分為兩個(gè)子事件：

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

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

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

$\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)$ 了，將所有人分成兩隊(duì)(一共有 $C_n^k$ 種分法)，一隊(duì)有k個(gè)人，他們中的每個(gè)人都拿到了自己的帽子；另一隊(duì)有n-k個(gè)人，每個(gè)人都沒有拿到自己的帽子。

$\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)式來驗(yàn)證(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ǎn)這一結(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ī)定，在第一輪里拿到了自己帽子的人離開房間，剩下的人把拿錯(cuò)的帽子放回箱子里，繼續(xù)隨機(jī)抽取，重復(fù)進(jìn)行下去直到所有的人都拿回自己的帽子為止。用變量 $R$ 表示需要經(jīng)過多少輪才能讓所有人都拿回帽子。試求 $R$ 的期望。

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

用 $R_n$ 表示當(dāng)房間里有n個(gè)人時(shí)需要經(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)

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

用 $A$ 表示事件「至少有兩個(gè)人在同一天出生」，用 $A^{'}$ 表示事件「沒有人的生日相同」，由于這兩個(gè)事件互補(bǔ)，所以有 $P(A) + P(A^{'}) = 1$ 。我們從 $P(A^{'})$ 著手，因?yàn)樗?img class="math-inline" src="https://math.jianshu.com/math?formula=P(A)" alt="P(A)" mathimg="1">的計(jì)算要簡(jiǎn)單得多。事件 $A^{'}$ 意味著，第一人在某一天出生了，第二個(gè)人的生日與他不同；第三個(gè)人的生日既和第一個(gè)人不同，也和第二個(gè)人不同；第四個(gè)人的生日和前面三個(gè)人的生日都不相同，以此類推，第n個(gè)人的生日和前n-1個(gè)人的生日都不相同。所以有：

$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時(shí)， $P(A)=0.507297$ ；當(dāng)n=57時(shí)， $P(A) = 0.99012$ 。這意味著，只需要有23個(gè)人，就有超過一半的幾率出現(xiàn)兩個(gè)人同一天過生日(對(duì)于概率論不熟悉的人可能會(huì)猜測(cè)至少需要157人)；只需要57個(gè)人，就能使這一概率值高達(dá)99%。以人數(shù)為橫軸，概率值為縱軸，繪圖如下：

Birthday Problem

秘書問題(Secretary Problem)

這個(gè)問題有各種版本的場(chǎng)景描述(最初的場(chǎng)景是要從眾多的候選者中選出綜合能力最好的那個(gè)秘書)，而我個(gè)人傾向于這樣來描述：在你生日這天，你的n個(gè)好朋友排成一隊(duì)給你送紅包，但在這n份紅包中你只能接受一份。每次拿到紅包后，你可以拆開紅包來查看面額大小，如果滿意，你選擇接受這一紅包，游戲結(jié)束；如果不滿意，你拒絕這份紅包(事后不能反悔)，然后去拆下一份紅包。這個(gè)問題的目標(biāo)是拿到面額最大的那個(gè)紅包，它的難點(diǎn)在于，每一份紅包的面額大小都是純粹隨機(jī)的，不管你已經(jīng)見過多少份紅包，下一份紅包對(duì)于你而言仍舊是完全未知的(雖然見過的紅包越多，對(duì)于面額的相對(duì)大小的判斷越準(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">是一個(gè)恒定不變的常數(shù)，與n的大小無關(guān)。

這樣的策略稱為k-policy，它的做法是，不管最開始的k個(gè)紅包面額如何，都不要接受，在這之后，如果遇到一個(gè)比前k個(gè)面額都大的紅包，就接受它，如果一直沒有遇到比前k個(gè)面額大的紅包，那么就接受最后一個(gè)紅包(即第n個(gè))。下面我們來求這種策略下的 $P(W)$ . 用隨機(jī)變量 $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$ 時(shí)的這個(gè)表達(dá)式，如果前 $i-1$ 個(gè)紅包中最大的那個(gè)在前k個(gè)位置里，就能確保在此之后、在最大的紅包之前，不會(huì)有紅包被選走。
$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}}$ ，對(duì)其進(jìn)行求導(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é)論是反直覺的(大概這就是概率論的魅力所在)，它表明，不管有多少份紅包，我們拿到最大的那個(gè)紅包的概率都是個(gè)常數(shù)，并且這個(gè)概率還不小(接近四成了)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

重拾「概率論」

重拾「概率論」

隨機(jī)變量與期望

分析幾何分布

分析快速排序

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

匹配問題(Match Problem)

生日問題(Birthday Problem)

秘書問題(Secretary Problem)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

重拾「概率論」

隨機(jī)變量與期望

分析幾何分布

分析快速排序

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

匹配問題(Match Problem)

生日問題(Birthday Problem)

秘書問題(Secretary Problem)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av