Как доказать математическое ожидание количества конечных нулей
Позволять $X$ быть равномерно выбранными из целых чисел $\{1, \dots, m\}$ за $m > 0$. За$x>0$, мы определяем $f(x)$ быть количеством конечных нулей в двоичном представлении $x$.
Что такое $$ \mathbb{E}(f(X))\;? $$
Если $m$ уходит в бесконечность, кажется, предел $1$. Как бы вы это доказать?
Если $b = \lfloor \log_2 (m)\rfloor + 1$ количество битов в двоичном представлении $m$ тогда кажется, что ответ таков:
$$ \frac{\sum_{i=1}^b \left\lfloor \frac{m}{2^i} \right\rfloor}{m} $$
Но почему это правда?
Ответы
По определению, $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^mf(j)}{m}\ . $$ Теперь позвольте $$ a_{ij}=\cases{0 & if the binary representation of $\ j$ \\ &has fewer than $\ я \ $ trailing zeroes\\ 1& otherwise.} $$ потом $$ f(j)=\sum_{i=1}^ba_{ij}\ , $$ и $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^m \sum_{i=1}^ba_{ij}}{m} $$ Но количество $\ \left\lfloor\frac{m}{2^i}\right\rfloor\ $ количество целых чисел в наборе $\ \{1,2,\dots,m\}\ $ которые кратны $\ 2^i\ $- то есть количество таких целых чисел, двоичное расширение которых имеет $\ i\ $или более завершающих нулей. Так$$ \left\lfloor\frac{m}{2^i}\right\rfloor=\sum_{j=1}^ma_{ij} , $$ и поэтому \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}
Есть ровно $2^{b-1}$ положительный $b$-битовые числа (т.е. числа $2^{b-1},..,2^b-1$) за $b=1,2,3,...$, так что давайте рассмотрим $m=2^b-1$. Позволять$N(\le b,t)$ быть количеством положительных чисел с $\le b$ биты (т.е. $1,...,m$) и $t$ конечный $0$с. Путем проверки (и, я полагаю, доказуемой простой комбинаторикой),$N(\le b,t)=2^{b-1-t}$, за $t=0..b-1$, так что имеем: $$\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 $м \ до \ infty$} \end{align}$$
В качестве перекрестной проверки позволяя $|X|$ обозначают битовую длину $X$, $N(b)$ обозначим количество положительных $b$-битовые числа и $N(b,t)$ обозначим количество положительных $b$-битовые числа с $t$ конечный $0$s, имеем (опять же при осмотре) $N(b,t)=\lceil 2^{b-2-t}\rceil$, давая
$$\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}$$ что тот же результат, что и раньше.