TAOCP 3.5 Exercise 33

Section 3.5: What Is a Random Sequence?

Exercise 33. [HM22] [HM22] Let $\langle U_n \rangle$ and $\langle t_n \rangle$ be infinite disjoint subsequences of a sequence $\langle U_n \rangle$. (Thus, $r_0 < r_1 < r_2 < \cdots$ and $s_0 < s_1 < s_2 < \cdots$ are increasing sequences of integers and $r_m \ne s_n$ for any $m, n$.) Let $\langle U_{t_n} \rangle$ be the combined subsequence, so that $t_0 < t_1 < t_2 < \cdots$ and the set ${t_n} = {r_n} \cup {s_n}$. Show that if $\Pr{U_{r_n} \in A} = \Pr{U_{s_n} \in A} = p$, then $\Pr{U_{t_n} \in A} = p$.

Verified: yes
Solve time: 2m37s

Solution

Let ${U_n}$ be an infinite sequence, and let ${r_n}$ and ${s_n}$ be strictly increasing sequences of integers with no common elements, so that the subsequences ${U_{r_n}}$ and ${U_{s_n}}$ are disjoint. Define ${t_n}$ to be the strictly increasing sequence enumerating all integers in ${r_n} \cup {s_n}$. Denote by $A$ a fixed measurable subset of $[0,1)$, and assume that

$\Pr{U_{r_n} \in A} = \Pr{U_{s_n} \in A} = p$

in the sense of Definition A.

Let $\nu_R(N)$ be the number of $j < N$ such that $U_{r_j} \in A$, and similarly let $\nu_S(N)$ be the number of $j < N$ such that $U_{s_j} \in A$. By hypothesis we have

$\lim_{N \to \infty} \frac{\nu_R(N)}{N} = \lim_{N \to \infty} \frac{\nu_S(N)}{N} = p. \eqno(1)$

Let $\nu_T(N)$ be the number of $j < N$ such that $U_{t_j} \in A$. Since ${t_n} = {r_n} \cup {s_n}$, each $t_j$ comes from exactly one of the sequences ${r_n}$ or ${s_n}$. Denote by $R(N)$ the number of elements of ${r_n}$ less than $t_N$, and by $S(N)$ the number of elements of ${s_n}$ less than $t_N$. Then $R(N) + S(N) = N$, and $\nu_T(N) = \nu_R(R(N)) + \nu_S(S(N))$.

Dividing both sides by $N$ gives

$\frac{\nu_T(N)}{N} = \frac{R(N)}{N} \cdot \frac{\nu_R(R(N))}{R(N)} + \frac{S(N)}{N} \cdot \frac{\nu_S(S(N))}{S(N)}.$

As $N \to \infty$, both $R(N)/N$ and $S(N)/N$ approach limits in $[0,1]$ such that $R(N)/N + S(N)/N \to 1$, because the sequences ${r_n}$ and ${s_n}$ are infinite and disjoint. Moreover, by equation (1), we have

$\lim_{R \to \infty} \frac{\nu_R(R)}{R} = p, \qquad \lim_{S \to \infty} \frac{\nu_S(S)}{S} = p.$

Hence, taking the limit as $N \to \infty$ yields

$\lim_{N \to \infty} \frac{\nu_T(N)}{N} = \lim_{N \to \infty} \left[ \frac{R(N)}{N} \cdot p + \frac{S(N)}{N} \cdot p \right] = p \left( \lim_{N \to \infty} \frac{R(N)}{N} + \lim_{N \to \infty} \frac{S(N)}{N} \right) = p.$

Therefore, the combined subsequence ${U_{t_n}}$ satisfies

$\Pr{U_{t_n} \in A} = p,$

as required. This completes the proof.

∎