Return value from normal distribution using Bernoulli trial generator Given a random Bernoulli trial generator, how do you return a value sampled from a normal distribution?
Came across this question in my interview prep. I thought it can be done by tuning the probability of success in the generator but I am not sure.
 A: This can be done with random bits using an algorithm presented by C.F.F. Karney, "Sampling exactly from a normal distribution".
This algorithm involves building up uniform(0,1) random numbers one bit at a time, from left to right, using unbiased random bits, and doing comparisons with these numbers. If these comparisons succeed, this means the initial bits of a normal random number have thus been generated, so the algorithm can fill up additional digits to the right with unbiased random bits. For details on the algorithm, see the paper.
In case the "Bernoulli trial generator" outputs biased random bits, the algorithm can produce unbiased random bits from those biased bits using a randomness extraction technique, such as von Neumann's algorithm, Peres's iterated von Neumann method, or Zhou and Bruck's "extractor tree" (see my note on randomness extraction).
A: The first thing that comes to my mind is to generate some samples and to use Central Limit Theorem. Averaging the sample data points will give you a value from Normal distribution.
