穿过一片麦田，去捡一个最大的麦穗，且不能回头、更换，在何处决定捡到大麦穗的可能性最大？

如题，是那个古老的问题

有关回应 · 2021-5-17 11:24:30

无先验分布的情形下的标答:
最佳策略为拒掉前
个, 其中分数最高的记为
,然后从第
个开始如果遇到评分高于
  的就选中.
如果
号是最佳选择且被选中,那么其他
个次佳的都在前
个被拒者中.
然后根据条件概率展开可得:

我们的目标是使得这个概率最大化,也就是
,先来估计近似解:
令
趋近无穷大, 把
表示为
的极限, 令
为
, 则
为
, 原式可以近似为如下积分:

求导易得
  时取得最大值.
接着我们来严格求解这个方程:
取差分易知,
等价于求
的第一个正整数解.
两边展开得:
这是个代数超越方程,两边取超越指数,解得其精确解为:

如果用近似解
的话每隔几项是错的,有误差,且错的那些项正好要求下取整 Floor,当然如果改成高斯取整 Round 的话,错误项会稀疏一点.
更有趣的是
的丢番图逼近序列
里存在的项必定都是无误差项...
复杂情景...没空不讲了...一堆坑要填...
习题: 使用DP算法计算精确解
.
最后,苏格拉底时代有
么,有微积分么,有超越指数么,有动态规划算法么...
[h1]hehe![/h1]

有关回应 · 2021-5-17 11:24:31

首先明确几个条件：
（1）只能捡一次麦穗，不能抛弃再捡
（2）只能单向挑选，不能倒回去捡之前看过的麦穗，但是可以记录沿途看到的麦穗
这一题不知道优雅的解法，有一个常用的近似方法:
假设共有n个麦穗，先定义一个k，在捡麦穗时，只看不捡前k个麦穗，同时记录其中最大的那颗的大小。然后在捡后续n-k个麦穗的过程中，只看不捡，直至第一次遇到大于之前记录的那颗，就立刻停下来选择这一颗。
理论上讲，理想的k/n应该约等于1/e。
具体的数学证明等我填坑。
事情过去了几天，发现前面的答主已经说的差不多了，特别有一位匿名答主的数学比我好得多，所以我就从易懂的角度写吧。
大体来说，其实有两个问题。
1.为何是1/e？
首先假设是均匀分布，那么在1到n的任何一个位置出现最大麦穗的概率都是1/n。
采用之前给出的方法，假设选到了第s个位置的麦穗，这个s应该服从以下条件：
（1）
；
（2）在[k+1,s-1]之间，没有麦穗比[1,k]之间最大的那颗大，所以才选了第s个；换言之，前s-1个麦穗中最大的那颗处于[1,k]之间，这个概率p满足
。
现在可以用一个条件概率来描述：

s可能是[k+1,n]中任意一个，将概率叠加，则有:

做数学变换：

不影响结果，可近似为
其中
,
,
。
求积分，得到
，只需求该概率最大值即可。
求导，有
，得到
。
此时已经完成了基本的证明求解，但思考一下可知。采用这种方法的前提是所有麦穗的大小服从均匀分布，且挑选者对麦穗大小没有先验的概念，完全根据临时决策来挑选。但若要更贴近现实，可以有一个先验条件，比如假设日常生活中麦穗的大小平均是h，服从某个正态分布，这样在n个麦穗中进行挑选时，等于有了一个参考条件，方法会变化。
2.这种舍弃一部分，再取剩余麦穗的方法，道理何在？有没有更好的方法？
问题1并不难，问题2才是关键，具体周末再说 (:3)rz

有关回应 · 2021-5-17 11:24:32

1/e是建立在人对“麦穗应该有多大”这个问题毫无认知的情况下的。丢弃前1/e，本质目的是以不高的成本，建立起一个模糊的先验认知。
如果对于“麦穗应该有多大”有先验认知，则解法完全不同。
比如，一个人见麦穗见得多了，他一开始就看到个特别大的，自然直接就选择了，没道理扔掉然后指望后面还有更大的之类。

有关回应 · 2021-5-17 11:24:33

这种纠结症客人在我们东莞是最讨厌的，所有人都不喜欢拿不定主意的人
我们经常给客人普及的方案就是：
王哥这样，你先挑三个觉得不错的留这，等下我再喊两批进来，如果有比这三个还好的，那一定就是你要的了。

有关回应 · 2021-5-17 11:24:34

看到很多知友在问
数学上自然常数e，
(e为底数)
e, Euler's number，无限不循环小数,取值近似2.718

1.秘书问题(secretary problem)
此类问题也被称作秘书问题，未婚妻选择问题 ，1/e问题，最佳选择问题。涉及到最优停止理论。
其中：

, 即37%

2.问题描述：
希望聘请到一位最好的秘书，现在有
位申请者，申请人以随机顺序逐一访问。在面试后立即作出关于每位特定申请人的决定，且一旦被拒绝，申请人不能被召回。求最优招聘方案。

3.解决方法：

The problem has an elegant solution, and the shortest rigorous proof known so far is provided by the odds algorithm (Bruss 2000). An easy analysis implies that the optimal win probability is always at least
, and that the latter holds even in a much greater generality (2003). The optimal stopping rule prescribes always rejecting the first
applicants that are interviewed (where e is the base of the natural logarithm) and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). Sometimes this strategy is called the
stopping rule, because the probability of stopping at the best applicant with this strategy is about
already for moderate values of
. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.

有一个优雅的解决方法，那就是赔率算法（Bruss 2000），如上。

4.数学推导：

对于某个固定的 k，如果最适合的人出现在了第 i 个位置（k

用 x 来表示 k/n 的值，并且假设 n 充分大，则上述公式可以写成：

对 -x · ln x 求导，并令这个导数为 0，可以解出 x 的最优值，它就是欧拉研究的神秘常数的倒数—— 1/e

（来自Albert_JIAO 死理性派恋爱法：拒绝掉前面37%的人 · 果壳）

5.说人话：
先用整体数目（遇到的麦穗总数）的37%作为实验的观测范围，用来预测整体的情况，以后一遇到比预测范围（前37%）任何一人都更好，就选择他。

虽然不能保证你绝对能找到最大的麦穗，但是你有36.8%的机会获得最大，而且在大量实验的验证下，这是最理想，最容易得到最大麦穗的方法。

6.参考文献
[1] F. Thomas Bruss (2000). "Sum the odds to one and stop". Annals of Probability. 28 (3): 1384–91.
[2] Ferguson, T. S. (1989). "Who solved the secretary problem?". Statistical Science. 4 (3): 282–296.
[3] wikipedia, Secretary problem [EB/OL]. Secretary problem
[4] Albert_JIAO. 死理性派恋爱法：拒绝掉前面37%的人[EB/OL]. http://www.guokr.com/article/6768, 2011-02-14
[5] tenos. 选择爱人的数学方法（经典秘书问题）[EB/OL]. 选择爱人的数学方法（经典秘书问题） - tenos - 博客园， 2014-05-23

穿过一片麦田，去捡一个最大的麦穗，且不能回头、更换，在何处决定捡到大麦穗的可能性最大？

5 个回复