TAOCP 3.4.1 Exercise 1

Let $U$ be a random variable uniformly distributed between 0 and 1.

taocpmathematicsalgorithmsvolume-2simple

Section 3.4.1: Numerical Distributions

Exercise 1. [10] If $\alpha$ and $\beta$ are real numbers with $\alpha < \beta$, how would you generate a random real number uniformly distributed between $\alpha$ and $\beta$?

Verified: yes
Solve time: 1m09s

Let $U$ be a random variable uniformly distributed between 0 and 1. To transform $U$ into a random variable $X$ uniformly distributed between $\alpha$ and $\beta$, we apply an affine mapping that stretches and shifts the interval $[0,1]$ to $[\alpha, \beta]$. Specifically, set

$X \leftarrow \alpha + (\beta - \alpha) U.$

This assignment requires exactly one replacement operation.

The probability that $X \le x$ for any $\alpha \le x \le \beta$ is

$\Pr{X \le x} = \Pr{\alpha + (\beta - \alpha) U \le x} = \Pr{U \le (x - \alpha)/(\beta - \alpha)} = \frac{x - \alpha}{\beta - \alpha},$

which is the distribution function of a uniform random variable on $[\alpha, \beta]$. This completes the proof.

∎

$\boxed{X \leftarrow \alpha + (\beta - \alpha) U}$