一道没太想通的数学题，题目谁都看得懂。

minker

8da一向人才辈出，今天due的一个VLSI的加分题靠着一些baidu勉强做出来但是总觉得不太完整，看看有木有人能写出来个我能看懂的比我靠谱的答案。。

题目如下：
连续投掷N次硬币，设N次中，连续出现正面向上的最长序列为k，则k存在期望E(k)。E(k)必然为N的单值函数，求E(k)-N的曲线的渐近线。换句话说，就是求当N趋于无穷大的时候E(k)的状态，也就是平均会有几个连续的硬币正面朝上。

自己做的虽然某种程度上看起来有点道理但是数学上肯定漏洞百出就不拿出来现眼了。

有没有大神来做一做。

翻译成最简单的中国话就是：

连续扔N次硬币平均会出现的连续最长正面向上的硬币个数是多少

SCI)_Dp_R

christiano 发表于 2012-9-15 04:40
E（k）近似于log2比较直观
第三步的细节，王教授能不能多讲一点？

找篇paper看吧，我也没看细节。50多年以前的结果了。

minker

SCI)_Dp_R 发表于 2012-9-15 01:56
k是最长的正面序列，则

k/log_2(n) -> 1 in probability.

大体思路是这样的吧。。我昨儿主要是为了细节头疼。。上面有一个哥们发了个连接偶看了就基本了解O(log2n)之前的具体步骤了，但是再往后就看不动了。。

christiano

SCI)_Dp_R 发表于 2012-9-15 01:56
k是最长的正面序列，则

k/log_2(n) -> 1 in probability.

E（k）近似于log2比较直观
第三步的细节，王教授能不能多讲一点？

boringegg

真心看不懂

SCI)_Dp_R

k是最长的正面序列，则

k/log_2(n) -> 1 in probability.

E(k)/log_2(n) -> 1.

E(k)=log_2(n)-2/3+eps    eps很小，但不收敛到0.

noblexer

清华男请不要调戏我们

minker

国妓米兰 发表于 2012-9-14 20:36
不就是一个期望求和函数吗？

难道我理解错了？

肿么求和法。概率没法算把。。

国妓米兰

不就是一个期望求和函数吗？

难道我理解错了？

Z_shaPT

看标题觉得很有信心

看id发现情况不妙

看完题目确定自己被骗了。。

SimoN

潜规则

会不会是e？

=F.Y=LSY

楼主还是和黑猪 木天使 或者伊万大师讨论吧

justforgc

看标题觉得很有信心

看id发现情况不妙

看完题目确定自己被骗了。。

slm1234

只能干捉鸡

怕娃落地

进来后有种被骗的感觉。

atlover

.   ...  ........

minker

nejcnejc 发表于 2012-9-14 12:44
我在算法导论里翻出来这个，不知道合不合LZ的胃口，看看吧
http://books.google.com/books?id=NLngYyWFl_Y ...

这个靠谱了，多谢。。看看能不能看懂。。

nejcnejc

我在算法导论里翻出来这个，不知道合不合LZ的胃口，看看吧
http://books.google.com/books?id ... %20flip&f=false

minker

frankoz 发表于 2012-9-14 11:26
matlab画一下啊

我有数值解，但是matlab没法算N趋近于无穷时候的情况~

fell

以后再有这样的事，请和黑猪私聊

hkkhhk

连续投掷N次硬币，设N次中

Springsun

进来后有种被骗的感觉。

minker

nejcnejc 发表于 2012-9-14 11:19
http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf

竟然是我们学校的东西。真是太神奇了！

不过题目略有区别吧，你的文章是说，得到n个连续正面向上平均要多少下，我的意思是扔了n下，平均最多有多少个正面向上~或许二者之间有关系但是肯定不是显式的。

thanks anyway。。

天谬

你直接PM DPR 不要调戏我们这些小学屌丝了。