A problem on binary number

Question

Let $B_n$ be $n$-bit binary number. Each bit could be either 0 or 1 with equal probability and mutually independent. Let $b_i$ be the $i^{th}$ bit of $B_n$. Let $Z_{ij}$ be the decimal value of the sequence $b_ib_{i+1}...b_j$ where $1 \leq i \leq j \leq n$. Also let $S_k = \{Z_{ij} | Z_{ij} \geq k\}$. What is the expected size of $S_k$?

Answer 1

An $n$-bit binary number takes values from $0$ to $2^n-1$, and in this example they are equally probable.

$Z_{ij}$ is a $j-i+1$-bit random variable; let's call $m=j-i+1$. So the probability it is greater than or equal to $k$ and $Z_{ij} \in S_k$ is $\max\left(0, \dfrac{2^{m}-k}{2^{m}}\right)$ and there are $n-m+1$ such $m$-bit sequences in $B_n$.

So the expected size of $S_k$ is $$\sum_{m=1}^{n} \max\left(0, (n-m+1)\dfrac{2^{m}-k}{2^{m}}\right).$$