Exercises

$A \cap B = \{4, 6\}$, so $\mathbb{P}(A \cap B) = 2/6 = 1/3$. $\mathbb{P}(A) = 3/6 = 1/2$, $\mathbb{P}(B) = 4/6 = 2/3$.

$\mathbb{P}(A \mid B) = \frac{1/3}{2/3} = \frac{1}{2}.KATEXPLACEHOLDER0END\mathbb{P}(B \mid A) = \frac{1/3}{1/2} = \frac{2}{3}.$$Note$\mathbb{P}(A \mid B) = \mathbb{P}(A)$here — in fact$A$and$B$are independent (as you can verify:$1/2 \times 2/3 = 1/3 = \mathbb{P}(A \cap B)$).

$\mathbb{P}(R_1) = 4/10$, $\mathbb{P}(R_1^c) = 6/10$. $\mathbb{P}(R_2 \mid R_1) = 3/9 = 1/3$, $\mathbb{P}(R_2 \mid R_1^c) = 4/9$.

$\mathbb{P}(R_2) = \frac{4}{10}\cdot\frac{3}{9} + \frac{6}{10}\cdot\frac{4}{9} = \frac{12}{90} + \frac{24}{90} = \frac{36}{90} = \frac{2}{5}.$$The answer is$2/5 = 4/10$: by symmetry, each ball is equally likely to be red regardless of draw position.

$\mathbb{P}(A \mid B) = \mathbb{P}(A \cap B)/\mathbb{P}(B) \geq 0$ since $\mathbb{P}(A \cap B) \geq 0$ and $\mathbb{P}(B) > 0$.

$\mathbb{P}(\Omega \mid B) = \mathbb{P}(\Omega \cap B)/\mathbb{P}(B) = \mathbb{P}(B)/\mathbb{P}(B) = 1$.

For pairwise disjoint events $A_1, A_2, \ldots$: $$\mathbb{P}\!\left(\bigcup_i A_i \,\Big|\, B\right) = \frac{\mathbb{P}(\bigcup_i A_i \cap B)}{\mathbb{P}(B)} = \frac{\mathbb{P}(\bigcup_i (A_i \cap B))}{\mathbb{P}(B)} = \frac{\sum_i \mathbb{P}(A_i \cap B)}{\mathbb{P}(B)} = \sum_i \mathbb{P}(A_i \mid B). \quad\blacksquare$$

$\mathbb{P}(S_4 = 3) = \binom{4}{3}(1/2)^3(1/2)^1 = 4 \times 1/16 = 1/4$.

Outcomes with exactly 3 heads: HHHT, HHTH, HTHH, THHH. That is 4 outcomes out of 16 equally likely outcomes. $\mathbb{P} = 4/16 = 1/4$. ✓

$\mathbb{P}(T = 5) = (1-0.2)^{5-1} \times 0.2 = 0.8^4 \times 0.2 = 0.4096 \times 0.2 = 0.08192$.

$\mathbb{E}[T] = 1/p = 1/0.2 = 5$ trials.

$A = (A \cap B) \cup (A \cap B^c)$, with the two pieces disjoint. So $\mathbb{P}(A) = \mathbb{P}(A \cap B) + \mathbb{P}(A \cap B^c)$.

Since $A \perp B$: $\mathbb{P}(A \cap B^c) = \mathbb{P}(A) - \mathbb{P}(A \cap B) = \mathbb{P}(A) - \mathbb{P}(A)\mathbb{P}(B) = \mathbb{P}(A)(1 - \mathbb{P}(B)) = \mathbb{P}(A)\mathbb{P}(B^c)$. $\blacksquare$

$\mathbb{P}(Y=0 \mid X=0) = 1-\epsilon$, $\mathbb{P}(Y=1 \mid X=0) = \epsilon$. $\mathbb{P}(Y=0 \mid X=1) = \epsilon$, $\mathbb{P}(Y=1 \mid X=1) = 1-\epsilon$.

Decide $X=0$ if $\mathbb{P}(X=0 \mid Y=0) > \mathbb{P}(X=1 \mid Y=0)$, i.e., $(1-\epsilon)\pi_0 > \epsilon(1-\pi_0)$, which gives $\pi_0(1-2\epsilon) > \epsilon - \pi_0\cdot 0$, equivalently $\pi_0 > \epsilon/(1-2\epsilon+2\epsilon) = \epsilon/(1)$...

