# Inverse sampling for discrete data [duplicate]

I have to pick a ball from a set of balls. Each ball has a size, so I have a distribution for ball sizes (I assume a number between 0-1).

I want to pick a new ball at each step with the probability associated with its size. I have read about Inverse transform sampling. But I wasn't able to find any numerical example. All I could find were some well known distributions, that are always reversible, however in my example two or more balls can have the same size. I'm not able to understand how to move forward.

Any help is greatly appreciated.

• Welcome to CV! For clarity, is it correct that you have a set of balls, all with known sizes? Dec 18, 2014 at 2:42
• yes the sizes are known. Dec 18, 2014 at 2:44

Given the sizes of the balls, and that probability of each ball being drawn is a known function of size, you can partition $(0,1)$ appropriately and map a series of random uniform draws to this partition. (You'll also have to make sure these probabilities properly sum to $1$.)

For instance, say you have 3 balls with $p_1 = \frac{1}{2}, p_2 = \frac{1}{3}, p_3 =\frac{1}{6}$. This would give the partitions $(0, \frac{1}{2}), (\frac{1}{2}, \frac{5}{6}), (\frac{5}{6}, 1)$. Generate a few uniform random draws,

>>> np.random.uniform(size = 5)
array([ 0.3214321 ,  0.4209206 ,  0.72415894,  0.84439061,  0.36170096])


and then map them to the partitions. In this case, the random uniform draws above would give ball $1, 1, 2, 3, 1$.

This first page of this note details this process nicely.

• thanks for the clear answer and reference. just to double check that I got this right: if I have say two balls of size 3, note them $3_1$ and $3_2$ which have the equal probabilities of $p_{3_1}=p_{3_2}$ I should consider them as two different values now. right? Dec 18, 2014 at 6:14
• Yes that's right: They should each be represented by a separate partition, but there's no reason they can't have equal probability. Dec 18, 2014 at 11:27