Content

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

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

隨機變量與期望

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

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

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

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

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

分析幾何分布

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

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

$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)式，設隨機變量 $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$ ，當首次試驗成功時取值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)式本質上是在運用(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)$ 。

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

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

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

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

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

這又是一道初看很棘手，但使用條件期望就能輕松解決的問題。用 $N_i$ 表示任意一種結果連續(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$ 。這兩個結果是一致的，之所以差了個倍數(shù)2，是因為在后一題里，任意一種結果出現(xiàn)k次就行，而在前一題里，需要特定某個結果出現(xiàn)k次才行。

分析快速排序

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

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

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

經典概率論問題

匹配問題(Match Problem)

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

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

對于(b)問，為了求出 $p(X=k)$ ，我們需要先求出 $p(X=0)$ ，雖然這一項指的是所有人都沒有拿到自己的那一頂帽子，但是不能簡單地用鏈式法則來求解：

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

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

我們需要借助條件概率來求解，用 $Z$ 表示事件「產生匹配的數(shù)量為零」，用 $M$ 表示事件「第一個人拿到了他的那頂帽子」，用 $NM$ 表示事件「第一個人沒有拿到他的那頂帽子」，用變量 $P_n$ 表示「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頂帽子中，成為了「多余的帽子」(因為這頂帽子沒有被他的主人取走)，而他所拿走的那頂帽子的主人則成了「多余的人」(因為他沒有機會取走他自己的帽子了)?，F(xiàn)在我們來研究一下事件 $\{Z\ |\ NM \}$ 。這一事件分為兩個子事件：

剩余n-1個人里沒有產生匹配，并且多余的人拿走了那頂多余的帽子，將此稱為事件A
剩余n-1個人里沒有產生匹配，并且多余的人沒拿走那頂多余的帽子，將此稱為事件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*}$

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

$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$ 可以化簡這一結果：

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

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

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

用 $R_n$ 表示當房間里有n個人時需要經過多少輪才能使所有人拿到自己的帽子，有 $E(R)=E(R_n)$ ；用變量 $X$ 表示第一輪里有多少人拿到了自己的帽子(即匹配的數(shù)量)。顯然， $E(R_1)=1$ 成立，現(xiàn)在我們假設有 $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個學生，假設每個人在任意一天出生的概率相同，都為 $1 / 365$ ，那么這n個學生中，有兩個人在同一天過生日的概率是多少？

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

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

Birthday Problem

秘書問題(Secretary Problem)

這個問題有各種版本的場景描述(最初的場景是要從眾多的候選者中選出綜合能力最好的那個秘書)，而我個人傾向于這樣來描述：在你生日這天，你的n個好朋友排成一隊給你送紅包，但在這n份紅包中你只能接受一份。每次拿到紅包后，你可以拆開紅包來查看面額大小，如果滿意，你選擇接受這一紅包，游戲結束；如果不滿意，你拒絕這份紅包(事后不能反悔)，然后去拆下一份紅包。這個問題的目標是拿到面額最大的那個紅包，它的難點在于，每一份紅包的面額大小都是純粹隨機的，不管你已經見過多少份紅包，下一份紅包對于你而言仍舊是完全未知的(雖然見過的紅包越多，對于面額的相對大小的判斷越準確)。

直觀上來看，n越大，紅包數(shù)量越多，拿到最大的那一份紅包就越困難。用數(shù)學的語言來說就是， $W$ 表示事件「拿到最大的紅包」，有 $n \rightarrow \infty, P(W) \rightarrow 0$ 。但是，下面我們將看到，在采用適當?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的大小無關。

這樣的策略稱為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}}$

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

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

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

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

重拾「概率論」

重拾「概率論」

隨機變量與期望

分析幾何分布

分析快速排序

經典概率論問題

匹配問題(Match Problem)

生日問題(Birthday Problem)

秘書問題(Secretary Problem)

相關閱讀更多精彩內容

友情鏈接更多精彩內容

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

重拾「概率論」

隨機變量與期望

分析幾何分布

分析快速排序

經典概率論問題

匹配問題(Match Problem)

生日問題(Birthday Problem)

秘書問題(Secretary Problem)

相關閱讀更多精彩內容

友情鏈接更多精彩內容

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