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

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_{i-1}$ and $k<n_{1}+...+n_{i}$, as these are the values of $k$ for which $i-1$ is the greatest value for which $n_{1}+n_{2}+...+n_{i-1}<n_{i}$, 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.