Given a probability $p$ and an integer $N$, I would like to generate a sample $S$ of the population $P=\{0,1,...,N\}$ such that integer $m\in P$ is sampled with probability $p^m$.

It is trivial to do this in time $O(N)$. I am looking for an algorithm that can perform this sampling in (expected) time proportional to the output, say $O(|S|)=O(\tfrac{1-p^{N+1}}{1-p})$.

Numerical precision is very important, and in most cases $p$ is very close to $1$ so that the expected size of the sample will remain constant as $N$ increases.

If the sampling probability were constant I could use a Poisson distribution to "jump" over unsampled integers (among other methods), but in this case the probability is not constant. What do I do?

  • $\begingroup$ How about repeatedly tossing a biased coin? $\endgroup$ Aug 26, 2020 at 21:24
  • 1
    $\begingroup$ Your probability distribution is invalid, it doesn't sum to $1$. Did you mean that the probability of sampling $m$ is $p(1 - p)^{m}$, with any rest chance left to $N$? $\endgroup$
    – orlp
    Aug 26, 2020 at 21:47
  • $\begingroup$ @orlp The sample may (probably will) have multiple elements. The expected size of the sample is the sum of the probabilities of selecting each element (as in the question). $\endgroup$ Aug 26, 2020 at 23:26
  • $\begingroup$ @elbrunovsky Ah, I see. $\endgroup$
    – orlp
    Aug 26, 2020 at 23:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.