意思決定理論 において、オッズアルゴリズム （またはブルースアルゴリズム）は、 最適停止 問題の領域に属する一連の問題に対する最適戦略を計算するための数学的手法である。これらの問題の解はオッズ戦略 から導き出され、オッズ戦略の重要性は、後述するようにその最適性にある。
オッズアルゴリズムは、最終成功 問題と呼ばれる一連の問題に適用されます 。正式には、これらの問題の目的は、連続して観測される一連の独立事象において、特定の基準を満たす最後の事象（「特定事象」）を特定する確率を最大化することです。この特定は、観測時に行われなければなりません。先行する観測を再検討することは許可されていません。通常、特定事象は、意思決定者が明確に定義された行動をとるために「停止」するという観点から真に関心のある事象として定義されます。このような問題は、さまざまな状況で発生します。
例 2つの異なる状況は、最後の特定のイベントで停止する確率を最大化することへの関心を示す例である。
ある車が最高額入札者（最良の「オファー」）に販売される広告が出されているとします。n {\displaystyle n} 「興味深い」 と定義し、先行するすべての入札よりも優れている場合は 1、そうでない場合は 0 とコード化します。入札は0 と 1 のランダムなシーケンス を形成します。売り手は 1 のみに興味を持ち、連続する 1 が最後になるかもしれないことを恐れるかもしれません。定義から、最後の 1 が最高入札であることがわかります。したがって、最後の 1 で売れる確率を最大化することは、最も良い価格 で売れる確率を最大化することと同じです。 医師は、特別な治療法を用いて、治療が成功した場合はコード1を、そうでない場合は0を使用する。医師は一連の患者を治療する。n {\displaystyle n} 「人道的利用」を 参照。）
定義 一連のn {\displaystyle n} 独立事象 。このシーケンスに別の独立事象のシーケンスを関連付けます。私 1 、 私 2 、 … 、 私 n {\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}} 私 k = 1 {\displaystyle \,I_{k}=1} 私 k = 0 {\displaystyle \,I_{k}=0} 私 1 、 私 2 、 … 、 私 n {\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}
させてp k = P （ 私 k = 1 ） {\displaystyle \,p_{k}=P(\,I_{k}\,=1)} q k = 1 − p k {\displaystyle \,q_{k}=\,1-p_{k}} r k = p k / q k {\displaystyle \,r_{k}=p_{k}/q_{k}} r k \displaystyle \,r_{k}} これは、k番目のイベントが興味深いものになる確率 を表しており、オッズアルゴリズムの名前の由来となっている。
アルゴリズム的手順 オッズアルゴリズムはオッズを逆順に合計します
r n + r n − 1 + r n − 2 + ⋯ 、 {\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,} この合計が初めて1に達するか、または1を超えるまで続きます。インデックスs でこれが起こった場合、s と対応する合計が保存されます。
R s = r n + r n − 1 + r n − 2 + ⋯ + r s 。 {\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,} オッズの合計が 1 に達しない場合は、s = 1 と設定します。同時に、
Q s = q n q n − 1 ⋯ q s 。 {\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,} 出力は
s {\displaystyle \,s} w = Q s R s {\displaystyle \,w=Q_{s}R_{s}}
オッズ戦略 オッズ戦略とは、イベントを一つずつ観察し、インデックスs 以降で最初の興味深いイベント（存在する場合）で停止するというルールです。ここで、s は出力aの停止閾値です。
オッズ戦略、ひいてはオッズアルゴリズムの重要性は、以下のオッズ定理にある。
オッズ定理 オッズ定理によれば、
オッズ戦略は最適で あり、つまり、最後の1で停止する確率を最大化します。 オッズ戦略の勝率は w = Q s R s {\displaystyle w=Q_{s}R_{s}} もしR s ≥ 1 {\displaystyle R_{s}\geq 1} w {\displaystyle w} 1/ e であり、この下限は可能な限り最良 です。
特徴 オッズアルゴリズムは、最適な戦略 と最適な勝率を 同時に計算します。また、オッズアルゴリズムの演算回数はnに対して（準）線形です。したがって、すべてのシーケンスに対してこれより高速なアルゴリズムは存在し得ないため、オッズアルゴリズムはアルゴリズムとして最適であると言えます。
情報源 2000年にブリュスが オッズアルゴリズムを考案し、その名を冠した。これはブリュスアルゴリズム（戦略）としても知られている。ウェブ上では無料の実装例を見つけることができる。
アプリケーション アイコンの高さが望ましさを示す秘書問題の3つの事例： 探索セットが小さすぎると、最良の候補(*)が見つかる前に最適ではない候補が選択されてしまいます。 理想的なセットは最良のものを特定する。 候補が多すぎる場合、最良の候補も含まれている場合は、最後の候補が選択されます。 応用範囲は、臨床試験 における医学的な問題から、販売上の問題、秘書業務の問題 、ポートフォリオ 選択、（一方通行の）検索戦略、軌道問題、駐車問題 、オンライン保守の問題など多岐にわたる。
同様の考え方で、ポアソン過程 のような独立増分 を持つ連続時間到着過程に対するオッズ定理が存在する（Bruss 2000 ）。場合によっては、オッズが事前に必ずしもわかっているとは限らない（上記の例 2 のように）ため、オッズ アルゴリズムを直接適用することはできない。この場合、各ステップでオッズの逐次推定値 を使用する。これは、未知のパラメータの数が観測数 n に比べて大きくない場合に意味がある。ただし、最適性の問題はより複雑になり、追加の研究が必要となる。オッズ アルゴリズムの一般化では、停止しなかった場合や誤った停止に対する報酬を異にしたり、独立性の仮定をより弱い仮定に置き換えたりすることができる（ Ferguson 2008 ） 。
バリエーション Bruss & Paindaveine 2000 は 最後の選択の問題について議論したk {\displaystyle k}
玉木(2010)は、 最後のいずれかの時点で停止するという問題を扱う乗法オッズ定理を証明した。ℓ {\displaystyle \ell } 松井と 安野（2014） によって得られている。
松井と 安野は2017年に 選択の問題について議論した。k {\displaystyle k} ℓ {\displaystyle \ell } ℓ = k = 1 、 {\displaystyle \ell =k=1,} ℓ = k ≥ 1 、 {\displaystyle \ell =k\geq 1,} この問題は、 Bruss & Paindaveine 2000 の問題と同等である 。Tamaki 2010 で議論されている問題は、次のように設定することで得られる。ℓ ≥ k = 1. {\displaystyle \ell \geq k=1.}
多肢選択問題 プレイヤーは許可されていますr {\displaystyle r} ギルバートと モステラー（1966） がケースについて議論しました。r = 2 、 3 、 4 {\displaystyle r=2,3,4} r = 2 、 3 {\displaystyle r=2,3} この問題については、Ano, Kakinuma & Miyoshi 2010 で議論されている。オッズ問題のその他のケースについては、Matsui & Ano 2016 を参照のこと。
この問題に対する最適な戦略は、一連の閾値によって定義される戦略のクラスに属する。（ 1 1 、 1 2 、 。 。 。 、 1 r ） {\displaystyle (a_{1},a_{2},...,a_{r})} 1 1 > 1 2 > ⋯ > 1 r {\displaystyle a_{1}>a_{2}>\cdots >a_{r}}
具体的には、次のような状況を想像してみてください。r {\displaystyle r} 1 {\displaystyle 1} r {\displaystyle r} r {\displaystyle r} 私 {\displaystyle i} 1 {\displaystyle 1} 1 私 {\displaystyle a_{i}}
いつr = 2 {\displaystyle r=2} Ano、Kakinuma 、 Miyoshi 2010は 、勝率の厳密な下限が次のようになることを示した。e − 1 + e − 3 2 。 {\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.} r {\displaystyle r} 松井と 安野は2016年に 、勝率の厳密な下限は、k回の試行のみで上位k人の候補者を選ばなければならない秘書問題の変種 の勝率であることを証明した。
いつr = 3 、 4 、 5 {\displaystyle r=3,4,5} e − 1 + e − 3 2 + e − 47 24 {\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}} e − 1 + e − 3 2 + e − 47 24 + e − 2761 1152 {\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}} e − 1 + e − 3 2 + e − 47 24 + e − 2761 1152 + e − 4162637 1474560 、 {\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},}
さらなる数値ケースについてはr = 6 、 。 。 。 、 10 {\displaystyle r=6,...,10} Matsui & Ano 2016 を参照してください。
参考文献 安野和也、柿沼博、三好直子（2010）。「複数選択機会を伴うオッズ定理」応用確率論47 （4 ）：1093–1104。doi ： 10.1239 / jap / 1294170522。S2CID 17598431 。 Bruss, F. Thomas (2000). 「オッズを1に合計して停止」 . The Annals of Probability . 28 (3). Institute of Mathematical Statistics: 1384–139 1. doi : 10.1214/aop/1019160340 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/182735 . ISSN 0091-1798 . 「最適停止のオッズ定理の境界に関する注記」、確率論年報 ～ 1862ページ、（2003年）。 「正しい決断の技術」、欧州数学会 ニュースレター 、第62号、14-20ページ、 （2005年）。 T・S・ファーガソン ：（2008年、未発表）Bruss, FT; Paindaveine, D. (2000). 「独立試行における最後の成功のシーケンスの選択」(PDF) . Journal of Applied Probability . 37 (2): 389– 399. doi : 10.1239/jap/1014842544 . Gilbert, J; Mosteller, F (1966). 「数列の最大値の認識」. Journal of the American Statistical Association . 61 (313): 35–73 . doi : 10.2307/2283044 . JSTOR 2283044 . 松井 隆、安野 健（2014）。「最適停止の乗法オッズ定理の下限に関する注記」。応用確率論ジャーナル 。51 （ 3）：885–889。doi ： 10.1239/ jap / 1409932681 。 松井 哲也、安野 健一 (2016). 「複数停止を伴う Bruss のオッズ問題の下限」.オペレーションズ リサーチの数学 41 (2): 700–714 . arXiv : 1204.5537 . doi : 10.1287/moor.2015.0748 . S2CID 31778896 . 松井 隆、安野 健（2017）。「オッズと1の対称多項式の比率を比較して停止する」。応用確率ジャーナル 。54 ： 12–22。doi ：10.1017 / jpr.2016.83。S2CID 41639968 。 Shoo-Ren Hsiao および Jiing-Ru. Yang: "マルコフ依存試行における最後の成功の選択", Journal of Applied Probability – 281、(2002)。 玉木、M（2010）。「乗法オッズを1に合計して停止」。応用確率ジャーナル 。47 （ 3）：761–777。doi ： 10.1239/ jap / 1285335408。S2CID 32236265 。 玉木光志：「軌道上の最適停止と投票問題」、応用確率論ジャーナル 946-959 ページ（2001年）。 E. Thomas、E. Levrat、B. Iung: 「メンテナンス予防のためのブリュスのアルゴリズムの貢献」、Sciences et Technologies de l'automation
外部リンク Bruss Algorithmus http://www.p-roesler.de/odds.html 
