穿過一片麥田，去撿一個最大的麥穗，且不能回頭、更換，在何處決定撿到大麥穗的可能性最大？

12-27

如題，是那個古老的問題

無先驗分布的情形下的標答:

最佳策略為拒掉前 $r-1$ 個, 其中分數最高的記為 $ext{Max}$ ,然後從第 $r$ 個開始如果遇到評分高於 $ext{Max}$ 的就選中.

如果 $i$ 號是最佳選擇且被選中,那麼其他 $i-1$ 個次佳的都在前 $r - 1$ 個被拒者中.

然後根據條件概率展開可得:

$egin{aligned} P_n(r)= sum_{i=1}^{n}Pleft(i 號被選擇iggl| i 是最佳選擇 ight) imes Pleft(i 是最佳選擇 ight)\ = left( sum_{i=1}^{r-1} 0 imes frac{1}{n} ight) + left( sum_{i=r}^{n} Pleft( 最好的前 i-1 名在前 r-1 號中iggl | i 是最佳選擇 ight) imes frac{1}{n} ight) \ =sum_{i=r}^{n} frac{r-1}{i-1} imes frac{1}{n} =frac{r-1}{n} sum_{i=r}^{n} frac{1}{i-1} =frac{r}{n}left(H_{n-1}-H_r ight)+frac{1}{n} end{aligned}$

我們的目標是使得這個概率最大化,也就是 $max P_n(r)$ ,先來估計近似解:

令 $n$ 趨近無窮大, 把 $x$ 表示為 $r/n$ 的極限, 令 $t$ 為 $i/n$ , 則 $mathrm{d}t$ 為 $1/n$ , 原式可以近似為如下積分:

$P(x)sim x int_{x}^{1}frac{1}{t},dt = -x ln x$

求導易得 $displaystyle x=frac{1}{e}$ 時取得最大值.

接著我們來嚴格求解這個方程:

取差分易知, $max P_n(r)$ 等價於求 $H_r > H_n-1$ 的第一個正整數解.

兩邊展開得: $displaystyle frac{1}{2r}+ln r > frac{1}{2n}+ln n-1$

這是個代數超越方程,兩邊取超越指數,解得其精確解為:

$frac{r(n)}{n}=frac{1}{n}leftlceil Releft(-frac{1}{2 W(a_n)} ight) ight ceil; a_n=-frac{e^ {1-frac{1}{2 n}}}{2 n}$

如果用近似解 $displaystyle frac{widehat{r}(n)}{n}=frac{1}{n}leftlceil frac{n}{e} ight ceil$ 的話每隔幾項是錯的,有誤差,且錯的那些項正好要求下取整 Floor,當然如果改成高斯取整 Round 的話,錯誤項會稀疏一點.

更有趣的是 $frac{1}{e}$ 的丟番圖逼近序列 $left{frac{1}{2},frac{1}{3},frac{3}{8},frac{4}{11},frac{7}{19},frac{32}{87},frac{39}{106},frac{71}{193}cdots ight}$ 里存在的項必定都是無誤差項...

複雜情景...沒空不講了...一堆坑要填...

習題: 使用DP演算法計算精確解 $r(n)$ .

最後,蘇格拉底時代有 $e$ 么,有微積分么,有超越指數么,有動態規劃演算法么...

hehe!

1/e是建立在人對「麥穗應該有多大」這個問題毫無認知的情況下的。丟棄前1/e，本質目的是以不高的成本，建立起一個模糊的先驗認知。

如果對於「麥穗應該有多大」有先驗認知，則解法完全不同。

比如，一個人見麥穗見得多了，他一開始就看到個特別大的，自然直接就選擇了，沒道理扔掉然後指望後面還有更大的之類。

這個題的答案取決於對麥穗幾率分布的先驗假設，所以可以說這個題的條件不足。

在給定先驗假設之後，一定存在一個讓期望值最大的策略。假設我們不知道任何關於麥穗大小的信息，這個策略就會非常簡單：很多答案提到的1/e就是此類情況。

如果先驗假設很複雜（比如裡面有很多未知參數），策略肯定是動態的。因為在不斷撿麥穗的過程中，策略中的未知參數也在一步一步被擬合出來，所以策略也在根據每一個麥穗的信息而變動。這時候自然不可能從一個簡單的策略中獲得最優解。

當然如果完全已經知道了麥穗大小的分布情況，我們只需要計算後續所有麥穗大小的最大值的期望值，與當前麥穗作比較應該就是最佳策略了。

