クリスマスイブに出会いの話を

アドベントカレンダーイベントのトリを務める、河村です。現在、自動運転のための画像認識技術の研究開発を推進する部門に所属しています。最近、管理業務が多くなってしまい、技術に浸かる機会がめっきり減ってしまいましたが、好きな数学と物理のネタで何か書きたいなぁと思っていました。

さて、今日はクリスマスイブなので、人生の伴侶をみつけるときにも使える「出会いと最良選択」に関する数学のネタを紹介してみようと思います。

問題設定

人生で出会うさまざまな選択肢のなかから、自分にとって最適な一つを選ぶにはどうしたらよいか悩みませんか？例えば、以下のようなシチュエーションでしょうか。

人生の伴侶を選ぶ
就職活動、転職活動で内定をもらったが、受諾するか否かを決める
あるポジションに最適な人を複数の候補者から採用する
順番に数種類あるお弁当を選ぶ

この問題は、結婚問題、秘書問題などと言われており、以下の条件のもとで、最良の（1位の）人やモノを選択する問題となります。「2位じゃダメなんですか？」と言われそうですが、やはり一番の人と過ごしたいですよね？人生の伴侶を選ぶ問題を以下のように定義します。

生涯出会えると想定される候補の人数は既知で $n$ 人とする
候補者は重複なく順位がつけられるとする（1位から $n$ 位まで）
ランダムな順序で1人ずつ出会う
出会った後に、その人を選ぶかどうか即座に決定する
選ばなかった人を二度と選ぶことはできない

ちなみに、この問題はいろいろなところで紹介されており、ご存知の方もいらっしゃるとは思うのですが、Appendix.には、「一番でなくてもいい。なるべく順位の高い人を選びたいなぁ」という発展版の紹介もしていますので、少々お付き合いいただければと思います。

結論

先に結論を書いてしまいます。与えられた条件のもとで、最良の人を選ぶ戦略は以下のようになります。

最初の $r$ 人は様子を見て選択しない（観察フェーズ）
$r+1$ 人目の人の相対順位が、$r$ 人まで出会った人すべての人よりも高ければその人を選択して終了する。そうでなければ選択せず次の人と出会う（決定フェーズ）
以後、選択が完了するか、$n$ 人の人と出会うまで繰り返す

疑似コードで書くとこんな感じです。$s[i]$ は、$i$ 番目の人の絶対順位を表しています。

partner_id = n-1
For i=r to n-1 do
    if s[i] > MAX(s[0], s[1], ... s[r-1])
        partner_id = i
        break
    else
        continue
    end if
return partner_id

ここで重要なパラメータである $r$ の最適値は、$n$ が十分大きいときは、$n/\mathrm{e}$ となり、この戦略と最適パラメータの元で最良の人と出会える確率は $1/\mathrm{e}\approx 36.8\% $ となります。ここで $\mathrm{e}$ は自然対数の底（$\mathrm{e}=2.71828...$）です。何も考えずにランダムに選ぶと、確率は $1/n$ ですので、1位の人を選択できる確率としては、かなり高いのではないでしょうか。

想定される人数が3人の場合

まずは生涯出会える人数が3人の場合について具体的に考えてみましょう。3人と順番に出会うパターンは、 $3!$ 通りで表1のA～Fの6パターンになります。人物の肩の数字は、その人の絶対順位を示します。

戦略1: とにかく最初に出会った人を選ぶ
戦略2: 最良選択戦略で選ぶ

