秘書問題
V n ( c ) {\displaystyle V_{n}(c)} を c {\displaystyle c} について微分すると ∂ V / ∂ c = ( − c 2 + n ) / ( 2 c 2 n ) {\displaystyle \partial V/\partial c=\left(-{c}^{\,2}+n\right)/\left(2{c}^{\,2}n\right)} となる。 c {\displaystyle c} の許容される値については常に ∂ 2 V / ∂ c 2 < 0 {\displaystyle \partial ^{\,2}V/\partial c^{\,2}<0} なので、 V {\displaystyle V} は c = n {\displaystyle c={\sqrt {n}}} のときに最大となることがわかる。 V {\displaystyle V} は c {\displaystyle c} の凸関数なので、最適な整数のしきい値は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } か ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } のどちらかとなる。したがって、本来の秘書問題に比べて基本報酬問題ではスキップする人数が少ないことが多い。なお、これは近似解ではなく、全ての n {\displaystyle n} について成り立つ。
秘書問題(英: secretary problem)は、最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。具体的には、次のような問題である。
秘書を1人雇いたいとする。
n {\displaystyle n} 人が応募してきている。 n {\displaystyle n} という人数は既知である。
応募者には順位が付けられ、複数の応募者が同じ順位になることはない(1位からn位まで重複無く順位付けできる)。
無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
毎回の面接後、その応募者を採用するか否かを即座に決定する。
その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
不採用にした応募者を後から採用することはできない。
E t = E ( X t | I t = 1 ) = t t + 1 {\displaystyle E_{t}=E\left(X_{t}|I_{t}=1\right)={\frac {t}{t+1}}}
本来の秘書問題と同様、最適ポリシーにはしきい値があり、ここではそれを c {\displaystyle c} とする。面接者は c {\displaystyle c} 人目以降の候補者を採用すべきである。Bearden (2006)によれば、 c {\displaystyle c} は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } または ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } である。実際、 n {\displaystyle n} 人の候補者で 1 ≤ c ≤ n {\displaystyle 1\leq c\leq n} の任意のしきい値について期待される報酬は次のようになる。
V n ( c ) = ∑ t = c n − 1 [ ∏ s = c t − 1 ( s − 1 s ) ] ( 1 t + 1 ) + [ ∏ s = c n − 1 ( s − 1 s ) ] 1 2 = 2 c n − c 2 + c − n 2 c n {\displaystyle V_{n}(c)=\sum _{t=c}^{n-1}\left[\prod _{s=c}^{t-1}\left({\frac {s-1}{s}}\right)\right]\left({\frac {1}{t+1}}\right)+\left[\prod _{s=c}^{n-1}\left({\frac {s-1}{s}}\right)\right]{\frac {1}{2}}={\frac {2cn-{c}^{2}+c-n}{2cn}}}