秘書問題で学ぶ100%婚活必勝講座（大嘘）

f:id:dw_dw_dt:20210130153934j:plain

今回は、「モーテル問題」「秘書問題」「浜辺の美女問題」

と言われる問題を確認してみたいと思います。

秘書問題

秘書を1人雇いたいとする。 $N$ 人が応募してきている。
応募者には順位が付けられ、複数の応募者が同じ順位になることはない。
無作為な順序で1人ずつ面接を行う。
毎回の面接後、その応募者を採用するか否かを即座に決定する。
その応募者を採用するか否かは、それまでの面接に基づいて決定する。
不採用にした応募者を後から採用することはできない。
このような状況で、最良の応募者を選択することが問題の目的である。

秘書問題 - Wikipedia

モデリング

まず、並んでいる $N$ 人を $1,2,...,N$ の数字の順列とみなします。

すると、 $1$ から $N$ までの数字を並べた順列は $N!$ パターン存在します。

その $N!$ 個の順列によって構成される集合を $\Omega$ 、その要素を $\omega$ とする。

$\omega=(\omega_{1},\omega_{2},...,\omega_{N})$ 。

また、 $t$ 人目の応募者と会った時点で得られている情報を $\mathscr{F}_{t}$ とする。

例えば、 $\mathscr{F}_{1}=\{Ω,\emptyset\}$ 、 $\mathscr{F}_{2}=\{Ω,\emptyset, \{ \omega | \omega_{2} > \omega_{1} \} , \{ \omega | \omega_{1} > \omega_{2} \} \}$ となります。

さて、候補者を選んだ際の効用の設計を以下で行います。

順位が下から $k$ 番目の候補者を選んだ際の効用を $f(k)$ とする。
今回は、もっとも良い候補者を選んだ場合のみ効用が発生する場合、つまり $f(N)=1$ で $k!=N$ では $f(k)=0$ となるような $f(k)$ を想定する。

ここで、 $X_{m}$ を、 $m$ 人目の候補者を選んだ際に、その人が全体で何番目かを表す確率変数とします。

つまり、 $X_{n}$ は $\omega$ の $n$ 番目の成分への射影であり、 $X_{n}(\omega)=\omega_{n}$ となります。

例えば、常に5番目に出会った候補者を採用するという戦略は $X_{5}$ であり、

その際の効用は $f(X_{5}(\omega))$ という確率変数であらわされることになる。

しかし、常に5番目の候補者を選択するという戦略のは直感的にもよくなさそうな気がします。

そこで、 $X_{m}$ の添え字の $m$ が機動的に変化する設定を考えたくなる。

そういった場合に役に立つのが最適停止時刻の考え方です。

確率空間 $(\Omega, \mathscr{F}, P)$ 上にフィルトレーション $\mathscr{F}_{t}$ と可積分な確率過程 $X_{t}$ が与えられているとする。
このとき、 $\mathscr{G}$ を停止時刻全体（つまり $\sigma \in \mathscr{G}$ として $\{ \omega | \sigma(\omega) \le N \} \in \mathscr{F}_{N}$ ）とすると、
$\max_{\sigma \in \mathscr{G}}E[X_{\sigma}$ ]を満たす停止時刻 $\sigma$ が最適停止時刻である。

この考え方を先の $X_{m}$ に導入します。

ある時点までに分かっている情報に基づいて採用かどうかを決めることは

停止時刻として表現できるので、

今回の問題は、停止時刻を $T(\omega)$ として
$\max_{T(\omega) \in \mathscr{G}} E[f(X_{T(\omega)}(\omega))$ ]を満たす $T(\omega)$ を求める

という問題に帰着します。

最適停止問題の解き方

本題に入る前に、最適停止問題 $\max_{\sigma \in \mathscr{G}}E[ X_{\sigma}$ ]の一般的な解き方を確認する。

天下り的ですが、 $\{Z_{n}\}^{N}_{1}$ を

$Z_{N}=X_{N}$
$Z_{N}, Z_{N-1},...$ と求まったとき、 $Z_{n-1}=E[Z_{n}|\mathscr{F}_{n-1}] \vee X_{n-1}$ と定める

この時、以下の性質が成り立つ。

$\{Z_{n}\}$ は優マルチンゲール
$X_{n} \le Z_{n}$
$Z_{n}$ は 1., 2.を満たす中で最小

つまり、この $\{Z_{n}\}$ は $\{X_{n}\}$ より値が大きい優マルチンゲールのうちで

最小のものということなのです（スネル包）。

で、この $Z_{n}$ を用いて作られる以下の停止時刻 $\sigma_{0}(\omega)$ が最適停止時刻になっている

最適停止問題 $\max_{\sigma \in \mathscr{G}}E[ X_{\sigma}$ ]における解は $\sigma_{0}(\omega)=min(n| X_{n}(\omega)=Z_{n}(\omega))$

具体例

コイントスを10回やります。最後に出た目の期待値を大きくするにはいつサイコロを振るのをやめればよいか？

$X_{n}$ を $n$ 回目に出た目とします。

$Z_{n}$ を求めていくと、

$Z_{10}=X_{10}$

$Z_{9}=E[Z_{10}|\mathscr{F}_{9}] \vee X_{9}=max(3.5, X_{9})$

$Z_{8}=E[Z_{9}|\mathscr{F}_{8}] \vee X_{8}=max(4.25, X_{8})$

$Z_{7}=E[Z_{8}|\mathscr{F}_{7}] \vee X_{7}=max(4.6..., X_{7})$

$Z_{6}=E[Z_{7}|\mathscr{F}_{6}] \vee X_{6}=max(4.9..., X_{6})$

$Z_{5}=E[Z_{6}|\mathscr{F}_{5}] \vee X_{5}=max(5.1..., X_{5})$

...

というふうに求まってっていくことがわかります。

で、肝心の停止時刻はというと $X_{n}$ の値を見ながら判定していくことになります。

あとコイントスが2回残っていれば、最後の1回の(10回目の)期待値が3.5なので、

次の(9回目の)コイントスで4以上、つまり $Z_{9}=X_{9}$ なら $\sigma_{0}=9$ となりそこでストップ、3以下なら $Z_{9}>X_{9}$ となり $\sigma_{0}=10$ となる

同様にして、残りコイントスが3~5回なら、次に出た目が4以下なら続行、5以上ならストップ

残りコイントスが6回以上であれば、次に出る目が6以外は続行

というのが最適戦略となる

また、 $Z_{n}$ が、そのまま続けた際の期待値と $X_{n}$ との比較になっていたことがわかります。

$\sigma_{0}$ の最適性の証明

ここでは $\sigma_{0}$ が最適となっていること、つまり $E[X_{\sigma}] \le E[X_{\sigma_{0}}]$ を確認します。

まず $\{Z_{n\wedge\sigma_{0}}\}$ が $\mathscr{F}_{n}$ マルチンゲールであることを示す。

$Z_{n\wedge\sigma_{0}}$

$=Z_{1} + \sum_{k=2}^{n}1_{\{k \le \sigma_{0}\}}(Z_{k}-Z_{k-1})$

$=Z_{1} + \sum_{k=2}^{n}1_{\{k \le \sigma_{0}\}}(Z_{k}-E[Z_{k}| \mathscr{F}_{k-1} ])$

よって $E[Z_{n\wedge\sigma_{0}} -Z_{(n-1)\wedge\sigma_{0}}| \mathscr{F}_{n-1} ]=0$ より結論を得る。

$\mathscr{F}_{n}$ マルチンゲールであることから

$E[Z_{1}] = E[Z_{1\wedge\sigma_{0}}] = E[Z_{N\wedge\sigma_{0}}] = E[Z_{\sigma_{0}} ]$

とわかる。

ここで $X_{n} \le Z_{n}$ と $Z_{n}$ の優マルチンゲール性より

$E[X_{\sigma}] \le E[Z_{\sigma} ] \le E[Z_{1}] = E[Z_{\sigma_{0}} ]$

この時、 $\sigma_{0}$ において $X_{\sigma_{0}} = Z_{\sigma_{0}}$ なので

$E[X_{\sigma}] \le E[Z_{\sigma} ] \le E[Z_{1}] = E[Z_{\sigma_{0}} ]= E[X_{\sigma_{0}} ]$

したがって、 $E[X_{\sigma}] \le E[X_{\sigma_{0}}]$ とわかった

今回の最適停止問題の解き方の概要

まずはじめに、 $\{f(X_{n}(\omega))\}$ が $\mathscr{F}_{n}$ 適合とは限らないので

$Y_{n}=E[ f(X_{n}(\omega) | \mathscr{F}_{n}]$ とおく。

$Y_{n}$ は $\mathscr{F}_{n}$ 適合なので、 $X_{n}$ の代わりに $Y_{n}$ を考えればよい。

すると、先ほどの議論から $T_{0}=min\{n| Y_{n}=Z_{n}\}$ となる $T_{0}$ を求めればよいとわかる。

$Y_{n}=E[ f(X_{n})| \mathscr{F}_{n}] = \sum_{k=1}^{N}f(k)E[1_{\{X_{n}=k\}}| \mathscr{F}_{n}]$

であるので、 $A_{n,i}=\{\omega|\omega_{n}が\omega_{1},...,\omega_{n}のうち、下から数えてi番目\}$ とおく。

ここで $A_{n,i} \in \mathscr{F}_{n}$ であり、 $A_{n,i} \cap A_{n,j} \neq \emptyset$ かつ $\Omega = \cup_{i=1}^{n}A_{n,i}$ が成立する。

補題1
$\alpha_{k;n,i}$ を、 $i \le k \le N-n+i \le N$ のとき ${}_{k-1}C_{i-1} {}_{N-k}C_{n-i} /{}_{N}C_{n}$ とし、
それ以外の時は $0$ とする。この時以下が成立する。
$E[1_{\{X_{n}=k\}} | \mathscr{F}_{n}] = \sum_{i=1}^{n}\alpha_{k;n,i}1_{A_{n,i}}$

補題1より、 $a_{n,i}= \sum_{k=1}^{N}f(k)\alpha_{k;n,i}$ とおくと以下が成立する。

$Y_{n}$
$=\sum_{k=1}^{N}f(k)E[1_{\{X_{n}=k\}}| \mathscr{F}_{n}]$
$=\sum_{i=1}^{n}\sum_{k=1}^{N}f(k)\alpha_{k;n,i}1_{A_{n,i}}$
$=\sum_{i=1}^{n}a_{n,i}1_{A_{n,i}}$

これで $Y_{n}$ についてかなりわかりやすい形になったので、次に $Z_{n}$ を考える。

命題1
$\{c_{n}\}_{n=0}^{N}$ を $c_{N}=0$ とし、帰納的に $c_{n-1}=\frac{1}{n}\sum_{i=1}^{n}(a_{n,i} \vee c_{n} )$ で定める。
この時以下が成立する。
$Z_{n}=\sum_{i=1}^{n}(a_{n,i} \vee c_{n})1_{A_{n,i}}$

これで、 $T_{0}=min\{ n| Y_{n} = Z_{n} \}$ の $Y_{n},Z_{n}$ の形が特定できた。

少し書き下すことで、 $T_{0}=min\{ n| a_{n,i} \ge c_{n} \}$ となることがわかる。

実はここまでの文脈では、 $f(k)$ についての情報は使っていない。

そこで、最良選択の $f(k)$ について、さらに内容を確認していく。

最良選択の場合、 $a_{n,i}=\alpha_{N;n,i}$ となる。

そして $\alpha_{N;n,i}$ は $i=n$ のときに ${}_{N-1}C_{n-1} {}_{N-N}C_{n-n} /{}_{N}C_{n} = \frac{n}{N}$ となり、

それ以外の時は0になる。

これを用いて $c_{n}$ を計算すると以下のようになる。

補題2
$\frac{1}{n+1}+...+\frac{1}{N-1} \le 1$ のとき、 $c_{n}=\frac{n}{N}(\frac{1}{n}+\frac{1}{n+1}+...+\frac{1}{N-1})$ が成り立つ。
$\frac{1}{n}+...+\frac{1}{N-1} > 1$ のとき、 $c_{n} > \frac{n}{N}$ となり $c_{1}=...=c_{n}$ が成り立つ。

$k_{N}$ を $\frac{1}{k_{N}+1}+...+\frac{1}{N-1} \le 1$ かつ $\frac{1}{k_{N}}+...+\frac{1}{N-1} > 1$ とすると

$n \le k_{N}$ では $c_{n} > \frac{k_{N}}{N} > a_{n,i}$ となり、停止条件にヒットすることはない。

そして $n$ が $k_{n}$ より大きいと、 $c_{n}$ が減少し、

たとえば、 $c_{k_{N}+1}=\frac{k_{N}+1}{N}(\frac{1}{k_{N}+1}+...+\frac{1}{N-1}) \le \frac{k_{N}+1}{N}$ となる。

一方で $a_{n,i}$ は、それまでで最良の時だけ $\frac{n}{N} (\ge c_{n})$ をとるので、

この問題での最適な戦略は、
$k_{N}$ 人と会ったあとは、今までで一番いい候補者に遭遇したらその人でdoneすればいい

ということですね！

例えば10人の候補者がいる場合は、初めの3人( $k_{N}$ )を見送った後、

それまでで一番いい人が現れたらその人に決めればよいということですね！

補題1の証明

よくあるインディケーター関数と確率に関する $E[1_{A}] = P(A)$ の条件付きverで、

$E[1_{\{X_{n}=k\}}| \mathscr{F}_{n}] = \sum_{\sigma \in S_{n}}P(\{X_{n}=k\}|A_{\sigma})1_{A_{\sigma}}$

ここで、 $S_{n}$ というのは $n$ 次対称群（ $\{1,2,...,n\}$ の順列全体からなる群）とする。

すると、 $P(\{X_{n}=k\}|A_{\sigma})$ というのは、

「いままでの $n$ 人の順位付けが与えられたうえで、 $n$ 番目にあった人はその中で $i$ 番目の順位でした。

ではその $n$ 番目にあった人は全体の $N$ 人のうち $k$ 番目である確率はいくつでしょう？」

という問題の答えになる。

すると、 $i \le k \le N-(n-i)$ が満たされなければ $P(\{X_{n}=k\}|A_{\sigma}) = 0$ となることがわかる。

上記の条件が満たされている場合について考える。

全体の並び方は $N!$ 個となる。

このうち、 $n$ 番目に会った人が、初めの $n$ 人のうちで $i$ 番目となる並び方は ${}_{N}C_{n}(n-1)!(N-n)!$ となる。

次に、 $n$ 番目に会った人が、初めの $n$ 人のうちで $i$ 番目かつ全体で $k$ 番目となる並び方は ${}_{k-1}C_{i-1} {}_{N-k}C_{n-i} (n-1)!(N-n)!$ となる。

したがって、 $P(\{X_{n}=k\}|A_{\sigma}) = \alpha_{k;n,i}$

命題1の証明

帰納法で示す。

$n=N$ のときは定義より $Z_{N}=Y_{N}=\sum_{i=1}^{N}a_{N,i}1_{A_{N,i}}$ となり成立。

$n$ の時成立すると仮定すると

$Z_{n-1}$

$= E[ Z_{n}| \mathscr{F}_{n-1}] \vee Y_{n-1}$

$= \sum_{i=1}^{n}(a_{n,i }\vee c_{n}) E[1_{A_{n,i}} | \mathscr{F}_{n-1}] \vee Y_{n-1}$

$= \frac{1}{n}\sum_{i=1}^{n}(a_{n,i }\vee c_{n}) \vee Y_{n-1}$

$= c_{n-1} \vee Y_{n-1}$

$= c_{n-1} \vee \sum_{i=1}^{n-1}a_{n-1,i}1_{A_{n-1,i}}$

$= \sum_{i=1}^{n-1}(c_{n-1} \vee a_{n-1,i}) 1_{A_{n-1,i}}$

よって帰納法より示された。

補題2の証明

帰納法で示す。

定義から $c_{N}=0$ , $c_{N-1}=\frac{1}{N}(0+0+...+\frac{N}{N})=\frac{1}{N}$ , $c_{N-2}=\frac{1}{N-1}(\frac{N-2}{N}+\frac{N-1}{N})=\frac{N-2}{N}(\frac{1}{N-2}+\frac{1}{N-1})$