5
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks David, this is exactly what I needed. Could you tell me how you know about this kind of problem and where I should go to learn more? $\endgroup$
    – Howard Dale
    Commented Jul 16, 2014 at 13:59
  • $\begingroup$ This is a very nice solution. One thing I notice about it is that the expected total number of coin tosses is not bounded as a function of $n$, since a coin with $p_i\approx 1$ will take a long time to come up tails. I wonder if this is an essential feature of a solution. $\endgroup$
    – Brendan McKay
    Commented Jul 17, 2014 at 0:18
  • 1
    $\begingroup$ I don't know much about this sort of question. I came up with the second part first, then I realized I needed the lemma. I remembered that there was a theorem that said something like "For any nice $f: [0,1] \to [0,1]$ which doesn't come too close to $0$ or $1$ in the interior, there is a way to use a $p$ coin to simulate an $f(p)$ coin", so I believed the lemma was true and then it wasn't hard to prove. This morning I did a little searching and found this survey arxiv.org/abs/math/0309222 on using one coin to simulate another. $\endgroup$
    – David E Speyer
    Commented Jul 17, 2014 at 13:27
  • $\begingroup$ @BrendanMcKay The paper I link in the previous comment has many results on speed of simulation. However, all of its bounds are allowed to blow up as $p \to 0^+$ and $1^-$. $\endgroup$
    – David E Speyer
    Commented Jul 17, 2014 at 13:31
  • $\begingroup$ For the problem in the lemma, expected run time must blow up as $p \to 1$. More specifically: Suppose we have an algorithm for using a $p$ coin to emulate an $f(p)$-coin, whose run time is bounded by $K$. Then $\lim_{p \to 1^{-}} f(p)$ is $0$ or $1$. Proof: Choose $\epsilon \in (0, 1/2)$. For $p$ close enough to $1$, $p^{2K}>1-\epsilon$. So the algorithm must terminate on $2K$ (or fewer) initial heads in order to keep the run time under $2K(1-\epsilon) > K$. Assuming WLOG that it terminates with the answer "heads", then $f(p) > 1-\epsilon$. Sending $\epsilon \to 0$, we have the result. $\endgroup$
    – David E Speyer
    Commented Jul 17, 2014 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .