Generating a random variable from a Biased Coin

Assume I want to generate a realization of a random variable $X$ with discrete distribution $F_X$. So I know the support of that random variable, but I don't know the distribution. However, if I call a value from the support, someone will tell me probability of that value according to $F_X$.

So in this case, you could call all the values from the support sequentially, then you could know the full distribution $F_X$, then you can use many methods to generate the realization of this random variable. However, I am considering the following procedure, I am not sure whether this procedure will let me generate the realization of $X$:

I first uniformly make a draw ($x$) from the support, then I will be told the probability of that specific value I draw from the support. Let's call this probability $p_x$. Then I flip a biased coin with Head probability $p_x$. If it really turns out to be head, then this value $x$ is generated from distribution $F_X$.

I am not sure whether the above claim is correct or not. Can some one prove it or disprove it mathematically?

Also, what if the biased coin does not turn up to be head? then what should I do? Should I redraw uniformly from the support, then repeat this procedure?

1 Answer

Your process will return $x$ with the proper probability. Now you need to generate all the other possible values with their proper probability. A way in the spirit of your question is to draw a different possible value $y$ and the a priori probability of $y$, $p_y$, so you exclude $x$ from the support for this draw. What you want is the probability of $y$ given that the variable is not $x$, so you want to accept $y$ with probability $\frac {p_y}{1-p_x}$, and you can flip a coin with this probability of heads. If you get heads, return $y$ and you are done. If not, you are still looking. Draw another possible value $z$ from the support except $x,y$ and you want to accept it with probability $\frac {p_z}{1-p_x-p_y}$. As your distribution is discrete, this will terminate within the number of steps equal to the number of possible values. You can even stop one before that, because if you have ruled out all the choices but one, the last choice is it.

• If I want to just generate a series of realizations of $X$ using this method, could I just do the following: uniformly draw and $x$, then I got $p_x$, then I flip this biased coin with H probability being $p_x$. Then if it turns out to be H, I record what I have drawn, which is $x$ and this is one realization of $X$. What if in this flip it turns out to be T, then should keep on flip this coin, until I get an H, or should I redraw a uniform sample $y$ from the support and get $p_y$, then flip a biased coin with H probability being $p_y$? – KevinKim Dec 8 '16 at 22:27
• No, as I said you should draw a new sample from the support less $x$ to get $y$ and $p_y$, then flip a new coin, but the probability of heads is not $p_y$ but $\frac {p_y}{1-p_x}$ The whole procedure above just gets you one realization of $X$. Repeat it as many times as you want realizations. You keep flipping until you get heads, which gives you the realization. When you get tails you don't get one, you keep going. I have edited a bit to make this clearer – Ross Millikan Dec 8 '16 at 22:31