Wednesday, August 12, 2015

derive an unbiased function given a biased one

For f'(),
p(0) = 0.4
p(1) = 0.6

Derive f() such that
p(0) = 0.5
p(1) = 0.5
// probabilities
p(0,0) = 0.4 * 0.4 = 0.16 // discard
p(1,1) = 0.6 * 0.6 = 0.36 // discard
p(0,1) = 0.4 * 0.6 = 0.24 // pick
p(1,0) = 0.6 * 0.4 = 0.24 // pick
//f() is non-deterministic
f():
    while true:
        t = f'()
        if t != f'():
            return t

No comments:

Post a Comment