賭けの定理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
*賭けの定理 :Odds-theorem [#e9fa3b27]
ベルヌーイ過程に伴う最適停止問題である。
-n 個の独立事象E{i} , 1=l~n があり、意思決定者はE(1),E{2...
ここでk番目の観測のみ、関心があるとする。ここで、k番目...
p(k)=Prob(Ik=1)
さらに、
q(k)=1-P(k) r(k)=p(k)/q(k)
とする。このとき、r(k)は、k番目の事象のオッズ比(dds ratio...
k番目のイベントが良ければ(面白い成果が得られれば)終了...
--オッズとは、ある事象の起こる確率をpとして、p/(1−p)の...
Consider a sequence of n independent events. Associate wi...
I1,I2,・・・・,In
with values 1 or 0. Here Ik=1 stands for the event that t...
p(k)=Prob(Ik=1)
be the probability that the kth event is interesting. Fur...
-一般化している。「+up:表」とは、前回よりも良い人現れる...
*オッズの計算とは odds-algorithm [#m41a0a25]
オッズのアルゴリズムは、後ろ側からオッズ比を合計する。
Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s)
この合計が、後ろ側から初めて1以上になるまで合計する。S回...
もし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 unti...
If the sum of the odds does not reach 1, it sets s = 1. A...
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 coine...
*F. T. Bruss [#p092f276]
Franz Thomas Bruss is a Belgian-German professor of mathe...
Bruss studied mathematics at the Universities Saarbrücken...
Bruss is a fellow of the Institute of Mathematical Statis...
*オッズ戦略は最適である:賭けの定理 [#z62aceeb]
''最適戦略は、オッズ戦略である。:賭けの定理''
言いかえれば
1.最適停止時期 s は、Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(...
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 p...
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...
*賭けに勝つ確率の定式化 [#ee703342]
勝つ確率 pi=P(I{i}=1) とおくと賭けの定理(Bruss[l] の結果...
られる。ただし、qi=1-pi,ri=pi/qi と定義する。
-最適停止ルール: 次式で正整数S
S= sup[{rk+・・・+rn >or=1] 1<k<n
最適停止ルールは、最初のs-1 回の対象をパスし、S 以降 最...
ここでは、最後から計算して、オッズ比rkの合計が1以上である...
-勝つ確率: 最適停止ルールの下で、勝つ確率P(s)は次式で与え...
P(s)= π(qi)・Σ(1/ri) ただしπはi=s~nの積、Σはi=s~nの...
-ある時刻まで対象をパスし、それ以降最初の成功で停止するル...
-pi=1/i の場合、Odds –theorem はお見合い問題(marrige prob...
*最適停止ルールの証明 [#uadf050c]
Bruss[2] では、最後からちょうど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 :初期条件
初期条件は、パスをしないので、相対順位を決める情報がない...
解くためには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のように与えられる。
-補題1
if i>n-m の場合は gi(m)=1
if i<n-m またはi=n-mの場合 gi(m)=Qi+1・Σ(Ri+1,j) Σは...
--補題1の証明。i>n-m の時は明らかである。それ以外の時、...
gi(m)=P(Ni+1<m-1}= Σ P{Ni+1=j} Σはj=0からm-1の和 ...
と書けるので、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
-補題2.gi(m) は非減少関数である。
--補題2の証明:これは、Ni は明らかにiの非増加関数であり、...
Vi-1(m) = pi・Vi(m) + qi・Vi(m)=Vi(m) i=1,・・・,n
が成立するので、Vi(m)はiに関して非減少関数である。最適停...
-定理 補題2より、最適停止ルールが閾値ルールとなることは...
Vi(m)=Qs*・Σ Rs*,j Σはj=1からmの和
--最適停止ルールが閾値ルールとなることは分っているので、...
s*=inf[i; Gi(m)>=Vi(m) ]
i>S*-1またはi=S*-1の時、Vi(m) は時刻i+1 以降の成功の出現...
以下である確率に他ならない。従って 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+...
V0(m)=Vs*-1(m)
=Qs*・ΣRs*,j Σはj=1~m
となるので s*において、勝つ確率は定理の式で与えられるこ...
*お見合い問題(秘書問題の定理: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<...
となるので、xj=ij/n,t=j/nとすると、n-->無限大では、上のRj...
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–homogene...
ポアソン過程のパラメータλがtの関数の場合、非定常ポアソン...
-今時間区間(0,1) をn ケの等間隔に分割し、k 番目の応募者が...
とする。
-Presman and Sonin[3] は、お見合い問題(秘書問題)において...
言いかえれば、次の積分公式をつかって
#ref(poisson.JPG)
N(x)=nとなる確率は
#ref(poisson2.JPG)
で表わされる。
閾値ルールが最適であることから、時刻x 以降の成功の出現個...
確率を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)
これは、お見合い問題の定理と一致している。
-''拒否がある場合'':お見合いや秘書の採用の場合、一定の確...
拒否確率βの場合の最適停止時期;x*=exp{-[(m!)^1/m]/β}
となる。一方勝つ確率は、βに関係なく、拒否がない場合の確率...
*参考文献 [#o98dc26b]
-[1] F. Thomas Bruss: Sum the Odds to One and Stop, Annal...
-[2] Bruss,F.T.(2000b), Selecting a sequence of last succ...
-[3] Presman,E.$\mathrm{L}$,and Sonin,I.M.(1972), The bes...
終了行:
*賭けの定理 :Odds-theorem [#e9fa3b27]
ベルヌーイ過程に伴う最適停止問題である。
-n 個の独立事象E{i} , 1=l~n があり、意思決定者はE(1),E{2...
ここでk番目の観測のみ、関心があるとする。ここで、k番目...
p(k)=Prob(Ik=1)
さらに、
q(k)=1-P(k) r(k)=p(k)/q(k)
とする。このとき、r(k)は、k番目の事象のオッズ比(dds ratio...
k番目のイベントが良ければ(面白い成果が得られれば)終了...
--オッズとは、ある事象の起こる確率をpとして、p/(1−p)の...
Consider a sequence of n independent events. Associate wi...
I1,I2,・・・・,In
with values 1 or 0. Here Ik=1 stands for the event that t...
p(k)=Prob(Ik=1)
be the probability that the kth event is interesting. Fur...
-一般化している。「+up:表」とは、前回よりも良い人現れる...
*オッズの計算とは odds-algorithm [#m41a0a25]
オッズのアルゴリズムは、後ろ側からオッズ比を合計する。
Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(s)
この合計が、後ろ側から初めて1以上になるまで合計する。S回...
もし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 unti...
If the sum of the odds does not reach 1, it sets s = 1. A...
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 coine...
*F. T. Bruss [#p092f276]
Franz Thomas Bruss is a Belgian-German professor of mathe...
Bruss studied mathematics at the Universities Saarbrücken...
Bruss is a fellow of the Institute of Mathematical Statis...
*オッズ戦略は最適である:賭けの定理 [#z62aceeb]
''最適戦略は、オッズ戦略である。:賭けの定理''
言いかえれば
1.最適停止時期 s は、Rs=r(n)+r(n-1)+r(n-2)+・・・・+r(...
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 p...
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...
*賭けに勝つ確率の定式化 [#ee703342]
勝つ確率 pi=P(I{i}=1) とおくと賭けの定理(Bruss[l] の結果...
られる。ただし、qi=1-pi,ri=pi/qi と定義する。
-最適停止ルール: 次式で正整数S
S= sup[{rk+・・・+rn >or=1] 1<k<n
最適停止ルールは、最初のs-1 回の対象をパスし、S 以降 最...
ここでは、最後から計算して、オッズ比rkの合計が1以上である...
-勝つ確率: 最適停止ルールの下で、勝つ確率P(s)は次式で与え...
P(s)= π(qi)・Σ(1/ri) ただしπはi=s~nの積、Σはi=s~nの...
-ある時刻まで対象をパスし、それ以降最初の成功で停止するル...
-pi=1/i の場合、Odds –theorem はお見合い問題(marrige prob...
*最適停止ルールの証明 [#uadf050c]
Bruss[2] では、最後からちょうど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 :初期条件
初期条件は、パスをしないので、相対順位を決める情報がない...
解くためには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のように与えられる。
-補題1
if i>n-m の場合は gi(m)=1
if i<n-m またはi=n-mの場合 gi(m)=Qi+1・Σ(Ri+1,j) Σは...
--補題1の証明。i>n-m の時は明らかである。それ以外の時、...
gi(m)=P(Ni+1<m-1}= Σ P{Ni+1=j} Σはj=0からm-1の和 ...
と書けるので、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
-補題2.gi(m) は非減少関数である。
--補題2の証明:これは、Ni は明らかにiの非増加関数であり、...
Vi-1(m) = pi・Vi(m) + qi・Vi(m)=Vi(m) i=1,・・・,n
が成立するので、Vi(m)はiに関して非減少関数である。最適停...
-定理 補題2より、最適停止ルールが閾値ルールとなることは...
Vi(m)=Qs*・Σ Rs*,j Σはj=1からmの和
--最適停止ルールが閾値ルールとなることは分っているので、...
s*=inf[i; Gi(m)>=Vi(m) ]
i>S*-1またはi=S*-1の時、Vi(m) は時刻i+1 以降の成功の出現...
以下である確率に他ならない。従って 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+...
V0(m)=Vs*-1(m)
=Qs*・ΣRs*,j Σはj=1~m
となるので s*において、勝つ確率は定理の式で与えられるこ...
*お見合い問題(秘書問題の定理: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<...
となるので、xj=ij/n,t=j/nとすると、n-->無限大では、上のRj...
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–homogene...
ポアソン過程のパラメータλがtの関数の場合、非定常ポアソン...
-今時間区間(0,1) をn ケの等間隔に分割し、k 番目の応募者が...
とする。
-Presman and Sonin[3] は、お見合い問題(秘書問題)において...
言いかえれば、次の積分公式をつかって
#ref(poisson.JPG)
N(x)=nとなる確率は
#ref(poisson2.JPG)
で表わされる。
閾値ルールが最適であることから、時刻x 以降の成功の出現個...
確率を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)
これは、お見合い問題の定理と一致している。
-''拒否がある場合'':お見合いや秘書の採用の場合、一定の確...
拒否確率βの場合の最適停止時期;x*=exp{-[(m!)^1/m]/β}
となる。一方勝つ確率は、βに関係なく、拒否がない場合の確率...
*参考文献 [#o98dc26b]
-[1] F. Thomas Bruss: Sum the Odds to One and Stop, Annal...
-[2] Bruss,F.T.(2000b), Selecting a sequence of last succ...
-[3] Presman,E.$\mathrm{L}$,and Sonin,I.M.(1972), The bes...
ページ名: