Flaw in expected value solving logic (Project Euler 323)

Question

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.

Answer 1

One thing that is going wrong is that at the informal level, "expected value $k$" is being identified with "value $k$." So for example at the almost end, when you think the expected number of $0$'s remaining is $1$, it is quite possible that there remains more than $1$, and also quite possible that there remain none. There is no reason to think that the expectations produced by these two cases will cancel.

It is not clear either what expectations even mean. When you say that the expected number of $0$'s after $k$ bitwise operations is $e$, are you conditioning on the event that the process has not terminated by time $\le k-1$?

In order to see what is going on, we will make a couple of calculations, with numbers far smaller than $32$. Imagine, for example, that the number $b$ of bits is $2$.

Then after one operation, with probability $1/4$ we will still be at $(1,1)$, with probability $1/2$ we will be at $(0,1)$ or $(1,0)$, and with probability $1/4$ we will be at $(0,0)$. Let $e$ be the expected number of operations used.

Thus with probability $1/4$ we have wasted a toss, and the expected number of tosses needed is $1+e$. With probability $1/2$, we have used $1$ toss, and the expected number of additional tosses is $2$. And with probability $1/4$ we do not need a second toss, so the expectation is $1$. It follows that $$e=\frac{1}{4}(1+e)+\frac{1}{2}(1+2)+ \frac{1}{4}(1).$$ Solve for $e$. We get $e=8/3$.

A calculation based on my understanding of your method would say that the expectation is $1+2$.

Answer 2

Intuitively, I think your reasoning makes sense if you talk about the average number of tries you should do in order to reach $2^{32}-1$. So, if you repeat the experiment a large number of times, in average, 7 should be enough.

However, the definition (according to Wikipedia) of the expected value of a random variable is the weighted average of all possible values that this random variable can take on. In other words, what you would need to calculate is the average of {probability that 1 is needed, 2 times the probability that two numbers are needed, 3 times the probability that three numbers are needed, etc.}. After a while, the probability that N numbers are needed will be so low that you won't impact the 10th digit after the decimal point.

But I must say that intuitively, I wouldn't be surprised that the value is around 7, following your reasoning.

Answer 3

The most obvious problem I see is that you went from "the expected value for the number of unflipped coins at stage 5 is 1" to "the expected number of flips required until there is just one unflipped coin is 5". You then compute the expected value of the number of flips to finish up, conditional on the beginning being right (implicitly assuming that you will always end up with only one unflipped coin at some point).

One way to actually solve the problem is to view your process as 32 independent Bernouli processes, and noting that (as you had when only one coin was remaining) the first success time has a geometric distribution. The time when the last process succeeds is the largest order statistic of the 32 processes. Although the page lists a formula for the order statistics, it is worthwhile to try to derive the formula, at least for the largest order statistic. This is fairly straight forward by using the CDF of the variables to determine the CDF of the order statistics. While it is possible to go from the CDF to the corresponding PDF (although wikipedia says that the distribution is called a probability mass function when the variable is discrete), one can go directly from the cumulative function directly to the expected value without passing through the pdf, at least for discrete variables.

Answer 4

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