# The Rademacher functions for counting binary digits

In the probability space $((0,1),{\cal B}(0,1), \lambda)$, we define the Rademacher functions as:
$R_n(\omega)=\displaystyle\sum_{k=0}^{2^n-1}(-1)^{k+1}I_{\Delta_{k,n}}(\omega)$, where

$(0,1)=\displaystyle\bigcup_{k=0}^{2^n-1}\Delta_{k,n}$

$\Delta_{k,n}=\left(\dfrac{k}{2^n},\dfrac{k+1}{2^n}\right]$, for $k=0,1,\dots2^n-2$
and
$\Delta_{2^n-1,n}=\left(1-\dfrac{1}{2^n},1\right)$

I know that if $\omega\in(0,1)$ and $\omega=\displaystyle\sum_{n=1}^{\infty}\dfrac{x_n}{2^n}$ is the binary representation of $\omega$, then: $R_n(\omega)=-1\ \Longleftrightarrow\$the $n^{th}$ binary digit of $\omega$ is 0 (i.e. $x_n=0$) $(I)$
and
$R_n(\omega)=1\ \Longleftrightarrow\$the $n^{th}$ binary digit of $\omega$ is 1 (i.e. $x_n=1$) $(II)$.

Some prefer this as the definition of the Rademacher functions.
I would like to know why these two definitions are equivalent, that is why the equivalences $(I)$ and $(II)$ hold. Intuitively I understand it, but I can't seem to write it down as a rigorous mathematical proof.

EDIT: I corrected the $\Delta_{k,n}$ sets. As it was, it wasn't a proper partition of $(0,1)$ (some elements were not included - the right endpoints of the $\Delta_{k,n}$'s).

-

The fact that $R_n(\omega)=1$ means that $\omega$ belongs to $\Delta_{k,n}$ for some odd integer $k$. That is, $k\leqslant2^n\omega\lt k+1$ and $k=2\ell+\color{red}{1}$ for some integer $\ell$. Hence $2^n\omega=2\ell+\color{red}{1}+s$ with $0\leqslant s\lt 1$. Since $0\leqslant k\lt2^n$, $0\leqslant\ell\lt2^{n-1}$ and $\ell$ is a binary integer $\ell=\sum\limits_{i=0}^{n-2}\ell_i2^i$ with $\ell_i=0$ or $\ell_i=1$. Thus, $$\omega=\frac2{2^n}\sum\limits_{i=0}^{n-2}\ell_i2^i+\frac{\color{red}{1}}{2^n}+\frac{s}{2^n}=\sum\limits_{i=1}^{n-1}\frac{\ell_{n-i-1}}{2^i}+\frac{\color{red}{1}}{2^n}+\frac{s}{2^n}.$$ This is the binary expansion of $\omega$, up to and including its $n$th bit, and this $n$th bit is $\color{red}{1}$.
To solve the case $R_n(\omega)=-1$, rewrite the whole paragraph replacing each $\color{red}{1}$ by $\color{blue}{0}$.
Very nice solution. However I have some issues. As the $\Delta_{k,n}$'s are constructed, the following inequality holds: $k<2^n\omega\leq k+1$. This allows $s=1$. If this is the case, then the $n^{th}$ bit of $\omega$ would be zero, wouldn't it? –  Nick Papadopoulos Jan 3 '13 at 11:42
You mean, as the $\Delta_{k,n}$'s are constructed now, right? Thus the issues you may have seem to be between you and yourself. Besides, the convention you now see fit to use to define the Rademacher functions is not very usual. –  Did Jan 3 '13 at 18:07
Yes, right now, after the edit which makes the question stand correctly! As the $\Delta_{k,n}$'s were constructed, they didn't partition $(0,1)$. I had taken all the $\Delta_{k,n}$'s to be open, not left closed as you considered in the answer. So, it was wrong and I thought it would be right to correct it. Usual or not, I'm afraid that this one I've been taught. The question I posed asked about the equivalence with this convention. I'm really sorry if by correcting the question i ruined your answer. I'll just accept your answer anyway. –  Nick Papadopoulos Jan 3 '13 at 18:58