Gamma Coding I

Gamma coding is a method to encode positive integers as strings of $0$ and $1$ (called bits) such that no encoding is a prefix of any other encoding. To encode an integer $x \geq 1$, you perform three steps: $\hspace{3pt}$ 1) Define $N = \floor{\log_2(x)}$ $\hspace{3pt}$ 2) Write out $N$ bits that are $0$ $\hspace{3pt}$ 3) Write out $x$ in binary form, which is an $(N+1)-$bit string.

$$$$

For example, $7 = 111$ becomes $00111$ in Gamma code, while $21 = 10101$ becomes $000010101$. We can combine Gamma codes into strings, and read off the components left to right. For example, $000110100011000100110011110101$ decodes to

$$\textcolor{red}{0001101}\textcolor{blue}{0001100}\textcolor{orange}{010}\textcolor{green}{011}\textcolor{pink}{00111}1\textcolor{gray}{010}\textcolor{yellow}{1} = \textcolor{red}{13},\textcolor{blue}{12},\textcolor{orange}{2},\textcolor{green}{3},\textcolor{pink}{7},1,\textcolor{gray}{2},\textcolor{yellow}{1}$$

We note the pattern by seeing the number of zeroes that lead (which is $N$), and then consider the next $N+1$ digits to be our number in binary. Each of these individual component numbers are called codewords. We create an infinite string of $0$ and $1$ bits, where each spot is $1$ with probability $0 < p < 1$. Let $F$ be the length of the first codeword in our string. In the above example, $F$ would be $7$. Find $\mathbb{E}\left[ F \right]$ when $p = 1/3$.