= Sampling a discrete uniform distribution
{title2=$X=x_{1+\lfloor nU\rfloor}$}
Let the numerical <support of a probability distribution> be $x_1<\cdots<x_n$. Its <cumulative distribution function> counts how many values have been passed:
$$
F_X(t)=\mathbb P(X\leq t)=\frac{|\{x\in S:x\leq t\}|}{n}.
$$
It is zero below $x_1$, equals $j/n$ on $x_j\leq t<x_{j+1}$ for $1\leq j<n$, and is one at and above $x_n$. Every jump is $1/n$, even when the horizontal gaps differ.
For <inverse transform sampling>, take an ideal <continuous uniform distribution> for $U$ on $[0,1)$. Partition that <interval> into $n$ <intervals> of width $1/n$ and output
$$
X=x_j\quad\text{when}\quad\frac{j-1}{n}\leq U<\frac{j}{n},\qquad j=1,\ldots,n.
$$
Each <interval> has <probability> $1/n$, proving the desired <discrete uniform distribution>. Using the <floor function>, the index is $j=1+\lfloor nU\rfloor$; for consecutive <integer> values the output is $X=a+\lfloor nU\rfloor$. With the usual <quantile function> convention $Q(u)=\inf\{t:F_X(t)\geq u\}$, one instead writes $Q(u)=x_{\lceil nu\rceil}$ for $0<u\leq1$, using the <ceiling function>. The endpoint conventions differ only at a finite <set> of points with <probability> zero under the ideal <continuous uniform distribution>.
For $S=\{1,2,4,8\}$, the four <intervals> $[0,1/4)$, $[1/4,1/2)$, $[1/2,3/4)$, and $[3/4,1)$ select $1,2,4,8$, respectively. Thus $U=3/10$ selects $2$, while $U=9/10$ selects $8$. The upper half of the <interval> selects values at least four, recovering <probability> $1/2$. Equal widths refer to the sampling <probability> coordinate, not to distances between output values. This is an exact mathematical construction assuming an ideal <continuous uniform distribution>; a finite computer random-number source needs its own justification of equal output chances.
Back to article page
