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

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

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

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

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

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

<p>I hope this helps!</p>

CC BY-SA 4.0
2020-04-12T01:37:04.467Z
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
CC BY-SA 4.0
2020-04-12T16:54:47.850Z
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
CC BY-SA 4.0
2020-04-12T17:50:31.237Z
@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
CC BY-SA 4.0
2020-04-12T20:57:31.270Z
Thanks for the follow up @usul - i think i get it. Accepted.
sn3jd3r
CC BY-SA 4.0
2020-04-12T01:26:41.297Z
2020-04-12T01:26:41.297Z
usul
<p>In the following <a href="https://web.stanford.edu/class/ee376a/files/lecture_notes.pdf" rel="nofollow noreferrer">lecture notes</a> chapter 3, page 12-13, they state the following</p>

<blockquote>
  <p>We begin by introducting some important notation:<br>
  - For a set <span class="math-container">$\mathcal{S},|\mathcal{S}|$</span> denotes its cardinality (number of elements contained on the set). For example, let <span class="math-container">$\mathcal{U}=\{1,2, \ldots, M\},$</span> then <span class="math-container">$|\mathcal{U}|=M$</span><br>
  - <span class="math-container">$  u^{n}=\left(u_{1}, \ldots, u_{n}\right)$</span> is an <span class="math-container">$n$</span> -tuple of <span class="math-container">$u$</span><br>
  - <span class="math-container">$ \mathcal{U}^{n}=\left\{u^{n} | u_{i} \in \mathcal{U} ; i=1, \ldots, n\right\} .$</span> It is easy to see that <span class="math-container">$\left|\mathcal{U}^{n}\right|=|\mathcal{U}|^{n}$</span><br>
  - <span class="math-container">$ U_{i}$</span> generated by a memoryless source <span class="math-container">$U^{'}$</span> implies <span class="math-container">$U_{1}, U_{2}, \ldots$</span> i.i.d. according to <span class="math-container">$U$</span> (or <span class="math-container">$P_{U}$</span> ). That is.  </p>
  
  <p><span class="math-container">$$p\left(u^{n}\right)=\prod_{i=1}^{n} p\left(u_{i}\right)$$</span>
  <strong>Definition</strong> <strong>12</strong>. The sequence <span class="math-container">$u^{n}$</span> is <span class="math-container">$\epsilon$</span> -typical for a memoryless source U for <span class="math-container">$\epsilon&gt;0,$</span> if
  <span class="math-container">$$
\left|-\frac{1}{n} \log p\left(u^{n}\right)-H(U)\right| \leq \epsilon
$$</span>
  or equivalently,
  <span class="math-container">$$
2^{-n(H(U)+\epsilon)} \leq p\left(u^{n}\right) \leq 2^{-n(H(U)-\epsilon)}
$$</span>
  Let <span class="math-container">$A_{\epsilon}^{(n)}$</span> denote the set of all <span class="math-container">$\epsilon$</span> -typical sequences, called the typical set.
  So a length- <span class="math-container">$n$</span> typical sequence would assume a probability approximately equal to <span class="math-container">$2^{-n H(U)}$</span>. Note that this applies to memoryless sources, which will be the focus on this course <span class="math-container">$^{1}$</span>.<br>
  <strong>Theorem 13 (AEP)</strong>. <span class="math-container">$\forall \epsilon&gt;0, P\left(U^{n} \in A_{\epsilon}^{(n)}\right) \rightarrow 1$</span> as <span class="math-container">$n \rightarrow \infty$</span></p>
  
  <p><strong>Proof</strong> This is a direct application of the Law of Large Numbers (LLN).
  <span class="math-container">$$
\begin{aligned}
P\left(U^{n} \in A_{\epsilon}^{(n)}\right) &amp;=P\left(\left|-\frac{1}{n} \log p\left(U^{n}\right)-H(U)\right| \leq \epsilon\right) \\
&amp;=P\left(\left|-\frac{1}{n} \log \prod_{i=1}^{n} p\left(U_{i}\right)-H(U)\right| \leq \epsilon\right) \\
&amp;=P\left(\left|\frac{1}{n}\left[\sum_{i=1}^{n}-\log p\left(U_{i}\right)\right]-H(U)\right| \leq \epsilon\right) \\
&amp; \rightarrow 1 \text { as } n \rightarrow \infty
\end{aligned}
$$</span>
  where the last step is due to the Law of Large Numbers (LLN), in which <span class="math-container">$-\log p\left(U_{i}\right)$</span> 's are i.i.d. and hence their arithmetic average converges to their expectation <span class="math-container">$H(U)$</span></p>
</blockquote>

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

<p>However in the proof they switch from using <span class="math-container">$p(u^n)$</span> to <span class="math-container">$p(U^n)$</span> and I am not sure what <span class="math-container">$p(U^n)$</span> represents? What would be wrong by doing it as follows?</p>

<p><span class="math-container">$$
\begin{aligned}
P\left(u^{n} \in A_{\epsilon}^{(n)}\right) &amp;=P\left(\left|-\frac{1}{n} \log p\left(u^{n}\right)-H(U)\right| \leq \epsilon\right) \\
&amp;=P\left(\left|-\frac{1}{n} \log \prod_{i=1}^{n} p\left(u_{i}\right)-H(U)\right| \leq \epsilon\right) \\
&amp;=P\left(\left|\frac{1}{n}\left[\sum_{i=1}^{n}-\log p\left(u_{i}\right)\right]-H(U)\right| \leq \epsilon\right) \\
&amp; \rightarrow 1 \text { as } n \rightarrow \infty
\end{aligned}
$$</span></p>

CC BY-SA 4.0
2020-04-12T01:59:36.683Z
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
CC BY-SA 4.0
2020-04-12T17:51:35.990Z
By the way, future questions like this are better suited to cs.stackexchange.
usul
<pr.probability><it.information-theory><st.statistics>
Notation in proof for Asymptotic Equipartition Property
sn3jd3r
# Notation in proof for Asymptotic Equipartition Property

(Asked by: username_0 on 2020-04-12)

In the following [lecture notes](https://web.stanford.edu/class/ee376a/files/lecture_notes.pdf) 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}
$$

**Tags:** pr.probability, it.information-theory, st.statistics

> **Comments:**
> **username_1**: 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.  
> **username_2**: By the way, future questions like this are better suited to cs.stackexchange.  

---

## 1 answers

### Answer by username_2 on 2020-04-12. Score: 1 | Accepted answer

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!

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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?  
> **username_2**: @username_0, 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.  
> **username_0**: Thanks for the follow up @username_2 - i think i get it. Accepted.  

---