More cleanly: decide $X=0$ iff $(1-\epsilon)\pi_0 > \epsilon(1-\pi_0)$, i.e., iff $\pi_0 > \epsilon$. For $\pi_0 > \epsilon$ the MAP detector decides $\hat{X}=Y$ (output equals received bit).

When $\pi_0 = 1/2$, Bayes' theorem gives $\mathbb{P}(X \mid Y) \propto \mathbb{P}(Y \mid X)$ since the prior is constant. MAP $\equiv$ ML: choose the $x$ maximizing the likelihood $\mathbb{P}(Y \mid X=x)$.

$\mathbb{P}(X=0 \mid Y=0) = \frac{(1-\epsilon)\pi_0}{(1-\epsilon)\pi_0 + \epsilon(1-\pi_0)}.$$For$\pi_0 = 1/2$:$\mathbb{P}(X=0 \mid Y=0) = (1-\epsilon)/(1) = 1-\epsilon$.

Let $Q(\cdot) = \mathbb{P}(\cdot \mid C)$. By assumption $Q(A \cap B) = Q(A)Q(B)$. We want to show $Q(A^c \cap B) = Q(A^c)Q(B)$.

$Q(B) = Q(A \cap B) + Q(A^c \cap B)$, so $Q(A^c \cap B) = Q(B) - Q(A \cap B) = Q(B) - Q(A)Q(B) = (1-Q(A))Q(B) = Q(A^c)Q(B)$. So $A^c \perp B \mid C$. $\blacksquare$

On days machine A runs (40% of days): two items produced, one by each machine. On days only B runs (60% of days): one item produced. In a population of 140 items per 100 days: 40 from A, 100 from B. So $\mathbb{P}(\text{from A}) = 40/140 = 2/7$ and $\mathbb{P}(\text{from B}) = 100/140 = 5/7$.

$\mathbb{P}(D) = 0.01 \times \frac{2}{7} + 0.05 \times \frac{5}{7} = \frac{0.02 + 0.25}{7} = \frac{0.27}{7} \approx 0.0386.$$

$\mathbb{P}(\text{from A} \mid D) = \frac{0.01 \times 2/7}{0.27/7} = \frac{0.02}{0.27} \approx 0.074.$$ Despite machine A having a lower defect rate, it contributes only about 7.4% of defective items because it produces fewer items.

$\{T > k\}$ = "first $k$ trials are all failures" = $\{X_1=0, \ldots, X_k=0\}$. By independence: $\mathbb{P}(T > k) = (1-p)^k$.

