In information theory, why is the entropy measured in units of bits?

Question

In information theory, we have the quantity "information".

Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{1}{2},\frac{1}{4},\frac{1}{4}\}}$. Then, information, $h$, is measured as $h(x) = -\log_{2}P(x)$.

So now we can say: $$h(a) = -\log_2 \bigg(\frac{1}{2}\bigg) = 1 \text{ bit}$$ $$h(b) = -\log_2 \bigg(\frac{1}{4}\bigg) = 2 \text{ bits}$$.

My question is, why does that computation result in a quantity measured in bits?

Explanations I've seen all say something along the lines of: "this quantity is measured in units of bits because of the log base 2" with no further explanation as to why. So why does taking the log (base 2) of a probability result in a quantity measured in units of bits?

Is it somehow related to the idea that if a system can be in $N$ states, then we can encode those $N$ states using $log_2 N$ bits? E.g. if a system can be in 4 states, we can encode those 4 states in binary with $log_2 4 = 2 \text{ bits}$: $00, 01, 10, 11$.

Answer 1

The entropy of a random variable $X$ can be described in terms of prefix-free binary encodings. Let $T(X)$ be the minimal average codeword length of a binary prefix code for $X$, and let $X^{\otimes n}$ be the random variable corresponding to $n$ independent samples of $X$. Then $$ \lim_{n\to\infty} \frac{T(X^{\otimes n})}{n}. $$

Shannon's source coding theorem allows a similar description. An encoding scheme for a variable $X$ over an alphabet $\Sigma$ is a pair of mappings $E\colon \Sigma^n \to \{0,1\}^{\ell(n)}$ and $D\colon \{0,1\}^{\ell(n)} \to \Sigma^n$. The entropy is the infimum of $H$ such that there are encoding schemes with $\ell(n) = Hn$ such that as $n\to\infty$, $$ \Pr_{x \sim X^{\otimes n}}[D(E(x))=x] \to 1. $$ In words, there is an encoding at rate $H$ if we can encoded $n$-tuples of samples of $\Sigma$ using $Hn$ bits in such a way that most of the time, we can decode the original sample from its encoding.

Both of these characterizations show that when encoding a large number of samples of $X$, each sample of $X$ takes $H(X)$ bits to encode.

Another characterization is the asymptotic equipartition (AEP) theorem, which states that $X^{\otimes n}$ consists, up to some small error, of roughly $2^{nH(x)}$ points whose probability is roughly $2^{-nH(x)}$.

Answer 2

Here is a simple intuition. Suppose we consider a random value that takes the values 0 or 1 with equal probability. Then this value can be represented in a single bit. Moreover, its Shannon entropy is $1$. Therefore, it is natural to say that its entropy is 1 bit. More generally, consider a random value that is distributed uniformly on the set of $n$-bit strings. Then this can be represented in $n$ bits; and the Shannon entropy is $n$, so it is natural to say that its entropy is $n$ bits.

Yes, it's definitely related to the fact that if the system has $N$ different possible states, its state can be represented in $\lg N$ bits. If the state is uniformly distributed over these $N$ different possibilities, a little bit of calculation will show that its Shannon entropy is $\lg N$. So, it makes a lot of sense to call its entropy $\lg N$ bits.