オッズ法のソースを表示

{{Expand English|Odds algorithm|date=2024年5月}}
'''オッズ法'''（おっずほう、[[英語|英]]: odds algorithm）は、最後の出来事判定問題を最大正解確率で解く数学的アルゴリズムである<ref>Bruss, F. T.; ''Sum the odds to one and stop'', Annals of Probability, Institute of Mathematical Statistics, 28 (3) 1384–1391 (2000).</ref>。最後の出来事判定問題とは、出来事が1番目から ''n'' 番目まで（それぞれ独立に）順番に目の前で起こり、出来事は性質 ''S'' を持つ出来事か、性質 ''S'' を持たない出来事のどちらかである。順番に判定し、目の前の出来事が性質 ''S'' を持つ最後の出来事と思ったら、その出来事を最後の出来事として選択し終了する。性質 ''S'' を持つ出来事が ''i'' 番目に出現する確率は事前にわかっていて、<math>f(i)</math>で、<math>0 < f(i) < 1</math>とする。
出現確率 <math>p</math> の出来事の出現確率と非出現確率の比 <math>p/(1-p)</math> を[[オッズ]]と呼ぶので、この名称がある。

== オッズ法の手順 ==
まず以下の式でインデックス ''s'' を計算する。
ここで ''s'' は、存在するならば、以下の式を満たす1以上 ''n'' 以下の最大の ''k'' であり、

 <math>f(k)/(1-f(k))+...+f(n)/(1-f(n)) \ge 1</math> 

存在しないならば、<math>s=1</math>とする。 

最適な判定法は、1番目から　<math>s-1</math>　番目までは見送り、''s'' 番目から ''n'' 番目までの中で最初に性質 ''S'' を持つ出来事を最後の出来事として選択する。この方法による正解確率は以下となる。 

<math>(1-f(s))...(1-f(n))(f(s)/(1-f(s))+...+f(n)/(1-f(n)))</math>

すなわち、最後の出来事判定問題の最大正解確率は(非出現確率の積)(オッズの和) となる。
（一般の場合で、出現確率1、非出現確率0の出来事のオッズは、無限大で1より大きいと考える。） 

具体的手順は、オッズを逆順に<math>f(n)/(1-f(n))</math>、<math>f(n-1)/(1-f(n-1))</math>、...と計算しながら、足し算して行き、はじめて和が1以上になったところで ''s'' が求まる。

== 例題 ==
10人の歩行者が独立に目の前を一人ずつ順番に通る。歩行者は奇数日生まれか偶数日生まれである。奇数日の人の割合は186/365=0.51、偶数日の人の割合は179/365=0.49とする。1番目から10番目の歩行者で、最後の偶数日生まれの人の判定問題をオッズ法を使って解くと次のようになる。

偶数日生まれの人のオッズは出現順番とは無関係に(0.49)/(0.51)である。 

10番目の人のオッズ <math>(0.49)/(0.51)=0.96 < 1 </math>

9番目と10番目の人のオッズの和 <math>(0.49)/(0.51) + (0.49)/(0.51) = 1.92 > 1</math>

これで　<math>s=9</math>　とわかる。したがって最適な判定法は、1番目から8番目の人は無視して、9番目以降で最初の偶数日生まれの人を最後の偶数日生まれの人として選べばよい。 

正解確率=(0.51)(0.51)((0.49)/(0.51) + (0.49)/(0.51)) = (0.49)(0.51) + (0.49)(0.51) = 0.4998 

この正解確率は、(9人目偶数日･10人目奇数日 または 9人目奇数日･10人目偶数日)の確率と一致している。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

{{DEFAULTSORT:おつすほう}}
[[Category:数学に関する記事]]
[[Category:数学の問題]]
[[Category:最適化アルゴリズムとメソッド]]