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?

  • $\begingroup$ Are you willing to specify a tolerance $\epsilon$ and accept a solution where the probability of selecting $i$ is within $\epsilon$ of $1/|S|$? $\endgroup$ – Brian Borchers Jan 20 '17 at 4:53
  • $\begingroup$ It is ok! But I want to tolerance is negligible. $\endgroup$ – Licheng Wang Jan 20 '17 at 5:22
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Jan 20 '17 at 5:49
  • $\begingroup$ 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/… $\endgroup$ – Brian Borchers Jan 20 '17 at 5:50
  • $\begingroup$ In my question, p(i) is known. $\endgroup$ – 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$

To generalize this, you have to use some information theory (calculate the bits of entropy of your biased die, generate a mapping and calculate its efficiency). You may take a look at this paper if you want the details.

  • $\begingroup$ It is a great suggestion! Thanks a lot! $\endgroup$ – Licheng Wang Jan 20 '17 at 5:25
  • $\begingroup$ This is a clever bit of von Neumannery, as so many things are. $\endgroup$ – Patrick Stevens Jan 20 '17 at 7:04
  • $\begingroup$ According to the paper suggested by Momo, p(i) is unknown but constant for all n. What if p(i) is known but variable according to different i? $\endgroup$ – Licheng Wang Jan 20 '17 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.