首页 > 代码库 > 连续正面的最长序列问题

连续正面的最长序列问题

设想你抛一枚硬币n次,你期望看到的连续正面的最长序列是多长?

这是算法导论第四章里的一个问题,今天看了好久,才明白过来,在这里做个记录。

书上从两个不同的角度分析了这个问题,一个是从概率的角度,通过计算这个序列长度的上界和下界推导出序列长度,一个是利用书上所说的指示随机变量(indicator random variable)的角度(个人理解就是期望),去分析。前者太复杂了,看了一半就晕了,这里只分析一下第二种的方法。

定义Xik表示序列长度至少为k的序列开始于第i次抛硬币的概率。

那么,这个长度至少为k的序列出现次数的期望就是:E[X1k+X2k+...+X(n-k+1)k]

这里的n-k+1是总长为n的序列中,长度为k的序列的个数。

这里,Xik很好算,就是1/2^k。

所以,这个期望算出来就是(n-k+1)/(2^k)。

因此,我们就可以通过代入不同的k值,计算出长度为k的序列的期望数目。

当k=c lg n时,计算出来期望可以写成O(1/n^(c-1))。

当c较大时,期望就会很小,那么它就不大可能发生;当c很小,比如c<1/2时,期望就会很大,这说明它很可能发生。因此可以得到结论这个连续正面的最长序列的期望就是O(lg n)

连续正面的最长序列问题