# Notation in proof for Asymptotic Equipartition Property

In the following lecture notes chapter 3, page 12-13, they state the following

We begin by introducting some important notation:
- For a set $$\mathcal{S},|\mathcal{S}|$$ denotes its cardinality (number of elements contained on the set). For example, let $$\mathcal{U}=\{1,2, \ldots, M\},$$ then $$|\mathcal{U}|=M$$
- $$u^{n}=\left(u_{1}, \ldots, u_{n}\right)$$ is an $$n$$ -tuple of $$u$$
- $$\mathcal{U}^{n}=\left\{u^{n} | u_{i} \in \mathcal{U} ; i=1, \ldots, n\right\} .$$ It is easy to see that $$\left|\mathcal{U}^{n}\right|=|\mathcal{U}|^{n}$$
- $$U_{i}$$ generated by a memoryless source $$U^{'}$$ implies $$U_{1}, U_{2}, \ldots$$ i.i.d. according to $$U$$ (or $$P_{U}$$ ). That is.

$$p\left(u^{n}\right)=\prod_{i=1}^{n} p\left(u_{i}\right)$$ Definition 12. The sequence $$u^{n}$$ is $$\epsilon$$ -typical for a memoryless source U for $$\epsilon>0,$$ if $$\left|-\frac{1}{n} \log p\left(u^{n}\right)-H(U)\right| \leq \epsilon$$ or equivalently, $$2^{-n(H(U)+\epsilon)} \leq p\left(u^{n}\right) \leq 2^{-n(H(U)-\epsilon)}$$ Let $$A_{\epsilon}^{(n)}$$ denote the set of all $$\epsilon$$ -typical sequences, called the typical set. So a length- $$n$$ typical sequence would assume a probability approximately equal to $$2^{-n H(U)}$$. Note that this applies to memoryless sources, which will be the focus on this course $$^{1}$$.
Theorem 13 (AEP). $$\forall \epsilon>0, P\left(U^{n} \in A_{\epsilon}^{(n)}\right) \rightarrow 1$$ as $$n \rightarrow \infty$$

Proof This is a direct application of the Law of Large Numbers (LLN). \begin{aligned} P\left(U^{n} \in A_{\epsilon}^{(n)}\right) &=P\left(\left|-\frac{1}{n} \log p\left(U^{n}\right)-H(U)\right| \leq \epsilon\right) \\ &=P\left(\left|-\frac{1}{n} \log \prod_{i=1}^{n} p\left(U_{i}\right)-H(U)\right| \leq \epsilon\right) \\ &=P\left(\left|\frac{1}{n}\left[\sum_{i=1}^{n}-\log p\left(U_{i}\right)\right]-H(U)\right| \leq \epsilon\right) \\ & \rightarrow 1 \text { as } n \rightarrow \infty \end{aligned} where the last step is due to the Law of Large Numbers (LLN), in which $$-\log p\left(U_{i}\right)$$ 's are i.i.d. and hence their arithmetic average converges to their expectation $$H(U)$$

My question is related to the proof. My understanding is the following; $$U^n$$ is a sequence of random variables $$U^n = (U_1, U_2, \ldots,U_n)$$ drawn i.i.d from some distribution $$p_U(u) = p(u)$$ and $$u^n$$ is a realization of the sequence.

However in the proof they switch from using $$p(u^n)$$ to $$p(U^n)$$ and I am not sure what $$p(U^n)$$ represents? What would be wrong by doing it as follows?

\begin{aligned} P\left(u^{n} \in A_{\epsilon}^{(n)}\right) &=P\left(\left|-\frac{1}{n} \log p\left(u^{n}\right)-H(U)\right| \leq \epsilon\right) \\ &=P\left(\left|-\frac{1}{n} \log \prod_{i=1}^{n} p\left(u_{i}\right)-H(U)\right| \leq \epsilon\right) \\ &=P\left(\left|\frac{1}{n}\left[\sum_{i=1}^{n}-\log p\left(u_{i}\right)\right]-H(U)\right| \leq \epsilon\right) \\ & \rightarrow 1 \text { as } n \rightarrow \infty \end{aligned}

• These are two different things: $p(u^n)$ means the probability assigned to the fixed string $u^n$, whereas $p(U^n)$ means you first sample your i.i.d. random variable $U^n$, and then you look at what your probability mass function assigns to your outcome. So, $p(u^n)$ is a function of your distribution and the choice of $u^n$, whereas $p(U^n)$ is only a function of your distribution. – Mahdi Cheraghchi Apr 12 at 1:59
• By the way, future questions like this are better suited to cs.stackexchange. – usul Apr 12 at 17:51

Your understanding is right, you just need to internalize it a bit more. $$U^n$$ is a random variable with a well-defined distribution. If you just write $$U^n$$, it has been defined exactly what you mean. But $$u^n$$ hasn't been defined. If you just write $$u^n$$, we don't know what sequence you mean.

Definition 12 can be stated more precisely like this: "Let $$U$$ be a memoryless source and let $$u^n$$ be a sequence. We say $$u^n$$ is $$\epsilon$$-typical for $$U$$ if ..." In this context, $$u^n$$ is given to us, so it is well-defined. So you see $$u^n$$ has to be given context for it to be used in a way that makes sense mathematically.

If we look at what you wrote at the bottom, since $$u^n$$ hasn't been defined, it's ambiguous. I would assume reading it that you are trying to make a statement like: "For all sequences $$u^n$$, ..." or "Let any sequence $$u^n$$ be given, then ..."

In fact, a statement like $$P(u^n \in A_{\epsilon}^n)$$ doesn't make sense: the probability should be taken over something, but there are no random variables in that statement. On the other hand, $$P(U^n \in A_{\epsilon}^n)$$ makes perfect sense. The probability is taken over the random variable $$U^n$$.

There is one more weird thing going on in this proof that throws people off. Some of the probability statements have $$p(U^n)$$ inside of them. This is a random number, that depends on the value of the random variable $$U^n$$. For example, if I write $$P(0.1 < p(U^n))$$, this is the probability, over randomness in $$U^n$$, that $$U^n$$ takes some realization whose probability is greater than $$0.1$$.

For example, if I roll a die and $$X$$ is a random variable for the outcome, in $$\{1,2,3,4,5,6\}$$, then $$P( p(X) = 1/6 ) = 1$$.

I hope this helps!

• Thank you for your answer. Would it be correct to say that $P(U^n \in A_{\epsilon}^n)$ is the probability of any possible realization of $U^n$ being in the typical set? I am still a bit confused about what $p(U^n)$ actually means... I don't recall seeing small $p$ and random variables mixed before. – sn3jd3r Apr 12 at 1:37
• That means, for example, you draw from $U^n$, and end up with something like 00101011001, and if 00101011001 belongs to the typical set, you win. What's the probability that you win? – Mahdi Cheraghchi Apr 12 at 16:54
• @sn3jd3r, yes, that would be correct. And yes, this is an unusual idea (but there is nothing technically fishy going on). $U^n$ is a random variable. So it makes sense to talk about $P(0.1 < f(U^n))$ for some function $f$, right? This is the probability that if we draw $U^n$ and apply the function $f$, we get something bigger than $0.1$. Okay, now we're going to apply the function $p$, which takes in a string and outputs the probability mass of that string. – usul Apr 12 at 17:50
• Thanks for the follow up @usul - i think i get it. Accepted. – sn3jd3r Apr 12 at 20:57