この二つの戦略で、何位の人を選択することができたかをそれぞれ示します。戦略1ですと、単純に最良の人を選択できる確率は $1/3$ になることがわかるかと思います。戦略2に基づくと、最初に出会った人は（たとえどんなに魅力的でも）選択せず様子を見ます。次に、2番目に出会った人が最初に出会った人よりも魅力的であれば選びます（パターンCとE）。パターンFはこの戦略で2位の人を選んでしまうので結果としては残念ながら失敗となります。もし2番目の人が最初に出会った人よりも魅力的でなければ、その人は選ばず次の人と出会うことにします。戦略2では、なんと1位の人を選ぶことができる確率が $1/2$ になります。パターンAとBのように、最初に1番の人が来てしまったら、もう最良の人とは出会えませんが、全パターンを平均すると、結果的に戦略2が確率を上げることができることがわかります。

パターン	戦略1での選択者と成否	戦略2での選択者と成否
A	1位〇	3位 ×
B	1位〇	2位 ×
C	2位 ×	1位〇
D	2位 ×	1位〇
E	3位 ×	1位〇
F	3位 ×	2位 ×

想定される人数が $n$ 人の場合

出会う可能性がある人の人数が3人の場合を参考に、$n$ 人になった場合を考えてみます。選択せずに観察だけをする人数を $r$ 人とします。観察する人数が多すぎると、直感的に1位の人を見逃してしまう確率が増えてしまいそうです（図2）。

一方で、観察する人数が少なすぎると1位の人ではなく、2位以下の人を最適だと選択してしまう確率が大きくなってしまいます（図3）。

真ん中くらいにちょうどよい $r$ がありそうです。一般解を求めるため、観察する人数が $r$ （$1 \le r \le n - 1 $）のときに、1位の人を選択することができる確率を $P(r)$ とします。まず、ちょうど $i$ 番目（$r+1 \le i \le n$）に最適な人が現れ、さらにその人を最良選択の戦略の基づいて選ぶことができる確率を $p_i$ とします。ちょうど $i$ 番目に1位の人が現れる確率は $1/n$ になります（図4）。

しかし、$i-1$ 番目までの人のなかでもっとも順位が高い人が、 $r+1$ から $i-1$ 番目に現れてしまうと、その人を誤って最良の人と選択してしまいますので、$i$ 番目の1位の人を選択することはできません（図5）。

そのため、$i$ 番目の1位の人を選択するためには、$i-1$ 番目までの人のなかでもっとも順位が高い人が、観察フェーズである$r$ 番目までにいる必要があります（図6）。

よって、$p_i$ は次のように表せます。

$$ p_i = \frac{1}{n}\frac{r}{i-1} $$

観察する人数を $r$ 人としたときに、1位の人を選択する合計の確率を $P(r)$ とすると、$P(r)$ は、1位の人が $r+1$ から $n$ 番目に現れた場合の確率の合計で表せるので、次のようになります。

$$ \begin{eqnarray} P(r) &=& \sum_{i=r+1}^{n} p_i\\ &=& \frac{1}{n}\sum_{i=r+1}^{n}\frac{r}{i-1} \end{eqnarray} $$

少々めんどうですが、任意の $n$ 人の状況での最適な観察人数がこれで計算できそうです。$n$ がいくつかのパターンで、観察フェーズの人数と、そのときに1位の人を選択できる確率を表2に示しました。およそ $1/3$ 程度の人数を観察し、その結果を参考に選択する必要があることがわかります。

	$r=1$	$r=2$	$r=3$	$r=4$	$r=5$	$r=6$	$r=7$	$r=8$	$r=9$
$n=3$	0.5	0.33	---	---	---	---	---	---	---
$n=4$	0.46	0.42	0.25	---	---	---	---	---	---
$n=5$	0.42	0.43	0.35	0.2	---	---	---	---	---
$n=10$	0.28	0.37	0.40	0.40	0.37	0.33	0.27	0.19	0.1

表2：候補者の数 $n$ と観察する人数 $r$ のときに、1位の人選択できる確率

Excel だとめんどうだったので、同僚に紹介してもらったGoogle Colaboratory を使ってみました。環境構築の手間が一切なく、めちゃめちゃ便利ですね。

