お見合い問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
*お見合い問題:marriage problem [#tead651f]
N回お見合いして、良い人を選択する確率的問題である。
応募者から一人の秘書を選ぶ問題と同じであり秘書問題ともよ...
条件は
-Nは既知。
-応募者には順位が付けられ、複数の応募者が同じ順位になるこ...
-無作為な順序で1人ずつお見合い
-毎回、その相手と結婚するか否かを即座に決定する。
-不採用にした相手を後から選択することはできない。
求めたいのは、S-1 回まで見送って、S回より、これまで以上...
秘書問題(secretary problem)は、最適停止問題の一種で、応...
*お見合い予定数Nの1/eの回数から最適。e:ネイピア数 [#aff...
驚くべきことに、お見合い回数Nが増加すれば、最適な回数S*は...
S*=N/e e=ネイピア数
そして、''最善の人が見つかる確率は、1/e=0.368''にNが増大...
''予定回数Nの37%あたりから、探し始めるのが良いので「37...
*証明:最適な停止規則 [#fe420de8]
最適ポリシーを停止規則 (stopping rule) と呼ぶ。
面接者は最初の S − 1 人の応募者をスキップし、その次の応...
任意の S について最善の応募者を選択する確率を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と結婚で...
2人スキップするのは,最後の一人を選ぶのと同じ.1と結婚で...
1人スキップする場合は,1と結婚できる確率は1/2
なので、1人スキップするのが最適であり、P(S*)=1/2 である。
i番目に最高の相手がいて,かつ,その相手と結婚できるという...
最高の相手と結婚できる確率は,
P(S)=Pr(Es+1)+Pr(Es+2)+...+Pr(EN)
になる。
最高の相手はランダムにちらばっているので,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で微分して0と置くことで、最適な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:/...
*お見合い回数、最適な選択開始回数、最善選択確率の関係 [#f...
最善な人が選ばれる確率は、1/ネイピア数 に近づく。
あくまで、お見合い候補者の中の最善の方が選ばれる確率です。
-もし、100人に一人の良い方を選ぶならば、お見合い回数nの...
-仮に、10回お見合いするとします。下表より、10人中最良の人...
#ref(marigge problem.JPG)
*最適停止問題の 1/eの法則 [#v2209286]
The essence of the model is based on the idea that real-w...
The model: An applicant must be selected on some time int...
#ref(arrival time.JPG) .
1/e-law: Let τ be such that F(τ) = 1 / e. Consider the st...
The 1/e-strategy
(i) yields for all N a success probability of at least 1/...
(ii) is the unique strategy guaranteeing this lower succe...
(iii) selects, if there is at least one applicant, none a...
When the 1/e-law was discovered in 1984 it came as a surp...
終了行:
*お見合い問題:marriage problem [#tead651f]
N回お見合いして、良い人を選択する確率的問題である。
応募者から一人の秘書を選ぶ問題と同じであり秘書問題ともよ...
条件は
-Nは既知。
-応募者には順位が付けられ、複数の応募者が同じ順位になるこ...
-無作為な順序で1人ずつお見合い
-毎回、その相手と結婚するか否かを即座に決定する。
-不採用にした相手を後から選択することはできない。
求めたいのは、S-1 回まで見送って、S回より、これまで以上...
秘書問題(secretary problem)は、最適停止問題の一種で、応...
*お見合い予定数Nの1/eの回数から最適。e:ネイピア数 [#aff...
驚くべきことに、お見合い回数Nが増加すれば、最適な回数S*は...
S*=N/e e=ネイピア数
そして、''最善の人が見つかる確率は、1/e=0.368''にNが増大...
''予定回数Nの37%あたりから、探し始めるのが良いので「37...
*証明:最適な停止規則 [#fe420de8]
最適ポリシーを停止規則 (stopping rule) と呼ぶ。
面接者は最初の S − 1 人の応募者をスキップし、その次の応...
任意の S について最善の応募者を選択する確率を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と結婚で...
2人スキップするのは,最後の一人を選ぶのと同じ.1と結婚で...
1人スキップする場合は,1と結婚できる確率は1/2
なので、1人スキップするのが最適であり、P(S*)=1/2 である。
i番目に最高の相手がいて,かつ,その相手と結婚できるという...
最高の相手と結婚できる確率は,
P(S)=Pr(Es+1)+Pr(Es+2)+...+Pr(EN)
になる。
最高の相手はランダムにちらばっているので,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で微分して0と置くことで、最適な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:/...
*お見合い回数、最適な選択開始回数、最善選択確率の関係 [#f...
最善な人が選ばれる確率は、1/ネイピア数 に近づく。
あくまで、お見合い候補者の中の最善の方が選ばれる確率です。
-もし、100人に一人の良い方を選ぶならば、お見合い回数nの...
-仮に、10回お見合いするとします。下表より、10人中最良の人...
#ref(marigge problem.JPG)
*最適停止問題の 1/eの法則 [#v2209286]
The essence of the model is based on the idea that real-w...
The model: An applicant must be selected on some time int...
#ref(arrival time.JPG) .
1/e-law: Let τ be such that F(τ) = 1 / e. Consider the st...
The 1/e-strategy
(i) yields for all N a success probability of at least 1/...
(ii) is the unique strategy guaranteeing this lower succe...
(iii) selects, if there is at least one applicant, none a...
When the 1/e-law was discovered in 1984 it came as a surp...
ページ名: