The Intuitive Origin of Entropy and Some Clever Uses
In my earlier piece "Untying the Knot of Entropy: From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (I)", I introduced entropy from a fairly "technical" angle and gave an interpretation of it. Of course, as a measure of uncertainty, entropy should also have a more intuitive, more down-to-earth origin, and this post is an attempt to fill in that gap, along with a couple of neat applications that follow from it.
The intuitive origin of entropy
Consider natural numbers made up of the ten digits 0–9. If we require the number to be less than 10000, there are naturally 10000 possibilities. If someone says "some natural number less than 10000," then any of 0–9999 could be the answer, so 10000 is itself a measure of the uncertainty of this statement. Similarly, consider sequences of length $m$ built from $n$ distinct elements (repetition allowed): there are $n^m$ possible sequences, and $n^m$ is likewise a measure of the uncertainty involved.
Since $n^m$ has an exponential form and the numbers can get absurdly large, we take a logarithm to get $m\log n$, which also serves as a measure of uncertainty — and in fact it agrees with our earlier definition of entropy. This is because
$$m\log n=-\sum_{i=1}^{n^m} \frac{1}{n^m}\log \frac{1}{n^m}$$
Readers might wonder: both $n^m$ and $m\log n$ qualify as measures of uncertainty, so what exactly makes us prefer $m\log n$ over $n^m$? The answer is additivity. The logarithmic measure is additive, which makes computations much more convenient. Of course, additivity is only a matter of convenience, not a necessity — if we instead used the form $n^m$, we would get a multiplicative measure instead.
Application 1: The efficiency of sorting algorithms
An efficient sorting algorithm is something every programmer needs to master, and here we want to estimate the average efficiency of the theoretically most efficient sorting algorithm. Suppose we want to sort $n$ numbers in increasing order. Since we're talking about a general-purpose algorithm, it must work in the general case, so let's assume the $n$ numbers are all distinct. Then there are $n!$ possible arrangements, with entropy $\log (n!)$. Using Stirling's formula, we get
$$\log (n!)\sim \log\left[\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right]\sim \mathcal{O}(n\log n)$$
Once the numbers are sorted in increasing order, there is only one possible arrangement, so the entropy at that point is 0. So, from an information-theoretic point of view, sorting is just the process of reducing entropy from $\mathcal{O}(n\log n)$ down to 0. Each operation we perform can only swap two numbers, changing the entropy by some fixed amount; assuming every operation is beneficial, the time required is then proportional to $\mathcal{O}(n\log n)$. This is, of course, an average-case statement, and it explains why the best average efficiency of sorting algorithms is $\mathcal{O}(n\log n)$.
Application 2: How many times must you shuffle to mix up a deck of cards?
For anyone who plays poker, shuffling is the most mundane of tasks. A brand-new deck of cards is usually arranged in order, and to mix it up people typically use the "riffle shuffle," where the deck is split into two halves that are then interleaved. The question we want to ask is: how many riffle shuffles are needed before the deck is truly mixed up? (Question source: http://duodaa.com/blog/index.php/archives/463/)
Naturally there's a lot of vagueness here. First, exactly what process the riffle shuffle is hasn't been precisely defined; second, what counts as "mixed up" isn't defined either. But we don't need precision here — after all, we're not actually shuffling cards with mathematics, just estimating. We can use information entropy to get a rough estimate. Shuffling is somewhat like the reverse of a sorting algorithm: similarly, for $n$ cards, if they are sufficiently random, the entropy is $\mathcal{O}(n\log n)$. Each riffle shuffle roughly changes the positions of about $n$ cards, so the amount of entropy changed per shuffle is roughly proportional to $n$. Therefore, after about $\mathcal{O}(\log n)$ shuffles, the deck should be roughly randomized. What matters here is that $\log n$, which agrees with the result given at http://duodaa.com/blog/index.php/archives/463/.
A closing remark
Although this post is somewhat rough around the edges, one thing is clear: entropy really is a remarkably powerful thing!
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.