Shannon's source coding theorem states the following:

$n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of information loss, as n→∞; conversely if they are compressed into fewer than n⋅H(x) bits it is virtually certain that information will be lost.

I was thinking about the easy case when the $X_1,\dots,X_n$ are uniformly distributed on the integers $[1,n]$. Now suppose I want to transmit a value of $(X_1,\dots,X_n)$. Clearly, each $X_i$ has entropy $\log n$ and thus, if we were to send $o(n\log n)$ bits, we would lose information about some of the $X_i$, with high probability $1 - o(1)$.

The way to argue the Theorem for this case, is that it $\log n$ bits suffice to reconstruct any $X_i$, and conversely, if you receive, for example, only $(1/4)n\log n$ bits, then, you would need to correctly guess $3/4 n\log n$ bits, which happens with probability of only $2^{-3/4n\log n}$. Is my reasoning correct?


The theorem you quote is not stated formally, so it is in fact impossible to prove it. That said, the idea behind the source coding theorem is that a variable of entropy $H(X)$ behaves (roughly) as if it was uniformly distributed on $2^{H(X)}$ values. When the distribution of $X$ is uniform, the theorem becomes trivial, once stated formally. So it's a good idea for you to look up a formal statement of the theorem, and then verify that it indeed holds for uniformly distributed random variables.


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.