def probability(observed_count, max_candidates):
    sum = 0
    for person in list(range(max_candidates)):
        if person >= observed_count:
            sum += observed_count / float(person
)
    return sum / float(max_candidates)

n = 10
print("n=" + str(n))
for r in list(range(1, n, 1)):
    print(r, probability(r, n))

解析的考察

一般解として解析的な考察を加えたいので、$n\to\infty$ の仮定をおいて近似します。

高校の微分積分で習った区分求積法の公式

$$ \int_0^1 f(x)dx = \lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n} f\left(\frac{i}{n}\right) $$

を思い出すと、$x=\displaystyle\frac{r}{n}$ として $P(r)$ は $n$ が十分大きいときに次のように近似することができます。

$$\begin{eqnarray} P(x=\frac{r}{n}) &=& \lim_{n\to\infty}\frac{r}{n}\frac{1}{n}\sum_{i=r+1}^{n}\frac{1}{(i-1)/n} \\ &=& x\int_{x}^{1}\frac{1}{t}dt = -x \log x \end{eqnarray}$$

$P(x=\displaystyle\frac{r}{n})$ を最大にする $x$ は、

$$ \frac{d}{dx}x\log x=0 $$

を解いて、

$$ x=\frac{r}{n}=\frac{1}{\mathrm{e}} \to r=\frac{n}{\mathrm{e}}$$ となります。$n=100$ の場合には、約37人となります。そのときの最大の確率は $$ P_{\mathrm{max}}=\frac{1}{\mathrm{e}} $$ であり、約37%になります。いくつかの条件 $n$ における $P(r)$ をプロットしたものが図8になります。$n=100$ で、ほぼ極限値に一致していることがわかります。

この戦略に基づくと、どんなにたくさんの候補がいても、およそ37%の確率で1位の人を選択することができます。人数が少ないときは、それよりも高い確率で1位の人を選択できることがわかります。最初の何人かは、どんなに魅力的でも我慢して見送り、決定フェーズに最適な人が来たら全力でアタックをかけてみることが重要だとわかります。

おわりに

さまざまな状況において、最適な人やものを選択する戦略について述べました。とは言っても、伴侶を選ぶ場合は相手もあることなので、こちらの思い通りにはいかないでしょう。ただ、こちらの思いを受け止めてもらえるか否かも含めて最良の人と考えれば、きっと最適な伴侶と出会えるのではないでしょうか。

この議論の前提は、選択するチャンスは一度だけ、選択しなかったら二度と選ぶことはできないというものです。センスタイムジャパンでの採用では、みなさまにとって最良の選択をしてほしいと考えており、他社の選考結果をお待ちすることもあります。じっくりいろいろな会社をみていただき、それでもセンスタイムが合っている、ぜひ働いてみたいと思ってもらえれば幸いです。

Appendix.

今回ご紹介した最良選択戦略は、あくまで1位の人を選ぶ確率を最大化するものでした。実は、選択する人の順位の期待値を最小化する方がより実践的かもしれません。つまり、必ずしも1位の人でなくても、10位、20位の人でなければ良い、1位でなくても2位か3位くらいの人を選びたいという戦略になります。

選択する人の順位の期待値を最小化する戦略^[1]

最初の議論では1位の人を選択したいので、決定フェーズでは今まで出会った人を含めた相対順位が1位の人でないと選択しませんでした。Appendix.でご紹介する戦略では、選択するか見送るかを判断する相対順位の閾値を使います。またこの閾値はだんだん変化させていきます。直感的には、最初の方は厳しめに、相対順位が1位の人を選択します。だんたん出会う人が増えてきたら、見逃してしまった可能性を考慮して、相対順位が2番目の人、3番目の人でもよしとします。この可変な閾値(Threshold)を数列として用意します。 $${t_1, t_2, ..., t_{n-1}}$$

