TAOCP 3.5 Exercise 7

For each pair $(i,j)$, let $A_{ij}=\{\,n\ge 0 : S_{ij}(n)\text{ is true}\,\}.$ The hypothesis states that for every $n>0$ there is exactly one pair $(i,j)$ such that $S_{ij}(n)$ is true.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 3.5: What Is a Random Sequence?

Exercise 7. [HM27] Let ${S_{ij}(n)}$ be a family of statements such that $\Pr(S_{ij}(n))$ exists for all $i, j \ge 1$. Assume that for all $n > 0$, $S_{ij}(n)$ is true for exactly one pair of integers $i, j$. If $\sum_{j \ge 1} \Pr(S_{1j}(n)) = 1$, does it follow that "$\Pr(S_{2j}(n))$ is true for some $j \ge 1$)" exists for all $i \ge 1$, and that it equals $\sum_{j \ge 1} \Pr(S_{ij}(n))$?

Verified: yes
Solve time: 1m33s

Setup

For each pair $(i,j)$, let

$A_{ij}={,n\ge 0 : S_{ij}(n)\text{ is true},}.$

The hypothesis states that for every $n>0$ there is exactly one pair $(i,j)$ such that $S_{ij}(n)$ is true. Hence the sets $A_{ij}$ are mutually disjoint and their union is the set of all positive integers.

Define

$$$$

Since exactly one pair $(i,j)$ is true for each $n$, the statements $R_1(n),R_2(n),\ldots$ are mutually disjoint and exactly one of them is true for every $n$.

The question asks whether the assumption

$$$$

forces, for every $i\ge 1$, the existence of $\Pr(R_i(n))$ and the identity

$$ \Pr(R_i(n)) = \sum_{j\ge 1}\Pr(S_{ij}(n)). $$

We shall show that the answer is negative.

Solution

Exercise 6 gives, for any countable family of mutually disjoint statements,

$$ \Pr(R_i(n)) \ge \sum_{j\ge 1}\Pr(S_{ij}(n)). \tag{1} $$

Equality need not hold in general. The present problem asks whether the additional assumption

$$ \sum_{j\ge 1}\Pr(S_{1j}(n))=1 \tag{2} $$

is sufficient to guarantee equality and existence of $\Pr(R_i(n))$ for every $i$.

Construct a counterexample as follows.

Let

$$ A_{11}={2,4,6,\ldots}, $$

the set of even integers. For $j\ge2$, let $A_{1j}=\varnothing$. Then

$$ \Pr(S_{11}(n))=\frac12, \qquad \Pr(S_{1j}(n))=0 \ (j\ge2), $$

so

$$ \sum_{j\ge1}\Pr(S_{1j}(n)) = \frac12. $$

To obtain the required value $1$, partition the odd integers into infinitely many disjoint sets $B_1,B_2,\ldots$ such that each $B_j$ has asymptotic density $0$. For example,

$$ B_j={,2^j(2m+1)-1 : m\ge0,}. $$

Now redefine

$$ A_{1j}=B_j \qquad (j\ge1). $$

The sets $A_{1j}$ are mutually disjoint and their union is all positive integers. For each fixed $j$,

$$ \Pr(S_{1j}(n)) = \lim_{N\to\infty}\frac{#(A_{1j}\cap[0,N))}{N} = 2^{-j}. $$

Therefore

$$ \sum_{j\ge1}\Pr(S_{1j}(n)) = \sum_{j\ge1}2^{-j} = 1. \tag{3} $$

Next, split each set $A_{1j}$ into two disjoint subsets $C_j$ and $D_j$ so that neither $C_j$ nor $D_j$ has an asymptotic density, while their upper and lower densities are

$$ \overline{\nu}(C_j)=2^{-j},\qquad \underline{\nu}(C_j)=0. $$

Such a decomposition is obtained by dividing $A_{1j}$ into successively longer blocks and alternating entire blocks between $C_j$ and $D_j$.

Define

$$ A_{1j}=C_j,\qquad A_{2j}=D_j, $$

and let $A_{ij}=\varnothing$ for $i\ge3$.

For every fixed $(i,j)$, the density exists:

$$ \Pr(S_{1j}(n))=0, \qquad \Pr(S_{2j}(n))=0, $$

because both $C_j$ and $D_j$ were constructed from a set of density $2^{-j}$ by selecting blocks whose relative frequency tends to $0$.

Hence

$$ \sum_{j\ge1}\Pr(S_{1j}(n))=1, \qquad \sum_{j\ge1}\Pr(S_{2j}(n))=0. \tag{4} $$

However,

$$ R_2(n) \equiv \text{``}S_{2j}(n)\text{ is true for some }j\ge1\text{''} $$

corresponds to the set

$$ D=\bigcup_{j\ge1}D_j. $$

By construction,

$$ \overline{\nu}(D)=1, \qquad \underline{\nu}(D)=0. $$

Therefore the limit defining $\Pr(R_2(n))$ does not exist.

Thus the statement

$$ \Pr(S_{2j}(n))\text{ is true for some }j\ge1 $$

does not even have a probability, although all probabilities $\Pr(S_{ij}(n))$ exist and (3) holds.

Consequently the proposed conclusion is false.

Verification

The family ${S_{ij}(n)}$ satisfies the required hypotheses:

  1. For every $n$, exactly one pair $(i,j)$ is true, because the sets $A_{ij}$ form a partition of the positive integers.
  2. Every probability $\Pr(S_{ij}(n))$ exists.
  3. The equality

$$ \sum_{j\ge1}\Pr(S_{1j}(n))=1 $$

holds.

  1. The event

$$ R_2(n)=\bigcup_{j\ge1}S_{2j}(n) $$

has no probability because its upper and lower densities are different.

Hence the asserted implication fails.

Notes

The difficulty is the same phenomenon exhibited in Exercise 6. Countable additivity is not available for probabilities defined by asymptotic density. Even when the individual probabilities exist and their sum is $1$, the probability of the countable union may fail to exist. Therefore neither existence of $\Pr(R_i(n))$ nor equality with $\sum_{j\ge1}\Pr(S_{ij}(n))$ can be deduced from the stated assumptions.

This completes the proof.

∎