In my previous work "Entropy is Not Easy: From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (I)", I introduced entropy from a more "professional" perspective and provided an interpretation. Of course, as a measure of uncertainty, entropy should have a more popular and intuitive origin. This article aims to supplement that part and provide some clever applications.
The Intuitive Origin of Entropy
Consider natural numbers composed of the ten digits 0–9. If we require the number to be less than 10,000, there are naturally 10,000 such numbers. If we say "a certain natural number less than 10,000," then any number from 0 to 9,999 could appear. Thus, 10,000 is a measure of the uncertainty of this event. Similarly, consider a sequence of length m composed of n different elements (which can be reused). There are n^m possible cases for this sequence, and n^m can also be seen as a measure of the uncertainty of this situation.
Since n^m is in exponential form, the numbers can become exceptionally large. Therefore, we take the logarithm to obtain m \log n, which can also serve as a measure of uncertainty. This is consistent with our original definition of entropy, because: m\log n = -\sum_{i=1}^{n^m} \frac{1}{n^m} \log \frac{1}{n^m}
Readers might wonder why we use m \log n instead of n^m as the measure of uncertainty. The answer is additivity. The measure after taking the logarithm possesses additivity, which makes calculations convenient. Of course, additivity is a requirement for convenience, not a necessity. If the n^m form were used, it would correspond to multiplicativity.
Application 1: Efficiency of Sorting Algorithms
Efficient sorting algorithms are essential for programming, and we now want to estimate the theoretical maximum average efficiency of a sorting algorithm. Suppose we want to sort n numbers in ascending order. Since it is a general algorithm, it must be applicable to general cases. Therefore, assuming the n numbers are distinct, there are n! possible permutations. Its entropy is \log(n!). Using Stirling’s approximation: \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 ascending order, the state is unique, and the entropy is 0. From an information theory perspective, sorting is the process of reducing entropy from \mathcal{O}(n\log n) to 0. Each operation we perform (such as swapping two numbers) changes a certain amount of entropy. Assuming each operation is beneficial, the time taken is proportional to \mathcal{O}(n\log n). This explains why the average maximum efficiency of sorting algorithms is \mathcal{O}(n\log n).
Application 2: How Many Times to Shuffle a Deck?
For card games, shuffling is a very common task. A new deck is usually ordered. To randomize it, we often use the riffle shuffle (splitting the deck into two and interleaving them). The question is: how many times must we perform this shuffle to ensure the deck is sufficiently randomized? (Source: http://duodaa.com/blog/index.php/archives/463/)
Admittedly, there are ambiguities here. First, the riffle shuffle process is not strictly defined; second, the definition of "randomized" is not precise. However, we do not need extreme precision, as we are not actually using mathematics to shuffle cards. We can use information entropy to make a simple estimate. Shuffling is like the reverse process of a sorting algorithm. Similarly, for n cards, if they are sufficiently random, the entropy is \mathcal{O}(n\log n). A riffle shuffle basically changes the positions of n cards, so the entropy change per shuffle is roughly proportional to n. Therefore, after \mathcal{O}(\log n) shuffles, the deck becomes chaotic. The key factor here is \log n, which is consistent with the results provided in the link above.
Reflection
Although this article is somewhat rough, it is clear: entropy is indeed a very magical thing!
Please include the original address when reprinting: https://kexue.fm/archives/3638
For more details regarding reprinting, please refer to: Scientific Space FAQ