最大麦穗问题

由来

在微信上偶然看到一片文章《她用算法买到了房子!居然还有这种操作?!》
引出了柏拉图麦穗问题,于是就研究了一下相关的算法。

问题

苏格拉底带弟子们来到一片麦田,让他们在麦田行进过程中,每人选摘一支最大的麦穗,不能走回头路,且只能摘一枝。 第一个弟子刚走几步便摘了自认为是最大的麦穗,结果发现后面还有更大的;第二个弟子一直是左顾右盼,东挑西捡,一直到了终点才发现,前面几个最大的麦穗已经错过了;第三个弟子吸取前两位教训,当他走了三分之一时,即分出大、中、小三类麦穗,在随后的三分之一的田地里选定一个相对最大的,然后从容走完剩下的三分之一。
那么问题来了:
请给出一个最大可能得到最大麦穗的算法,并给出证明。当麦穗数目趋向于无穷时,获得最大麦穗的概率是多少?

结论

假设麦地的麦穗有n个,n充分大,那么问题的答案是,在前k个中记住一个最大的麦穗,然后在后面的麦穗中摘掉你遇到的比它大的第一个,其中k=n/e,取整即可(n充分大其实不需要考虑这个),概率是1/e。

分析

知乎链接
详细分析

欢迎打赏!