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 '20 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$ – Peter Shor Mar 26 '20 at 16:16
  • $\begingroup$ @PeterShor Thank you. I can see that. I will update now. $\endgroup$ – sn3jd3r Mar 26 '20 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 '20 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$ – Peter Shor Mar 27 '20 at 22:22

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, privacy policy and cookie policy

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