The problem statement for Project Euler #323 is as follows:
Let $y_0, y_1, y_2, …$ be a sequence of random unsigned 32 bit integers (i.e. $0 \leq y_i < 2^{32}$, every value equally likely).
For the sequence $x_i$ the following recursion is given:
$x_0 = 0$ and
$x_i = x_{i-1} | y_{i-1}$, for $i > 0$. ( | is the bitwise-OR operator)
It can be seen that eventually there will be an index N such that $x_i = 2^{32} -1$ (a bit-pattern of all ones) for all $i \geq N$.
Find the expected value of N. Give your answer rounded to 10 digits after the decimal point.
I'm not interested in the actual solution to the problem, but I wish to understand where my attempts have gone wrong. My attempt to the problem thus far has been as follows:
For any $y_i$, the chance of any bit being a 1 is $\frac{1}{2}$ as all values are equally likely. In other words, the chance that a bit will "flip" from a 0 to a 1 on the next turn is $\frac{1}{2}$.
Thus the expected number of 1s in $x_1$ is $32 \div 2 = 16$
Following this logic, the expected number of 1s in $x_2$ is 24, as half of the sixteen zeroes would flip.
Then the expected number of 1s in $x_3$ is 28, for $x_4$ it's 30 and for $x_5$ it's 31.
The expected value for the last bit is equivalent to flipping a coin until we hit a head (1), which would be $\sum_{1}^{\infty} \frac{n}{2^n} = 2$.
Therefore the expected value of N is 5 + 2 = 7.
However, apart from the fact that the answer is completely wrong, something makes me think that expected values just don't work that way. Can someone please clarify where I've made a mistake?
Disclaimer: Although I try to refrain from posting questions related to Project Euler on Math StackExchange, I believe that the answer to my problem would make it no easier for anyone else to solve the problem, and might in fact help others understand where they went wrong.
Best Answer
Each time you OR an $y_i$ into $x_{i-1}$, you are OR-ing a $1$ in the $k$-th position with probability $\frac{1}{2}$, and what you are OR-ing into the $32$ bit positions is $32$ independently chosen bits. If $X_k$ denotes the value of $i$ at which the $k$-th bit turns from $0$ to $1$, then $X_k$ is a geometric random variable with parameter $\frac{1}{2}$. Thus, $$P\{X_k \leq m\} = 1 - P\{X_k > m\} = 1 - \frac{1}{2^m}.$$ Also, the $X_k$'s are independent random variables.
The time $N$ at which you arrive at the all-ONEs state is thus the maximum of $32$ independent geometric random variables with parameter $\frac{1}{2}$. Now, $$P\{N > m\} = P\{\text{at least one}~X_k > m\} = 1 - P\{\text{all}~ X_k \leq m\} = 1 - \left(1 - \frac{1}{2^m}\right)^{32}$$ and $$\begin{align*}E[N] &= \sum_{m=0}^{\infty} P\{N > m\} = \sum_{m=0}^{\infty} 1 - \left(1 - \frac{1}{2^m}\right)^{32} \\ &= 1 + \left[1 - \left(\frac{1}{2}\right)^{32}\right] + \left[1 - \left(\frac{3}{4}\right)^{32}\right] + \left[1 - \left(\frac{7}{8}\right)^{32}\right] + \cdots \end{align*}$$ which should work out to be close to $7$.