秘書問題
秘書問題や類似する問題の直接的解法として Odds algorithm がある。
この問題の最適ポリシーを最適停止規則 (optimal stopping rule) と呼ぶ。それは『面接者は最初の r {\displaystyle r} 人の応募者をスキップし、その後にきた最初の候補者(すなわち、それまで面接した中で最もよい応募者)を採用する』というものであることが知られている。 (ここで用いられる r {\displaystyle r} の値を閾値と呼び、上記のような規則を閾値戦略と呼ぶことが多い) 任意の r ∈ { 1 , 2 , ... , n } {\displaystyle r\in \{1,2,\ldots ,n\}} について最良の応募者を選択する確率は次の通りである。
最良の応募者は k + 1 {\displaystyle k+1} 人目であるとする。 最良の応募者が、 { r + 1 , r + 2 , ... , n } {\displaystyle \{r+1,r+2,\ldots ,n\}} 人目にいる場合だけ、成功する(最良の応募者を選択する)可能性がある。(すなわち r ≤ k ≤ n − 1 {\displaystyle r\leq k\leq n-1} の場合だけ考えれば良い) 最良の応募者が, r + 1 , r + 2 , ... , n {\displaystyle r+1,r+2,\ldots ,n} 人目にいる場合それぞれについて (これらの事象の起きる確率は全て 1 / n {\displaystyle 1/n} )、 以下のように考える。