6

最高楼层问题

 3 years ago
source link: https://lotabout.me/2018/max-level-of-skiplist/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

最高楼层问题

Table of Contents

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

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

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

E(x)=0p0(1−p)+1p1(1−p)+2p2(1−p)+…=(1−p)(p+2p2+3p3…)=(1−p)p(1−p)2=p1−p=11−p−1

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

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

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

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

期望上界的证明

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

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

E[M]≤L−1∑k=0kPr[M=k]+∞∑k=LkPr[M=k]

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

knpk=O(1/k2),∀k≥L

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

∞∑i=01i2=π22≤2

那么就有：

∞∑k=Lknpk≤∞∑k=LO(1k2)=O(1)

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

L=2log1/pn

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

L−1∑k=0kPr[M=k]≤L−1∑k=0LPr[M=k]=LL−1∑k=0Pr[M=k]=LPr[M<L]≤L

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

E[M]≤L−1∑k=0kPr[M=k]+∞∑k=LkPr[M=k]≤L+0=O(logn)

证明 L 是合适的

即我们要证明当 n 足够大时，L=2log1/pn 满足 LnpL≤1/L2，亦即 L3npL≤1。

代入 L=2log1/pn 的值：

f(n)=L3npL=8log1/p(n)3n

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

With High Probability

With High Probability 是另一种说明可能性的方式。它表示如果某个依赖参数 n 的事件，发生的概率是 pn 且 limn→∞pn=1，则说这个事件是“大概率”发生的。

我们说多人爬楼梯的最高层数“大概率”是 O(logn) 的。考虑 clog1/pn 层，上文提到，最高层数大于等于 k 的概率为：

Pr[M≥k]≤npk=npclog1/pn=n1nc=1nc−1

那么 M<k 的概率为 1−1nc−1，当 n→∞ 时，概率趋近于 1。那么“大概率”告诉我们什么信息呢？它告诉我们，当 n 很大时，最高层数几乎不可能大于 clog1/pn （因为概率太小了）。并且根据常数 c 的不同，我们能预测它的概率。

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK