Cómo demostrar la expectativa del número de ceros finales

Question

Dejar $X$ ser muestreados uniformemente de los enteros $\{1, \dots, m\}$ para $m > 0$. por$x>0$, definimos $f(x)$ ser el número de ceros finales en la representación binaria de $x$.

Que es $$ \mathbb{E}(f(X))\;? $$

Si $m$ va al infinito parece que el límite es $1$. ¿Cómo probarías eso?

---

Si $b = \lfloor \log_2 (m)\rfloor + 1$ es el número de bits en la representación binaria de $m$ entonces parece que la respuesta es:

$$ \frac{\sum_{i=1}^b \left\lfloor \frac{m}{2^i} \right\rfloor}{m} $$

Pero, ¿por qué es esto cierto?

Answer 1

Por definición, $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^mf(j)}{m}\ . $$ Ahora deja $$ a_{ij}=\cases{0 & if the binary representation of $\ j$ \\ &has fewer than $\ yo\ $ trailing zeroes\\ 1& otherwise.} $$ Luego $$ f(j)=\sum_{i=1}^ba_{ij}\ , $$ y $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^m \sum_{i=1}^ba_{ij}}{m} $$ Pero la cantidad $\ \left\lfloor\frac{m}{2^i}\right\rfloor\ $ es el número de enteros en el conjunto $\ \{1,2,\dots,m\}\ $ que son múltiplos de $\ 2^i\ $—Es decir, el número de tales enteros cuya expansión binaria tiene $\ i\ $o más ceros finales. Entonces$$ \left\lfloor\frac{m}{2^i}\right\rfloor=\sum_{j=1}^ma_{ij} , $$ y por lo tanto \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

Hay exactamente $2^{b-1}$ positivo $b$-números de bits (es decir, los números $2^{b-1},..,2^b-1$) para $b=1,2,3,...$, así que consideremos $m=2^b-1$. Dejar$N(\le b,t)$ ser el número de números positivos con $\le b$ bits (es decir $1,...,m$) y $t$ arrastrando $0$s. Por inspección (y comprobable mediante una simple combinatoria, supongo),$N(\le b,t)=2^{b-1-t}$, para $t=0..b-1$, entonces tenemos: $$\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}$$

---

Como una verificación cruzada, dejando $|X|$ denotar la longitud de bits de $X$, $N(b)$ denotar el número de positivos $b$-números de bits y $N(b,t)$ denotar el número de positivos $b$-números de bits con $t$ arrastrando $0$s, tenemos (nuevamente por inspección) $N(b,t)=\lceil 2^{b-2-t}\rceil$, dando

$$\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}$$ que es el mismo resultado que antes.