Expected number of tosses - coin tossing

Question

I have here 2 methods for generating a random number, and I need to calculate the expected number of tosses for each method. In each, we let n = log(N) Ne be the bit-length of N and let B(n-1)B(n-2)....B(0) be the binary representation of N (so B(n-1) = 1) Method 1:

For i = n  1 down to 0, do {
if B(i) = 1 OR there is a j > i such that C(j) < B(j),
then use a coin toss to generate a new C(i) [0 or 1].
Otherwise, set C(i) = 0
}
Output C(n-1)C(n-2).....C(1)C(0)

Method 2:

Use n + 10 coin tosses to generate a random number M between 0 and
2^(2n+10) - 1. 
If M < N * (2^(2n+10) / N) - output M, 
otherwise repeat.

Thanks in advance

Answer 1

Fix some positive integer $N$ and introduce:

• the bit-length $n$ of $N$, that is, the unique positive integer $n$ such that $2^{n-1}\leqslant N\lt2^{n}$,
• the binary expansion $(B_k)_{0\leqslant k\leqslant n-1}$ of $N$, that is, the unique $B_k$ in $\{0,1\}$, $B_{n-1}=1$, such that $N=B_0+2B_1+\cdots+2^{n-1}B_{n-1}$,
• the number $L$ of leading ones in the binary expansion of $N$, defined by $B_{n-k}=1$ for every $1\leqslant k\leqslant L$ and $B_{n-L-1}=0$,
• the length $K$ of the first block of zeroes after the $L$ leading ones, that is, $K=0$ if $L=n$ and, otherwise, $B_{n-L-i}=0$ for every $1\leqslant i\leqslant K$ and $B_{n-L-K-1}=1$,
• the integer $U=B_0+2B_1+\cdots+2^{n-L-K-1}B_{n-L-K-1}$ which is the number $N$ stripped of its leading block of ones and of its next block of zeroes.

For example, if $N=1100010010$, then $n=10$, $L=2$, $K=3$ and $U=10010$.

Call $T$ the mean number of tosses needed in Method 1. The first zero happens at toss $k$ with probability $2^{-k}$. If $k\leqslant L$, one uses $n$ tosses. If the first $L$ tosses are ones, the $K$ next digits need no toss and one is left with the tosses needed for $U$. Hence, $$ T=(1-2^{-L})n+2^{-L}(L+T_{U}), $$ that is, $$ n-T=2^{-L}(n-L-T_{U})=2^{-L}K+2^{-L}(n_{U}-T_{U}), $$ where $n_U$ and $T_U$ are based on $U$ as $n$ and $T$ are based on $N$. If $N=1^{L_1}0^{K_1}1^{L_2}0^{K_2}1^{L_3}\ldots$, one gets $$ T_N=n-2^{-L_1}K_1-2^{-L_1-L_2}K_2-2^{-L_1-L_2-L_3}K_3-\cdots $$ For example, if $N=1100010010$, then $T_N=10-2^{-2}3-2^{-3}2-2^{-4}1=9-\frac1{16}$.

On the other hand, Method 2 as written in the post is quite odd hence I suggest to consider Method 2 below:

Use n coin tosses to generate a random number M between 0 and 2^n - 1 
If M < N then output M
Otherwise repeat

The mean number $R$ of tosses needed in this (revised version of) Method 2 is the number $n$ of tosses needed for one pass times the mean number of passes. Each pass is succesful with probability $N/2^{n}$ hence $R=n2^{n}/N$.

One sees that $n\lt R\leqslant2n$ and $T\leqslant n$ (the only case when $T=n$ being when $N=2^{n}-1$). Hence $T\lt R$, that is, Method 1 is more effective than (the revised version of) Method 2, for every positive number $N$.