重拾「概率论」

2019-12-30 本文已影响0人廖致君

Content

随机变量与期望
- 分析几何分布
- 分析快速排序
经典概率论问题
- 匹配问题(Match Problem)
- 生日问题(Birthday Problem)
- 秘书问题(Secretary Problem)

这个学期上了Prof. Sheldon Ross的<Elements of Stochastic Processes>，总算是把本科阶段时曾经粗浅地接触过、但是现在早已忘掉绝大部分的概率论知识给重新捡起来了。自我感觉概率论的水平有不小的提高，于是决定趁热打铁整理一下笔记，写下这篇小文章。

随机变量与期望

随机变量是一座桥梁，它的一端是这个世界上的各种或复杂或简单的随机现象(不确定性是这个世界的本质之一)，另一端是包括代数计算在内的各种数学工具。对于随机现象，我们可以定义一个随机变量 $X$ ，针对每一种可能出现的结果，我们都可以给这个随机变量赋予一个取值，这样一来，我们就能够运用数学的力量来对这个世界的随机性进行分析。很多时候，我们关心的是平均值，我们有下面四种方法来计算随机变量 $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)式是随机变量期望值的定义式。由于使用这一公式需要知道该随机变量的概率质量函数——当你已知其概率质量函数时，你可以求出包括期望、方差等在内的所有统计值——而在复杂的现实世界中我们很难得到一个变量的分布表达式（甚至很多时候连求出均值都显得困难），因此该式使用相对较少。

(2)式表明，当一个随机变量可以表示成若干个随机变量之和的形式时，它的期望即为这些变量的期望之和。当一个随机事件可以拆解成具有先后顺序的子事件时，这一表达式很有效。

(3)式是计算期望值最常用的式子，实际上，「条件于(conditioning on )」是概率论体系中最为核心的技术之一。在分析现实世界的随机现象时，如果你能够获取额外的信息，这便意味着一些本是未知且随机的元素不再随机，而是成为了确定性因素，这将影响你原本的分析计算结果。

(4)式又叫条件恒等式(Conditioning Identity)，是同时应用了(1)(3)两式得到的，根据求随机变量函数值的期望值的公式，我们有

$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$ 的函数值(仍旧是一个随机变量)，它表示，当变量 $Y$ 取不同的值(这是随机事件)时，变量 $X$ 的期望值(这是一个数值)也随之变化，这正是随机变量的定义(由某一随机现象得到某一对应的数值)，因此， $E(X\ |\ Y)$ 是一个随机变量。

下面我们通过一些例子来展示这四个式子的运用。

分析几何分布

一系列相互独立的试验，每次试验成功的概率都是 $p$ ，用随机变量 $X$ 表示出现第一次成功试验时所需要的试验次数，其概率质量函数为 $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}{\frac{d}{dp} (1-p)^{k}} = p \frac{d}{dp}[\sum_{k=1}^{\infty}{(1-p) ^k}]\ \\ = p \frac{d}{dp}[\frac{1-p}{p}] = p*\frac{1}{p^2} = \frac{1}{p}$

使用(2)式，设随机变量 $A$ 为第一次实验过后仍需要几次实验才能出现第一次成功，即 $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)式。

现在我们同时运用(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 \}$ 成为了一个服从几何分布的随机变量，其参数和 $X$ 完全相同，所以有 $E(A\ | Y=0) = E(X)$ 和 $E(A^2\ |Y=0) = E(X^2)$ 。

下面我们考虑一个以几何分布为基础的问题。现在变量 $X$ 不再表示出现第一次成功试验时所需要的试验次数，而表示连续出现k次成功试验时所需要的试验次数。试求变量 $X$ 的期望。

要想最大化条件期望这一工具的威力，我们要找到合适的变量来作为条件。现定义变量 $Y$ 为出现第一次失败时所需要的试验次数，这个变量将帮助我们轻松求出 $X$ 的期望值。

以 $k=10$ 为例，独立随机试验的设定在于，哪怕你已经连续9次成功，你也不能确定下一次就会成功。不管在连续9次成功之后失败了，还是在连续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*}$

接着我们进一步拓展。几何分布的试验只有两种结果，即成功与失败。现在我们对其推广，假设每次独立随机试验都会有m种可能结果，每种结果出现的概率都是 $\frac{1}{m}$ ，用随机变量 $N$ 表示任意一种结果连续出现k次所需要的试验次数。试求 $N$ 的期望值。

