Generating normal distribution by random generation of each binary bit

Question

I'm making a circuit that draws a random amount of current by switching parallel resistors on or off. The resistances increase by factors of two from resistor to resistor, so this can be modeled as generating a word by randomly setting each bit. With a 50/50 chance of each one being on or off, the generated words follows a uniform distribution.

I want the current to be normally distributed. I can set the probability of each resistor being on or off arbitrarily. Is there any way to use this capability to get a normal distribution?

I'm leaning towards there not being one, or else there would be no need for the Box-Muller transform. But if I'm wrong, this method would be a big help.

Answer 1

I'm not sure I understand the circuit set-up--in particular how many 0/1 random variables you can generate, or whether you are talking about a discrete or continuous uniform distribution. Also, I don't know what operations you can perform on the uniform random variables. So I can only make generic suggestions--I hope $\ge 1$ useful ones.

(1) By summing a large number of $X_i \sim \mathsf{Bernouli}(p=.5)$ random variables (derived from _discrete uniform) you can get a binomial random variable that may be indistinguishable from normal.

In the R simulation below I generate 100 Bernoullis and normalize to get a RV $Z$ that is perpaps close enough to $\mathsf{Norm}(0,1).$ This procedure is replicated to get 1000 $Z$'s. They are close enough to normal to look 'good' (essentially linear) in a normal probability plot, but not good enough to fool a Shapiro-Wilk test for normality (not shown).

> set.seed(306)
> z = replicate(1000, (sum(rbinom(100, 1, .5))-50)/5)
> mean(z); sd(z); qqnorm(z, pch=20)
[1] -2e-04    # aprx 0
[1] 1.055706  # aprx 1

(2) If you have continuous standard uniforms, summing 12 of them and subtracting the number 6, will get you very close to standard normal. (This was the method of generating normal variates used in the early days of computing when only the four basic arithmetic operations were 'cheap'.)

> set.seed(318)
> z = replicate(1000, sum(runif(12))-6)
> mean(z); sd(z); shapiro.test(z) 
[1] -0.02129932
[1] 0.9895096

        Shapiro-Wilk normality test

data:  z 
W = 0.9984, p-value = 0.5104

(3) If you can generate continuous standard uniform random variables, you can get standard exponential ones, and then use Box-Muller.

(4) If you can generate continuous standard uniform random variables, you can use Wichura's rational function approximation to the inverse standard normal CDF $\Phi^{-1}(U) \sim \mathsf{Norm}(0,1).$

My suggestion (4) is now the method used in R statistical software to get standard normal random variables: runif is a source of continuous standard uniforms; qnorm is the inverse standard normal CDF ('quantile function'); and rnorm generates standard normals using the method just described. (Legacy and efficiency issues limit this exact demo to one random variable at a time, but the method is sound.)

> set.seed(1234); rnorm(1)
[1] -1.207066
> set.seed(1234); qnorm(runif(1))
[1] -1.207066

Answer 2

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