# 32.2 Weighted uniform sampling

Most computer programming languages provide a primitive which allows us to sample uniformly a random integer in the range $[1,N]$ for any given natural number $N$.

###### Theorem 32.2.1

Let $S=\{n_{1},...,n_{t}\}$ be a set of natural numbers and $N=n_{1}+n_{2}+...+n_{t}$. Then there exists an $O(n)$ algorithm to sample an $n\in S$ according to its weighting in the set. That is, if $X$ is the random variable for which of the objects, then

$\Pr[X=t]=n_{t}/N_{i}$ (32.1)

The algorithm is this

• sample $k\in[1,N]$

• let $x\leftarrow 1$

• while $n_{1}+n_{2}+...+n_{x} increment $X$ by 1

• return $x$

To prove that this algorithm satisfies the condition, we can check how many different values of $k$ are associated with each $n_{i}$.

First we can examine an easier case, before tackling the more general one.

For $n_{1}$ we know that if $1\leq k that the value output will be $n_{1}$ (as $n_{1} so we will return $x=1$) and there are $n_{1}$ integer values in the range $1\leq k.

In the more general case that for $n_{i}$ we will output $x=i$ provided that $k\geq n_{1}+...+n_{i-1}$ and $k, as these are the values of $k$ for which $i-1$ is the greatest value for which $n_{1}+n_{2}+...+n_{i-1}, so we will increment $x$ a total of $i-1$ times, and thus we will return $x=1+i-1=i$. As we are after, there are $n_{i}$ values in this interval.