0
$\begingroup$

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?

$\endgroup$
7
  • $\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$ Commented Jan 20, 2017 at 4:53
  • $\begingroup$ It is ok! But I want to tolerance is negligible. $\endgroup$ Commented Jan 20, 2017 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$ Commented Jan 20, 2017 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$ Commented Jan 20, 2017 at 5:50
  • $\begingroup$ In my question, p(i) is known. $\endgroup$ Commented Jan 20, 2017 at 6:09

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It is a great suggestion! Thanks a lot! $\endgroup$ Commented Jan 20, 2017 at 5:25
  • $\begingroup$ This is a clever bit of von Neumannery, as so many things are. $\endgroup$ Commented Jan 20, 2017 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$ Commented Jan 20, 2017 at 7:49

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.