TAOCP 3.5 Exercise 12

Section 3.5: What Is a Random Sequence?

Exercise 12. [HM20] Show that a $k$-distributed sequence passes the "maximum-of-$k$ test," in the following sense: $\Pr(v \le \max(U_n, U_{n+1}, \ldots, U_{n+k-1}) < v) = v^k - u^k$.

Verified: yes
Solve time: 1m07s

Solution

Let

$$ M_n=\max(U_n,U_{n+1},\ldots,U_{n+k-1}). $$

We must prove that for every $0\le u<v\le1$,

$$ \Pr(u\le M_n<v)=v^k-u^k. $$

The event $M_n<v$ occurs exactly when each of the $k$ terms is less than $v$:

$$ M_n<v \iff U_n<v,\ U_{n+1}<v,\ \ldots,\ U_{n+k-1}<v. $$

Since the sequence is $k$-distributed, Definition B with

$$ u_1=\cdots=u_k=0,\qquad v_1=\cdots=v_k=v $$

gives

$$ \Pr(M_n<v) = \Pr(0\le U_n<v,\ldots,0\le U_{n+k-1}<v) = v^k. $$

Similarly,

$$ M_n<u \iff U_n<u,\ U_{n+1}<u,\ \ldots,\ U_{n+k-1}<u, $$

hence

$$ \Pr(M_n<u) = u^k. $$

Now

$$ u\le M_n<v $$

is the difference of the events $M_n<v$ and $M_n<u$. Therefore

$$ \Pr(u\le M_n<v) = \Pr(M_n<v)-\Pr(M_n<u) = v^k-u^k. $$

Thus a $k$-distributed sequence passes the maximum-of-$k$ test:

$$ \boxed{\Pr!\bigl(u\le \max(U_n,U_{n+1},\ldots,U_{n+k-1})<v\bigr)=v^k-u^k.} $$

This completes the proof.

∎