How to prove the expectation of the number of trailing zeros Let $X$ be uniformly sampled from the integers $\{1, \dots, m\}$ for $m > 0$.  For $x>0$, we define $f(x)$ to be the number of trailing zeros in the binary representation of $x$.
What is
$$
\mathbb{E}(f(X))\;?
$$
If $m$ goes to infinity it seems the limit is $1$.  How would you prove that?

If $b = \lfloor \log_2 (m)\rfloor + 1$ is the number of bits in the binary representation of $m$ then it seems the answer is:
$$
\frac{\sum_{i=1}^b \left\lfloor \frac{m}{2^i} \right\rfloor}{m}
$$
But why is this true?
 A: There are exactly $2^{b-1}$ positive $b$-bit numbers (i.e. the numbers $2^{b-1},..,2^b-1$) for $b=1,2,3,...$, so let's consider $m=2^b-1$.
Let $N(\le b,t)$ be the number of positive numbers with $\le b$ bits (i.e. $1,...,m$) and $t$ trailing $0$s. By inspection (and provable by some simple combinatorics, I suppose), $N(\le b,t)=2^{b-1-t}$, for $t=0..b-1$, so we have:
$$\begin{align}E\,f(X)
&=\sum_{t=0}^{b-1}tP(f(X)=t)\\
&=\sum_{t=0}^{b-1}t{N(\le b,t)\over m}\\
&={2^{b-1}\over m}\sum_{t=0}^{b-1}t{2^{-t}}\\
&={2^b-b-1\over m}\\
&={m-b\over m}\\
&=1-{b\over m}\\
&\to 1\quad\text{as $m\to\infty$}
\end{align}$$

As a cross-check, letting $|X|$ denote the bit-length of $X$, $N(b)$ denote the number of positive $b$-bit numbers and $N(b,t)$ denote the number of positive $b$-bit numbers with $t$ trailing $0$s, we have (again by inspection) $N(b,t)=\lceil 2^{b-2-t}\rceil$, giving
$$\begin{align}E\,f(X)
&=\sum_{l=1}^{b}E(f(X)\mid|X|=l)\,P(|X|=l)\\
&=\sum_{l=1}^{b}\left(\sum_{t=0}^{l-1}t\,{N(b,t)\over N(b)}\right){N(b)\over m}\\
&={1\over m}\sum_{l=2}^b\left(\sum_{t=1}^{l-1}t\,\lceil 2^{b-2-t}\rceil\right)\\
&={1\over m}\sum_{l=2}^b\left(\sum_{t=1}^{l-2}t\,2^{b-2-t}+(b-1)\right)\\
&={1\over m}\sum_{l=2}^b\left((2^{b-1}-b)+(b-1)\right)\\
&={1\over m}\sum_{l=2}^b\left(2^{b-1}-1\right)\\
&={2^b-b-1\over m}
\end{align}$$
which is the same result as before.
A: By definition,
$$
\mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^mf(j)}{m}\ .
$$
Now let
$$
a_{ij}=\cases{0 & if the binary representation of $\ j$ \\
&has fewer than $\ i\ $ trailing zeroes\\
1& otherwise.}
$$
Then
$$
f(j)=\sum_{i=1}^ba_{ij}\ ,
$$
and
$$
\mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^m \sum_{i=1}^ba_{ij}}{m}
$$
But the quantity $\ \left\lfloor\frac{m}{2^i}\right\rfloor\ $ is the number of integers in the set $\ \{1,2,\dots,m\}\ $ that are multiples of $\ 2^i\ $—that is, the number of such integers whose binary expansion has $\ i\ $ or more trailing zeroes. So
$$
\left\lfloor\frac{m}{2^i}\right\rfloor=\sum_{j=1}^ma_{ij}
 ,
$$
and therefore
\begin{align}
\frac{\displaystyle\sum_{i=1}^b\left\lfloor\frac{m}{2^i}\right\rfloor}{m}&= \frac{\displaystyle\sum_{i=1}^b \sum_{j=1}^ma_{ij}}{m}\\
&=\frac{\displaystyle\sum_{j=1}^m \sum_{i=1}^ba_{ij}}{m}\\
&= \mathbb{E}(f(X))\ .
\end{align}
