Problem 43 - A Computational Introduction to Number Theory and Algebra

Question

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a finite, non-empty, 4 -wise independent family of random variables, each uniformly distributed over a set \(S\). Let \(\alpha\) be the probability that the \(X_{i}\) 's are distinct. For \(i, j=1, \ldots, n,\) let \(C_{i j}\) be the indicator variable for the event that \(X_{i}=X_{j},\) and define \(K:=\\{(i, j): 1 \leq i \leq n-1, i+1 \leq j \leq n\\}\) and \(Z:=\sum_{(i, j) \in K} C_{i j} .\) Show that: (a) \(\left\\{C_{i j}\right\\}_{(i, j) \in K}\) is pairwise independent; (b) \(\mathrm{E}[Z]=n(n-1) / 2 m\) and \(\operatorname{Var}[Z]=(1-1 / m) \mathrm{E}[Z] ;\) (c) \(\alpha \leq 1 / \mathrm{E}[Z]\) (d) \(\alpha \leq 1 / 2,\) provided \(n(n-1) \geq 2 m\) (hint: Exercise 8.4).

Step-by-Step Solution

Answer

In this exercise, we have a family of 4-wise independent random variables X_i, uniformly distributed over a set S. We have calculated the expected value and variance of Z, which counts the number of equal pairs of X_i's. We have derived bounds for α, the probability that all X_i's are distinct. Specifically, we showed that if n(n-1) ≥ 2m, α ≤ 1/2.

Step 1: (a) Pairwise Independence of \(\left\\{C_{i j}\right\\}_{(i, j)\in K}\)

To prove that the collection \(\{C_{i j}\}_{(i, j)\in K}\) is pairwise independent, we need to show that for any distinct pairs \((i_1, j_1)\) and \((i_2, j_2)\) in \(K\), the random variables \(C_{i_1 j_1}\) and \(C_{i_2 j_2}\) are independent. Since they are indicator variables, it is enough to prove that $$ P(C_{i_1 j_1} = 1, C_{i_2 j_2} = 1) = P(C_{i_1 j_1} = 1) P(C_{i_2 j_2} = 1). $$ Let \(i_1 \neq i_2\) and \(j_1 \neq j_2\), then $$ P(C_{i_1 j_1} = 1, C_{i_2 j_2} = 1) = P(X_{i_1} = X_{j_1}, X_{i_2} = X_{j_2}) $$ Since the family of random variables \(X_i\) is 4-wise independent and uniformly distributed, we have $$ P(X_{i_1} = X_{j_1}, X_{i_2} = X_{j_2}) = P(X_{i_1} = X_{j_1})P(X_{i_2} = X_{j_2}) = \frac{1}{m} \cdot \frac{1}{m}. $$ On the other hand, \(P(C_{i_1 j_1} = 1) = P(X_{i_1} = X_{j_1}) = \frac{1}{m}\) and \(P(C_{i_2 j_2} = 1) = P(X_{i_2} = X_{j_2}) = \frac{1}{m}\). Hence, the collection \(\{C_{i j}\}_{(i, j)\in K}\) is pairwise independent.

Step 2: (b) Expected Value and Variance of \(Z\)

Let's calculate \(\mathrm{E}[Z]\) and \(\operatorname{Var}[Z]\). First, we have $$ \mathrm{E}[Z] = \sum_{(i, j) \in K} \mathrm{E}[C_{i j}] = \sum_{(i, j) \in K} P(C_{i j} = 1) = \frac{1}{m} \sum_{(i, j) \in K} 1 $$ As \(K\) contains all pairs \((i, j)\) such that \(1 \leq i \leq n-1\) and \(i+1 \leq j \leq n\), the number of such pairs is \(\frac{n(n-1)}{2}\). Therefore, $$ \mathrm{E}[Z] = \frac{1}{m} \cdot \frac{n(n-1)}{2}. $$ Now, to find the variance of \(Z\), since the \(C_{i j}\) variables are pairwise independent, we have $$\operatorname{Var}[Z] = \sum_{(i, j) \in K} \operatorname{Var}[C_{i j}] = \sum_{(i, j) \in K} (\mathrm{E}[C_{i j}^2] - \mathrm{E}[C_{i j}]^2). $$ Since \(C_{ij}\) is an indicator variable, \(C_{ij}^2 = C_{ij}\). Also, \(\mathrm{E}[C_{i j}] = \frac{1}{m}\) as shown earlier. Thus, we get $$\operatorname{Var}[Z] = \sum_{(i, j) \in K} \left(\frac{1}{m} - \frac{1}{m^2}\right) = \frac{1}{m}\left(1-\frac{1}{m}\right)\sum_{(i, j) \in K} 1 = (1-\frac{1}{m})\mathrm{E}[Z]. $$

