(Ahrens and Dieter 1974) For generating the binomial, write the probability p in its binary expansion p = .p1p2 ···base 2 = ∞ i=1 pi2−i . Consider the following algorithm. Algorithm CO (Count Ones)...

(Ahrens and Dieter 1974) For generating the binomial, write the probability p in its binary expansion p = .p1p2 ···base 2 = ∞ i=1 pi2−i . Consider the following algorithm. Algorithm CO (Count Ones) (0) Initialize m = n, J = 0, i = 0.

(1) Increment i = i + 1, and generate k ∼ binomial(m,1/2).

(2) If pj = 1 then m = k; else J = J + k and m = m − k.

(3) If m = 0 then deliver J ; else go to (1).

Show that this generates the binomial distribution. (This algorithm will fly if the computer has a machine instruction to add the number of ones in a string of random bits of length m that is binomial(m,1/2). If your computer has such a machine instruction, you might consider comparing this algorithm’s performance with gbrus.)