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

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

<p>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. </p>

CC BY-SA 3.0
2017-09-09T22:00:15.210Z
What sort of random number generator are you assuming access to?
Aryeh
CC BY-SA 3.0
2017-09-09T22:22:40.487Z
@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.
verifying
<reference-request><sample-complexity>
Complexity of Proportional Sampling
verifying
# Complexity of Proportional Sampling

(Asked by: username_0 on 2017-09-09)

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.

**Tags:** reference-request, sample-complexity
> **Comments:**
> **username_1**: What sort of random number generator are you assuming access to?  
> **username_0**: @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.  

---

## 0 answers