Step 3: (c) Bound for \(\alpha\) using \(\mathrm{E}[Z]\)

We can express \(\alpha\) as $$ \alpha = P(\text{all \(X_i\)'s are distinct}) = 1 - P(\text{at least one pair of \(X_i\)'s are equal}). $$ Now, notice that \(Z\) counts the number of equal pairs of \(X_i\)'s, so \(P(Z \geq 1) = P(\text{at least one pair of \)X_i\('s are equal})\). By Markov's inequality, we get $$ P(Z \geq 1) \leq \frac{\mathrm{E}[Z]}{1}. $$ Thus, $$ \alpha = 1 - P(Z \geq 1) \geq 1 - \frac{\mathrm{E}[Z]}{1} \Rightarrow \alpha \leq \frac{1}{\mathrm{E}[Z]}. $$

Step 4: (d) Bound for \(\alpha\) using Hint

Using Exercise 8.4 as a hint, we see that if \(n(n-1) \geq 2m\), then \(\mathrm{E}[Z] \geq 1\). Recall that we have \(\alpha \leq \frac{1}{\mathrm{E}[Z]}\). Since \(\mathrm{E}[Z] \geq 1\), then we have $$ \alpha \leq \frac{1}{\mathrm{E}[Z]} \leq \frac{1}{1} = 1. $$ So, if \(n(n-1) \geq 2m\), then \(\alpha \leq \frac{1}{2}\).

Key Concepts

Random Variables

Random variables are fundamental in understanding probability theory. They are variables that can take different values, each with an associated probability. The values are outcomes of a random process.
Think of a random variable as a numerical representation of an event.

• Discrete random variables take on a countable number of outcomes, like rolling a die.
• Continuous random variables can take any value within a range, such as the height of a person.

In our exercise, \(\{X_{i}\}_{i=1}^{n}\) represents a collection of random variables, each taking values from a set \(S\), uniformly distributed, meaning all outcomes in \(S\) are equally likely. Understanding this uniform distribution is key to analyzing their behavior, like independence and probability of distinct outcomes.

Pairwise Independence

Pairwise independence is a specific type of independence among random variables. Two random variables are pairwise independent if the occurrence of one does not affect the probability of occurrence of the other. In simpler terms:

• Two events are independent if knowing the outcome of one provides no information about the other.
• Pairwise independent variables satisfy \(P(A \cap B) = P(A) \cdot P(B)\).

In the exercise, we establish that \(\{C_{i j}\}_{(i, j) \in K}\) is a set of indicator variables, which are used to check if pairs of outcomes are equal. By demonstrating that the probability of any two such indicators being 1 is the product of their individual probabilities, we confirm they are pairwise independent.

Variance and Expectation

To delve into statistics of random variables, two concepts are crucial: expectation and variance.

• Expectation (or expected value) reflects the average outcome if the random process is repeated many times. It is calculated as
  \(\mathrm{E}[X] = \sum x_i \cdot P(x_i)\), where \(x_i\) are possible outcomes of the random variable \(X\).
• Variance measures the spread of these outcomes: \(\operatorname{Var}[X] = \mathrm{E}[(X - \mathrm{E}[X])^2]\). A higher variance means more variability.

In the exercise, we calculate \(\mathrm{E}[Z]\) as \(\frac{n(n-1)}{2m}\), using the total number of pairs in \(K\). The variance involves subtracting the expectation squared from \(\mathrm{E}[C_{ij}^2]\), demonstrating how much individual outcomes vary from the expected sum.

Markov's Inequality

Markov's Inequality provides a way to bound the probability of a random variable being greater than or equal to some value. It's especially useful when dealing with expectations and probabilities:

• If \(X\) is a non-negative random variable and \(a > 0\), Markov's inequality tells us \(P(X \geq a) \leq \frac{\mathrm{E}[X]}{a}\).
• This is a basic tool in probability to relate expectations with tail probabilities.

Applying Markov's Inequality in the exercise allows us to bound the probability that not all \(X_i\) are distinct. By considering \(Z\) (count of equal pairs), we use that \(P(Z \geq 1)\) is bounded by \(\mathrm{E}[Z]\), thus leading us to \(\alpha \leq \frac{1}{\mathrm{E}[Z]}\). This helps in quantifying the probability of distinctions among \(X_i\)'s efficiently.