[I copied over Alkjash's post, which linked to a PDF to LessWrong, to test our editor and generally show that it's not super hard to copy over things from existing LaTeX material. It took me about 8 minutes to convert the PDF to our formatting]

Introduction

This is the start of a sequence on the entropy method in combinatorics. As with any method in combinatorics, it's best explained by solving a series of problems. The best references on the subject are Chapter 14 of Alon and Spencer [1] and Radhakrishnan's expository paper [2].

Today, we solve three toy problems to motivate the definition of entropy.

1. Sorting

At his summer job at Ollivander's, Harry is given $n$ wands of unknown weight $w_{1}, \dots, w_{n}$ which he is to sort in increasing order. All Harry has to work with is a balance scale which determines the relative masses of any two wands $w_{i}$ and $w_{j}$ . How many weighings does Harry need?

Take a minute to think about this problem if you haven't seen it before.

1.1 Solution

In the beginning, Harry is agnostic about which of $n!$ possible orderings is the true answer. In his mind there are $n!$ possible worlds, one for each ordering of the wands.

After some number of weighings, suppose Harry sees a set $S$ of possible worlds before he weighs $w_{i}$ and $w_{j}$ against each other. The answer lets him distinguish between the set of worlds $S_{<}$ in which $w_{i} < w_{j}$ and the set of worlds $S_{>}$ in which $w_{i} > w_{j}$ . Either way, he gets to eliminate one or the other.

But Harry may be unlucky and only eliminate the smaller of $S_{<}$ and $S_{>}$ at each step. He will be left with the larger of $S_{<}$ and $S_{>}$ , which is at least half the size of $S$ . That is, each weighing decreases the total number of possible worlds by at most a factor of two.

Thus, he needs $l o g_{2} n!$ steps to halve the total number of possible worlds down to a unique one.

1.2 Exercises

1. Check that $l o g_{2} n! = Θ (n l o g n)$ , so this lower bound matches the best possible sorting algorithm runtime.

2. Check that being allowed to weigh any set of weights against any other set doesn't help - Harry still needs $l o g_{2} n!$ weighing operations.

3. What is the exact number of weighings needed to sort 5 wands?

4. The solution suggests that a good sorting algorithm balances the sizes of $S_{<}$ and $S_{>}$ as closely as possible at each step. How does your favorite sorting algorithm do in this regard?

2. Twenty Questions

Fred and George play a game to prepare for Easter 2018. Fred picks a prank out of a universe of $n$ mischievous schemes, and George asks Yes/No questions about it until he figures out the exact plan. How many questions does George need to ask?

2.1 Solution

Again, each of George's questions only lets him at most halve the number of possible schemes Fred has in mind. Thus, he needs at least $l o g_{2} n$ questions to narrow down n possibilities down to one.

2.2 Exercises

1. Is there a strategy for George that uses exactly $⌈ l o g_{2} n ⌉$ questions?

2. Suppose Fred is allowed to lie at most once. How many questions does George need?

3. Suppose Fred is allowed to lie at most $k$ times. How many questions does George need?

3 Twenty Questions with Priors

Fred and George, being twins, know each other rather well. Knowing Fred, George expects that the prank is likely to concern First Years, Professor Snape, Harry Potter, and toilet humor. In fact, George knows the probability that Fred chooses scheme $i$ is $2^{- i}$ for each $1 \leq i \leq n - 1$ and $2^{- (n - 1)}$ for scheme $n$ .

George still needs $l o g_{2} n$ questions to guarantee finding the answer, but can he do better on average?

3.1 Solution

George's best strategy is to keep asking "Is the answer strategy i?", going up from $i = 1$ to $i = n - 1$ . There's a half chance he gets it right on the first try, a quarter on the second, and so on.

In expectation, he needs just less than $2$ questions to win.

3.2 Exercises

1. Compute the exact expectancy of the number of questions George has to ask.

2. **IMPORTANT** Suppose the probability that Fred chooses scheme $i$ is $p_{i}$ for each $1 \leq i \leq n$ . What should George's strategy be in this case? How many questions does George need on average?

References

[1] N. Alon and J. H. Spencer, The Probabilistic Method, 3rd ed., Wiley, 2008.

[2] J. Radhakrishnan, Entropy and counting, Computational mathematics, modelling and algorithms 146 (2003).