Problem 13 - A Computational Introduction to Number Theory and Algebra

Question

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a family of random variables, and let \(S_{i}\) be the image of \(X_{i}\) for \(i=1, \ldots, n .\) Show that \(\left\\{X_{i}\right\\}_{i=1}^{n}\) is mutually independent if and only if for each \(i=2, \ldots, n,\) and for all \(s_{1} \in S_{1}, \ldots, s_{i} \in S_{i},\) we have $$ \mathrm{P}\left[X_{i}=s_{i} \mid\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]=\mathrm{P}\left[X_{i}=s_{i}\right] $$

Step-by-Step Solution

Answer

Question: Prove that a family of random variables \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent if and only if the probability of each \(X_{i}\) conditioned on the values of the previous random variables is equal to the probability of \(X_{i}\) for each \(i=2,\ldots,n\). Answer: We prove both directions: 1. If \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent, the probability of each \(X_{i}\) conditioned on the values of the previous random variables is equal to the probability of \(X_{i}\) for each \(i=2,\ldots,n\). 2. If the probability of each \(X_{i}\) conditioned on the values of the previous random variables is equal to the probability of \(X_{i}\) for each \(i=2,\ldots,n\), then \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent. Using the definition of mutual independence, we find that the given condition holds under these assumptions. Using induction on the number of random variables, we can show that the random variables are mutually independent if the given condition holds.

Step 1: Definition of Mutual Independence

A family of random variables \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent if for any subset \(I\subseteq \left\{1,\ldots, n\right\}\) and any choice of \(s_i \in S_i\) for \(i\in I\), we have $$ \mathrm{P}\left[\bigcap_{i\in I}\left(X_{i}=s_{i}\right)\right]=\prod_{i\in I}\mathrm{P}\left[X_{i}=s_{i}\right]. $$

Step 2: Prove the forward implication (Mutual independence implies the given condition)

Assume \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent. For each \(i=2,\ldots,n\), we want to show that the given condition holds. Consider the conditional probability for \(i\): $$ \mathrm{P}\left[X_{i}=s_{i} \mid\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]. $$ By the definition of conditional probability, we have: $$ \mathrm{P}\left[X_{i}=s_{i} \mid\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]=\frac{\mathrm{P}\left[\left(X_{i}=s_{i}\right) \cap \left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]}{\mathrm{P}\left[\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i-1}=s_{i-1}\right)\right]}. $$ Since the random variables are mutually independent, we can apply the mutual independence definition in the numerator and denominator, yielding: $$ =\frac{\mathrm{P}\left[X_{i}=s_{i}\right]\prod_{j=1}^{i-1}\mathrm{P}\left[X_{j}=s_{j}\right]}{\prod_{j=1}^{i-1}\mathrm{P}\left[X_{j}=s_{j}\right]}=\mathrm{P}\left[X_{i}=s_{i}\right]. $$ This proves that if \(\left\{X_{i}\right\}_{i=1}^{n}\) is mutually independent, then the given condition holds.

Step 3: Prove the reverse implication (Given condition implies mutual independence)

Assume the given condition holds for each \(i=2,\ldots,n\). We want to show that the random variables are mutually independent. Consider an arbitrary subset \(I\subseteq \left\{1,\ldots, n\right\}\) and an arbitrary choice of \(s_i \in S_i\) for \(i\in I\). Let \(I=\left\{i_1,\cdots,i_k\right\}\), where \(1\le i_1< \cdots < i_k \le n\). We will use induction on \(k\) to prove that $$ \mathrm{P}\left[\bigcap_{j=1}^k\left(X_{i_j}=s_{i_j}\right)\right]=\prod_{j=1}^k\mathrm{P}\left[X_{i_j}=s_{i_j}\right]. $$ - Base case \((k=1)\): When \(k=1\), this is true by the definition of probability. - Inductive step: Assume the statement holds for \(k-1\). For \(k\), we have: $$ \mathrm{P}\left[\bigcap_{j=1}^k\left(X_{i_j}=s_{i_j}\right)\right]=\mathrm{P}\left[\left(X_{i_k}=s_{i_k}\right) \cap \left(\bigcap_{j=1}^{k-1}\left(X_{i_j}=s_{i_j}\right)\right)\right]. $$ Now, we can apply the given condition for \(i=i_k\). Notice that \(X_{i_k}=s_{i_k}\) only depends on the previous random variables, which are all in the intersection in the conditioning term. Therefore, we have: $$ =\mathrm{P}\left[X_{i_k}=s_{i_k}\right]\mathrm{P}\left[\bigcap_{j=1}^{k-1}\left(X_{i_j}=s_{i_j}\right) \mid \left(X_{i_k}=s_{i_k}\right)\right]. $$ By the induction hypothesis for \(k-1\): $$ =\mathrm{P}\left[X_{i_k}=s_{i_k}\right]\mathrm{P}\left[\bigcap_{j=1}^{k-1}\left(X_{i_j}=s_{i_j}\right)\right]=\prod_{j=1}^k\mathrm{P}\left[X_{i_j}=s_{i_j}\right]. $$ Thus, the induction is complete, and the random variables are mutually independent. This concludes the proof for both directions of the condition.