I have been reading whatever sources I could get my hands on today, regarding this problem. Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas M. Cover and Joy A. Thomas. The book seems well regarded so I assume i am misunderstanding something.

I.e the following slides. I am confused by the notation - which comes from the book. If we look at slides 14 and 16 in the slides deck linked. Firstly on slide 14 they denote a sequence of random variables (i.e a sequence of bits, as far as I understand) as $X^n$ $$ X^n = (X_{1}, \ldots, X_{n}), \quad X_{n} \sim p(x) $$ and the codeword for that sequence as $\hat{X}^n$. Now moving on to slide 16 they seem to mix between $X^n$ and $x^n$ i.e they mention that the distortion between sequences $$ d\left(x^{n}, \hat{x}^{n}\right)=\frac{1}{n} \sum_{i=1}^{n} d\left(x_{i}, \hat{x}_{i}\right) $$

And distortion for a $\left(2^{n R}, n\right)$ code: $$ D=E d\left(X^{n}, g_{n}\left(f_{n}\left(X^{n}\right)\right)\right)=\sum_{x^{n}} p\left(x^{n}\right) d\left(x^{n}, g_{n}\left(f_{n}\left(x^{n}\right)\right)\right) $$

but as far as i can $x^n$ and $X^n$, and consequently $\hat{x}^n$ and $\hat{X}^n$ denote the same thing? What is the idea behind this, if any? It would make more sense to me to keep the capitalization consistent unless I am missing something? This notation is consistent across all sources I could find.

  • $\begingroup$ To the person downvoting this. Do you mind mentioning why, so i can update the question? $\endgroup$
    – sn3jd3r
    Mar 26, 2020 at 15:54
  • $\begingroup$ I didn't downvote, but your question is unclear. What is the same thing as what? And why do you think they should be different? $\endgroup$ Mar 26, 2020 at 16:16
  • $\begingroup$ @PeterShor Thank you. I can see that. I will update now. $\endgroup$
    – sn3jd3r
    Mar 26, 2020 at 16:19
  • $\begingroup$ Typically, people use different notation (e.g., uppercase letters v. lowercase ones) when things are random variables (as opposed to deterministic or general, non necessarily random things). That seems to be what is happening here. $\endgroup$
    – Clement C.
    Mar 26, 2020 at 20:56
  • $\begingroup$ The capital letters are the random variables. The lower-case letters are the possible values of the random variables. So we have the equation $\mathrm{E} X = \sum_{x} p(x) x$. If you used all capital $X$'s in that equation, it would be confusing. $\endgroup$ Mar 27, 2020 at 22:22

1 Answer 1


In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the definition of expectation as $E[X] = \sum p(x) \cdot x$. Moreover, vector values are denoted using length as superscripts, for example $X^n$ means $(X_1, \ldots, X_n)$ (similarly for $x^n$). Moreover a substring $(X_i, \ldots, X_j)$ is often denoted by $X_i^j$. These slides seem to be consistent with this convention.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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