TAOCP 3.5 Exercise 4

Let A(n)=S(n)\text{ and }T(n),\qquad B(n)=S(n)\text{ or }T(n).

taocpmathematicsalgorithmsvolume-2hm-simple

Section 3.5: What Is a Random Sequence?

Exercise 4. ▶ [HM14] Prove that $\Pr(S(n)$ and $T(n)) + \Pr(S(n)$ or $T(n)) = \Pr(S(n)) + \Pr(T(n))$, when $S$ and $T$ are any two statements and at least one of the limits exist. For example, if a sequence is 2-distributed, we would find that

$$\Pr(u_n \le U_n < v_1 \text{ or } u_2 \le U_{n+1} < v_2) = v_1 - u_1 + v_2 - u_2 - (v_1 - u_1)(v_2 - u_2).$$

Verified: yes
Solve time: 1m15s

Solution

Let

$$ A(n)=S(n)\text{ and }T(n),\qquad B(n)=S(n)\text{ or }T(n). $$

For each integer $N>0$, let

$$ \nu_A(N),\quad \nu_B(N),\quad \nu_S(N),\quad \nu_T(N) $$

denote the number of integers $j$, $0\le j<N$, for which $A(j)$, $B(j)$, $S(j)$, and $T(j)$ are true, respectively.

For every $j$, exactly one of the following three possibilities occurs:

  1. $S(j)$ and $T(j)$ are both true;
  2. $S(j)$ is true and $T(j)$ is false;
  3. $S(j)$ is false and $T(j)$ is true.

Hence each occurrence counted by $\nu_S(N)$ or $\nu_T(N)$ is counted once in $\nu_B(N)$, except that occurrences where both statements are true are counted twice. Therefore

$$ \nu_S(N)+\nu_T(N)=\nu_A(N)+\nu_B(N). $$

Dividing by $N$,

$$ \frac{\nu_S(N)}{N}+\frac{\nu_T(N)}{N} = \frac{\nu_A(N)}{N}+\frac{\nu_B(N)}{N}. \tag{1} $$

Assume that at least one of the limits $\Pr(S(n))$ or $\Pr(T(n))$ exists. Without loss of generality, suppose $\Pr(S(n))$ exists. Then

$$ \frac{\nu_A(N)}{N} = \frac{\nu_S(N)}{N} +\frac{\nu_T(N)}{N} -\frac{\nu_B(N)}{N}. $$

Taking $\limsup$ and $\liminf$, and using the existence of

$$ \lim_{N\to\infty}\frac{\nu_S(N)}{N} =\Pr(S(n)), $$

gives

$$ \overline{\nu}(A) = \Pr(S(n)) +\overline{\nu}(T) -\overline{\nu}(B), $$

and

$$ \underline{\nu}(A) = \Pr(S(n)) +\underline{\nu}(T) -\underline{\nu}(B). $$

Subtracting,

$$ \overline{\nu}(A)-\underline{\nu}(A) = \bigl(\overline{\nu}(T)-\underline{\nu}(T)\bigr) - \bigl(\overline{\nu}(B)-\underline{\nu}(B)\bigr). \tag{2} $$

Interchanging the roles of $A$ and $B$ in (1) yields

$$ \overline{\nu}(B)-\underline{\nu}(B) = \bigl(\overline{\nu}(T)-\underline{\nu}(T)\bigr) - \bigl(\overline{\nu}(A)-\underline{\nu}(A)\bigr). \tag{3} $$

Adding (2) and (3),

$$ \overline{\nu}(A)-\underline{\nu}(A) = \overline{\nu}(B)-\underline{\nu}(B). $$

Substituting this equality into (2),

$$ 2\bigl(\overline{\nu}(A)-\underline{\nu}(A)\bigr)=0. $$

Therefore

$$ \overline{\nu}(A)=\underline{\nu}(A), \qquad \overline{\nu}(B)=\underline{\nu}(B). $$

Thus both probabilities $\Pr(A)$ and $\Pr(B)$ exist. Taking limits in (1) gives

$$ \Pr(A)+\Pr(B)=\Pr(S(n))+\Pr(T(n)). $$

Since $A(n)$ is the statement $S(n)$ and $T(n)$, and $B(n)$ is the statement $S(n)$ or $T(n)$,

$$ \boxed{ \Pr(S(n)\text{ and }T(n)) + \Pr(S(n)\text{ or }T(n)) = \Pr(S(n)) + \Pr(T(n)) }. $$

For the example, let

$$ S(n):\ u_1\le U_n<v_1, \qquad T(n):\ u_2\le U_{n+1}<v_2. $$

If the sequence is $2$-distributed, Definition B gives

$$ \Pr(S(n))=v_1-u_1, \qquad \Pr(T(n))=v_2-u_2, $$

and

$$ \Pr(S(n)\text{ and }T(n)) =(v_1-u_1)(v_2-u_2). $$

Hence

$$ \Pr(S(n)\text{ or }T(n)) = (v_1-u_1)+(v_2-u_2) -(v_1-u_1)(v_2-u_2). $$

Therefore

$$ \boxed{ \Pr(u_1\le U_n<v_1 \text{ or } u_2\le U_{n+1}<v_2) = v_1-u_1+v_2-u_2-(v_1-u_1)(v_2-u_2) }. $$

This completes the proof.

∎