2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Somewhat related: stats.stackexchange.com/questions/117689. Given that Bernoulli trials return only zeros and ones, it's hard to see what tuning it might do. Consider instead using it to generate binary sequences, because from there it's easy to obtain a uniform value in $[0,1)$ and you're off and running (search "Box Muller"). $\endgroup$
    – whuber
    Nov 12, 2020 at 22:47
  • 1
    $\begingroup$ If you generate $n=100$ observations from $\mathsf{Binom}(100, 1/2)$ you will have 100 observations that are nearly $\mathsf{Norm}(\mu=25,\sigma=5),$ (except rounded to integers). In R, x = rbinom(100, 100, .5); mean(x); sd(x); shapiro.test(x)$p.val returns $\bar X \approx 50, S \approx 5,$ and P-value > 5% for the normality test. $\endgroup$
    – BruceET
    Nov 12, 2020 at 22:48
  • 1
    $\begingroup$ For some historically clever solutions, see jstor.org/stable/2245712?seq=1. I believe this may be the article in which Stigler describes Galton's dice, which had special (floating) values written on them which when summed emulated a standard Normal variate remarkably well. $\endgroup$
    – whuber
    Nov 12, 2020 at 22:51

2 Answers 2

3
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Even as a practical solution this works poorly unless you generate those "samples" in a particularly clever way. (That's what Galton's dice were all about.) $\endgroup$
    – whuber
    Jan 25, 2021 at 17:44
  • $\begingroup$ You're right. I think it'd be helpful to have this "suggested" solution and your comment here for others to see in case they think of using CLT as a potential solution. $\endgroup$
    – Peyman
    Feb 1, 2021 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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