コイントスで確率1/3の事象を作る話だったはずの何か
-
- いいね！1
Akso de la Malbono
@Cryolite
う，ぐ，ぎょ……疑問2はすごい簡単だったっていうか rejection sampling で reject が確定した瞬間に終われば良いのか……．
2013-07-01 16:18:32
Masahiro Kasahara
@mkasahara
@Cryolite @chunjp 疑問その1は「存在しない」のが答えじゃないですかね。例えばp=1/10だとアルゴリズムが作れない。
2013-07-01 16:21:21
Masahiro Kasahara
@mkasahara
@Cryolite @chunjp 有限時間で停止するので、乱数はnビット(有限)しか使えない。そうすると等確率の2^n個の入力が考えられるけど、各入力にたいして決定的(deterministic)に出力がyes/noで出るならその確率は2^-n刻みにしかできない。QED
2013-07-01 16:23:14
のの＠すべてを痴る者
@nono_ria
float a,r,p;//pに求める確率を格納 r=1.0; a=0.0; bool c=0; while(a<p&&a+r>p){ r*=0.5; c=0; if(rand()%2==1){ a+=r; c=1; } } c==0で真、c==1で偽。
2013-07-01 16:27:07
Akso de la Malbono
@Cryolite
読み返してたら早い段階で実数の場合の回答いただいていたのに気付いてなかったことに気が付きました……すいません……orz
2013-07-01 18:56:45
Tomoaki Nishiyama
@NishiyamT
@mkasahara @Cryolite @chunjp pは有理数なのでn/m(n,mは整数)と表される。（多倍長演算で）m*[大きな素数]を法とする線形合同法を構成する。で、pに独立な時間とはいかないけど、pに対してある有限時間でできるアルゴリズムはできるのでは。
2013-07-01 19:19:51
Akso de la Malbono
@Cryolite
independent tosses of a fair coin だけを乱数源とする，という制約はどの程度きつい（妥当）なんだろうか……．最初に個人的に直感で予想してたよりはだいぶ強力だったけれど．
2013-07-01 19:30:42
Tomoaki Nishiyama
@NishiyamT
@chunjp @mkasahara なるほど、coin toss 条件の要求がついてたんですね。納得。約分後にmが2以外の素因数持つときは有限時間で決定できないということですね。
2013-07-01 20:08:07
Akso de la Malbono
@Cryolite
完全に蛇足ですけれど，有理数 l/m に対して 2^n >= lm となる最小の n を取って， n 回のコイントスでできる長さ n の 2^n 個の「表」「裏」の列のうち，適当な lm 個が出る中でその中の l^2 個が出る事象が確率 l/m を持つのでそれ使う……
2013-07-01 23:47:25
Akso de la Malbono
@Cryolite
……というのを元々考えていて，要するに https://t.co/bXqsJ8IAns の一般化で，条件付き確率に除算が出てくることを使っているわけですけれど，まー，多分どうでもよくなった感．
2013-07-01 23:52:15