Let $p_1,...,p_n$ be a list of numbers, each specified by $n^{O(1)}$ bits. Let $\mu = \sum_{i} p_i$ be the sum of all numbers in the list. I want to sample from the set $\{1,...,n\}$ where each $j$ is drawn with probability $p_j/\mu$.

I'm looking for a reference where the complexity of this problem is analyzed explicitly taking the bit size of the numbers into consideration?

I was only able to find references where the numbers $p_j$ are treated as ideal real numbers. In this case, on a turing machine operating over the reals, the complexity seems to be $O(n)$ pre-processing time and $O(\log n)$ per sample.

  • $\begingroup$ What sort of random number generator are you assuming access to? $\endgroup$ – Aryeh Sep 9 '17 at 22:00
  • $\begingroup$ @Aryeh To be honest I have no idea of how the choice of random number generators will affect the answer. So my answer to your question would be the generator that gives the best upper bound. On the other hand, if this is cheating, then I would be happy to assume a generator which flips a coin with 1/2 probability of getting 0 and 1/2 probability of getting 1. $\endgroup$ – verifying Sep 9 '17 at 22:22

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.