후행 0의 수에 대한 기대치를 증명하는 방법

Question

허락하다 $X$ 정수에서 균일하게 샘플링되다 $\{1, \dots, m\}$ ...에 대한 $m > 0$. 에 대한$x>0$, 우리는 정의 $f(x)$ 이진 표현에서 후행 0의 수입니다. $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} $$

그러나 이것이 사실 인 이유는 무엇입니까?

Answer 1

정의상 $$ \mathbb{E}(f(X))=\frac{\displaystyle\sum_{j=1}^mf(j)}{m}\ . $$ 이제 $$ a_{ij}=\cases{0 & if the binary representation of $\ 제이$ \\ &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\ $또는 더 많은 후행 0. 그래서$$ \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}

Answer 2

정확히 있습니다 $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}$, for $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 $m \ to \ 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}$$ 이전과 같은 결과입니다.