首页 > 代码库 > 连续正面的最长序列问题
连续正面的最长序列问题
设想你抛一枚硬币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)
连续正面的最长序列问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。