Working through a measure theory textbook, and would like to understand dyadic expansions before I can understand its connections with the law of large numbers. I want to see this proved in detail,

For a mapping $F$ from $\Omega=(0,1]$ into itself given by $$F\omega=\begin{Bmatrix} 2\omega & \mbox{if } 0< \omega\leqslant\frac{1}{2} \\ 2\omega-1 & \mbox{if } \frac{1}{2}< \omega\leqslant1 \end{Bmatrix}$$ and $$d_1(\omega)=\begin{Bmatrix} 0 & \mbox{if } 0< \omega\leqslant\frac{1}{2} \\ 1 & \mbox{if } \frac{1}{2}< \omega\leqslant1 \end{Bmatrix}$$ and $d_i(\omega)=d_1(F^{i-1}\omega)$ , How do we prove that $\omega=\sum_{i=1}^{\infty }d_i(\omega)/{2^i}$?

-
It suffices to show that $\omega - \sum_{i=1}^n d_i(\omega) / 2^i \in (0,1/2^n]$ for all $n \geq 1$. The case $n=1$ is by definition. Then you can probably go by induction. – Willie Wong Mar 7 '12 at 12:22
What maybe useful is the observation that if $\tau\in (0,1/2^n]$ and $\sigma: \mathbb{N} \to \{0,1\}$ is any function, you have that $$d_{n+1}(\sum_{i=1}^n \sigma(i)/2^i + \tau) = d_{n+1}(\tau) = d_1(2^n\tau)$$ – Willie Wong Mar 7 '12 at 12:25

The Idea: Suppose that $0.b_1b_2b_3\dots$ is the binary expansion of $\omega$, non-terminating if there is a choice. The map $F$ is essentially just a shift map: it takes $0.b_1b_2b_3\dots$ to $0.b_2b_3b_4\dots$. The map $d_1$ then picks off the first bit of the expansion, and in general $d_n$ picks off the $n$-th bit. Here are the details.

It’s not hard to check that

$$F^2(\omega)=\begin{cases} 4\omega,&\text{if }0<\omega\le\frac14\\\\ 4\omega-1,&\text{if }\frac14<\omega\le\frac12\\\\ 4\omega-2,&\text{if }\frac12<\omega\le\frac34\\\\ 4\omega-3,&\text{if }\frac34<\omega\le1\;. \end{cases}$$

In fact, it’s not hard to prove by induction on $n$ that for $k=0,\dots,2^n-1$, $F^n(\omega)=2^n\omega-k$ iff $\frac{k}{2^n}<\omega\le\frac{k+1}{2^n}$. And $\frac{k}{2^n}<\omega\le\frac{k+1}{2^n}$ iff $k<2^n\omega\le k+1$ iff $k=\lceil 2^n\omega\rceil-1$, so if we wish, we can simply write $F^n(\omega)=2^n\omega-\lceil 2^n\omega\rceil+1$.

Next, observe that $$0<\omega-\frac{d_1(\omega)}2\le\frac12$$ for all $\omega\in(0,1]$. Suppose that $$0<\omega-\sum_{k=1}^n\frac{d_k(\omega)}{2^k}\le\frac1{2^n}\;.\tag{1}$$

Then $$0<2^n\omega-\sum_{k=1}^nd_k(\omega)2^{n-k}\le 1\;.$$ Let $m=\sum_{k=1}^nd_k(\omega)2^{n-k}$; $m$ is an integer, and $m<2^n\omega\le m+1$, so $m+1=\lceil 2^n\omega\rceil$, and $2^n\omega-\lceil 2^n\omega\rceil+1=2^n\omega-m$.

Now $d_{n+1}(\omega)=d_1(F^n(\omega))=d_1(2^n\omega-\lceil 2^n\omega\rceil+1)=d_1(2^n\omega-m)$; this is $1$ if $2^n\omega-m>\frac12$ and $0$ otherwise. But

\begin{align*} 2^n\omega-1>\frac12&\text{ iff }\omega-\frac{m}{2^n}>\frac1{2^{n+1}}\\ &\text{ iff }\omega-\sum_{k=1}^n\frac{d_k(\omega)}{2^k}>\frac1{2^n}\\ &\text{ iff }\omega-\sum_{k=1}^{n+1}\frac{d_k(\omega)}{2^k}>0\;, \end{align*}

so in all cases $$0<\omega-\sum_{k=1}^{n+1}\frac{d_k(\omega)}{2^k}\le\frac1{2^{n+1}}\;.\tag{2}$$

(The second inequality in $(2)$ follows from the fact that Since $2^n\omega-m\le 1$.) Thus, $(1)$ implies $(2)$, and by induction $(1)$ holds for all $n\ge 1$. Since $\frac1{2^n}\to 0$ as $n\to\infty$, it follows that $$\omega=\sum_{k=1}^\infty\frac{d_k(\omega)}{2^k}\;.$$

-
Thank you for the wonderful proof. I was able to go through it except for the inequalities reached on $k<2^n\omega\le k+1$ iff $k=\lceil 2^n\omega\rceil-1$ and on $m+1$ using the ceiling function. I have not used ceiling/floor functions- in a formal setting before. Can you kindly clarify the inequality with the ceiling function, that I believe is being applied over an integer assumption? – user23600 Mar 7 '12 at 13:35
@Praneeth: By definition $\lceil x\rceil$ is the unique integer $n$ such that $n-1<x\le n$; it’s just like the floor (greatest integer) function, except that it rounds up instead of down. Thus, when I have $k<2^n\omega\le k+1$, that tells me that $k+1$ is the smallest integer $\ge 2^n\omega$, and that’s by definition the ceiling of $2^n\omega$. – Brian M. Scott Mar 7 '12 at 13:39
@Brian-Got it..Thanks! – user23600 Mar 7 '12 at 13:44