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
The algorithm is this

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

•
let $x\leftarrow 1$

•
while $n_{1}+n_{2}+...+n_{x}<k$ 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<n_{1}$ that the value output will be $n_{1}$ (as $n_{1}<n_{1}$ so we will return $x=1$) and there are $n_{1}$ integer values in the range $1\leq k<n_{1}$.
In the more general case that for $n_{i}$ we will output $x=i$ provided that $k\geq n_{1}+...+n_{i1}$ and $k<n_{1}+...+n_{i}$, as these are the values of $k$ for which $i1$ is the greatest value for which $n_{1}+n_{2}+...+n_{i1}<n_{i}$, so we will increment $x$ a total of $i1$ times, and thus we will return $x=1+i1=i$. As we are after, there are $n_{i}$ values in this interval.