# Is it possible to flip an unbalanced coin in a balanced manner?

Say, I have a coin and the up-face is two times heavy than the down-face. If I flip the coin as usual, the probability of face-down is two times of that of face-up. Now, if I make the following agreement: only if two successive face-down occurs, I output "face-down"; otherwise, I always output "face-up". By doing so, is the output sequence balanced?

More in general, say I have a sampling algorithm that output i from the space S with probaibility p(i). Now, if I want a new sampling algorithm that sample i from S in a random and uniform manner, i.e., selecting i from S with exact probability 1/|S|, how can I do?

• Are you willing to specify a tolerance $\epsilon$ and accept a solution where the probability of selecting $i$ is within $\epsilon$ of $1/|S|$? – Brian Borchers Jan 20 '17 at 4:53
• It is ok! But I want to tolerance is negligible. – Licheng Wang Jan 20 '17 at 5:22
• is $p(i)$ unknown to you or do you know it? Momo's answer below deals with the case where $p(i)$ is unknown and you want to produce 0-1 outputs that have probability 1/2. – Brian Borchers Jan 20 '17 at 5:49
• See also this question, which deals with a different problem in which the random inputs 0 or 1 with probability 1/2, but the output has $|S|=3$. math.stackexchange.com/questions/2356/… – Brian Borchers Jan 20 '17 at 5:50
• In my question, p(i) is known. – Licheng Wang Jan 20 '17 at 6:09

The way you do for the coin is that you flip twice, and reject the flips if outputs are identical ($HH$ or $TT$). When you get two different outputs ($HT$ or $TH$), then you output for example: $h$ if you have $HT$ and $t$ if you have $TH$. It is easy to see that the probability for outputting $h$ and $t$ are both equal to $1/2$