#freeze
*お見合い問題：marriage problem [#tead651f]
N回お見合いして、良い人を選択する確率的問題である。
応募者から一人の秘書を選ぶ問題と同じであり秘書問題ともよばれる。

条件は
-Nは既知。
-応募者には順位が付けられ、複数の応募者が同じ順位になることはない
-無作為な順序で1人ずつお見合い
-毎回、その相手と結婚するか否かを即座に決定する。
-不採用にした相手を後から選択することはできない。

求めたいのは、Ｓ-1　回まで見送って、S回より、これまで以上に良いひとが現れれば選択するとして、探し始めるのが最適かという問題である。

秘書問題（secretary problem）は、最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。
*お見合い予定数Ｎの1/eの回数から最適。e：ネイピア数 [#affacb84]
驚くべきことに、お見合い回数Nが増加すれば、最適な回数S*は、ネイピア数を使って表現される。
 S*=N/e 　　e=ネイピア数
そして、''最善の人が見つかる確率は、1/e=0.368''にNが増大すれば、近づく。

''予定回数Nの37%あたりから、探し始めるのが良いので「３７％」ルールとも''呼ばれる。

*証明：最適な停止規則 [#fe420de8]
最適ポリシーを停止規則 (stopping rule) と呼ぶ。
面接者は最初の Ｓ − 1 人の応募者をスキップし、その次の応募者が候補者（すなわち、それまで面接した中で最もよい応募者）なら採用する。
任意の Ｓ　について最善の応募者を選択する確率をP(S)とする。

簡単な例で考えよう。N=3で、応募者1が最高，2がその次，3が最悪とする。
起こりうる順番は，
  (1,2,3), (1,3,2)
  (3,2,1), (2,3,1)
  (3,1,2), (2,1,3)
の6通り.
この場合
 0人スキップするのは，最初の一人を選ぶのと同じ．1と結婚できる確率は1/3.
 2人スキップするのは，最後の一人を選ぶのと同じ．1と結婚できる確率は1/3
 1人スキップする場合は，1と結婚できる確率は1/2
なので、１人スキップするのが最適であり、P(S*)=1/2　である。

i番目に最高の相手がいて，かつ，その相手と結婚できるという事象をEiとする。(i>S）
最高の相手と結婚できる確率は，
 P(S)=Pr(Es+1)+Pr(Es+2)+...+Pr(EN)
になる。

最高の相手はランダムにちらばっているので，i番目にいる確率は1/Nである。また、i番目の最高の相手と結婚できるためには，1からi-1番目までで最も良い相手が，S-1番目までに入っている必要があり，この確率は(S-1)/(i-1)である。独立性と条件付き確率より、これらの積がi回目に最高の相手が見つかる確率である。 (^-^ 
 P(Ei)=(1/N) ×S/(i-1)
S回以降で最高の相手が見つかる確率は
 P(S) =((S-1)/N) ・　Σ1/(i-1)　　　　だだし、SからNまでの合計
である。
S/N の極限を x、i/N を t、1/N を dt とすると、上記の総和は次の積分で近似できる。
#ref(stoppingrule.JPG)
そこで、P(S)の近似値P(X)は
 P(x)= -xlog(x)
これを　xで微分して０と置くことで、最適なx*=S*/N　を求められる。
 P'(x)=-log(x)-1=0
となるので、
 S*/N=1/e　eはネイピア数
証明　終わり。

*見合い予定回数Nが小さい場合 [#q9f2a259]

Nが小さい場合、最適な 停止回数 は標準的な動的計画法の手法で得られる
最善を選択する確率は非常に急速に1/eに近づく。

-Nが1から9の場合の停止回数、最良の人が見つかる確率を次の表で示します。
-9回見合いするなら、3回見送り、4回目以降で選ぶのが最適です。
#ref(stoppingrule2.JPG)

*鳩山 由紀夫　首相の研究 [#caac26ec]
鳩山首相は、[[講演　生活の中における情報と意思決定>http://elib.doshisha.ac.jp/cgi-bin/retrieve/sr_bookview.cgi/U_CHARSET.EUC-JP/BD00011513/Body/039000010005.pdf]]　の中で、この問題を紹介されています。
*お見合い回数、最適な選択開始回数、最善選択確率の関係 [#f23bfd0c]
最善な人が選ばれる確率は、1/ネイピア数　に近づく。
あくまで、お見合い候補者の中の最善の方が選ばれる確率です。
-もし、100人に一人の良い方を選ぶならば、お見合い回数ｎの場合、ランダムに見合いする場合、n/100が候補者のなかにその方のいる確率ですから、これを掛けなければいけません。たくさんの方と会う必要がありますね。
-仮に、10回お見合いするとします。下表より、10人中最良の人を選ぶ方法は、3回見送り4回目から以前より良い人を選ぶ方法が最適であります。最良の人が選ばれる確率は、概ね0.4＝４０％ですね。さらに10人の中に、100人に1人の良い人がいる確率は10/100ですから、これを掛けると４％の確率で100人に１人の良い人が見つかることになります。なかなか良い人を見つけるのは大変ですね。
#ref(marigge problem.JPG)

*最適停止問題の　1/eの法則 [#v2209286]

The essence of the model is based on the idea that real-world problems pose themselves in real time and that it is easier to estimate times in which specific events (arrivals of applicants) should occur more likely (if they do) than to estimate the distribution of the number of specific events which will occur. This idea lead to the following approach, the so-called Unified approach(1984):

The model: An applicant must be selected on some time interval [0,T] from an unknown number N of rankable applicants. The goal is to maximize the probability of selecting online the best under the hypothesis that all arrival orders of different ranks are equally likely. Suppose that all applicants have independently of each other the same arrival time density f on [0,T] and let F denote the corresponding arrival time distribution function, that is

#ref(arrival time.JPG) . 
1/e-law: Let τ be such that F(τ) = 1 / e. Consider the strategy to wait and observe all applicants up to time τ and then to select, if possible, the first candidate after time τ which is better than all preceding ones. Then this strategy, called 1/e-strategy, has the following properties:

The 1/e-strategy

(i) yields for all N a success probability of at least 1/e, 
(ii) is the unique strategy guaranteeing this lower success probability bound 1/e, and the bound is optimal, 
(iii) selects, if there is at least one applicant, none at all with probability exactly 1/e. 
When the 1/e-law was discovered in 1984 it came as a surprise. The reason was that a value of about 1/e had been considered before as being out of reach in a model for unknown N, whereas now this value was achieved as a lower bound, and this in a model with arguably weaker hypotheses (see e.g. Math. Reviews 85:m).
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS