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 1/2. What is the expected running time of your algorithm as a function of p?
Answer
von Neumann 曾經對這個問題提出解法，主要是利用對稱性。可以參考這份文件。
主要的想法是這樣子的：我們擲銅板兩次，銅板丟出{HT}和{TH}的機率都是 $p(1-p)$ ，所以如果我們讓銅板丟出{HT}當作H，而丟出{TH}當作T，如果丟出{HH}或{TT}的話就再重新投擲兩次。這樣子的話我們就可以用這個 biased 的銅板來模擬 unbiased 的銅板。
接下來我們來關心一下期望值的問題:
所以平均我們要丟 $$\frac{1}{p(1 - p)}$$ 次銅板才可以成功的完成一回。
算這個期望值有另外一個較簡單的方法：
只丟兩次就模擬成功的機率是 $e = 2p(1 - p)$ ，而如果不成功的話，就等於丟的那兩次不算再重新丟兩次，假設期望值是丟 $t$ 次的話，那
$$t = e \times 2 + (1 - e) \times (2 + t)$$
$$ \Rightarrow t = 2/e = \frac{1}{p(1 - p)}$$
沒有留言:
張貼留言