——————————

更新：

我還看到一個爭議的來源：那就是對題目的理解有分歧。

理解1：拿到最大麥穗的幾率最大。

理解2：拿到的麥穗儘可能大。

其中理解1是個讓幾率最大化的問題，理解2是個讓期望值最大化的問題，其中第一種理解對於先驗分布的依賴會弱一些，畢竟它只關心麥穗大小的排序，而不是大小的絕對值。而第二種理解會很強的依賴於先驗分布。

從自然科學來蹭熱度吧~
首先光照、灌溉、肥力、植株密度、蟲害影響並不能完全一致，好苗、差苗、瘋苗有時候不種田的人都能看出來~

但不可避免的是最南邊的麥穗普遍比北邊的要粗壯些，因為植株不受其它植株的遮擋，光照量最大最充足！
不管你用什麼方式去推論、判斷，哪怕掏出概率學，一旦沒選擇最南邊從東往西這條線路，那麼成功的幾率低得令人髮指。

離職中，閑著也是閑著，再扯一下~
假設我們要從數個場所里選擇一個場所，拎一個身高最高的人，只能選擇一個場所，只能拎一次~
那麼我們就不能跑到幼兒園看到小明就興沖沖的把他從娃娃堆里拎出來，但你若是跑到籃球隊把大明拎出來就沒問題。
當然也不排除大明沒去打籃球，反而跑幼兒園玩親子互動這種概率事件！

傳統的解法是先拋棄e分之一，
但是真正的最優解是動態策略。（打臉收回這句話，下文前前後後討論了四種情況，假設正態分布求最大和求較大，只能比出排名求最大和較大。其中只知排名求最大確實答案是先拋棄1/e）
假設大小是正態分布，每一步根據之前的結果，實時進行參數估計，再計算接下來能拿到最大的期望，再做決定
很多人的答案都是來源於Wiki，Wiki上還掛有e分之一的論文。
想到了先拋棄再篩選，以為找到了妙招，然後證明這一招的最優解在e分之一處。沒想到還有統計學這一招吧

有同志提到非參估計，確實這個問題沒有說是正態分布。但是，就算非參估計，e分之一也不對。
比如我在倒數第二個上，發現它排所有100個的第40名，我有理由相信它比倒數第一個好。我們可以把正態分布的按大小估計來做動態策略，改成按排名的動態策略

輪子哥也用了e分之一，看來我又一次站在大多數的對立面。 @vczh 能不能來一決高下

鑒於收到這麼多贊，我要把答案上升到雞湯高度：人生就應該時時反思，每走一步都不忘回首過去，找到自己的定位，不忘初心的人大多沒有好結局

經回復區提醒，這個原題不是要選較大的，而是選最大的，我誤解了題意。
不過如果已知分布或自然正態分布的話，依然是動態策略，比如剛開始1/e，均值為10，最大值為20，後來的1/e都是19.9附近，但沒有大於20。突然遇到一個20.001的，那麼有理由相信，剛開始的1/e是運氣不好，均值太低，遇到大於20.001的概率很大，不能直接拿著20.001就跑了。
沒有錯，動態的策略就是這麼強勢

只知排名不知分布求最大麥穗的話，1/e是對的。

看來大家對於這種老問題新解很有興趣。以下內容被舉報誘導投票了。本來想說集贊出一個系列：我們都做過的題，還有新情況。既然被要求修改，那就改了。不重要，沒有答題經驗，試水失敗，算了不玩了
-------
評論區要求根據排名給較大麥穗（非最大）演算法，我沒有嚴謹論證過，暫且給出以下方法。
首先，迭代條件是，如果未來能拿到的期望，比現在這個麥穗大，就拋棄現在這個，否則就要現在這個。
其次，舉個例，有100個項，考察第99個，如果其排名在99個中占第50名以後，則拋棄，否則就拿走。
倒數第98個，最後兩個名次優秀的期望是33.3名，那麼第98個要是是40名，果斷拋棄。
依次類推。
這一個辦法不嚴謹的是，沒有考慮下一步的動態策略對這一步計算的影響，如果有同志有興趣，給一個完美版演算法吧。

題目漏了一個字，此題經典版本是要求撿到《最大》麥穗的可能性最大，而不是要求儘可能撿更大的麥穗。也就是說，如果撿不到最大的那一個，那麼就算撿了第二大的也是無意義。這樣才會有1/e這個解。

1/e解法的問題是，如果最大的麥穗在前面37%，結果就是只能拿到最後那一棵，而不是退而求其次。雖然滿足題設，但並不符合人之常情。

這種糾結症客人在我們東莞是最討厭的，所有人都不喜歡拿不定主意的人
我們經常給客人普及的方案就是：
王哥這樣，你先挑三個覺得不錯的留這，等下我再喊兩批進來，如果有比這三個還好的，那一定就是你要的了。

這不就是那個如何娶老婆的演算法嗎。假設一輩子能交到100個女朋友，先跟100/e炮人一遍然後放棄之，從那之後遇到比之前所有人都好的馬上結婚。

柏拉圖有一天問老師蘇格拉底：「什麼是愛情？」

蘇格拉底叫他到麥田走一次，要不回頭地走，在途中要摘一株最大最好的麥穗，但只可以摘一次。

柏拉圖覺得很容易，充滿信心地出去，誰知過了半天他仍沒有回去。

最後，他垂頭喪氣地出現在老師跟前訴說空手而回的原因：「很難得看見一株不錯的，卻不知道是不是最好的。因為只可以摘一株，只好放棄，再往前走看看有沒有更好的。已經走到盡頭時，才發覺手上一株麥穗也沒有——」

蘇格拉底微微一笑，告訴他「這就是愛情！」

羅永浩有一天問老師蘇格拉底：「什麼是愛情？」

蘇格拉底叫他到麥田走一次，要不回頭地走，在途中要摘一株最大最好的麥穗，但只可以摘一次。

羅永浩把麥田分為三等份。走第一個1/3的麥田時，他只看不摘，分出大、中、小三類麥穗。在第二個1/3的麥田裡，他驗證大小是否正確。終於在第三個1/3里，羅永浩選擇了麥穗中最大最美麗的一支。

羅永浩告訴蘇格拉底：「這是麥田中最大的一支麥穗。」

蘇格拉底質疑道：「你這個並不是整個麥田中最大的那一支。」

羅永浩辯解到：「那我就說，這是後1/3麥田中最大的一支麥穗，聽明白了嘛。」

蘇格拉底依舊質疑：「那你怎麼能說這個就是後1/3麥田中最大的一支呢？」

羅永浩趾高氣昂的說：「這是我們眼中後1/3麥田中最大的一支麥穗，聽明白了嘛。」

蘇格拉底怒火中燒破口大罵：「你懂個鎚子懂!」

羅永浩哈哈大笑：「老師您怎麼知道我在搞鎚子！」

首先明確幾個條件：

（1）只能撿一次麥穗，不能拋棄再撿

（2）只能單向挑選，不能倒回去撿之前看過的麥穗，但是可以記錄沿途看到的麥穗

這一題不知道優雅的解法，有一個常用的近似方法:
假設共有n個麥穗，先定義一個k，在撿麥穗時，只看不撿前k個麥穗，同時記錄其中最大的那顆的大小。然後在撿後續n-k個麥穗的過程中，只看不撿，直至第一次遇到大於之前記錄的那顆，就立刻停下來選擇這一顆。
理論上講，理想的k/n應該約等於1/e。
具體的數學證明等我填坑。

事情過去了幾天，發現前面的答主已經說的差不多了，特別有一位匿名答主的數學比我好得多，所以我就從易懂的角度寫吧。

大體來說，其實有兩個問題。

1.為何是1/e？

首先假設是均勻分布，那麼在1到n的任何一個位置出現最大麥穗的概率都是1/n。

採用之前給出的方法，假設選到了第s個位置的麥穗，這個s應該服從以下條件：

（1） $sgeq k+1$ ；

（2）在[k+1,s-1]之間，沒有麥穗比[1,k]之間最大的那顆大，所以才選了第s個；換言之，前s-1個麥穗中最大的那顆處於[1,k]之間，這個概率p滿足 $p=frac{k-1}{s-1}$ 。

現在可以用一個條件概率來描述：

$P(選到s，且s最好)=P(s最好)P(選到s|s最好)$

s可能是[k+1,n]中任意一個，將概率疊加，則有:

$P(k)=sum_{s=k+1}^{n}{frac{1}{n}frac{k-1}{s-1}}$

做數學變換：

$P(k)=sum_{s=k}^{n-1}{frac{1}{n}frac{k-1}{s}}=frac{k-1}{n}sum_{s=k}^{n-1}{frac{1}{s}}$

不影響結果，可近似為 $P(k)simfrac{k}{n}sum_{s=k}^{n}{frac{1}{s}}sim xint_{x}^{1}frac{1}{t}dt$

其中 $x=frac{k}{n}$ , $t=frac{s}{n}$ , $dt=frac{1}{n}$ 。

求積分，得到 $P(k)=-xlnx$ ，只需求該概率最大值即可。

求導，有 $frac{dP}{dx}=-(lnx+1)=0$ ，得到 $x=frac{k}{n}=frac{1}{e}$ 。

此時已經完成了基本的證明求解，但思考一下可知。採用這種方法的前提是所有麥穗的大小服從均勻分布，且挑選者對麥穗大小沒有先驗的概念，完全根據臨時決策來挑選。但若要更貼近現實，可以有一個先驗條件，比如假設日常生活中麥穗的大小平均是h，服從某個正態分布，這樣在n個麥穗中進行挑選時，等於有了一個參考條件，方法會變化。

2.這種捨棄一部分，再取剩餘麥穗的方法，道理何在？有沒有更好的方法？

問題1並不難，問題2才是關鍵，具體周末再說 (:3)rz

在線僱傭

我原本第一反應，就是走過一段觀察距離，然後摘下下一個超過之前所有的麥穗。

後來我一想，這是不是太呆板了。

於是我第二反應，隨便摘一顆，反手就是一打火機。

獨此一顆，何與之爭？這就很機智。

但我很快意識到，這種機智太歹毒，是不應該被鼓勵的。

這個找麥的過程，我想到一個詞——「麥上麥」。自然就會聯想到「人上人」。

找麥上麥不就是找人上人嗎？

這是我的第三反應。

走過一段觀察距離，做到對麥心中有數。要知道5%甚至3%級別的麥穗長多大。

接下來，就是找到一顆3%～5%級別的麥穗。天選之穗可能難尋，但麥中龍鳳絕不難找。

折斷這一株上其它小的麥穗。把尿撒在這株下面的土壤里。

然後等。等下一泡尿，再下一泡……當然還可以用抽出的麥桿，吹優美的和旋給它聽。
日月穿梭，耐心等待，它終將長成一株麥王。

所以，我們不難悟出一個公式

出色天賦+額外優質資源+耐心的等待=

別人家的孩子

先取1000個抽樣，然後再取被。。

哪裡禿就往哪裡走，密的地方搶營養。

謝邀，這個題挺經典的…記得我上過的ME和EE的課都討論過這個問題
假設說這個題目的意思是要挑一個最大（最好）的出來，問怎麼挑成功的概率最大

那麼數學上講，應該是先取一組樣本作為對照組
然後取從對照組往後的第一個高於對照組最高水平的麥穗
可以推導得到對照組的樣本數量在1/e*樣本總數個的時候你挑出最好的一個的概率最大

但是放到這個條件來看似乎不太現實，因為你並不知道一共有多少個麥穗對吧
所以最好的辦法是搞他個幾十台聯合收割機，全采完收完之後挨個過秤
不過似乎就和「不能回頭」這個題設衝突了
這就是工程師思維和數學家思維的區別吧（逃）

前半段路程看一下最大的麥穗會有多大，後半段路程開始看到一個和前半段最大的麥穗差不多大的麥穗就撿

看到很多知友在問 $e$

數學上自然常數e， $ln(chi) = log_{e}chi$ (e為底數)

e, Euler"s number，無限不循環小數,取值近似2.718

1.秘書問題(secretary problem)

此類問題也被稱作秘書問題，未婚妻選擇問題 ，1/e問題，最佳選擇問題。涉及到最優停止理論。

其中：

$frac{1}{e} approx 0.37$ , 即37%

2.問題描述：

希望聘請到一位最好的秘書，現在有 $n$ 位申請者，申請人以隨機順序逐一訪問。在面試後立即作出關於每位特定申請人的決定，且一旦被拒絕，申請人不能被召回。求最優招聘方案。

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 ${displaystyle 1/e}$ , and that the latter holds even in a much greater generality (2003). The optimal stopping rule prescribes always rejecting the first ${displaystyle sim n/e} {displaystyle sim n/e}$ 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 ${displaystyle 1/e}$ stopping rule, because the probability of stopping at the best applicant with this strategy is about ${displaystyle 1/e}$ already for moderate values of ${displaystyle n}$ . 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.