<s>[INST] Question from MIT integration Bee 2023 final: Evaluate $\int^1_0 (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n})^2{\rm d}x$ I am trying to evaluate the last question from MIT integration Bee 2023 Final.
$$\int^1_0 \left (\sum^\infty_{n=0}\frac{\left\lfloor 2^nx\right\rfloor}{3^n} \right )^2{\rm d}x$$
My approach is to divide $(0,1)$ into $1/2^n$ intervals and write the general term of the $y$-value. E.g. For $x \in (k/2^n, (k+1)/2^n)$,
$$f(x)=\left (\sum^{n-1}_{k=0}\frac{\left\lfloor k/2^k\right\rfloor}{3^{n-k}}\right)^2$$
I know that the final integral is just summing up the areas of all the infinite rectangles but I can't solve it. Please help. Thank you.
(The final answer of this question is $27/32$. Candidates were allowed to solve it within 4 minutes.)
 [/INST] Here is a slightly advanced solution: Define $X_1, X_2, \ldots$ on $[0, 1]$ by
$$ X_k (x) := [\text{$k$th digit in the binary expansion of $x$}] = \lfloor 2^k x\rfloor - 2 \lfloor2^{k-1}x\rfloor. $$
Then
\begin{align*}
\sum_{n=0}^{\infty} \frac{\lfloor 2^n x \rfloor}{3^n}
= \sum_{n=1}^{\infty} \frac{1}{3^n} \sum_{k=1}^{n} 2^{n-k}X_k
= \sum_{k=1}^{\infty} \frac{X_k}{2^k} \sum_{n=k}^{\infty} \frac{2^n}{3^n}
= \sum_{k=1}^{\infty} \frac{X_k}{3^{k-1}} .
\end{align*}
Now by regarding $[0, 1]$ as a probability space with the probability measure $\mathrm{d}x$, we find that $X_1, X_2, \ldots$ are i.i.d. $\text{Bernoulli}(\frac{1}{2})$ variables. So,
\begin{align*}
\int_{0}^{1} \left( \sum_{n=0}^{\infty} \frac{\lfloor 2^n x \rfloor}{3^n} \right)^2 \, \mathrm{d}x
= \mathbf{E} \left[ \left( \sum_{k=1}^{\infty} \frac{X_k}{3^{k-1}} \right)^2 \right]
= \sum_{j,k=1}^{\infty} \frac{1}{3^{j+k-2}} \mathbf{E}[X_j X_k].
\end{align*}
Using the independence, we get $\mathbf{E}[X_j X_k] = \frac{1}{4} + \frac{1}{4} \mathbf{1}_{\{j = k\}}$. Hence, the expectation reduces to
\begin{align*}
\sum_{j,k=1}^{\infty} \frac{1}{3^{j+k-2}} \left( \frac{1}{4} + \frac{1}{4} \mathbf{1}_{\{j = k\}} \right)
= \frac{1}{4} \left( \sum_{k=1}^{\infty} \frac{1}{3^{k-1}} \right)^2 + \frac{1}{4} \left( \sum_{k=1}^{\infty} \frac{1}{9^{k-1}} \right)
= \boxed{\frac{27}{32}}
\end{align*}
</s>