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 的大作中提到】
: ... 的意思是，无穷长。。
|
