Pergunta

Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I write a Las Vegas algorithm (called GenUnbiasedBit) that returns 1 or 0 with equal (nonzero) probability, using calls from GenBiasedBit as a source of randomness? I'm not really sure how to approach this problem. Since 1 and 0 must be generated with equal chance, I'm assuming they must both have a 50/50 chance of being selected. Since this is a Las Vegas algorithm, I'm not sure how to guarantee that its output is correct, if we don't know the probability of GenBiasedBit generating a 1 or 0.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top