TAOCP 4.1 Exercise 8
Equation (5) asserts that a distribution function $F(x)$ is monotonically nondecreasing, with $F(x_1) \le F(x_2) \quad \text{if } x_1 \le x_2; \qquad F(-\infty) = 0, \quad F(+\infty) = 1.$ By definiti...
Section 4.1: Positional Number Systems
Exercise 8. [**] [M10] Prove Eq. (5).
Verified: yes
Solve time: 1m09s
Equation (5) asserts that a distribution function $F(x)$ is monotonically nondecreasing, with
$F(x_1) \le F(x_2) \quad \text{if } x_1 \le x_2; \qquad F(-\infty) = 0, \quad F(+\infty) = 1.$
By definition, $F(x) = \Pr{X \le x}$, which is the probability that the random variable $X$ takes a value less than or equal to $x$. If $x_1 \le x_2$, then the event ${X \le x_1}$ is a subset of the event ${X \le x_2}$, because any outcome satisfying $X \le x_1$ automatically satisfies $X \le x_2$. Since probabilities are nonnegative and additive on nested events, it follows that $F(x_1) \le F(x_2)$.
Furthermore, as $x \to -\infty$, no outcome satisfies $X \le x$, so $F(-\infty) = 0$. As $x \to +\infty$, all outcomes satisfy $X \le x$, so $F(+\infty) = 1$. This completes the proof.
∎