Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost

A block is accepted with probability $p=M\mathrm{/}{2}^h$. By the definition of $h$, $M\le 2^h$, and either $M=2^h$ or $M>2^{h-1}$; hence $p\ge 1\mathrm{/}2$. If $p=1$, every block is accepted and each valid $b$ is output with probability $2^{-h}=1\mathrm{/}M$. If $p<1$, for a fixed valid $b<M$ the probability that the algorithm outputs $b+1$ on block $t$ is $(1-p{)}^{t-1}{2}^{-h}$ by [F1], and summing gives $2^{-h}{\sum }_{t\ge 0}(1-p{)}^t=2^{-h}\mathrm{/}p=1\mathrm{/}M$.

The events that the first $j$ blocks are all rejected decrease with $j$ and have probability $(1-p{)}^j\le 2^{-j}$ by [F1]. Their intersection is the event that the algorithm never halts, and [F2] gives that event probability ${\lim }_{j\to \mathrm{\infty }}(1-p{)}^j=0$. Thus the procedure halts almost surely.

Let $K$ be the number of blocks read before the first acceptance. For integer $j\ge 0$, $\mathbb{P}(K>j)=(1-p{)}^j$. The tail function is constant on each interval $[j,j+1)$, so [F3] gives $\mathbb{E}[K]={\sum }_{j\ge 0}(1-p{)}^j=1\mathrm{/}p\le 2$, with the $p=1$ case interpreted as $K=1$. Computing $h$ as the binary length of $M-1$ takes $O(h)$ transitions. Each block reads and stores $h$ bits in $O(h)$ transitions; comparing that $h$-bit integer with $M$ takes $O(h)$ transitions, and incrementing an accepted value and writing the output use at most $h+1$ bits. Since $h\ge 1$, these operations also take $O(h)$ transitions, so the nonrandom work per block is $O(h)$. By [F4], these transitions and the $h$ random-bit generations are charged. Thus expected random-bit use is at most $2h$ and expected total bit transitions are $O(h)$.