Rational Bernoulli rejection has exact law, geometric failure, and bounded expected bit cost

By minimality of $k$, $n\le N<2n$ for $n>1$. [F1] gives acceptance probability $a=n\mathrm{/}N>1\mathrm{/}2$ and rejection probability $r=1-a<1\mathrm{/}2$. On one accepted block, the $n$ possible accepted integers have equal probability $1\mathrm{/}N$, with $m$ of them returning $1$ and $n-m$ returning $0$.

By independence of attempts, the probability that the first accepted block occurs at attempt $j$ and returns $1$ is $r^{j-1}m\mathrm{/}N$, while the probability that it occurs at attempt $j$ is $r^{j-1}n\mathrm{/}N$. Summing over $1\le j\le M_{\max }$ gives success probability $1-r^{M_{\max }}$ and returned-one probability $(m\mathrm{/}n)(1-r^{M_{\max }})$; dividing yields conditional success probability $m\mathrm{/}n$. The no-acceptance event has probability $r^{M_{\max }}<2^{-M_{\max }}$.

With no cap, $r^M\to 0$, so the probability of never accepting is zero. Let $J$ be the first accepted attempt, setting $J=\mathrm{\infty }$ on the null nontermination event. For each $M$, $J\wedge M={\sum }_{j=0}^{M-1}{\mathbf{1}}_{\{J>j\}}$; these truncations increase to $J$, and independence gives $\mathbb{P}(J>j)=r^j$. By [F3] and the geometric identity [F4] with $0\le r<1\mathrm{/}2$, $\mathbb{E}J={\sum }_{j\ge 0}{r}^j=(1-r{)}^{-1}=N\mathrm{/}n<2$. Taking $M\to \mathrm{\infty }$ in step 2.1 gives output-one probability $m\mathrm{/}n$ and hence the exact Bernoulli$(m\mathrm{/}n)$ law. Each attempt consumes $k$ bits, so the expected bit cost is $kN\mathrm{/}n<2k$. The cases $m=0$ and $m=n$ use the explicit zero-bit branches in the algorithm.