Browsed by
Tag: 概率

各以1/2的概率输出0和1

各以1/2的概率输出0和1

在看CLRS中的第五章,发现课后的这道习题非常有意思。 题目:Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 – p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability...

Read More Read More