Come dimostrare l'aspettativa del numero di zeri finali

Question

Permettere $X$ essere uniformemente campionato dagli interi $\{1, \dots, m\}$ per $m > 0$. Per$x>0$, definiamo $f(x)$ essere il numero di zeri finali nella rappresentazione binaria di $x$.

Cosa è $$ \mathbb{E}(f(X))\;? $$

Se $m$ va all'infinito sembra che il limite sia $1$. Come lo dimostreresti?

---

Se $b = \lfloor \log_2 (m)\rfloor + 1$ è il numero di bit nella rappresentazione binaria di $m$ allora sembra che la risposta sia:

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

Ma perché è vero?

Answer 1

Per definizione, $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^mf(j)}{m}\ . $$ Adesso molla $$ a_{ij}=\cases{0 & if the binary representation of $\ j$ \\ &has fewer than $\ io\ $ trailing zeroes\\ 1& otherwise.} $$ Poi $$ f(j)=\sum_{i=1}^ba_{ij}\ , $$ e $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^m \sum_{i=1}^ba_{ij}}{m} $$ Ma la quantità $\ \left\lfloor\frac{m}{2^i}\right\rfloor\ $ è il numero di numeri interi nell'insieme $\ \{1,2,\dots,m\}\ $ che sono multipli di $\ 2^i\ $- cioè, il numero di tali numeri interi la cui espansione binaria ha $\ i\ $o più zeri finali. Così$$ \left\lfloor\frac{m}{2^i}\right\rfloor=\sum_{j=1}^ma_{ij} , $$ e quindi \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

Ci sono esattamente $2^{b-1}$ positivo $b$-bit numeri (cioè i numeri $2^{b-1},..,2^b-1$) per $b=1,2,3,...$, quindi consideriamo $m=2^b-1$. Permettere$N(\le b,t)$ essere il numero di numeri positivi con $\le b$ bit (es $1,...,m$) e $t$ finale $0$S. Per ispezione (e dimostrabile da alcuni semplici calcoli combinatori, suppongo),$N(\le b,t)=2^{b-1-t}$, per $t=0..b-1$, quindi abbiamo: $$\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}$$

---

Come controllo incrociato, lasciare $|X|$ denotano la lunghezza in bit di $X$, $N(b)$ denota il numero di positivi $b$-bit numeri e $N(b,t)$ denota il numero di positivi $b$-bit numeri con $t$ finale $0$s, abbiamo (di nuovo mediante ispezione) $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}$$ che è lo stesso risultato di prima.