一个人爬楼梯，每爬一层前先抛个硬币，如果是正面则继续向上，如果是反面则停下结束，问平均能爬到的最高层数是多少（期望）？

这个问题是不是太简单了？那么考虑 N 个人各自爬楼梯，都依照上面的规则，只统计它们中爬得最高的楼层，问楼层数的期望是多少？

单人问题

单人的问题可以套用统计学中的 几何分布，得到期望为 $\frac{1}{1-p} - 1$，在抛硬币的情况下就是平均 $1$ 层。自己算的话如下式：

$$ \begin{align} E(x) &= 0p^0(1-p) + 1p^1(1-p) + 2p^2(1-p) + \dots \\ &= (1-p)(p + 2p^2 + 3p^3 \dots) \\ &= (1-p)\frac{p}{(1-p)^2} = \frac{p}{1-p} = \frac{1}{1-p} - 1 \end{align} $$

和几何分布的结果是一致的。不过要提醒的是几何分布关心的是成功概率和次数，而我们关心的是失败的。

多人问题

很直接地，我们想一开始有 $n$ 个人，它们中有 50% 的人会掷到正面，因此第 1 层会有 $\frac{n}{2}$ 个人，第 2 层有 $\frac{n}{4}$ 个人。进一步，第 $k$ 层有 $\frac{n}{2^k}$ 人。所以当最后一层只剩一个人的时候，即 $\frac{n}{2^k} = 1$ 时，即到了最高层，于是最高能到的层数为 $k = \log_2n$。

上面的分析好像没什么大问题，那么如果问 1024 个人最高能爬到多少层，你回答层数的期望是 10 层，对不对呢？不知道，也算不出来，但很可能是错的。事实上满足几何分布的独立同分布变量，它们的最大值的期望并没有一个良好的解析式可以表示（数学好的话可以看看这个答案）。

但是当 n 足够大的时候，我们能确定它“大概”就是 $\log_2n$ 层。下面是一些证明，不感兴趣的就跳过吧。

期望上界的证明

其实这个问题是计算数据结构跳表 (skiplist) 的高度的另一种说法。这里这里跟据 一个讲义 讲解一下如何推导得到期望的上界（建议看看原文）。

我们知道，一个人爬到至少第 $k$ 层的概率是 $p^k$，$n$ 个人中 至少有一个人 达到 $k$ 层及以上的概率不太于 $np^k$（即所有人都到达 $k$ 层及以上的概率）。设 $M$ 为任意一人达到的最高层数，则 $M \ge k$ 的概率 $Pr[M \ge k] \le np^k$。现在我们要求 $M$ 的期望 $E[M]$ 的上界，我们把期望的计算拆成两部分：

$$ E[M] \le \sum_{k=0}^{L-1}{kPr[M=k]} + \sum_{k=L}^{\infty}{kPr[M=k]} $$

拆成两部分的原因是我们知道随着 $k$ 的增长，后面的部分增长会越来越慢，这样我们选取适当的 $L$ 并对 $k$ 比较大的部分应用缩放，然后再单独处理 $k$ 小的部分，就可以得到一个小的上界。为此，我们要找到一个 $L$，满足：

$$ knp^k = O(1/k^2), \forall k \ge L $$

为什么要选 $1/k^2$ 呢？因为我们知道下面这个和（巴塞尔问题）：

$$ \sum_{i=0}^{\infty}{ \frac{1}{i^2} } = \frac{\pi^2}{2} \le 2 $$

那么就有：

$$ \sum_{k=L}^{\infty}{ knp^k } \le \sum_{k=L}^{\infty}{ O(\frac{1}{k^2}) } = O(1) $$

现在的问题是 $L$ 到底是多少呢？我们希望当 $n$ 足够大时，$L$ 满足：$Lnp^L \le L^2 $，换言之，我们希望得到 $L^3 n p^L = O(1/n)$。这东西不是人能解出来的，但我们只需要找到一个合适的值就行了。我们选的值是：

$$ L = 2\log_{1/p}{n} $$

下一小节我们会验证这个值的正确性，这里我们先考虑式子剩余的部分：

$$ \sum_{k=0}^{L-1}{kPr[M=k]} \le \sum_{k=0}^{L-1}{LPr[M=k]} = L \sum_{k=0}^{L-1}{Pr[M=k]} = L Pr[M < L] \le L $$

于是，我们的期望的上界为：

$$ E[M] \le \sum_{k=0}^{L-1}{kPr[M=k]} + \sum_{k=L}^{\infty}{kPr[M=k]} \le L + 0 = O (\log n) $$

证明 L 是合适的

即我们要证明当 $n$ 足够大时，$L = 2\log_{1/p}{n}$ 满足 $Lnp^L \le 1/L^2$，亦即 $L^{3} np^L \le 1$。

代入 $L = 2\log_{1/p}{n}$ 的值：

$$ f(n) = L^{3} np^L = \frac{8\log_{1/p}(n)^3}{n} $$

上面的式子在 $n \to \infty$ 时趋近于 0 （参考Orders Of Growth Corollary 2.2），得证。

With High Probability

With High Probability 是另一种说明可能性的方式。它表示如果某个依赖参数 $n$ 的事件，发生的概率是 $p_n$ 且 $\lim_{n \to \infty} p_n = 1$，则说这个事件是“大概率”发生的。

我们说多人爬楼梯的最高层数“大概率”是 $O(\log n)$ 的。考虑 $c \log_{1/p} n$ 层，上文提到，最高层数大于等于 $k$ 的概率为：

$$ Pr[M \ge k] \le np^k = n p^{c \log_{1/p} n} = n \frac{1}{n^c} = \frac{1}{n^{c-1} } $$

那么 $M < k$ 的概率为 $1 - \frac{1}{n^{c-1} }$，当 $n \to \infty$ 时，概率趋近于 $1$。那么“大概率”告诉我们什么信息呢？它告诉我们，当 $n$ 很大时，最高层数几乎不可能大于 $c \log_{1/p} n$ （因为概率太小了）。并且根据常数 $c$ 的不同，我们能预测它的概率。

“大概率”与上面证明的最大区别是“大概率”并不能保证没有反例出现，而严格的上界证明可以。不过对于一些概率算法来说，“大概率”就已经足够保证算法的性能了。

参考