Simulate a n-dice

Question

You have 2 coins.

one (A) has probabilities 1/2 for H and 1/2 for T, The other (B) has probabilities (n-1)/n for H and 1/n for T.

You wish to use these 2 coins to simulate a balanced n-faces dice. with a finite and pre-known number of flips.

Is it possible to do so?

If the probabilities where (for example) A = (1/2,1/2), B=(4/5,1/5) and you wished to simulate a 5-faces dice you would roll B, if you got T you would return 4 otherwise you would flip A 2 times and return the binary number you got ( 0 , 1 , 2 or 3 )

But if you had only one coin A=(1/2,1/2) and you wished to simulate a 7-faces dice it's provable that it is not possible

Answer 1

An algorithm is given for simulating a fair die with $n$ sides using two biased coins, one with $p = 1/2$ and one $p = 1/n$, for arbitrary integer $n$ in On Dice and Coins: Models of Computation for Random Generation by Feldman et. al in section 2.1.

The algorithm reproduced here is (with two corrections by me, $\leq$ replaced with $<$):

1. Flip the $1/n$ coin once and the fair coin $k = \lceil 2\log n\rceil$ times. Let $v$ be the number that represents the value of the sequence of the $k$ fair coin flips when viewed as a binary number.

2. If the $1/n$ coin is tails then if $v \color{red} < d(n-1)$ then output $(v \bmod n-1) + 1$ else output $n$.

3. If the $1/n$ coin is heads then if $v \color{red}< r(n-1)$ output $(v \bmod n-1) + 1$ else output $n$.

Where a $1/n$ coin is heads $1/n$ of the time and $d = \lfloor 2^k/(n-1)\rfloor$ and $r = 2^k \bmod n - 1$.