#freeze
*賭けの定理 ：Odds-theorem [#e9fa3b27]
ベルヌーイ過程に伴う最適停止問題である。
-n 個の独立事象E{i} , 1=l～n があり、意思決定者はE(1),E{2},・・・,E{n}を逐次観察する。E{i} はi 回目の試行に伴う事象で、2 つの結果「＋up：表」か「ーdown；裏」のどちらかを表す。簡単のためにE(i)が表の時は、E{i} が裏の時は、I{i}=0 と定義する。従って、意思決定者はI{1},I{2},・・・,I_{n}を逐次観察することになる。
ここでｋ番目の観測のみ、関心があるとする。ここで、ｋ番目の事象に面白い成果が得られる確率を考える。
 p(k)=Prob（Ik=1) 
さらに、
 q(k)=1-P(k) r(k)=p(k)/q(k) 
とする。このとき、r(k)は、k番目の事象のオッズ比(dds ratio)を表わす

ｋ番目のイベントが良ければ（面白い成果が得られれば）終了するとしよう。

--オッズとは、ある事象の起こる確率をpとして、p/（1−p）の値をいう。確率論のほかギャンブルでも盛んに使われてきた数値である。


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.

-一般化している。「＋up：表」とは、前回よりも良い人現れる事象や、株式やルーレットで賭けに勝つ(コインを入手する）事象などとして良い。

*オッズの計算とは　odds-algorithm [#m41a0a25]

オッズのアルゴリズムは、後ろ側からオッズ比を合計する。
 Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s)
この合計が、後ろ側から初めて１以上になるまで合計する。S回目に初めて１になったとしよう。
もし１に達しない場合は、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
 １．ｓ　, the stopping threshold 
 ２． 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 [#p092f276]
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.

*オッズ戦略は最適である：賭けの定理 [#z62aceeb]
''最適戦略は、オッズ戦略である。：賭けの定理''
言いかえれば
 1.最適停止時期　s　は、Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s)が初めて１より大なる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. 

*賭けに勝つ確率の定式化 [#ee703342]

勝つ確率　pi=P(I{i}=1) とおくと賭けの定理(Bruss[l] の結果) は次のように述べ
られる。ただし、qi=1-pi,ri=pi/qi と定義する。
-最適停止ルール: 次式で正整数S
 S= sup[{rk+・・・+rn　>or＝１]　1<k<n
最適停止ルールは、最初のs-1 回の対象をパスし、S 以降　最初の成功でストップすることである。
ここでは、最後から計算して、オッズ比rkの合計が1以上であるsを最適停止時期としている。
-勝つ確率: 最適停止ルールの下で、勝つ確率P(s)は次式で与えられる。
 P(s)= π(qi)・Σ(1/ri)　ただしπはi=ｓ～nの積、Σはi=ｓ～nのの和


-ある時刻まで対象をパスし、それ以降最初の成功で停止するルールのことを閾値ルールと呼ぶ。
-pi=1/i の場合、Odds –theorem はお見合い問題(marrige problem or secretary problem) の解を与える。この場合、成功とは相対順位1(見送った間の最良の人よりも良い人） の応募者の出現を意味し、最後の成功で停止することは最良の応募者(絶対順位1：ｎ人の中で1番良い人) の採用を意味する。

*最適停止ルールの証明 [#uadf050c]
Bruss[2] では、最後からちょうどm 番目の成功時点で停止したら勝ちである。そこで、ｎより前のmで成功しても停止するような、一般の停止問題を考える。

ダイナミックプログラミング　DP(dynamic Programming)を用いて問題を定式化する。
そのために下記の変数を定義する
 Vi(ｍ)　最初のi 回の対象をパスし、それ以降最適に振舞って勝つ確率
 gi(ｍ)　時刻i でI{1} =1 成功を観測した時、そこで停止して勝つ確率
このとき、次のDP 方程式が成立する。
 Vi-1(m) = pi・MAX[gi(m),Vi(m)]　+　qi・Vi(m)　i=1,・・・,n
 ただし　V0(n)=0　：初期条件
初期条件は、パスをしないので、相対順位を決める情報がないので、最後まで見送ってしまうことになる状況なので確率０とする。

解くためにはgi(ｍ) を最初に求めなければならない。

そこで、kからｎまで連続して失敗する確率を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(ｍ) は次補題１のように与えられる。
-補題１
 if i>n-m の場合は　　　　　　gi(ｍ)=1
 if i<n-m またはi=n-mの場合　gi(ｍ)=Qi+1・Σ（Ri+1,j)　Σはj=0からm-1までの和
--補題１の証明。i>n-m の時は明らかである。それ以外の時、定義より
 gi(m)=P(Ni+1<m-1}= Σ　P{Ni+1=j}　Σはj=0からm-1の和　　　a式
と書けるので、P(Nk=j}=Qk・Rk,j　より
 gi(m)=　Σ　Qi+1・Ri+1,j　Σはj=0からm-1の和
 gi(m)=　Qi+1・Σ　Ri+1,j　Σはj=0からm-1の和
となる。QED

-補題２．gi(ｍ) は非減少関数である。
--補題2の証明：これは、Ni は明らかにiの非増加関数であり、Niよりも Ni+1が大または等しい。そこで　Niよりもm-1が大または等しければ、Ni+1よりもm-1が大または等しい。P{Ni　<= m-1}　<=　P{Ni+1　<= m-1}が成立する。したがって　上のa式より　gi-1(m)よりもGi(m)が大きいは等しい。DP方程式より
 Vi-1(m) = pi・Vi(m)　+　qi・Vi(m)=Vi(m)　i=1,・・・,n
が成立するので、Vi(m)はiに関して非減少関数である。最適停止ルールは閾値ルールになる。

-定理　補題２より、最適停止ルールが閾値ルールとなることは分っているので、その閾値をs* とすると、s*において、勝つ確率は次式で与えられる。
 Vi(m)＝Qs*・Σ　Rs*,j　　　Σはj=１からmの和
--最適停止ルールが閾値ルールとなることは分っているので、その閾値をS* とすると次式で与えられる。
 s*＝inf[i;　Gi(m)>=Vi(m)　]
i>S*-１またはi=S*-1の時、Vi(m) は時刻i+1 以降の成功の出現個数が1 以上、min(m, n-i)
以下である確率に他ならない。従って P(Nk=j}=Qk・Rk,j より
 Vi(m)=P[1<or= Ni+1 <or=}min(m, n-i) ]
 　　 =Σ　P(Ni+1=j)　　　Σはj=1からmin(m, n-i)までの総和
      =Qi+1・ΣRi+1,j　Σはj=1からmin(m, n-i)までの総和
である。
したがって、S*の式は補題1のGi(m)の式より
 S*=inf[i :Qi+1・ΣRi+1,j >or= Qi+1・ΣRi+1,j ]
 左のΣはj=0からm-1の和、右のΣはj=1からmの和
   =inf[i : 1 >or= ΣRi+1,m ]
   =inf[i : ΣRi,m >or=1]
となるので、最適ルールは閾値s{*} の閾値ルールとなることが示された。
一方、勝つ確率はs*は n-m 以下であるので、Vi(m)=Qi+1・ΣRi+1,j　Σはj=1からmin(m, n-i)までの総和　より
 　　V0(m)=Vs*-1(m)
     　　=Qs*・ΣRs*,j　Σはj=1~m
となるので　s*において、勝つ確率は定理の式で与えられることが示された。　QED

*お見合い問題(秘書問題の定理：Pi=1/i　の場合 [#v6842c78]
最適停止ルール: n-->無限大 のとき、
 S*/n-->t*=EXP[-(m!)^(1/m)]
勝つ確率　：n-->無限大 のとき
　V0(m)＝t*・Σ　｛[(m!)^(1/m)]^k｝/k!　Σはk=1~mの和
で与えられる。
-[証明]：pi=1/i,qi=1-pi,より　ri=1/(i-1)である。
 Rj,m　＝ Σ　(ri1・ri2・・・・・rim)　j<i1<i2<・・・<im<n
       ＝ Σ　(1/(i1-1))・(1/(i2-1))・・・・(1/(im-1))　j<i1<i2<・・・<im<n
となるので、xj=ij/n,t=j/nとすると、n-->無限大では、上のRj,mは次の積分Rm(t)で近似できる。
 Rm(t)=∬・・∬　(1/x1)dx1・(1/x2)dx2・・・・(1/xm)dxm
 積分区間は、順にt->1,x1->1,・・・,xm->1　である。
そこで
 Rm(t)=[-log(t)^m]/m!
に近ずく。t*はRm(t)=1の根であるので、t*=EXP[-(m!)^(1/m)]が証明された。
次に、勝つ確率は
 Vi(m)＝Qs*・Σ　Rs*,k 　Σはk=1~mの和
       ＝(s*-1)/n　・Σ　Rs*,k 　Σはk=1~mの和
n-->無限大では、次式で近似できる。
 t*・Σ　Rk(t*) Σはk=1~mの和
 =t*・Σ[-log(t*)^m]/m!  Σはk=1~mの和
 =t*・Σ｛[(m!)^(1/m)]^k｝/k!　Σはk=1~mの和

*お見合い問題の漸近特性：非定常ポアソン過程：non–homogeneous　Poisson process [#sbc0134f]
ポアソン過程のパラメータλがtの関数の場合、非定常ポアソン過程とよぶ。
-今時間区間(0,1) をn ケの等間隔に分割し、k 番目の応募者が時刻k/n, 1<k< nに出現するもの
とする。
-Presman and Sonin[3] は、お見合い問題(秘書問題）において、このように設定することで、ｎを無限大とすると、時間区間(x, 1) の間に出現する成功の数(相対順位1 の応募者の数)N(x) はintensity rate λ(t)=1/t の非定常ポアソン分布に従うことを示した。

言いかえれば、次の積分公式をつかって
#ref(poisson.JPG)
N(x)=nとなる確率は
#ref(poisson2.JPG)
で表わされる。
閾値ルールが最適であることから、時刻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を求めると
#ref(poisson3.JPG)
となる。これを代入してfm(x)を求められる。
#ref(poisson4.JPG)
これは、お見合い問題の定理と一致している。
-''拒否がある場合''：お見合いや秘書の採用の場合、一定の確率で拒否されることもあるでしょう。申込が拒否される確率をβとするとき、この問題はλ(t)＝β/tとおいて、非定常ポアソン分布の計算を行えば、上記と同様に最適確率が求められる。やってみれば分かるが、
 拒否確率βの場合の最適停止時期；x*=exp｛-[(m!)^1/m］/β｝
となる。一方勝つ確率は、βに関係なく、拒否がない場合の確率と同じである。n　が無限大ですからこうなるのですが・・・、不思議でしょうか。


*参考文献 [#o98dc26b]
-[1] F. Thomas Bruss: Sum the Odds to One and Stop, Annals of Probability Vol. 28, 1384–1391 (2000). 
-[2] Bruss,F.T.(2000b), Selecting a sequence of last successes in independent trials, J.Appl.Prob.　37,389-399
-[3] Presman,E.$\mathrm{L}$,and Sonin,I.M.(1972), The best choice problem for a random number of objects,TheoryProbab.Appl. 17,657-668
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS