Entropy
TODO: read original Shannon paper.
Basic assumption of probability theory: the information of an event is determined by its rarity.
$$i_m = log 1/p_m = - log p_m$$
This implies that more information is conveyed by rare events than common events. This also shows that by definition information is always positive as $p$ cannot be larger than 1.
Information is a property of an event coming from a stochastic source. Entropy instead is a property of a source which can for example be represented as a vector of probabilities, i.e. a (discrete) probability distribution.
More entropy means we can encode more messages in a probability distribution.
Entropy is the average information content i.e. the expected information over all possible messages $m$ under probability distribution $p$:
$$\mathbb{H} [ p ] = \mathbb{E}_p [i_m]$$ $$= - \sum_m p_m log p_m$$ $$p \dot log p$$
Where we define $0 log 0 = 0$.
Imagine a delta distribution $\delta_k$ with $p_i=0$ for all states except when $i=k$. Then for all states we either have $0 log 0 = 0$ or $1 log 1 = 0$.
So entropy shows that there is no uncertainty in this distribution - which makes sense because it's deterministic - and that as a result we cannot convey any information with it! I.e. we cannot produce different messages; we can only send a single message and because of this the expected information content of a message is 0. So entropy is minimized with a deterministic distribution.
The uniform distribution instead maximizes the entropy. For M states, each state has probability $\frac{1}{M}$. So the entropy is:
$$\mathbb{H}[uniform] = - \sum_m \frac{1}{M} log \frac{1}{M} = log M$$
What this tells us is that if we have a binary system with M discernible states (so we use log with base 2), we can encode a maximum of $log_2 M$ bits of information.
Entropy as the expected number of bits needed to encode a specific outcome
In informatics, information needs to be stored in terms of bits.
Assume we have a bitstring of length n. Then we can encode $2^n$ different outcomes.
If all these outcomes are equally likely to occur (the source behaves like a uniform probability distribution), then the probability of each outcome occurring is $\frac{1}{2^n}$.
If we then observe one of these outcomes, this outcome gives information $n=log_2(2^n)$.
Example: flip a fair coin $n=3$ times. Then each outcome has probability $\frac{1}{2^3}=\frac{1}{8}$. The flips are independent and each bit encodes the outcome of one flip. The information of each single bit is $I(1/2)=-log_2(1/2)=1$. The total information of the whole bitstring is 3x1 = 3=n. So the more we flip, the more information each outcome bitstring provides us.
Note that $n=3$ corresponds to the amount of bits we need to encode each outcome and that information can thus be interpreted as such in this context.
Entropy and efficient bit encoding
If some outcomes are more frequent than others, then we can reduce the expected amount of bits we need to encode the outcome by assigning shorter codes to more frequent outcomes. Entropy is thus the expectation of information in the observed outcomes (assuming there is no noise in our observations!).
Entropy expresses the expected amount of bits we need to encode the information of outcomes if our encoding of a random variable is optimal.
An encoding is optimal if every outcome is encoded such that the length of the used code is equal to the information of that outcome.
Example:
- Have two coin flips
- Possible "interal", states of our stochastic system: HH, HT, TH, TT
- Let's say we only observe the number of heads and we try to encode these outcomes
- This gives three outcomes: 0, 1, 2
- These outcomes have probability distribution (1/4, 1/2, 1/4) since HT and TH both contain a single head.
- The information values are (2, 1, 2)
- Since outcome 1 is most frequent, we assign the shortest code to this outcome
- I'm assuming prefix coding so that each bitstring can be interpreted as a unique indication of a sequence of events
- 1 <- 0; 0 <- 10, 2 <- 11
- So entropy is 3/2: we expect to need 3/2 bits to efficiently encode all information in the outcomes
- Of course, this means in practice we need 2 bits, so that's the best we can do here.
Entropy and uncertainty
Take a "Bernouilli experiment" e.g. a coin flip with probability p of success (e.g. "heads").
Probability distribution P over random variable X is given by $P_{X}=(p, 1-p)$ over the two possible outcomes. This gives entropy:
$$H(X)= -p log_2(p) - (1-p) log_2(1-p)$$
With $I(X=heads) = - log_2 (p)$ and $I(X=tails)= - log_2(1-p)$. Again, we get the entropy by computing the expectation over these two information values.
If p=0 or p=1, the outcome of the coinflip is always fixed and will give entropy 0. So entropy is as low as it can be, because there is no uncertainty in the outcome.
Instead, we have maximum uncertainty when p=1/2. In this case, the entropy is 1. If you plot the entropy of the Bernouilli experiment against $p$, you'll see that the entropy is maximal at this point.
Random strings
Weird consequence of information being determined by the rareness of an event: even though ".asdf70987asdf" is meaningless, it contains more information than "Good morning, Joe" (let's assume the strings are equal length; I didn't bother) according to this definition of information.
This paradox can be explained by realizing that a information is always defined against the background of a set of meaningfully distinguishable events. We human do not distinguish different random strings and will typically see these all as a single event "random string", which is actually very very common if you have a stochastic source randomly producing strings. So all is well in the end: random strings indeed do not convey much information.
Trying to explain entropy in layman's terms
Trying to apply the Feynman technique here.
Entropy... thermodynamics... Shannon's information ... noisy communication channels... How does it all relate?
I'm focusing on the information theoretic concept.
- We have some source of randomness
- E.g. coins are being flipped and the randomness is determined by internal states of the coin, e.g. it being heavier on one side resulting in it being fair.
- In thermodynamics e.g. the movement of molecules
- We do not directly observe the source but events resulting from that source
- We only observe the results from the flipping: heads or tails.
- E.g. in thermodynamics the temperature of water
Entropy measures uncertainty in the outcomes of some system. If there are more possible "internal states" there is more uncertainty about the outcome.
Let's take a simple system where all outcomes are determined by three coin flips. We have coin A, B and C.
Now we can ask: how much information does one particular outcome provide about the underlying stochastic process? (The coins can be fair, some can be fair and others biased etc.)
In terms of communication, we have a "communication channel" where on the receiving end we receive a number of heads and tails, and on the side of the sender we have the flipping of the coins. We can try to cast thermodynamic examples also in terms of this "communication channel" by distinguishing the internal atomic/microscopic state of a system with the measures we have of that system.
Entropy can then be seen as the amount of information you are missing when only having access to the macroscopic measure of the system rather than knowing the full microscopic state.
Analogously, in terms of digital communication: when we receive a message, how much of this message tells us something about the original message and how much is noise? I.e. how much uncertainty is there in the transmission?
TODO: ( In NMC there was a remark about a similar situation in spike-based timing )
Imagine we observe an outcome: two of the coins show heads, one shows tails. This means that there are three "internal" states in our coin-flipping system that can lead to this particular outcome.
- A: tails, B: heads, C: heads
- A: heads, B: tails, C: heads
- A: heads, B: heads, C: tails
Similarly, when we observe a single heads we also have three possible configurations. If instead I tell you that we observe three times heads, there is only one possible system configuration that leads to this outcome:
- A: heads, B: heads, C: heads
This also makes clear than entropy is defined relative to a set of different discernible outcomes. In our system, we have three possible outcomes: 1x heads, 2x heads, 3x heads.