$i$ 番目の人が、今まで出会った人の中でもっとも良かったら選択するという戦略から、今まで出会った人の中での相対順位が $t_i$ 以上であればその人を選択するという戦略に変更します。$i$ 番目まで選択できなかった条件の下で、それ以降に選択できる人の順位の期待値(eXpectation)を $x_i$ とします。すると、$x_i$ と $t_i$ は漸化式でかけて次のように定められます。

$$ \begin{eqnarray} x_{n-1} &=& \frac{n+1}{2} \\ t_i &=& \left[ \frac{i+1}{n+1} x_i\right] \\ x_{i-1} &=& x_i + \frac{t_i}{i}\left( \frac{n+1}{i+1}\frac{t_i+1}{2} - x_i \right) \end{eqnarray} $$

2行目の $[y]$ はガウス記号で、$y$ を超えない最大の整数を示します。$n=10$ の場合の計算結果を表3 に示します。3人目までは、$t_i = 0$ すなわち、選択しない観察フェーズとなります。4人目、5人目は $t_i = 1$ なので、出会った人が1位の人であったら選択します。6人目、7人目となると、$t_i = 2$ にします。そろそろ出会える人が少なくなってきたので、少し妥協して今まで出会った人との相対順位が2位以上であれば選択します。選択する人の絶対順位の期待値 $x_i$ は、だんだん小さくなっていきますが、この戦略をとることによる最初の期待値 $x_1$ は2.56 であり、10人のなかで上位2～3位の人を選択できそうだということになります。

$i$	1	2	3	4	5	6	7	8	9
$t_i$	0	0	0	1	1	2	2	3	5
$x_i$	2.56	2.56	2.56	2.68	2.89	3.15	3.59	4.28	5.5

表3：$n=10$ の場合の、選択する人の絶対順位の期待値 $x$ と選択する閾値となる相対順位 $t$

表4は、$n=100$ 場合です。最初に述べた1位の人を選択する場合（約37人）よりも少ない27人が観察フェーズとなることがわかります。また、48人以上になったら、相対順位2位の人でも選択します。この戦略に従うと、100人の候補者がいても、平均して3位～4位の人を選ぶことができます。

$i$	1	...	27	28	...	47	48	...	59	60	...	98	99
$t_i$	0	0	0	1	1	1	2	2	2	3	...	37	50
$x_i$	3.60	...	3.60	3.61	...	4.18	4.23	...	4.98	5.06	...	38.0	50.5

表4：$n=100$ の場合の、選択する人の絶対順位の期待値 $x$ と選択する閾値となる相対順位 $t$

$n$ が十分大きいときの解析解を解くのは難しそうなので数値計算をしてみました。図9がその結果となります。選択する人の順位の期待値 $x_1$ は、約3.87に収束します。驚くべきことに、どんなにたくさんの候補者がいても平均4位以内の人を選択できることになります。

候補者の数が与えられたときに、選択する閾値となる相対順位 $t[i]$ と、選択する人の絶対順位の期待値 $x[i]$ を計算するコードです。PEP8のチェックをかけたら、一行が長いと怒られたので細かく変数に代入をしています。少し読みにくいかもしれません。

import numpy as np


def solve_recursion(max_candidates):
    score_threshold = [0] * (max_candidates - 1)  # t[i]
    expected_score = [0] * (max_candidates - 1)  # x[i]

    expected_score[max_candidates - 2] = (max_candidates + 1) / 2.0

    for i in list(range(max_candidates - 1, 1, -1)):
        ex = expected_score[i - 1]
        th = np.floor((i + 1)/(max_candidates + 1) * ex)
        alpha = (max_candidates + 1) * (th + 1) / (2.0 * (i + 1))

        score_threshold[i - 1] = th
        expected_score[i - 2] = ex + th / float(i) * (alpha - ex)

    return score_threshold, expected_score

thresholds, expected_values = solve_recursion(100)

for i in list(range(len(thresholds))):
    print(i+1, int(thresholds[i]), expected_values[i])