$\{T > m+n\} \subseteq \{T > m\}$, so $\{T > m+n\} \cap \{T > m\} = \{T > m+n\}$. $$\mathbb{P}(T > m+n \mid T > m) = \frac{\mathbb{P}(T > m+n)}{\mathbb{P}(T > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \mathbb{P}(T > n). \quad\blacksquare$$

$\Omega = \{1,2,3,4\}$ with $\mathbb{P}(\{k\}) = 1/4$. $A = \{1,2\}$, $B = \{1,3\}$, $C = \{1,4\}$. $\mathbb{P}(A) = \mathbb{P}(B) = \mathbb{P}(C) = 1/2$.

$A \cap B = \{1\}$, $\mathbb{P}(A \cap B) = 1/4 = \mathbb{P}(A)\mathbb{P}(B)$. ✓ $A \cap C = \{1\}$, $\mathbb{P}(A \cap C) = 1/4 = \mathbb{P}(A)\mathbb{P}(C)$. ✓ $B \cap C = \{1\}$, $\mathbb{P}(B \cap C) = 1/4 = \mathbb{P}(B)\mathbb{P}(C)$. ✓

$A \cap B \cap C = \{1\}$, $\mathbb{P}(A \cap B \cap C) = 1/4$. But $\mathbb{P}(A)\mathbb{P}(B)\mathbb{P}(C) = 1/8 \neq 1/4$. So $A$, $B$, $C$ are not mutually independent. $\blacksquare$

From the proof in Theorem TMarkov Chain Implies Conditional Independence: $\mathbb{P}(A \cap C \mid B) = \mathbb{P}(A \mid B)\mathbb{P}(C \mid B)$.

The condition $\mathbb{P}(A \cap C \mid B) = \mathbb{P}(A \mid B)\mathbb{P}(C \mid B)$ is symmetric in $A$ and $C$: it also reads $C \perp A \mid B$. This is the Markov condition for $C \multimap B \multimap A$. $\blacksquare$

$\mathbb{P}(X=+1 \mid Y=y) \propto f(y \mid +1) \cdot 1/2 = \frac{1}{\sigma\sqrt{2\pi}}e^{-(y-1)^2/(2\sigma^2)} \cdot 1/2$. Similarly for $X=-1$.

Decide $+1$ if $f(y \mid +1) > f(y \mid -1)$: $$e^{-(y-1)^2/(2\sigma^2)} > e^{-(y+1)^2/(2\sigma^2)}$$ $$(y-1)^2 < (y+1)^2 \quad\Leftrightarrow\quad -4y < 0 \quad\Leftrightarrow\quad y > 0.$$ So $\hat{x} = \text{sign}(Y)$, the minimum distance decoder. $\blacksquare$

$\{T_r = k\}$ = {exactly $r-1$ successes in trials $1,\ldots,k-1$} $\cap$ {trial $k$ is a success}.

By the binomial formula, the first event has probability $\binom{k-1}{r-1}p^{r-1}(1-p)^{k-r}$. The second event (trial $k$ is a success) has probability $p$, and is independent of all earlier trials.

$\mathbb{P}(T_r = k) = \binom{k-1}{r-1}p^{r-1}(1-p)^{k-r} \cdot p = \binom{k-1}{r-1}p^r(1-p)^{k-r}, \quad k = r, r+1, \ldots \qquad\blacksquare$$

By the first Borel-Cantelli lemma (Chapter 1): if $\sum p_n < \infty$, then $\mathbb{P}(\limsup A_n) = 0$. This holds without the independence assumption.

$\limsup A_n = \{A_n \text{ i.o.}\}$. Its complement is $\liminf A_n^c = \bigcup_{N=1}^\infty \bigcap_{n=N}^\infty A_n^c$. By continuity of probability, it suffices to show $\mathbb{P}(\bigcap_{n=N}^\infty A_n^c) = 0$ for each $N$.

By independence and $1-x \leq e^{-x}$: $$\mathbb{P}\!\left(\bigcap_{n=N}^{N+M} A_n^c\right) = \prod_{n=N}^{N+M}(1-p_n) \leq \prod_{n=N}^{N+M} e^{-p_n} = e^{-\sum_{n=N}^{N+M} p_n}.$$ Taking $M \to \infty$: since $\sum_{n=N}^\infty p_n = \infty$ (the tail of a divergent series is still infinite), the exponential $\to 0$. So $\mathbb{P}(\bigcap_{n=N}^\infty A_n^c) = 0$. $\blacksquare$

Let $m = D_1 + D_2 + D_3$ (number of "yes" votes) and $n=3$. By conditional independence of sensors given the target state: $$\mathbb{P}(H_1 \mid \mathbf{D}) = \frac{p^m(1-p)^{3-m}\cdot\pi} {p^m(1-p)^{3-m}\cdot\pi + q^m(1-q)^{3-m}\cdot(1-\pi)}.$$

Decide $H_1$ iff $\mathbb{P}(H_1 \mid \mathbf{D}) > 1/2$, i.e., iff numerator $>$ denominator: $$\left(\frac{p}{q}\right)^m \left(\frac{1-p}{1-q}\right)^{3-m} > \frac{1-\pi}{\pi}.$$ Taking $\log$ and rearranging (using $p > q$, so $\log(p/q) > 0$ and $\log((1-p)/(1-q)) < 0$): $$m \cdot \log\frac{p(1-q)}{q(1-p)} > \log\frac{(1-\pi)((1-q)/(1-p))^3}{\pi}.$$ This is a threshold $m > k^*$ for some $k^*$ determined by the priors and channel parameters. For equal priors ($\pi = 1/2$) and equal log-likelihood ratio per bit, $k^* = 3/2$, giving the majority vote rule $k = 2$: decide target present if 2 or more sensors say yes.

By independence: $\mathbb{P}(X_1^n = x_1^n) = p^{k}(1-p)^{n-k}$ where $k = \sum_i x_i$ is the number of ones.

By the weak law of large numbers (Chapter 11), $\frac{1}{n}\sum_i X_i \xrightarrow{p} p$. For any $\epsilon > 0$: $\mathbb{P}(|\frac{1}{n}\sum_i X_i - p| > \epsilon) \to 0$. Most probability mass concentrates on sequences with $k/n \approx p$.

Sequences with exactly $k = np$ ones each have probability $p^{np}(1-p)^{n(1-p)}$. There are $\binom{n}{np}$ such sequences. By Stirling: $\binom{n}{np} \approx 2^{nH(p)}$ where $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$ is the binary entropy. This is the seed of the source coding theorem.

Let $\Omega = \{(a,b) : a,b \in \{0,1\}\}$ with uniform probability $1/4$. $A = \{(1,0),(1,1)\}$ (first coordinate is 1), $B = \{(0,1),(1,1)\}$ (second coordinate is 1), $C = \{(1,0),(0,1)\}$ (exactly one coordinate is 1).

$\mathbb{P}(A) = \mathbb{P}(B) = 1/2$, $\mathbb{P}(A \cap B) = 1/4 = \mathbb{P}(A)\mathbb{P}(B)$. So $A \perp B$. ✓

$\mathbb{P}(C) = 1/2$. $\mathbb{P}(A \cap C) = \mathbb{P}(\{(1,0)\}) = 1/4$. $\mathbb{P}(A \mid C) = 1/2$, $\mathbb{P}(B \mid C) = 1/2$. $\mathbb{P}(A \cap B \mid C) = \mathbb{P}(\emptyset \cap C)/\mathbb{P}(C)= 0 \neq 1/4$. So $A$ and $B$ are NOT conditionally independent given $C$.

$C$ is a common effect of $A$ and $B$. Once we observe $C$ (one of two possible causes is active), knowing one cause is active ($A=1$) tells us the other is not ($B=0$). This "explaining away" makes $A$ and $B$ negatively correlated given $C$, even though they are independent marginally.

Let all $A_n = A$ where $\mathbb{P}(A) = 1/2$. Then $\sum_n \mathbb{P}(A_n) = \infty$ and $\limsup A_n = A$, so $\mathbb{P}(\limsup A_n) = 1/2 > 0$. But this example is not a counterexample — it gives positive probability. Let us try: $A_1 = \Omega$, all $A_n = \emptyset$ for $n \geq 2$. Then $\sum p_n = 1 < \infty$.

Better counterexample: $A_n$ are nested and decreasing with $\mathbb{P}(A_n) = 1/n$. Then $\sum 1/n = \infty$ but $\limsup A_n = \bigcap_n A_n$ can have probability 0 if the sets shrink to $\emptyset$.

Kochen-Stone (1964): If $\sum_n \mathbb{P}(A_n) = \infty$ and $$\limsup_{N \to \infty} \frac{\left(\sum_{n=1}^N \mathbb{P}(A_n)\right)^2} {\sum_{m,n=1}^N \mathbb{P}(A_m \cap A_n)} > 0,$$ then $\mathbb{P}(\limsup A_n) > 0$. This condition controls the level of correlation between events. The proof uses Cauchy-Schwarz applied to $\mathbb{E}[\sum_{n=1}^N \mathbf{1}_{A_n}]$.

By independence: $\mathbb{P}(X_1^n = x^n, Y_1^n = y^n) = \prod_{i=1}^n \mathbb{P}(X_i = x_i, Y_i = y_i)$. Each factor equals $\mathbb{P}(X=x_i)\mathbb{P}(Y=y_i \mid X=x_i) = \frac{1}{2}[(1-\epsilon)\mathbf{1}(y_i=x_i) + \epsilon\mathbf{1}(y_i \neq x_i)]$.

$\mathbb{P}(X_i = Y_i) = (1-\epsilon)$ for each $i$. By independence: $\mathbb{P}(X_1^n = Y_1^n) = (1-\epsilon)^n$. For $\epsilon = 0.05$, $n=100$: $(0.95)^{100} \approx 0.006$.

Let $D_i = \mathbf{1}(X_i \neq Y_i)$. The $D_i$ are i.i.d. Bernoulli$(\epsilon)$, so $\sum_i D_i \sim \text{Bin}(n, \epsilon)$ with mean $n\epsilon$ and variance $n\epsilon(1-\epsilon)$. By Chebyshev (Chapter 10): $\mathbb{P}(|\frac{1}{n}\sum D_i - \epsilon| > \delta) \leq \frac{\epsilon(1-\epsilon)}{n\delta^2} \to 0$. The disagreement fraction concentrates near $\epsilon$.