How to prove the expectation of the number of trailing zeros

Question

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?

Answer 1

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}

Answer 2

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.