e******r 发帖数: 220 | 1 Given a method called bias() that outputs a 1 with probability x and a 0
with probability (1-x), write a method called fair() that outputs a 1 with
probability 0.5 and a 0 with probability 0.5. We don't know what x is.
That is, how to coorect a bias coin to a fair coin?
In addition, comment on how long you think your method might take to run.
Thanks |
s*m 发帖数: 34 | 2 call bias()两次,如果是00,11,扔掉
如果是01, output 0; 10 output 1.
【在 e******r 的大作中提到】 : Given a method called bias() that outputs a 1 with probability x and a 0 : with probability (1-x), write a method called fair() that outputs a 1 with : probability 0.5 and a 0 with probability 0.5. We don't know what x is. : That is, how to coorect a bias coin to a fair coin? : In addition, comment on how long you think your method might take to run. : Thanks
|
T**********n 发帖数: 480 | 3 孙博牛鼻!
【在 s*m 的大作中提到】 : call bias()两次,如果是00,11,扔掉 : 如果是01, output 0; 10 output 1.
|
w*******g 发帖数: 9932 | 4 我觉得如果输出是00,或11, 应该call fair()
【在 T**********n 的大作中提到】 : 孙博牛鼻!
|
T**********n 发帖数: 480 | 5 有区别么?
死等到01/10不就是call fair么?
【在 w*******g 的大作中提到】 : 我觉得如果输出是00,或11, 应该call fair()
|
T**********n 发帖数: 480 | 6 对呀,如果真是极端情况那个bias以0.99999999999999999999的概率输出1
那效率低也没办法了
因为这个时候系统的输入除了了一串1之外没别的了
不可能加入什么扰动得到比一串1更多的信息,赫赫 |
y***u 发帖数: 101 | 7 The efficiency depends on the entropy contained in the coins,
the entropy is very low for very high or very low biases.
in fact I think sxm's method is asymptotically optimal
【在 T**********n 的大作中提到】 : 对呀,如果真是极端情况那个bias以0.99999999999999999999的概率输出1 : 那效率低也没办法了 : 因为这个时候系统的输入除了了一串1之外没别的了 : 不可能加入什么扰动得到比一串1更多的信息,赫赫
|
w*******g 发帖数: 9932 | 8 如果x 驱近于1, 那不要等白了头.
【在 T**********n 的大作中提到】 : 有区别么? : 死等到01/10不就是call fair么?
|
t*s 发帖数: 1504 | 9 只能等。。因为这种情况就相当于输入无意义。。。
【在 w*******g 的大作中提到】 : 如果x 驱近于1, 那不要等白了头.
|
c***a 发帖数: 655 | 10 有区别啊。P(00)=x*x, P(11)=(1-x)*(1-x)
不相等(除非x=0.5)
大家怎么看这个耍流氓的解法:
bool fair(){
static bool state=false;
return (state= !state);
}
hoho..
【在 T**********n 的大作中提到】 : 有区别么? : 死等到01/10不就是call fair么?
|
|
|
T**********n 发帖数: 480 | 11 老猫同学你这个是确定的输出啊
不过rand出来的也就比这个好一点而已,可是已经离人家题意太远了,赫赫赫
【在 c***a 的大作中提到】 : 有区别啊。P(00)=x*x, P(11)=(1-x)*(1-x) : 不相等(除非x=0.5) : 大家怎么看这个耍流氓的解法: : bool fair(){ : static bool state=false; : return (state= !state); : } : hoho..
|
w*******g 发帖数: 9932 | 12 不是已经有个fair() function了吗? 为什么不能用呢?
【在 t*s 的大作中提到】 : 只能等。。因为这种情况就相当于输入无意义。。。
|
T**********n 发帖数: 480 | 13 fair是要求你用bias来实现的亚
【在 w*******g 的大作中提到】 : 不是已经有个fair() function了吗? 为什么不能用呢?
|
t*s 发帖数: 1504 | 14 这个也太确定了点吧。。。
【在 T**********n 的大作中提到】 : 老猫同学你这个是确定的输出啊 : 不过rand出来的也就比这个好一点而已,可是已经离人家题意太远了,赫赫赫
|
R****r 发帖数: 227 | 15 bool fair(){
static bool state=false;
if (bias()) return (state= !state);
else return state;
}
haha
【在 T**********n 的大作中提到】 : fair是要求你用bias来实现的亚
|
t*s 发帖数: 1504 | 16 ...
【在 R****r 的大作中提到】 : bool fair(){ : static bool state=false; : if (bias()) return (state= !state); : else return state; : } : haha
|
s***t 发帖数: 195 | 17 this is not correct. your prior P(0) = 1 and P(1) = 0
and P(1 | 0) = P(0 | 1) = p, and P(0 | 0) = P(1 | 1) = (1-p).
therefore, you P(x_1 = 1) = p, and P(x_1 = 0) = (1-p), which is biased.
you need a properly unbiased initialization of the state.
【在 R****r 的大作中提到】 : bool fair(){ : static bool state=false; : if (bias()) return (state= !state); : else return state; : } : haha
|
R****r 发帖数: 227 | 18 blah blah..
bool fair() {
return
[[ fair() fair() fair() ... ]] > [[ fair() fair() fair() ... ]]
}
【在 s***t 的大作中提到】 : this is not correct. your prior P(0) = 1 and P(1) = 0 : and P(1 | 0) = P(0 | 1) = p, and P(0 | 0) = P(1 | 1) = (1-p). : therefore, you P(x_1 = 1) = p, and P(x_1 = 0) = (1-p), which is biased. : you need a properly unbiased initialization of the state.
|
t*s 发帖数: 1504 | 19 what if they are equal?
it's quite likely when bias() is very bias...:)
【在 R****r 的大作中提到】 : blah blah.. : bool fair() { : return : [[ fair() fair() fair() ... ]] > [[ fair() fair() fair() ... ]] : }
|
R****r 发帖数: 227 | 20 ... 的意思是,无穷长。。
【在 t*s 的大作中提到】 : what if they are equal? : it's quite likely when bias() is very bias...:)
|
t*s 发帖数: 1504 | 21 time complexity=o(infinity)?
【在 R****r 的大作中提到】 : ... 的意思是,无穷长。。
|