[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 de finition of entropy.
1. Sorting
At his summer job at Ollivander's, Harry is given n wands of unknown weight w1,…,wn 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 wi and wj. 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 wi and wj against each other. The answer lets him distinguish between the set of worlds S< in which wi<wj and the set of worlds S> in which wi>wj. 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 log2n! steps to halve the total number of possible worlds down to a unique one.
1.2 Exercises
1. Check that log2n!=Θ(nlogn), 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 log2n! 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 fi gures 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 log2n questions to narrow down n possibilities down to one.
2.2 Exercises
1. Is there a strategy for George that uses exactly ⌈log2n⌉ 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≤i≤n−1 and 2−(n−1) for scheme n.
George still needs log2n questions to guarantee fi nding 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 fi rst 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 pi for each 1≤i≤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).
[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 de finition of entropy.
1. Sorting
At his summer job at Ollivander's, Harry is given n wands of unknown weight w1,…,wn 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 wi and wj. 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 wi and wj against each other. The answer lets him distinguish between the set of worlds S< in which wi<wj and the set of worlds S> in which wi>wj. 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 log2n! steps to halve the total number of possible worlds down to a unique one.
1.2 Exercises
1. Check that log2n!=Θ(nlogn), 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 log2n! 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 fi gures 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 log2n questions to narrow down n possibilities down to one.
2.2 Exercises
1. Is there a strategy for George that uses exactly ⌈log2n⌉ 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≤i≤n−1 and 2−(n−1) for scheme n.
George still needs log2n questions to guarantee fi nding 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 fi rst 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 pi for each 1≤i≤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).