-1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mahdi Cheraghchi Apr 12 at 1:59
  • $\begingroup$ By the way, future questions like this are better suited to cs.stackexchange. $\endgroup$ – usul Apr 12 at 17:51
1
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sn3jd3r Apr 12 at 1:37
  • $\begingroup$ 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? $\endgroup$ – Mahdi Cheraghchi Apr 12 at 16:54
  • $\begingroup$ @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. $\endgroup$ – usul Apr 12 at 17:50
  • $\begingroup$ Thanks for the follow up @usul - i think i get it. Accepted. $\endgroup$ – sn3jd3r Apr 12 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.