Detailed mathematical approach

Problem Summary

Let \(Y_n\) be the bitwise OR of \(n\) independent uniformly random \(b\)-bit integers. Starting from \(Y_0=0\), we define \(T\) as the first step at which every bit has become 1. For the actual problem \(b=32\), and we want the expected value \(\mathbb E[T]\).

Mathematical Approach

1) Track one bit first.

Fix one coordinate, for example the least significant bit. In one random \(b\)-bit integer, that bit is 0 with probability \(1/2\) and 1 with probability \(1/2\).

After \(n\) independent draws, this bit is still 0 in the OR if and only if every one of those \(n\) draws had a 0 there. Therefore

$\Pr(\text{fixed bit still 0 after }n\text{ steps})=\left(\frac12\right)^n=2^{-n}.$

So the same bit has already become 1 with probability

$1-2^{-n}.$

2) Why the \(b\) bits can be multiplied.

For a single random draw, the bits are independent. Across different draws, the samples are also independent. Therefore the full \(n\times b\) table of bit values is a collection of independent Bernoulli variables.

Whether coordinate \(j\) is still 0 after \(n\) steps depends only on the \(n\) Bernoulli variables in column \(j\). Different columns use disjoint sets of independent variables, so these events are independent across coordinates.

Hence the probability that every one of the \(b\) bits has already turned into 1 is

$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$

3) Convert that into the distribution of the stopping time.

The event \(T \le n\) means exactly that after \(n\) draws, all bits are already 1. So

$\Pr(T \le n)=\left(1-2^{-n}\right)^b.$

Therefore the tail probability is

$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$

This is the quantity summed by the program.

4) Tail-sum formula for the expectation.

For a nonnegative integer-valued random variable,

$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$

Substituting the tail above gives

$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$

This series converges very quickly because \(2^{-n}\) shrinks exponentially.

5) Optional exact closed form.

Expand with the binomial theorem:

$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$

Now sum over \(n\ge 0\) and use the geometric series

$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}}.$

So we also get the exact identity

$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$

The C++ code does not use this alternating finite sum; it uses the tail series directly, because it is simple and numerically stable for the small value \(b=32\).

6) Worked example for \(b=1\).

With one bit, the process stops when the first 1 appears. So this is just a geometric waiting time with success probability \(1/2\), and we know immediately that

$\mathbb E[T]=2.$

The formula above gives the same result:

$\mathbb E[T]=\sum_{n=0}^{\infty}2^{-n}=\frac{1}{1-\frac12}=2.$

7) Worked example for \(b=2\).

Now both bits must be collected. The probability that both bits are already 1 after \(n\) steps is

$\left(1-2^{-n}\right)^2.$

Hence

$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$

Expanding gives

$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$

so

$\mathbb E[T]=2\sum_{n=0}^{\infty}2^{-n}-\sum_{n=0}^{\infty}4^{-n}=4-\frac{4}{3}=\frac{8}{3}.$

This is exactly the second checkpoint used in the program.

Algorithm

1) Fix \(b\) (for the problem, \(b=32\)).

2) For \(n=0,1,2,\dots\), compute

$\text{term}_n=1-\left(1-2^{-n}\right)^b.$

3) Add these terms to an accumulator for \(\mathbb E[T]\).

4) Stop when the current term is below \(10^{-20}\). Because the tail is exponentially small, the neglected remainder is far below the requested decimal precision.

Complexity Analysis

The number of iterations is tiny because the terms decay exponentially. In practice the runtime is effectively constant, and the memory usage is

$O(1).$

Checks And Final Result

The C++ code checks

$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$

For the actual problem \(b=32\), the final value is

$\mathbb E[T]\approx 6.3551758451.$

Further Reading

1. Problem page: https://projecteuler.net/problem=323
2. Expected value and tail-sum formulas: https://en.wikipedia.org/wiki/Expected_value
3. Binomial theorem: https://en.wikipedia.org/wiki/Binomial_theorem