这又是一道初看很棘手，但使用条件期望就能轻松解决的问题。用 $N_i$ 表示任意一种结果连续出现 $i$ 次所需要的的试验次数，那么有 $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$ 。这两个结果是一致的，之所以差了个倍数2，是因为在后一题里，任意一种结果出现k次就行，而在前一题里，需要特定某个结果出现k次才行。

分析快速排序

快速排序是一种常用的排序算法，随机从数列中选出一个数字，数列中剩余的所有数字和它进行比较，比它小的落入到左侧的子数列中，比它大的落入到右侧的子数列中，然后对这两个子数列分别进行同样的操作，重复下去，直到每个子数列只有1个或2个数字为止。最后我们将得到一个从左到右依照从小到大排列好的数列。这是典型的分治法应用，将一个复杂的大问题不断地拆解成容易解决的小问题。

为了分析这一算法，我们先定义一些必要的变量。用 $X$ 表示完成对一个数列的排序所需要进行的大小比较的次数；用 $M_n$ 表示对一个长度为n的数列进行排序平均需要进行多少次大小比较；用 $R$ 表示第一个随机选取的数字在全体n个数字中的排名，如果 $R=i$ ，那么有 $i-1$ 个数字比这个数小，落入它的左侧，有 $n-i$ 个数字比它大，落入它的右侧。根据条件期望我们得到：

$\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个人在一个房间里聚会，每个人头戴一顶帽子，现在大家都把帽子放到房间中心的一个箱子里，每个人依次上前去随机抽取帽子，如果他刚好抽到了他自己的那顶帽子，我们说此时产生了一个匹配(match)。用随机变量 $X$ 表示产生了多少个匹配。试求(a) $X$ 的期望值；(b) $X$ 的概率质量函数。

对于 (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$ 表示事件「产生匹配的数量为零」，用 $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顶帽子中，成为了「多余的帽子」(因为这顶帽子没有被他的主人取走)，而他所拿走的那顶帽子的主人则成了「多余的人」(因为他没有机会取走他自己的帽子了)。现在我们来研究一下事件 $\{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*}$

现在我们可以求出 $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*}$

有了概率质量函数之后，我们可以用期望的定义式即(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)问的答案一致。下面我们拓展原问题，现在规定，在第一轮里拿到了自己帽子的人离开房间，剩下的人把拿错的帽子放回箱子里，继续随机抽取，重复进行下去直到所有的人都拿回自己的帽子为止。用变量 $R$ 表示需要经过多少轮才能让所有人都拿回帽子。试求 $R$ 的期望。

从(a)题的结果我们知道，不管房间里有多少人，平均而言，一轮中只有一个人能够拿回自己的帽子，于是我们直观猜测 $E(R)=n$ 。现在我们用数学归纳法来证明这个结论。

用 $R_n$ 表示当房间里有n个人时需要经过多少轮才能使所有人拿到自己的帽子，有 $E(R)=E(R_n)$ ；用变量 $X$ 表示第一轮里有多少人拿到了自己的帽子(即匹配的数量)。显然， $E(R_1)=1$ 成立，现在我们假设有 $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个人，就有超过一半的几率出现两个人同一天过生日(对于概率论不熟悉的人可能会猜测至少需要157人)；只需要57个人，就能使这一概率值高达99%。以人数为横轴，概率值为纵轴，绘图如下：

Birthday Problem

秘书问题(Secretary Problem)

这个问题有各种版本的场景描述(最初的场景是要从众多的候选者中选出综合能力最好的那个秘书)，而我个人倾向于这样来描述：在你生日这天，你的n个好朋友排成一队给你送红包，但在这n份红包中你只能接受一份。每次拿到红包后，你可以拆开红包来查看面额大小，如果满意，你选择接受这一红包，游戏结束；如果不满意，你拒绝这份红包(事后不能反悔)，然后去拆下一份红包。这个问题的目标是拿到面额最大的那个红包，它的难点在于，每一份红包的面额大小都是纯粹随机的，不管你已经见过多少份红包，下一份红包对于你而言仍旧是完全未知的(虽然见过的红包越多，对于面额的相对大小的判断越准确)。

直观上来看，n越大，红包数量越多，拿到最大的那一份红包就越困难。用数学的语言来说就是， $W$ 表示事件「拿到最大的红包」，有 $n \rightarrow \infty, P(W) \rightarrow 0$ 。但是，下面我们将看到，在采用适当的策略之后， $P(W) = 1/e$ 是一个恒定不变的常数，与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的函数 $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$

这一结论是反直觉的(大概这就是概率论的魅力所在)，它表明，不管有多少份红包，我们拿到最大的那个红包的概率都是个常数，并且这个概率还不小(接近四成了)。