賭けの定理 :Odds-theorem †ベルヌーイ過程に伴う最適停止問題である。
k番目のイベントが良ければ(面白い成果が得られれば)終了するとしよう。
Consider a sequence of n independent events. Associate with this sequence another sequence I1,I2,・・・・,In with values 1 or 0. Here Ik=1 stands for the event that the kth observation is interesting (as defined by the decision maker), and Ik=0 for non-interesting. Let p(k)=Prob(Ik=1) be the probability that the kth event is interesting. Further let q(k)=1-P(k) and r(k)=p(k)/q(k). Note that r(k) represents the odds of the kth event turning out to be interesting, explaining the name of the odds-algorithm.
オッズの計算とは odds-algorithm †オッズのアルゴリズムは、後ろ側からオッズ比を合計する。 Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s) この合計が、後ろ側から初めて1以上になるまで合計する。S回目に初めて1になったとしよう。 もし1に達しない場合は、S=1として、その時点で下記の値を計算する Qs=q(n)・q(n-1)・・・・q(s) 計算のアウトプットは、下記の成功確率Wsと停止時期sである。 成功確率 Ws=Qs・Rs 停止時期 s これを後ろ側から、計算することで、停止時期を決める。 このように、オッズを計算して、成功確率と停止時期を決めることをオッズ戦略と呼ぶ。 The odds-algorithm sums up the odds in reverse order until this sum reaches or exceeds the value 1 for the first time. If this happens at index s, it saves s and the corresponding sum Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s). If the sum of the odds does not reach 1, it sets s = 1. At the same time it computes Qn=q(n)・q(n-1)・・・・q(s). The output is 1.s , the stopping threshold 2. Ws=Qs・Rs ,the win probability The odds algorithm is due to F. T. Bruss (2000) who coined this name. It is also known under the name Bruss-algorithm (strategy). F. T. Bruss †Franz Thomas Bruss is a Belgian-German professor of mathematics at the Université Libre de Bruxelles. He is director of "Mathématiques Générales" and co-director of the probability chair. Bruss studied mathematics at the Universities Saarbrücken, Cambridge and Sheffield. In 1977 he obtained the Dr. rer. nat (Ph.D.) in Saarbrücken with his thesis Hinreichende Kriterien für das Aussterben von Modifizierten Verzweigungsprozessen (Sufficient conditions for the extinction of Branching Processes) under Professor Gerd Schmidt, and the legal Dr. en sciences of Belgium one year later. After a scientific career at the University of Namur he moved to the United States and taught at the University of California at Santa Barbara, University of Arizona, Tucson, and University of California at Los Angeles. In 1990 he returned to Europe and became Professor of Mathematics at Vesalius College,Vrije Universiteit Brussel, and in 1993 at the Université Libre de Bruxelles. He held visiting positions at the Universities of Zaire, University of Strathclyde, Antwerp, Purdue University, Namur, and the Université Catholique de Louvain. Bruss is a fellow of the Institute of Mathematical Statistics, a fellow of the Alexander von Humboldt Foundation and elected member of the Tönissteiner Kreis e.V. オッズ戦略は最適である:賭けの定理 †最適戦略は、オッズ戦略である。:賭けの定理 言いかえれば 1.最適停止時期 s は、Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s)が初めて1より大なるS 2.最適な勝つ確率は、上記のsに応じて Ws=Qs・Rs 3.勝利する確率は 少なくとも1/e=0.378・・・ であり、nが大きいとこれに近ずく。 The Odds-theorem states that The odds-strategy is optimal, that is, it maximizes the probability of stopping on the last 1. The win probability of the odds-strategy equals Ws=Qs・Rs If Rs>1 or Rs=1, the win probability W is always at least 1/e=0.378・・・, and this lower bound is best possible. 賭けに勝つ確率の定式化 †勝つ確率 pi=P(I{i}=1) とおくと賭けの定理(Bruss[l] の結果) は次のように述べ られる。ただし、qi=1-pi,ri=pi/qi と定義する。
最適停止ルールの証明 †Bruss[2] では、最後からちょうどm 番目の成功時点で停止したら勝ちである。そこで、nより前のmで成功しても停止するような、一般の停止問題を考える。 ダイナミックプログラミング DP(dynamic Programming)を用いて問題を定式化する。 そのために下記の変数を定義する Vi(m) 最初のi 回の対象をパスし、それ以降最適に振舞って勝つ確率 gi(m) 時刻i でI{1} =1 成功を観測した時、そこで停止して勝つ確率 このとき、次のDP 方程式が成立する。 Vi-1(m) = pi・MAX[gi(m),Vi(m)] + qi・Vi(m) i=1,・・・,n ただし V0(n)=0 :初期条件 初期条件は、パスをしないので、相対順位を決める情報がないので、最後まで見送ってしまうことになる状況なので確率0とする。 解くためにはgi(m) を最初に求めなければならない。 そこで、kからnまで連続して失敗する確率をQkとする。 Qk=π(qi)=qk・qk+1・・・・qn またNk は時刻k 以降に出現する成功の数表わすとする。 Nk=Ik+Ik+1+・・・・+In また Rk,jをつぎのように定義する Rk,j= Σ (ri1・ri2・・・・・rij) K<i1<i2<・・・<ij<n Rk,0=1 Bruss[2] より、次の関係が成り立つ。 P(Nk=j}=Qk・Rk,j この時、gi(m) は次補題1のように与えられる。
お見合い問題(秘書問題の定理:Pi=1/i の場合 †最適停止ルール: n-->無限大 のとき、 S*/n-->t*=EXP[-(m!)^(1/m)] 勝つ確率 :n-->無限大 のとき V0(m)=t*・Σ {[(m!)^(1/m)]^k}/k! Σはk=1~mの和 で与えられる。
お見合い問題の漸近特性:非定常ポアソン過程:non–homogeneous Poisson process †ポアソン過程のパラメータλがtの関数の場合、非定常ポアソン過程とよぶ。
言いかえれば、次の積分公式をつかって N(x)=nとなる確率は で表わされる。 閾値ルールが最適であることから、時刻x 以降の成功の出現個数がl 以上m 以下である 確率をfm(x) とし、fm(x) の最大値を実現するxを求めれば最適な停止時期が得られる。 fm(x)=P(1<N(x)<m) =Σ [x(-logx)^n/n1] Σはn=1~mの和 これを微分すると f'm(x)=(-logx)^m/m! -1 これを零とおいて、極致を与える最適なxを求めると となる。これを代入してfm(x)を求められる。 これは、お見合い問題の定理と一致している。
参考文献 †
|