秘書問題- 維基百科，自由的百科全書

在概率及博弈論上，秘書問題（Secretary problem），類似的名稱有相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題等，屬於最佳停止問題（ ... 秘書問題 維基百科，自由的百科全書 跳至導覽 跳至搜尋 在概率及博弈論上，秘書問題（Secretaryproblem），類似的名稱有相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題等，屬於最佳停止問題（英語：Optimalstopping）。

內容是這樣的：要聘請一名秘書，有n個應聘者。

每次面試一人，面試後就要及時決定是否聘他，如果當時決定不聘他，他便不會回來。

面試後總能清楚了解應聘者的合適程度，並能和之前的每個人做比較。

問什麼樣的策略，才使最佳人選被選中的概率最大。

求解最優策略[編輯] 這個問題的最優解是一個停止規則。

在這個規則里，面試官會拒絕頭r-1個應聘者（令他們中的最佳人選為應聘者M），然後選出第一個比M好的應聘者。

可見最優策略包含於這個系列的策略中。

（如果M在所有n個應聘者中也是最好的一個，那麼這個策略將選不出任何人選）對於任意的截斷值r，最佳人選被選中的概率是： P ( r ) = ∑ i = 1 n P ( applicant  i  isselected | applicant  i  isthebest ) × P ( applicant  i  isthebest ) = ( ∑ i = 1 r − 1 0 × 1 n ) + ( ∑ i = r n P ( thebestofthefirst  i − 1  applicants isinthefirst  r − 1  applicants | applicant  i  isthebest ) × 1 n ) = ∑ i = r n r − 1 i − 1 × 1 n = r − 1 n ∑ i = r n 1 i − 1 . {\displaystyle{\begin{aligned}P(r)&=\sum_{i=1}^{n}P\left({\text{applicant}}i{\text{isselected}}|{\text{applicant}}i{\text{isthebest}}\right)\timesP\left({\text{applicant}}i{\text{isthebest}}\right)\\&=\left(\sum_{i=1}^{r-1}0\times{\frac{1}{n}}\right)+\left(\sum_{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{thebestofthefirst}}i-1{\text{applicants}}\\{\text{isinthefirst}}r-1{\text{applicants}}\end{array}}\right|{\text{applicant}}i{\text{isthebest}}\right)\times{\frac{1}{n}}\right)\\&=\sum_{i=r}^{n}{\frac{r-1}{i-1}}\times{\frac{1}{n}}\quad=\quad{\frac{r-1}{n}}\sum_{i=r}^{n}{\frac{1}{i-1}}.\end{aligned}}} 求和符號內概率的計算是基於：如果應聘者i是（所有應聘者中的）最佳人選，他被選中若且唯若頭i-1個應聘者中的最佳人選處在頭r-1個被拒絕的應聘者中。

令n趨近無窮大，把x表示為r/n的極限，令t為i/n，dt為1/n，總和可以近似為如下積分： P ( x ) = x ∫ x 1 1 t d t = − x ln ⁡ ( x ) . {\displaystyleP(x)=x\int_{x}^{1}{\frac{1}{t}}\,dt=-x\ln(x).} 令P(x)對x的導數為0，解出x，我們得到最優的x等於1/e。

從而，當n增大時，最優截斷值趨近於n/e最佳人選被選中的概率為1/e。

對於較小的n值，最優的r也可以通過動態規劃方法得到。

下表給出了一些最優的r值： n 1 2 3 4 5 6 7 8 9 r 1 1 2 2 3 3 3 4 4 P 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.406 此問題的變種[編輯] 選擇者可選多於一人 求職者的數目未知 求職者之間的關係可影響選擇 被拒絕的求職者有一定機率能被叫回來 選擇者滿足於次好的人 參考[編輯] 譯自本頁英文版 T.S.Ferguson."Whosolvedthesecretaryproblem?"Statisticalscience,volume4,pp.282-296.1988. 數學傳播第二卷第三期 :海外學人相親記[1]（頁面存檔備份，存於網際網路檔案館） 本版未標示充足內容請見英文版 取自「https://zh.wikipedia.org/w/index.php?title=秘書問題&oldid=63176608」 分類：博弈論 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 已展開 已摺疊 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 已展開 已摺疊 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他語言 DeutschEnglishفارسیFrançaisעבריתՀայերեն日本語NederlandsNorskbokmålPolskiРусскийУкраїнськаTiếngViệt 編輯連結