TAOCP 5 Exercise 9

Section 5: Introduction to Sorting

Exercise 9. [M27] After $N$ independent, uniformly distributed random variables between 0 and 1 have been sorted into nondecreasing order, what is the probability that the $r$th smallest of these numbers is $\le x$?

Each of the following exercises states a problem that a computer programmer might have had to solve in the old days when computers didn't have much random-access memory. Suggest a "good" way to solve the problem, assuming that only a few thousand words of internal memory are available, supplemented by about half a dozen tape units (enough tape units for sorting); solutions that work well under such limitations also prove to be efficient on modern machines.

Verified: yes
Solve time: 6m33s

Setup

Let (X_1, X_2, \ldots, X_N) be independent random variables, each uniformly distributed on ([0,1]).
After sorting these variables into nondecreasing order we obtain the order statistics

[ X_{(1)} \le X_{(2)} \le \cdots \le X_{(N)}. ]

The exercise asks for (\Pr!\bigl(X_{(r)} \le x\bigr)), where (1 \le r \le N) and (x) is a real number.

Solution

For a fixed (x) with (0 \le x \le 1), each variable satisfies (\Pr(X_i \le x) = x).
The event ({X_{(r)} \le x}) means that at least (r) of the (N) variables are (\le x).
Because the variables are independent, the number of variables that fall in ([0,x]) follows a binomial distribution with parameters (N) and (x). Hence

[ \Pr!\bigl(X_{(r)} \le x\bigr) = \sum_{k=r}^{N} \binom{N}{k} x^{k} (1-x)^{N-k}, \qquad 0 \le x \le 1. ]

For completeness we extend the definition to all real (x):

[ \Pr!\bigl(X_{(r)} \le x\bigr) = \begin{cases} 0, & x < 0,\[4pt] \displaystyle\sum_{k=r}^{N} \binom{N}{k} x^{k} (1-x)^{N-k}, & 0 \le x \le 1,\[12pt] 1, & x > 1. \end{cases} ]

This is the required probability.

Verification

We check the formula by two independent methods.

1. Boundary cases

   • For (r = 1) (the minimum): (\Pr(X_{(1)} \le x) = 1 - \Pr(\text{all } X_i > x) = 1 - (1-x)^N).
     The sum from (k=1) to (N) equals (1 - \binom{N}{0}x^0(1-x)^N = 1 - (1-x)^N). ✓
   • For (r = N) (the maximum): (\Pr(X_{(N)} \le x) = \Pr(\text{all } X_i \le x) = x^N).
     The sum from (k=N) to (N) is (\binom{N}{N}x^N = x^N). ✓

2. Beta‑integral identity
   The cumulative distribution function of the (r)‑th order statistic of (N) i.i.d. uniform variables is known to be the regularized incomplete beta function:

   [ \Pr!\bigl(X_{(r)} \le x\bigr) = I_x(r,, N-r+1) = \frac{1}{\mathrm{B}(r,, N-r+1)} \int_0^x t^{r-1}(1-t)^{N-r},dt. ]

   Integrating by parts repeatedly, or using the well‑known identity

   [ I_x(r,, N-r+1) = \sum_{k=r}^{N} \binom{N}{k} x^{k} (1-x)^{N-k}, ]

   shows that our binomial sum equals the beta integral. This confirms the formula for all (0 \le x \le 1).

Both checks agree with the derived expression, and the piecewise definition handles the trivial cases (x<0) and (x>1) correctly.

∎

Notes

The probability is the tail of a binomial distribution; it can also be expressed in terms of the incomplete beta function. In the context of sorting, this result is often used to analyze the distribution of the (r)‑th element after a random permutation or to study the behavior of selection algorithms.