Can the minimum number of coinflips needed for a bias-free random range be explicitly defined? Imagine you have a perfect coin, a source of randomness that can choose between 0 or 1 with equal probability independently, but this source of randomness is expensive (e.g. it's a slow source). I would like to optimize for minimum usage.
This can be used to generate a number $r \in \mathbb{N}$ so that $0 \leq r \lt n$, where each number has equal probability. A simple process can be used: Flip $x$ coins, where $2^x > n$ and $2^x$ is the smallest such number, and read the result in base-2, let this number be $q$.  If $q<n$, the procedure is complete. Otherwise, repeat it.
However, this is not very efficient: Especially if $n$ is slightly more than some power of 2, there's a near 50% chance of failure. The average number of coinflips needed $E$ is then close to $2x$. There's a way to sometimes optimize further. Flip $x' = x + k$ coins, and read the larger number as binary. Let $m$ be the number so that $mn < 2^{x'}$ is the largest such multiple. Now, there's a much smaller chance of failure. For any value of $k$, the failure chance is now at most $(\frac{1}{2})^k$ as $$2^{x'} - mn < 2^x$$ However, $k$ more coins are used per attempt. That leads to an optimization problem.
Some examples:
i) Let $n = 3$. Trying out $x = 2, m = 1$. Then success chance $P = \frac{mn}{2^x} = \frac{3}{4}$.
$$E = \frac{3}{4} 2 + \frac{1}{4} (E + 2)$$
$$\frac{3}{4} E = \frac{6}{4} + \frac{1}{2} = 2$$
$$ E = \frac{4}{3} 2 = \frac{8}{3} < 3$$
Since E < 3 here, no need to try out any other possible $x$. $x=2$ is optimal. More commonly , a direct formula for $E$ would be $$E = \frac{n}{P}$$, derived similar to above, replacing $2 \rightarrow n$ and $\frac{3}{4} \rightarrow P$.
ii) Let $n = 5$. Trying out $x = 3$, $m = 1$ leads to $P = \frac{5}{8}$. Plug into the formula to get $E = \frac{24}{5} = 4.2$. Trying out $x=4$, $m=3$ leads to $P = \frac{15}{16}$ or $E = \frac{64}{15} > 4.2$, thus $x=3,m=1$ is correct.
You might be asking, what's the smallest counterexample to the $m=1$ assumption?
iii) For $n=9$, trying $x=4$,$m=1$  yields $P = \frac{9}{16}$, $E = \frac{64}{9}$. But, trying $x=5, m=3$ yields $P=\frac{27}{32}$, $E = \frac{160}{27} < 6$. So $x=5$ is optimal.
iv) Using the result from (ii): For $n = 15, x = 4$. So the sequence is not even strictly increasing.
Now comes the tricky question: Is there some more direct way of solving the problem for arbitrary $n$? What's the value of $x$ for lowest possible $E$?
Then $m$ can be derived as $$m = \Bigl \lfloor \frac{2^x}{n} \Bigr \rfloor$$
I presume the answer will need some number theory; as it deals with division remainders, common multiples, and such.
 A: The terms I will use are not necessarily standard, I just made them up. I don't have a definitive answer, but I will synthesize my thoughts on the problem (I have thought about it for some years now!).
I think we can formalize the problem in the following way. Let us denote $\mu := \frac{1}{2}\left(\delta_0 + \delta_1\right)$.
Let $n \in \mathbb{N}^*$, and $\phi : \{0,1\}^{\mathbb{N}} \rightarrow \{0,\cdots,n-1\}$ be a measurable map such that $\phi_*(\mu^{\otimes \mathbb{N}}) = Uniform(\{0,\cdots,n-1\})$. That is, such a $\phi$ is a rule of decision, such that when it looks at an infinite sequence of coin tosses, decides which result it should give.
We say that $\phi$ is completely finitely decidable if there exists $m \in \mathbb{N}^*$, a map $\phi_m : \{0,1\}^m \rightarrow \{0,\cdots,n-1\}$ such that for almost all $(\omega_0,\cdots) \in \{0,1\}^{\mathbb{N}}$, $\phi_m(\omega_0,\cdots,\omega_{m-1}) = \phi(\omega_0,\cdots)$.
In other words, $\phi$ is completely finitely decidable if there exists an $m$ such that you don't have to look after the $m$-th coin in order to decide.
Proposition: No completely finitely decidable rule of decision exists, if $n$ is not a power of two.
Proof: Exercise!
We say that $\phi$ is almost surely finitely decidable if, for almost all $(\omega_0,\cdots) \in \{0,1\}^{\mathbb{N}}$, there exists $m$ such that for all $(\omega'_0,\cdots) \in \{0,1\}^{\mathbb{N}}$, if the two coincide up to $m$, then $\phi(\omega_0,\cdots) = \phi(\omega'_0,\cdots)$.
That is, almost everytime, you can stop tossing coins at some point, but this moment is not necessarily the same for all eventualities.
A measurable map $T : \{0,1\}^{\mathbb{N}} \rightarrow \mathbb{N}$ is a time stop for $\phi$ if for almost all $(\omega_0,\cdots)$, the $m$ in the above definition can be chosen as $T(\omega_0,\cdots)$ (is this clear?).
You described an example of a couple $(\phi,T)$ such that $\phi$ is almost surely finitely decidable. Another can be described informally in this way: toss coins and form the binary expansion of a real number in $[0,1]$. If the real number gets caught between $\frac{k}{n}$ and $\frac{k+1}{n}$ and cannot escape in any further step, then decide that the result should be $k$.
There are now many ways to define that some $(\phi,T)$ is better than a $(\phi',T')$: you might ask that almost surely, $T\leq T'$ (but this might be too strong to ask), or $\mathbb{E}[T] \leq \mathbb{E}[T']$ (but this might be too weak to ask).
