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$

integration

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

Best Answer

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*}