Question

(Shannon's Theorem) Let \(\left\\{X_{i}\right\\}\) be a sequence of independent random variables on the sample space \(\Omega\) having the common distribution \(\lambda=\sum_{1}^{r} p_{j} \delta_{j}\) where \(0<\) \(p_{j}<1, \sum_{1}^{r} p_{j}=1\), and \(\delta_{j}\) is the point mass at \(j .\) Define random variables \(Y_{1}, Y_{2}, \ldots\) on \(\Omega\) by $$ Y_{n}(\omega)=P\left(\left\\{\omega^{\prime}: X_{i}\left(\omega^{\prime}\right)=X_{i}(\omega) \text { for } 1 \leq i \leq n\right\\}\right) . $$ a. \(Y_{n}=\prod_{1}^{n} p_{X_{i}} .\) (The notation is peculiar but correct: \(X_{i}(\cdot) \in\\{1, \ldots, r\\}\) a.s., so \(p X_{i}\) is well-defined a.s.) b. \(\lim _{n \rightarrow \infty} n^{-1} \log Y_{n}=\sum_{1}^{r} p_{j} \log p_{j}\) almost surely. (In information theory, the \(X_{i}\) 's are considered as the output of a source of digital signals, and \(-\sum_{i}^{r} p_{j} \log p_{j}\) is called the entropy of the signal.)

Short answer

a. \( Y_n = \prod_{i=1}^{n} p_{X_i} \); b. \( \lim_{n \to \infty} n^{-1} \log Y_n = \sum_{j=1}^{r} p_j \log p_j \).

Step-by-step solution

Understanding the Problem

We have a sequence of independent random variables \( \{X_i\} \) with a categorical distribution given by \( \lambda = \sum_{j=1}^{r} p_j \delta_j \), where each \( \delta_j \) represents a point mass at \( j \). We need to explore properties of the random variable \( Y_n \) which indicates the joint probability of observing the same sequence of outcomes up to \( n \) as in \( \omega \).

Step a: Show \( Y_n = \prod_{i=1}^{n} p_{X_i} \)

Since each \( X_i \) is independent and follows the same distribution \( \lambda \), the probability that \( X_i(\omega') = X_i(\omega) \) for all \( i \) up to \( n \) is the product of each single probability. Therefore, \( Y_n(\omega) = P(\{\omega' : X_i(\omega') = X_i(\omega) \text{ for } 1 \leq i \leq n\}) = \prod_{i=1}^{n} p_{X_i}. \)

Step b: Show \( \lim_{n \to \infty} n^{-1} \log Y_n = \sum_{j=1}^{r} p_j \log p_j \) almost surely

For large \( n \), by the Law of Large Numbers each term in the product \( \prod_{i=1}^{n} p_{X_i} \) will be contributed by occurrences \( X_i = j \) with frequency \( p_j \). The log of this product is \( \sum_{i=1}^{n} \log p_{X_i} \). Therefore,\[ \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^{n} \log p_{X_i} = \sum_{j=1}^{r} p_j \log p_j, \]which describes the average rate of information or entropy, leading to the stated result by the strong law of large numbers.

Key concepts

Entropy

Entropy is a concept related to uncertainty or randomness in a system. It quantifies the average amount of information produced by a stochastic source of data. In simple terms, it's a measure of unpredictability. In the case of a categorical distribution, entropy is calculated using the probabilities of each possible outcome.

Imagine you are trying to predict the outcome of rolling a fair six-sided die. The entropy provides a way to quantify the inherent unpredictability of the die roll. Naturally, an outcome that's always the same has zero entropy because there's no uncertainty. However, with a six-sided die, the entropy is higher because any of the six outcomes is possible.

The mathematical formula for entropy, given a probability distribution \((p_1, p_2, ..., p_r)\), is
\[-\sum_{j=1}^{r} p_j \log p_j\].
Each term in the sum represents the information content of a single outcome, weighted by the probability of that outcome occurring.

Independent Random Variables

Independent random variables are fundamental to understanding probability and statistics. Two or more random variables are said to be independent if the occurrence of one does not affect the occurrence of another. Simply put, knowing the result of one variable gives you no information about another.

For instance, think about flipping two coins. The result of the first coin flip has no bearing on what you'll see when you flip the second coin. This is the essence of independence.

In the given exercise, the sequence of variables \(X_i\) is independent. Each variable follows the same categorical distribution independently of others. This independence allows us to calculate joint probabilities by taking their product. For example, if you have independent random variables with probabilities \(p_1, p_2, p_3, ..., p_n\), the probability of achieving a specific sequence is \(p_1 \cdot p_2 \cdot p_3 \cdot ... \cdot p_n\). This principle was used to demonstrate step a in the solution.

Categorical Distribution

A categorical distribution describes a scenario where a random variable can take on one of a few discrete values, with each value having a specific probability. This type of probability distribution is quite intuitive and is exemplified by simple events like rolling a die or selecting a single-colored marble from a bag.

Consider a die roll: there are six outcomes, each with an equal probability of 1/6. This is a classic categorical distribution where each outcome has a probability assigned to it.

In the problem under discussion, each random variable \(X_i\) follows a categorical distribution denoted as \(\lambda = \sum_{j=1}^{r} p_j \delta_j\). This notation indicates that the variable can take on values \(1, 2, ..., r\), each with probabilities \(p_1, p_2, ..., p_r\), wherein \( \delta_j \) represents the point mass at \(j\). This structure underpins the entropy calculation, as it determines the probabilities used in the entropy formula.

Law of Large Numbers

The Law of Large Numbers is a fundamental theorem in statistics that ensures stability in probabilities over a large number of trials or observations. It states that as the number of experiments increases, the average of the results will converge to the expected value.

Consider flipping a fair coin. Initially, you may not exactly get half heads and half tails, but as you flip the coin more times, the proportion of heads and tails will get closer to 50% each.

In the context of the given exercise, the Law of Large Numbers explains why the average value of the logarithm of probabilities converges to the entropy. For a large number of variables, the frequency of each category matches its probability, allowing us to use this law to prove the desired result in step b. The strong law variant ensures almost sure convergence, meaning that this convergence will happen with probability 1.