海辺の美女の問題（結婚相手の最初の4割捨てろ理論？）をカシオの高精度計算サイトに作った（林先生が驚く初耳学？） #初耳学

今日、新聞のテレビ欄を見ていたら、林先生が驚く初耳学の紹介で、

”結婚相手の最初の4割は捨てろ理論”と書いてあった。

もちろんまだ観てないのだが、、これってあれ？海辺の美女の問題？

私はこれを”数学100の問題”（日本評論社）で初めて知った。

海辺にn人の美女が並んでいる。美女には順位がついているがそれはわかってない状態で一人ずつ会う。 一体何人目を誘うのがいいのか？

という戦略の問題です。

OPTIMAL SELECTION BASED ON RELATIVE RANK

(the "Secretary Problem")
BY Y. S. CHOW, S. MORIGUTI, H. ROBBINS AND S. M. SAMUELS

https://www.math.upenn.edu/~ted/210F10/References/Expectations.pdf

という論文で解決されたというもの。

平均順位はn→∞で3.86950・・・となる。

数学100の問題にはプログラムもついていたので、それをカシオの高精度計算サイトkeisan.casio.jpに自作式として登録した。

これ。

海辺の美女の問題(結婚する相手を探す問題)

例えば20人をやってみよう。

会った順番	ここまで誘わなかったときの順位の期待値	これまでにあった中でこの順位より良ければ誘う。
19	10.5	10
18	8.0131578947368	7
17	6.6162280701754	5
16	5.6996904024768	4
15	5.046826625387	3
14	4.5624613003096	3
13	4.1847910216718	2
12	3.8871308644915	2
11	3.6431218742558	2
10	3.4580088062093	1
9	3.3031170164974	1
8	3.1694373479977	1
7	3.0649243461647	1
6	3.0020780109983	1
5	3.0017316758319	誘わない
4	3.0017316758319	誘わない
3	3.0017316758319	誘わない
2	3.0017316758319	誘わない
1	3.0017316758319	誘わない

ということで5人は捨てろ、という。その時は大体3位くらいの順位に当たる。

実はn→∞の時の最善の相手を選ぶ確率は1/eになる、と知られている。なのでn/eをスキップする、ということで大体37％捨てる、つまり4割捨てろという。

※秘書問題、最適停止問題などという名前でも知られているそうです。

って実際にテレビ観てみないとこの問題なのかどうかわからないですが、、、10時以降にまた追記します。

林先生の解法はこうでした。やっぱり上の話でした。n→∞とした場合の近似確率の話。

今、あなたが20歳とする。35歳までに理想の人に会いたい。

1年で1人ずつ出会う場合を考える。よりを戻さないものとする。

全部でn人とする。t番目に一番いい人がいるとする。

見定め期間を見つけて暫定No.1を決めておく。k人を見定める。

ｔよりもkが大きいと確率0％。

で確率はk/(t-1)でいいと。

http://mathtrain.jp/hisyomondai

を参考に。

で答えはk=n/e。

e=2.718で大体1/e=0.37。

37%捨てるということで、20歳から35歳で15人にあうとしたら、最初の6人を見送る。

もうちょっと説明すると、

t番目に一番いい人がいる確率は1/nで、

k人を飛ばすとする。kがtより大きいと確率0になる。とばしちゃうから。

k人飛ばしてtまで見るときは、その飛ばしたk人の中に2番目にいい人がいないとだめ。

そうしないとｔにたどり着く前に別の人を選んじゃう。

なので確率がk/(t-1)になる。tはk+1～nまでの可能性があって、かつどこにいい人がいるかという確率が1/nなんで

Σ1/n * k/(t-1)　[t=k+1～n]

と求まる。ここからnが十分大きいとしましょう。

log(m)～1+1/2+1/3+・・・1/m

を使うと、

この確率は

k/n * log(n/k)

と近似できる。

これをkで微分すると1/n*log(n/k) -1/nでこれを0と置くと、

log(n/k)=1

だからn/k=e。k=n/eとなります。n人いてn/e飛ばす、ということ。