There is a discrete distribution where integers, $k$, from $1$ to $n$ occur with probability $p\_{k}$, all $p\_{k}$ are unknown.


Rather than having access to the distribution we have access to $n$ coins, with the $k$th coin having probability $p\_{k}$ of giving a result of heads.


Can we sample *exactly* from the distribution by flipping the coins finitely many times?


We can sample approximately by flipping each coin $M$ times and then randomly selecting one of the results of heads and outputting the value of $k$ for the coin that produced it. Unfortunately we require exact sampling.


I'm sure this must have been studied somewhere but I really can't find it.



Exactly sampling from a distribution with access to the probabilities only
I will assume all $p\_i$ are strictly between $0$ and $1$.


**Lemma** We can use a coin with probability $p$ of coming up heads to emulate a coin with probability $p/(1+p)$ of coming up heads. 


**Proof** Flip the coin until it first comes up tails. The emulated coin is declared to be heads if we have flipped an even number of times. The emulated coin comes up heads with probability
$$p(1-p) + p^3(1-p) + p^5(1-p) + \cdots = \frac{p(1-p)}{1-p^2} = \frac{p}{1+p}. \quad \square$$


Set $q\_i = p\_i/(1+p\_i)$. So we may assume we have coins with probability of heads $q\_k$. Flip all coins until exactly one coin comes up heads, and select the corresponding $k$.


Let $S$ be the probability that not precisely one coin comes up heads. The probability of picking $k$ is
$$q\_k \prod\_{j \neq k} (1-q\_j) + S q\_k \prod\_{j \neq k} (1-q\_j) + S^2 q\_k \prod\_{j \neq k} (1-q\_j) + \cdots = \frac{q\_k \prod\_{j \neq k} (1-q\_j)}{1-S}.$$
So the ratio of the probability of picking $k$ and the probability of picking $\ell$ is
$$\frac{q\_k/(1-q\_k)}{q\_{\ell}/(1-q\_{\ell})}= \frac{p\_k}{p\_{\ell}}.$$
Since the probabilities must add up to $1$, the probability of picking $k$ is $p\_k$.


