How to algorithmically simulate probabilistic distributions using other distributions
In this article, we explore (in short) how we can generate random numbers of any distribution if we have a corrupt toin coss generator (i.e. a random toin that produces 1 with (unknown) probability and 0 with (unknown) probability ).
So first of all, we convince ourselves that we can construct a fair coin tosser (i.e. 1 and 0 occur both with probability 0.5) from the above mentioned corrupt coin tosser.
Therefore, we do the following: We execute the corrupt coin tosser two times. Then there are four possible outcomes:
- 01: In this case, we output 0
- 10: In this case, we output 1
- 00: In this case, we repeat the experiment
- 11: In this case, we repeat the experiment
We repeat until we have either 01 or 10 as output. Then, we can compute: The probability of reaching the result “01″ is the following: Either we reach “01″ immediately or we get first some “00″ and “11″. Thus, we can compute the probability of reaching “01″ as follows: . Using the fact that and geometric series, we compute that this probability is 0.5. Moreover, we can do the same for the outcome “10″. Thus, we get a fair random 0/1-number-generator.
We saw that we can w.l.o.g. assume that we have a fair 0/1-random-number-generator . Armed with this knowledge, we can now say that we can generate any discrete random distribution, where the number of results is finite. Therefore, we can just employ a binary encoding of successive calls to . To be more precise, if we want to have possible outcomes (namely from 0 to ), we do calls to . If the binary encoding of the successive -calls yields a number less than , we are done and return that number as the result of our random process. Otherwise, we repeat until we get such a number as the result.
So, up to now we saw that we can w.l.o.g. assume that we have random number generators that generate a random number between 0 and .
For now, we assume that we want to construct a random variable with a specific distribution. To generate any such variable, we need a continuous random variable. That is, we have to convert somehow our discrete variable to a continuous one.
There are several methods to do so, however we focus on the following: We assume is a fair 0/1-random-number-generator. Then, we execute times the generator and interpret the result as a -digit binary number. After that, we divide the result by . Note that this yields still a discrete random variable, but for large it “behaves” like a uniformly distributed variable over the intervall . To be honest, I do not know if there is a (theoretical) way of transforming any discrete random variable into a uniformly distributed continuous random variable.
So, we now assume that we have (almost) a random variable that is uniformly distributed over . If we now want a (continuous) random variable with the distribution , we can do as follows (we assume to be strictly increasing, and thus we also assume that there is an inverse with ): We define this random variable as follows: .
Now we compute:
This tells us that is a random variable with the distribution , which is what we wanted.
Note that out of a continuous variable it is no problem to derive a discrete random variable that e.g. takes only integral values.