Algorithm Soup

A Hash Table that Uses Less Space Than the Items that it Stores

When people talk about “space-efficient hash tables”, they are usually talking about the following type of guarantee: If we are storing $n$ keys, each of which are $w$ bits, then the total space usage should be $(1 + \epsilon)wn$ bits for some small $\epsilon$ .

But, what if I told you we can do better? In fact, it’s possible to construct a hash table that uses fewer than $nw$ bits. That is, the hash table uses less space than if we were to write each of the $n$ keys, one after another, in an array. As terminology, I’ll refer to such a hash table as extremely tiny.

Techniques for building extremely tiny hash tables have been known to theoreticians for decades. But how hard is it to build one in the real world? Not that hard at all, it turns out.

In this post, I’ll show you how to build a very simple extremely tiny hash table for 32-bit keys.

The Construction. Since our keys are 32-bits, we can write each key $x$ as $x_1 \circ x_2 \circ x_3 \circ x_4$ , where each $x_i$ is one byte. Our extremely tiny hash table $H$ will have the following structure: it consists of 256 sub-hash-tables $H_1, H_2, \ldots, H_{256}$ . To insert a key $x = x_1 \circ x_2 \circ x_3 \circ x_4$ into $H$ , we simply insert the three-byte item $x_2 \circ x_3 \circ x_4$ into table $H_{x_1}$ . And to query whether $x \in H$ , we simply query whether $x_2 \circ x_3 \circ x_4 \in H_{x_1}$ .

Finally, each $H_i$ is just a classical linear-probing hash table, dynamically resized to have a load factor (i.e., space efficiency) between 80% and 90%. That’s the entire construction.

Analysis. The trick here is that, even though $H$ is storing 4-byte keys, each $H_i$ is only storing 3-byte keys. The first byte of each key is encoded implicitly by the choice of which $H_i$ the key is stored in. This is a (somewhat unusual) application of a technique known as “quotienting”.

How much space do the $H_i$ ‘s consume? Remember that each $H_i$ is kept at a load factor of 80% or above. So, if $H_i$ is storing $n_i$ 3-byte keys, then it uses at most $3 n_i / 0.8 = 3.75 n_i$ bytes of space.

The different sub-hash-tables $H_1, \ldots, H_{256}$ may have very different sizes than each other at any given moment. Nonetheless, since the sum of their sizes in $n$ (the total number of keys in $H$ ), the total space used by the sub-hash tables is at most $3.75 n$ bytes of space.

Finally, we need to account for the metadata of the 256 sub-hash-tables. All things considered, in my implementation, this uses less than 6000 bytes. So our total space is at most $3.75 n + 6000$ bytes.

For any $n \ge 5334$ , the total space of our hash table comes out to less than 31 bits per key. We’ve built a real-world extremely tiny hash table.

Real-World Performance. So is this data structure fast? Well, it’s not blazingly fast. But it’s not embarrassingly slow either.

On my laptop, the time to first insert ten million keys and then do twenty million queries (half positive, half negative) is 3.7 seconds. If we instead use the C++ std::unordered_set (configured to use the same hash function as our original hash table), the same sequence of operations takes 7.3 seconds.

So we’re faster than the C++ hash table, but at the same time, that’s not a Herculean feat. (And it’s also not a fair comparison since, of course, the C++ hash table supports much more functionality). But it is a proof of concept: you can build extremely tiny hash tables in the real world.

My code is available at https://github.com/williamkuszmaul/tinyhash.

Train Tracks with Gaps: Applying the Probabilistic Method to Trains (Best Paper, FUN 2020)

Some Context: This post is a shortened version of a paper that won the best-paper award at FUN 2020. The paper is ostensibly about trains but the real-world applicability may be somewhat… limited. The actual purpose of the paper is educational: we get to see some of the funnest techniques in probabilistic combinatorics being used to solve a cute problem involving trains.

Part 1: A Consequential Train Ride

A few years ago, while traveling on a train, and on only a few hours of sleep, I was staring out the window. The train crossed a bridge over a road, and the ground was momentarily replaced by a steep drop. Startled, my sleep-deprived mind briefly wondered whether there was still a track underneath us. “Of course there is,” I thought to myself. “Without a track, the train car would have fallen into the gap.”

“Ah, no so fast!” responded the latent mathematician inside me. “If the train car had more than two sets of wheels, then perhaps it could cross the bridgeless gap without falling in.” It was true.

Consider, for example, a train with four sets of wheels: one set in the rear, one set in the front, and one set in each of the first and third quartiles.

basic_gap-1

As long as the gap in the track is less than the distance between any pair of wheels, then at least three sets of wheels will touch track at all times. Assuming that the center of mass of the train is in the middle half of the train, then the the train does not fall into the gap.

“In fact,” continued the latent mathematician, “what if we have ${n}$ sets of wheels? Maybe we can build a mono-rail using an asymptotically small amount of track.”

“That’s a stupid idea,” responded I. “Gaps in train track are not something to optimize.”

But I was sleep deprived, so I did it anyway.

The Basic Observation: More Wheels Means Less Track.

Consider a train car with ${2n}$ sets of wheels. Half the sets are evenly dispersed across the first quarter of the train car, and half the sets are evenly dispersed across the final quarter. The train can safely drive down the track as long as at least one set of wheels from each side of the train car is touching track at all times. The train car looks something like this:

Want to build a monorail, but you’re short on track? No problem! You can get away with filling in only an ${O(1/n)}$ fraction of the track:

ezgif.com-gif-maker

Every quarter of a train length, we place a piece of track whose length is a ${\frac{1}{4n}}$ fraction of the length of the train car. We get asymptotic cost savings!

To see that this is the best we can do, suppose that the fraction of track that is filled in is less than ${\frac{1}{n}}$ , and for symmetry sake suppose the track is circular (i.e., the end of the track loops back to the start). If we place the train at a random position in the circular track, then each wheel has a less than ${\frac{1}{n}}$ chance of touching track. By a union bound, it follows that the probability of any wheel in the rear quarter of the train touching the track is less than ${1}$ . Thus no matter how the track is placed, if the total fraction of track that is filled in is less than ${\frac{1}{n}}$ , then there is some position at which the train falls through.

Part 2: Trains with Non-Uniform Wheel Placements

Consider a train car that has ${n}$ wheels in its rear quarter and ${n}$ wheels in its front quarter, but suppose that the wheels aren’t evenly spaced. For example, maybe the rear of the car looks something like this:

uneven_wheels1-1

Can we still fill in an asymptotically small fraction of the track in a way that will allow the train car to drive down the track? In other words, can we place down a small amount of track in a way so that, as the train drives down it there is always at least one wheel from each of the front and rear quarters of the train touching track? It turns out that, via a simple application of the probabilistic method with alterations, we can.

To formalize the situation, let’s focus just on the first quarter of the train. (In particular, up to a constant factor in the amount of train track that we install, we can consider the two quarters of the train separately.) Suppose this portion of the train is ${f}$ feet long, and assume that each of the ${n}$ sets of wheels resides at a distinct integer offset from the rear of the train. Our goal is to build a train track that is ${\ell}$ feet long. We build the train track out of pillars that are each ${1}$ foot long and are each placed at integer positions on the track. We are required to put down the pillars in a way so that, as the train drives down the track, at least one wheel from the rear quarter is always touching the track (i.e., touching some pillar). We want to use as little track as possible, with the best we could hope for being a total of ${\frac{\ell}{n}}$ pillars.

As a reminder, there are three variables: the number of wheels ${n}$ (in the quarter of the train car that we’re considering), the length ${f}$ of one quarter of the train car, and the length ${\ell}$ of the train track. In general, we have ${n \le f \le \ell}$ . Note that, although ${n}$ and ${f}$ could reasonably be close to one another (e.g., ${f = 2n}$ ), we also want to be able to handle cases where ${n \ll f}$ . This allows for the train car to be configured in truly strange ways — for example, the positions of the wheels could even form a geometric series:

uneven_wheels2-1

A Randomized Algorithm for Building Track.

Our algorithm for deciding where to put the pillars is a simple example of the probabilistic method with alterations. In particular, we begin by randomly constructing a track that uses only a small number of pillars, and then we show that this track can be slightly altered in order to support (the rear quarter of) the train car at every point. The result will be a train track of length ${\ell}$ using only ${O\left(\frac{\ell \ln n}{n}\right)}$ pillars (and as we shall see later, this is optimal).

We begin by installing each pillar randomly with probability ${\frac{\ln n}{n}}$ . Even though this strategy has nothing to do with the structure of where the wheels are on the train, it already does remarkably well. In particular, if we place the train at some given position on the track, then there are ${n}$ different pillar positions that could potentially hold up the rear quarter. Each of these pillars positions has a ${\frac{\ln n}{n}}$ probability of having a pillar installed. It follows that, for a given position on the track, the rear quarter of the train has a

$\displaystyle \left(1 - \frac{\ln n}{n} \right)^{n}$

probability of falling through the track. Taking advantage of the identity ${\left(1 - \frac{1}{k}\right)^k \le \frac{1}{e}}$ , which holds for any ${k \ge 1}$ , we see that the wheels fall through the track with probability at most,

$\displaystyle \frac{1}{e^{\ln n}} = \frac{1}{n}.$

In other words, out of all the places we can place the train on the track, only a ${\frac{1}{n}}$ -fraction of them will be problematic (in expectation). To fix this, we can just install one additional pillar to remedy each of these problematic positions. The result is a train track that fully supports the rear quarter of our train, and that uses only ${\left(\frac{1 + \ln n}{n}\right) \ell}$ total feet of track, in expectation.

The construction is kind of fun to visualize. We start with some random pillars, and then we add additional pillars as needed so that the train never falls through the track:

Webp.net-gifmaker (2) (1)

Of course, our bound of ${\left(\frac{1 + \ln n}{n}\right) \ell}$ isn’t quite as good as we did when the wheels were evenly spaced out (we are a roughly ${\ln n}$ factor worse). But it’s still pretty amazing! No matter how the wheels are distributed across each quarter of the train car, we can get away with installing only a ${O\left(\frac{\ln n}{n} \right)}$ fraction of the track!

Part 3: A Matching Lower Bound

In the rest of this post, we’re going to prove that the construction above is optimal. (This is where the math gets really cool.) That is, we’ll show that there exists a train car configuration for which ${\Omega\left(\ell \frac{\ln n}{n} \right)}$ pillars are necessary. We are going to again use the probabilistic method, but this time in a more sophisticated way.

We continue to focus only on the rear quarter of the train car, which is ${f}$ feet long. We set ${f = 2n}$ , and we will construct the rear quarter of the train car by placing ${n}$ wheels at integer positions in the set ${\{1, 2, \ldots, 2n\}}$ . We will then consider a track of length ${\ell = 2f}$ , and show that ${\Omega(\log n)}$ pillars are necessary in order to support the rear quarter of the train car at all positions on the track. Recall that each pillar is one foot wide and is placed at an integer offset on the track.

Let ${C}$ be the set of wheel-positions in the rear quarter of the train car. We choose ${C}$ by placing a wheel at each position in ${\{1, 2, \ldots, 2n\}}$ independently with probability ${\frac{1}{2}}$ . This means that ${C}$ has ${n}$ wheels in expectation, but may not actually have exactly ${n}$ wheels. The important thing to note is that, with at least ${50\%}$ probability, ${C}$ has ${n}$ or more wheels.

Now consider a track layout given by a subset ${T}$ of ${\{1, 2, \ldots, 4n\}}$ , and satisfying ${|T| = \frac{\ln n}{4}}$ . Whereas ${C}$ is a random variable, ${T}$ is a fixed set.

Define ${X_{C, T}}$ to be the event that, for every possible position of the rear quarter of the train on the track, at least one wheel from the rear quarter of the train is supported by track. From the perspective of the train car, ${X_{C, T}}$ is a good event. Formally, ${X_{C, T}}$ occurs if for every offset ${k \in \{0, 1, \ldots, 2n\}}$ , we have ${(k + C) \cap T \neq \emptyset}$ .

The key to proving the desired lower bound is to show that the probability of ${X_{C, T}}$ occurring is very small, namely that ${\Pr[X_{C, T}] < \frac{1}{2 \binom{4n}{(\ln n) / 4}}}$ . Because ${T}$ is a ${\frac{\ln n}{4}}$ -element subset of ${\{1, 2, \ldots, 4n\}}$ , there are at most ${\binom{4n}{(\ln n) / 4}}$ possibilities for ${T}$ . Taking a union bound over all of these possibilities implies that

$\displaystyle \Pr[X_{C, T} \text{ for any }T] < \frac{1}{2}.$

On the other hand, we know that the number of wheels ${|C|}$ is less than ${n}$ with probability at most ${1/2}$ . By a union bound, the probability that either ${|C|}$ has fewer than ${n}$ wheels or that ${X_{C, T}}$ holds for some ${T}$ is less than ${1}$ . Hence there must exist a car ${C}$ with ${n}$ or more sets of wheels, and such that no track ${T}$ of size smaller than ${(\ln n) / 4}$ satisfies ${X_{C, T}}$ . In fact, with slightly more careful bookkeeping, one can show that an even stronger property is true: almost all choices of how to place ${n}$ wheels in ${C}$ require a track of size larger than ${(\ln n) / 4}$ to support the car.

To complete the lower bound, the challenge becomes to show that ${\Pr[X_{C, T}]}$ is very small. That is, for a given choice of track ${T}$ containing ${(\ln n)/4}$ pillars, the probability that ${T}$ supports the rear-quarter of the train car ${C}$ is small.

Rather than examine the event ${X_{C, T}}$ directly, we instead examine a related quantity. Define ${Y_{C, T}}$ to be the number of positions ${k \in \{0, 1, \ldots, 2n\}}$ for which ${(k + C) \cap T = \emptyset}$ (i.e., the number of positions in which the rear quarter of the car, given by ${C}$ , falls through the track ${T}$ ).

The relationship between ${X_{C, T}}$ and ${Y_{C, T}}$ is that ${X_{C, T}}$ occurs if and only if ${Y_{C, T} = 0}$ . Our approach to completing the analysis will be to first show that ${\mathop{\mathbb E}[Y_{C, T}]}$ is relatively large, and then to show that the probability of ${Y_{C, T}}$ deviating substantially from its expected value is small. This, in turn, implies that ${\Pr[Y_{C, T} = 0]}$ is small, completing the analysis. In other words, the problem of proving that there exists a train-car configuration requiring a large amount of track is reduced to the problem of proving a concentration inequality on the random variable ${Y_{C, T}}$ .

For each position ${k \in \{0, 1, \ldots, 2n\}}$ , the set ${T - k}$ consists of ${(\ln n) / 4}$ elements. Since each of these elements is contained in ${C}$ with probability ${1/2}$ , the probability that ${C}$ avoids all of the elements in ${T - k}$ is given by,

$\displaystyle \frac{1}{2^{(\ln n) /4}} = \frac{1}{n^{1/4}}.$

Summing over the values of ${k}$ , it follows that the expected number of positions ${k}$ in which ${(C + k) \cap T = \emptyset}$ is

$\displaystyle \mathop{\mathbb E}[Y_{C, T}] = 2n \cdot \frac{1}{n^{1/4}} > n^{3/4}.$

The final step of the analysis is to prove a concentration inequality on ${Y_{C, T}}$ . Standard Chernoff bounds do not apply here because ${Y_{C, T}}$ is not a sum of independent indicator random variables. Instead, we employ a more powerful tool, namely McDiarmid’s Inequality:

McDiarmid’s Inequality (1989): Let ${A_1, \ldots, A_m}$ be independent random variables over an arbitrary probability space. Let ${F}$ be a function mapping ${(A_1, \ldots, A_m)}$ to ${\mathbb{R}}$ , and suppose ${F}$ satisfies,

$\displaystyle \sup_{a_1, a_2, \ldots, a_m, \overline{a_i}} |F(a_1, a_2, \ldots, a_{i - 1}, a_i, a_{i + 1}, \ldots , a_m) - F(a_1, a_2, \ldots, a_{i - 1}, \overline{a_i}, a_{i + 1}, \ldots , a_m)|$ $\displaystyle \le R,$

for all ${1 \le i \le m}$ . That is, if ${A_1, A_2, \ldots, A_{i - 1}, A_{i + 1}, \ldots, A_m}$ are fixed, then the value of ${A_i}$ can affect the value of ${F(A_1, \ldots, A_m)}$ by at most ${R}$ ; this is known as the Lipschitz Condition. Then for all ${S > 0}$ ,

$\displaystyle \Pr[|F(A_1, \ldots, A_m) - \mathop{\mathbb E}[F(A_1, \ldots, A_m)]| \ge R \cdot S] \le 2e^{-2S^2 / m}.$

To apply McDiarmid’s Inequality to our situation, recall that ${Y_{C, T}}$ is defined to be the number of positions in the track ${T}$ that the rear quarter of the car, given by ${C}$ , falls through. Whereas the track ${T}$ is fixed, each of the ${2n}$ possible wheels in ${C}$ is picked with probability ${1/2}$ . Define the indicator random variables ${A_1, A_2, \ldots, A_{2n}}$ so that ${A_i}$ indicates whether ${i \in C}$ . As required by McDiarmid’s Inequality, the ${A_i}$ ‘s are independent of one-another, and ${Y_{C, T}}$ is a function of the ${A_i}$ ‘s.

Now we show that the Lipschitz Condition holds with ${R = (\ln n) / 4}$ . Recall that the track ${T}$ consists of only ${(\ln n) / 4}$ pillars. Out of the ${2n}$ possible wheels ${i}$ that ${C}$ could contain, each of those wheels ${i}$ is only relevant (to the car’s stability) when the car is ${k}$ feet down the track for some ${k}$ that places wheel ${i}$ on top of a pillar. Since there are only ${(\ln n)/4}$ pillars, each wheel ${i}$ is only relevant to the train car’s stability for ${(\ln n) / 4}$ positions ${k}$ on the track. In other words, for a given wheel position ${i \in \{1, 2, \ldots, 2n\}}$ , there are only ${(\ln n) / 4}$ values of ${k \in \{0, 1, \ldots, 2n\}}$ for which ${(C + k) \cap T}$ can possibly contain ${i}$ . As a result, each ${A_i}$ can only affect the value of ${Y_{C, T}}$ by at most ${(\ln n) / 4}$ , meaning that the Lipschitz Condition holds with ${R = (\ln n) / 4}$ .

Applying McDiarmid’s Inequality, we can deduce that

$\displaystyle \Pr[n^{3/4} - Y_{C, T} > n^{5/8} \cdot (\ln n) / 4] \le 2e^{-n^{1/4}}.$

When ${n}$ is large, this probability is much smaller than ${\frac{1}{2 \binom{4n}{(\ln n) / 4}}}$ . It follows that

${\Pr[X_{C, T}] = \Pr[Y_{C, T} = 0] < \frac{1}{2 \binom{4n}{(\ln n) / 4}}}$ .

Summing over all possible options for the track ${T}$ , the probability that any of them support the train car ${C}$ is therefore less than ${1/2}$ . This completes the proof: we have shown (non-constructively) that some train car ${C}$ with ${n}$ or more wheels fails to be supported by any track ${T}$ consisting of ${(\ln n)/4}$ or fewer pillars.

Conclusion. If you’ve made it to here, you might want to take a look at the paper that this blog post is based on. It turns out that there’s even more fun to be had: in fact, the train-track problem can be used to give illustrative examples of some of the most useful techniques in probabilistic combinatorics, including, e.g., the Lovász Local Lemma and the Method of Conditional Expectations!

¹ This research was partially sponsored by the United States Air Force Research Laboratory and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

I’m Above Average and So Are You

Derek Severs’ short essay “I Assume I’m Below Average” recently went viral on Hacker News. The article begins:

Ninety-six percent of cancer patients claim to be in better health than the average cancer patient.
Ninety-four percent of professors say they are better-than-average teachers.
Ninety percent of students think they are more intelligent than the average student.
Ninety-three percent of drivers say they are safer-than-average drivers.

What the article doesn’t discuss, however, is whether the people in these statistics are actually wrong.

There’s no fundamental reason why you can’t have 90% of people be better than average. For example, more than 99.9% of people have an above-average number of legs. And more than 90% of people commit fewer felonies than average. These examples are obvious, but they’re not so different than some of the examples above.

Any cancer patient that isn’t on the verge of dying probably is doing above average. (Unfortunately, so many cancer patients die, that the 96% number probably is still over-optimistic.)

What about the fraction of students that are above average? It depends on the class. Looking at Stanford’s data for the grade distribution of their graduate Algorithms class, about 78% of students (anyone with an A or A+) have an above-average grade.

This type of skew will happen in any probability distribution where a small number of people bring the average way down. I suspect another example of this is car drivers (consider the fact that, in America, 1 in 7 drivers don’t wear a seatbelt, or that 1 in 50 drivers admit to driving drunk in the past month!). Whether or not university professors fit this type of distribution is harder to tell.

To be clear, the examples given at the beginning are pretty extreme, and people probably are overly optimistic about their standings. But the examples aren’t as extreme as they look at first glance.

This reminds me of an old joke about there being an imaginary town called Lake Wobegon, “where all the women are strong, all the men are good-looking, and all the children are above average.” The joke, of course, is that the children can’t actually all be above average. But almost all of them can be. You just need one to bring the average down. (Poor Timmy.)

What is the actual infection rate at universities?

Here’s a question: what fraction of students at MIT have COVID-19 right now?

Since MIT tests students twice a week, this question should be pretty easy to answer. But it’s not.

That’s because MIT, along with other universities in the area, doesn’t report their infection rate. What they report is the positive test rate.

The Positive Rate is computed as

${\frac{\text{\# positive tests}}{\text{\# tests performed}}.}$

At first glance, this might sound like the fraction of the population that has the virus, but it’s not. That’s because, once you test positive, you don’t get any additional tests for 14 days (the length of a quarantine). That means that, in the time that a normal person would have gotten tested four times, an infected person only gets tested once. The true percent of the MIT population with coronavirus is probably more like

$\displaystyle 4 \cdot 0.22\% = 0.88\%.$

In my view, that’s pretty bad. Roughly speaking, this suggests that every two weeks, each student has a ${0.0088}$ chance of getting the virus. If a student lives at MIT for a year, their chance of avoiding the virus extrapolates to

$\displaystyle (1 - 0.88 / 100)^{26} < 0.8.$

So, by the end of the year, we may be looking at roughly 20% of MIT’s population having had the virus.

Of course, my extrapolation could be way off. But that’s the problem: MIT should be providing data that makes it easy to perform this sort of extrapolation, and they’re not.

Other schools are doing the same thing. Here’s Northeastern University’s infographic.

In my opinion, this graphic crosses the line to intellectually dishonest. The sea of blue is intended to comfort the reader without providing any useful information.

This is incredibly harmful. I’ve heard first hand from students who are convinced that the virus risk is low enough that they should just continue business as usual. Graphics like the one above inappropriately perpetuate that belief. In a crisis where bad math can literally kill, universities should do better.

My favorite example of: the probabilistic method

The “probabilistic method” is the art of applying probabilistic thinking to non-probabilistic problems. Applications of the probabilistic method often feel like magic. Here is my favorite example:

Theorem (Erdös, 1965). Call a set ${X}$ sum-free if for all ${a, b \in X}$ , we have ${a + b \not\in X}$ . For any finite set ${S}$ of positive integers, there is a sum-free subset ${X \subseteq S}$ of size ${|X| > |S| / 3}$ .

This theorem seems to have nothing to do with probability. Yet Erdös’s proof relies on a short and beautiful probabilistic argument.

Proof. Erdös’s first insight is to treat the set ${S}$ as living in ${\mathbb{Z}_p}$ for some large prime number ${p}$ , rather than living in ${\mathbb{Z}}$ . Living in ${\mathbb{Z}_p}$ only makes the theorem harder to prove, since any set ${X}$ that is sum-free in ${\mathbb{Z}_p}$ is also sum-free in ${\mathbb{Z}}$ . But, as we shall see, ${\mathbb{Z}_p}$ has several structural properties that Erdös beautifully exploits.

Let ${p = 3k + 2}$ be a prime number satisfying ${p > s}$ for all ${s \in S}$ . (The fact that such a prime exists is actually nontrivial, and uses the fact that there are infinitely many primes congruent to ${2}$ mod ${3}$ .) We’ll be using ${p}$ and ${k}$ throughout the rest of the proof.

Erdös begins his construction by defining a large sum-free set in ${\mathbb{Z}_p}$ which is not necessarily a subset of ${S}$ :

$\displaystyle \text{MIDDLE-THIRD} = \{k + 1, k + 2, \ldots, 2k + 1\}.$

As the name suggests, MIDDLE-THIRD consists of what is roughly the middle third of ${\mathbb{Z}_p}$ . One can easily confirm that MIDDLE-THIRD is sum-free in ${\mathbb{Z}_p}$ .

Next, Erdös selects a random value ${r \in \{1, 2, \ldots, p - 1\}}$ , and examines the set

$\displaystyle X_r = S \cap (r \cdot \text{MIDDLE-THIRD}),$

In words, ${X_r}$ is the set of ${s \in S}$ that can be written as ${rx \pmod p}$ for some ${x \in \text{MIDDLE-THIRD}}$ . If we could show that ${X_r}$ is a sum-free set of size greater than ${|S| / 3}$ , then the proof would be complete.

The good news is that ${X_r}$ is always sum-free, no matter the value of ${r}$ . This is because, if we have ${a + b = c}$ for some ${a, b, c \in X_r}$ , then we also have ${a / r + b / r = c / r}$ , violating the sum-freeness of MIDDLE-THIRD. (Here we are implicitly exploiting a nontrivial property of ${\mathbb{Z}_p}$ , namely that it supports division!)

The bad news is that ${|X_r|}$ could potentially be too small. To prove the theorem, we need to show that there is some option for ${r}$ that results in ${|X_r| > |S| / 3}$ .

Rather than directly finding a value of ${r}$ for which ${|X_r| > |S| / 3}$ , Erdös instead proves a probabilistic statement: the expected value of ${|X_r|}$ for a randomly chosen ${r}$ satisfies ${\mathbb{E}[|X_r|] > |S| / 3}$ . Of course, if ${\mathop{\mathbb E}[|X_r|] > |S| / 3}$ , then there must exist some ${r}$ for which ${|X_r| > |S| / 3}$ . What’s neat is that we don’t actually construct ${r}$ , we just prove it exists.

Our new challenge is to prove that ${\mathbb{E}[|X_r|] > |S| / 3}$ . One way to think of ${|X_r|}$ is as the number of ${x \in \{k + 1, k + 2, \ldots, 2k + 1\}}$ for which ${rx \in S}$ . Thus we can expand ${\mathbb{E}[|X_r|]}$ as

$\displaystyle \mathbb{E}[|X_r|] = \sum_{x = k + 1}^{2k + 1} \Pr[rx \in S].$

This is where Erdös really exploits the structure of ${\mathbb{Z}_p}$ . In ${\mathbb{Z}_p}$ , every non-zero element ${x}$ is an additive generator, meaning that the multiples ${x, 2x, 3x, \ldots, (p - 1)x}$ of ${x}$ are just the numbers ${1, 2, \ldots, p - 1}$ in some order. The result is that ${rx}$ is just a random element of ${\{1, 2, \ldots, p - 1\}}$ , and thus

$\displaystyle \mathbb{E}[|X_r|] = \sum_{x = k + 1}^{2k + 1} \frac{|S|}{p - 1}$

$\displaystyle = (k + 1) \frac{|S|}{p - 1}$

$\displaystyle > |S| / 3.$

Putting the pieces together, we have shown that ${\mathbb{E}[|X_r|] > |S| / 3}$ , which implies that there is some ${r}$ for which ${|X_r| > |S| / 3}$ . Since ${X_r}$ is sum-free, this completes the proof of the theorem.

Magic!

My favorite example of: the pigeonhole principle

This is part of a new sequence of posts titled,

My favorite example of: ${x}$ ,

for different values of ${x}$ . Today, ${x}$ is the pigeonhole principle.

The Erdös-Szekeres Theorem: Consider any sequence of ${n}$ distinct numbers. There must exist a subsequence ${S}$ of ${\sqrt{n}}$ numbers such that ${S}$ is either entirely increasing or entirely decreasing.

The Erdös-Szekeres Theorem is a classic result in permutation combinatorics. Although the theorem was first presented in 1935, the proof I’m going to describe appears in the 1959 paper “A simple proof of a theorem of Erdös and Szekeres”, written by Abraham Seidenberg. Seidenberg’s proof is arguably one of the slickest applications of the pigeonhole principle ever.

The Proof.

Consider a sequence ${x = x_1, x_2, \ldots, x_n}$ of ${n}$ distinct numbers. For each number ${x_i}$ , define

$\displaystyle a_i = \text{ length of longest increasing subsequence ending in }x_i$

and define

$\displaystyle b_i = \text{ length of longest decreasing subsequence ending in }x_i.$

For example, if ${x = 1, 4, 5, 3, 2}$ , then ${a_5 = 2}$ is the length of the longest increasing subsequence ending in ${x_5 = 2}$ and ${b_5 = 3}$ is the length of the longest decreasing subsequence ending in ${x_5 = 2}$ .

In order to prove the theorem, Seidenberg made one crucial observation:

Observation: If ${i < j}$ then either ${a_i \neq a_j}$ or ${b_i \neq b_j}$ .

To see why the observation holds, consider the case where ${x_i < x_j}$ . Then for any increasing subsequence ${S}$ that ends in ${x_i}$ , the longer subsequence ${S \cup \{x_j\}}$ is an increasing subsequence that ends in ${x_j}$ . This implies that ${a_j \ge a_i + 1}$ and thus that ${a_i \neq a_j}$ . A similar argument can be used in the case where ${x_i > x_j}$ to show that ${b_j \ge b_i + 1}$ , and thus that ${b_i \neq b_j}$ . In both cases, the observation holds.

In order to prove the theorem, our goal is to show that there is some ${i}$ for which either ${a_i \ge \sqrt{n}}$ or ${b_i \ge \sqrt{n}}$ . Seidenberg realized that he could prove this with a simple application of the pigeonhole principle.

Suppose for conradiction that ${a_i < \sqrt{n}}$ and ${b_i < \sqrt{n}}$ for all ${i}$ . Then there are fewer than ${\sqrt{n} \cdot \sqrt{n} = n}$ possibilities for each pair ${(a_i, b_i)}$ . It follows by the pigeonhole principle that at least two of the pairs

$\displaystyle (a_1, b_1), (a_2, b_2), (a_3, b_3), \ldots, (a_n, b_n)$

are equal to one-another. That is, there exists $i \neq j$ such that $(a_i, b_i) = (a_j, b_j)$ . But this contradicts Seidenberg’s observation, and thus completes the proof.

The Many Quirks of Qsort

In 1973, the author of the C programming language Dennis Ritchie was such a fan of the quicksort algorithm that he decided to name the language’s sort function after it.

In this post, I’m going to dive into some of the most interesting (and bizarre) aspects of the qsort function. I’m going to be focusing on the GNU C library version of qsort—you can find the code here and here.

The m in qsort. What if I told you that the world’s most famous implementation of quicksort actually uses… mergesort.

It’s true. The GNU implementation of qsort directly calls mergesort as the default sorting algorithm. It’s hard to tell exactly when this change occurred—based on the version history of glibc, it looks like the modification happened sometime between 1992 and 1995.

But why? I haven’t been able to find any documentation describing the reason for the transition from quicksort to mergesort, but I do have a conjecture. Although quicksort is typically faster than mergesort in practice, mergesort has one advantage: it performs fewer total comparisons. In the C library, this ends up being important, because the sort function performs comparisons by dereferencing a pointer to a comparison function. This makes comparisons much more expensive than they should be, giving mergesort an advantage.

I compared the library implementations of quicksort and mergesort on my machine, running both on a random array of ten million 64-bit integers. Mergesort was faster, taking 1.4 seconds instead of quicksort’s 1.7 seconds.

Then I modified the implementations to perform comparisons inline (and to also move objects around in 64-bit chunks instead of 8-bit chunks). This completely flipped things. Now quicksort became faster, taking 0.9 seconds instead of mergesort’s 1.2 seconds. So the pointer dereferences really do seem to be key.

If you really want quicksort, you can have it. Here’s a neat trick. If malloc fails, then qsort can’t allocate the memory needed for mergesort. In this case, qsort actually does use quicksort.

I wrote a function called malloc_all that allocates all of the memory in my system (this takes about half a second). If I call qsort after running malloc_all, then it runs the quicksort algorithm.

Wait, where’s the randomness? Here’s where things start to get interesting. If I call malloc_all and then I run qsort on the million-element array

$\displaystyle 0, 0, 0, \ldots, 0, 1, 2, 3, \ldots, 250000, 0, 1, 0, 2, 0, 3, \ldots, 0, 250000,$

then qsort takes a whopping 394 seconds to run. Wow!

It turns out that qsort‘s quicksort doesn’t use randomness to pick its pivot. As a consequence there are lots of natural inputs that cause the algorithm to take quadratic time!

Unlike C++, which requires that its sort function runs in ${O(n \log n)}$ time, the C standard places no such requirement on qsort. So it’s not that qsort is broken. It’s just quirky.

But why not use randomness? Most modern library implementations of quicksort are based on Bentley and McIlroy’s 1993 paper, Engineering a Sort Function. In it, Bentley and McIlroy advocate against using randomness, saying that “a library sort has no business side-effecting the random number generator”. As far as I can tell, this single sentence decided the fate of most modern quicksort library implementations. I think this is a bit of a shame, since it only takes a few lines to implement a library-specific random number generator, and then we would have a sort function without any worst-case inputs… But I’m also a theoretician, so I’m very biased.

The true namesake of qsort. I need to confess something: qsort isn’t actually named after quicksort. It’s named after quickersort, the variant of quicksort introduced by R.S. Scowen in 1965, three years after the introduction of quicksort.

There is one very neat way in which the two algorithms differ: quickersort implements its own recursion stack manually in a way that guarantees a stack depth of ${O(\log n)}$ . The way that quickersort does this is simple but clever. Suppose quickersort is executing a subproblem ${A}$ , which has two recursive child subproblems ${B}$ and ${C}$ , where ${B}$ is the smaller of the two child subproblems. After performing the partitioning step in ${A}$ , quickersort then executes ${B}$ recursively. After performing ${B}$ , however, quickersort then overwrites ${A}$ ‘s stack frame with ${C}$ ‘s stack frame, and performs ${C}$ at the same stack depth as ${A}$ was performed. The result is that, the only time that the stack depth ever increases is when the problem size decreases by at least a factor of two. Hence the bound of ${O(\log n)}$ on stack size.

A beautiful piece of code. At the end of the day, GNU libc qsort is one of my favorite pieces of code. I like the strange quirks. But there’s more to it than that. It’s a simple and beautifully written piece of code full of beautiful nuances and subtleties. If you have a few minutes, you might want to take a look.

You can also rerun the experiments in this blog post using this code.

The World’s Simplest Interesting Algorithm

In this post, I want to tell you about what I think might be the world’s simplest interesting algorithm.

The vertex cover problem. Given a graph ${G = (V, E)}$ , we want to find the smallest set of vertices ${S \subseteq V}$ such that every edge ${e \in E}$ is covered by the set ${S}$ . This means that for each edge ${e = (u, v)}$ , at least one of ${u}$ or ${v}$ is in ${S}$ .

The vertex cover problem is known to be NP-complete, meaning that it is very hard (or impossible) to find a polynomial-time algorithm for the problem.

But what we can do is find an approximately optimal solution to the problem. There’s a beautiful and simple algorithm that finds a set ${S}$ whose size is guaranteed to be within a factor of ${2}$ of optimal.

The algorithm. To build our set ${S}$ , we repeatedly find some edge ${e = (u, v)}$ that is not yet covered, and we add both ${u}$ and ${v}$ to our set ${S}$ . That’s the entire algorithm.

At first sight, this seems like a crazy algorithm. Why would we put both ${u}$ and ${v}$ into ${S}$ , when we only need one of ${u}$ or ${v}$ in order to cover the edge ${e = (u, v)}$ ?

The answer to this question is simple. If we define ${S_{\text{OPT}}}$ to be the optimal solution to the vertex-cover problem, then ${S_{\text{OPT}}}$ must contain at least one of ${u}$ or ${v}$ . By placing both of ${u}$ and ${v}$ into our set ${S}$ , we guarantee that at least half the elements in our set ${S}$ also appear in ${S_{\text{OPT}}}$ . That means that, once our algorithm finishes, we are guaranteed that ${|S| \le 2 |S_{\text{OPT}}|}$ .

A challenge. This might be the world’s simplest interesting algorithm (and analysis). But it also might not be. What do you think?

What Linearity of Expectation Has to Do with Needles and Pi

Take a needle of length ${\ell}$ and drop it in a random position on a hardwood floor whose boards have the same width ${\ell}$ :

stick_drop

There’s some probability ${p}$ that the needle crosses between two adjacent floorboards. It turns out that ${p}$ has a surprisingly simple formula,

$\displaystyle p = \frac{2}{\pi}.$

Does this mean we can drop thousands of needles (or, for safety-sake, popsicle sticks) to accurately estimate ${\pi}$ ? A few years ago, my friend Jake Hillard and I put this to the test. Jake measured out the width between floorboards in the Stanford History Department and 3D-printed a few dozen popsicle sticks of the same length. Here’s one I kept as a momento:

stick

(Since the sticks weren’t infinitesimally thin, the rule was to count a crossing only if the center of the stick crossed.)

With the help of Stanford Splash, we then recruited about a hundred middle- and high- school students to perform the experiment. In total, we recorded roughly ${4,000}$ popsicle-stick drops, and ended up estimating ${\pi}$ to about…. ${2.95}$ . That’s actually not too far from what we expected, since even with no experimental error at all, the standard deviation that we would expect with ${4,000}$ data points is roughly ${0.07}$ .

Ok, so dropping popsicle sticks clearly isn’t the best way to estimate ${\pi}$ . But I’m hoping I can convince you that it is one of the combinatorially coolest. And that’s because the formula for ${p}$ is actually just an extraordinarily slick (although slightly informal) application of linearity of expectation.

Anything Can be Solved with Enough Glue. For simplicity, I’ll assume for the rest of the post that $\ell = 1$. Imagine that, instead of dropping a single needle, we drop ${n}$ needles, glued together to form a regular ${n}$ -gon. Here’s an example for ${n = 8}$ :

polygon_drop

Each needle individually crosses between two floorboards with probability ${p}$ . By linearity of expectation, the expected total number of crossings by our ${n}$ -gon is ${n \cdot p}$ . That is, the ${n}$ -gon as a whole should, on average, induce ${n}$ times as many crossings as would a single needle.

But now let’s think about what this picture looks like when ${n}$ is large.

circle_drop

When ${n}$ is very large, our ${n}$ -gon starts to closely resemble a circle with circumference ${n}$ . The height of the ${n}$ -gon corresponds with the diameter of the circle, and is therefore roughly ${n / \pi}$ (This step of the argument isn’t actually as obvious as it sounds, and requires a bit more work to be formal). But no matter how we drop our circle-like ${n}$ -gon on the hardwood floor, the total number of crossings will always be almost exactly the same (up to ${\pm 1}$ )! In particular, the total number of crossings by needles in the ${n}$ -gon is just twice the height of the ${n}$ -gon, i.e., $2 \cdot n / \pi$ . Since the expected number of crossings can be expressed as ${n \cdot p}$ , it follows that, as ${n}$ grows large, ${n \cdot p}$ approaches ${2 \cdot n / \pi}$ . Hence the formula ${p = 2 / \pi}$ .

Proving Optimality for the 100 Prisoners Problem

The 100 Prisoners Problem is the single coolest algorithmic riddle I know. It’s a great example of a simple algorithm accomplishing something totally unexpected.

But the algorithm for the 100 Prisoners Problem is only half the story. The second, lesser known half, is a breathtakingly simple proof that no other algorithm can do better.

The Riddle: A sadistic prison warden runs a prison with 100 prisoners (numbered 1 through 100). He decides to force them to play the following game. The warden lines up 100 boxes in a room, and places a random permutation of the numbers 1 through 100 in the boxes. Each prisoner enters the room and is allowed to open 50 boxes. If the prisoner’s number is in one of the opened boxes, then the prisoner wins the game. Here’s the catch: In order for the prisoners to be set free, all of the prisoners have to win the game.

Before each prisoner enters the room, the boxes are reset to their initial configuration (so there’s no way for one person to leave a hint for the next person). Moreover, once the game has begun, no communication is permitted between the prisoners. They can, however, agree on a strategy beforehand for how to choose which boxes to open. The question is, what’s the optimal strategy?

The Algorithm: If the prisoners each independently open a random subset of the boxes, then the probability of all the prisoners winning is ${1/2^{100}}$ , which is astronomically small when you consider that there are fewer than ${2^{300}}$ atoms in the universe.

Surprisingly, there is a strategy which allows the prisoners to do much better, raising the probability of freedom to roughly 30 percent.

The algorithm works like this: When the ${i}$ -th prisoner walks in the room, they begin by opening the ${i}$ -th box. They then look at the number ${j}$ which they just revealed, and use that to decide which box to open next, opening the ${j}$ -th box. They continue like this until they’ve opened 50 boxes, opening each successive box according to the number in the previous box.

The Intuition: If a box has some number ${j}$ in it, think of the box as having an arrow pointing from the box to the ${j}$ -th box. If you start at a given box, and follow the arrows, eventually you’ll come in a full circle and get back to the box where you started. In other words, each box is part of a cycle of arrows.

The ${i}$ -th prisoner starts by opening the ${i}$ -th box. They then continue to open each box in the cycle until they get to the box containing the number ${i}$ . Notice that the arrow from the box containing the number ${i}$ actually goes back to the ${i}$ -th box, the very first box the prisoner opened. In other words, the box containing ${i}$ is guaranteed to be the last box in the cycle. It follows that the ${i}$ -th prisoner will win the game if and only if the cycle containing the ${i}$ -th box is of length no more than fifty.

In order for any prisoner to lose, there has to be some cycle of length more than fifty. This fact alone is very powerful, because it ensures that if any prisoners lose, then actually at least half of the prisoners lose (namely, all the prisoners in the cycle of length more than fifty lose). The algorithm manages to make it so that whether or not various prisoners lose is now highly correlated.

To see how powerful this observation is, consider the following slightly easier variant of the game: Each prisoner opens boxes just as before, but now they are permitted to open 75 boxes instead of 50. Using our algorithm, whenever any prisoners lose, at least 75 prisoners lose. But, since each prisoner individually has a ${1/4}$ chance of losing, the average number of prisoners who will lose is 25. Given that the average is 25, the fraction of the time that more than 75 can lose is at most ${\frac{25}{75} = 1/3}$ . The remaining ${2/3}$ of the time, all of the prisoners must win, resulting in them being set free.

Although this is a slick analysis, it doesn’t work when each prisoner is only allowed to open fifty boxes. Instead, we’ll do a more careful analysis, allowing us to calculate the exact probability of winning.

A Precise Analysis: Let’s start by counting the number of box configurations (i.e., permutations of numbers) which result in there being a cycle of length, say, 63. In order to construct such a permutation, we can begin by picking which boxes will be in the cycle. There are 100 ways to pick the first box in the cycle, 99 ways to then pick the second box in the cycle, and so on, ending with 38 ways to pick the final box in the cycle. But, of course, that’s not quite right, because what’s it mean for a box to be the “first” in the cycle? A cycle has no first element, meaning there are 63 ways to construct the same cycle. Dividing by 63, we get that the number of ways to construct a cycle of length 63 is

$\displaystyle \frac{100 \cdot 99 \cdot \cdots \cdot 38}{63}.$

Once we’ve constructed the cycle, we still need to determine where the other numbers will go. Notice that 63 numbers already have their positions determined by the cycle which we constructed. We’re left with 37 remaining numbers and 37 positions to put them. Putting them in an arbitrary ordering, there are

$\displaystyle 37 \cdot 36 \cdot 35 \cdots \cdot 1$

ways to complete the construction of our permutation.

Multiplying the number of ways to pick the cycle by the number of ways to then complete the permutation, it follows that the number of permutations containing a cycle of length 63 is

$\displaystyle \frac{100 \cdot 99 \cdot \cdots \cdot 1}{63}.$

But that’s just the total number of permutations ${n!}$ divided by ${63}$ . In other words, if you pick a permutation at random, then the probability of there being a cycle of length ${63}$ is ${1/63}$ .

The same is true if we replace ${63}$ with any of the numbers ${51, 52, \ldots, 100}$ . The probability of there being any cycle of length greater than 51, and the prisoners therefore losing the game, is exactly

$\displaystyle \frac{1}{51} + \frac{1}{52} + \cdots + \frac{1}{100}.$

At this point, we could just do out the summation by hand to get the answer. But there’s an easier way. In particular, we use the fact that the ${n}$ -th Harmonic number ${H_n}$ , which is defined to be

$\displaystyle H_n = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n},$

satisfies ${H_n \approx \ln n}$ . Notice that the probability of the prisoners losing the game can be written as ${H_{100} - H_{50}}$ . Plugging in the approximation for ${H_n}$ , we get that the probability of some prisoner losing is roughly

$\displaystyle \ln 100 - \ln 50 = \ln \frac{100}{50} = \ln 2 \approx 0.7,$

as desired.

Proving Optimality: A natural question is, can we do better? Surprisingly there’s a very simple and elegant proof that we cannot. Moreover, the proof gives a deep intuition for why the algorithm does so well.

Consider the following variant of the game, which I call The Baby 100 Prisoner’s Problem. In this version of the game, whenever a prisoner opens a box, the box is left open for any prisoners who come later. When a prisoner comes in, if their number has already been revealed, then the prisoner wins for free. Otherwise, the prisoner is allowed to open up to 50 of the remaining boxes in search of their number. Once the prisoner finds their number, they are not permitted to open any more boxes.

The baby problem is clearly much easier than the original. In fact, it’s not even an interesting algorithmic problem anymore, since every strategy will perform exactly the same. In particular, when opening a box that has never been opened before, then because the numbers are randomly permuted in the boxes, it doesn’t really matter what your strategy is for picking which box to open.

So the baby problem is easier than the original, and has the property that every algorithm performs optimally on it. Our proof strategy for showing that the cycle algorithm for the 100 Prisoner’s Problem is optimal will be to show that the cycle algorithm performs exactly the same for the standard problem as it does for the baby version of the problem. In other words, by using the cycle algorithm, we make it so that the full problem is just as easy as the baby one!

Consider the cycle algorithm for the standard version of the problem. Suppose the ${i}$ -th prisoner comes into the room, and all the previous prisoners have won the game so far. The ${i}$ -th prisoner wishes to find the box containing the number ${i}$ . Notice that if that box has ever been opened before (by a previous prisoner), then the entire cycle for that box must have also been opened by the past prisoner. Since all the past prisoners won the game, the cycle must be length no greater than fifty. It follows that the ${i}$ -th prisoner will also win the game! In other words, if the box containing ${i}$ has been opened at some point in the past, then we’re guaranteed to successfully find it now. On the other hand, if the box hasn’t been opened yet, then all the boxes which we will open will be in a cycle which has not yet been explored. That is, we will be opening only boxes which have not yet been opened.

But that’s exactly what happens in the baby problem! If the box we’re looking for has been opened before then we get it for free, and otherwise, we open new boxes to search for it! The cycle algorithm allows us to simulate the baby problem while actually playing the standard problem. Since the algorithm manages to do as well on the standard problem as it does on the baby problem, and since no algorithm for the standard problem can do better than any algorithm for the baby problem, it follows that the cycle algorithm must be optimal.

Conclusion: The 100 Prisoners Problem implicitly relies on a number of beautiful ideas from permutation combinatorics. At the heart of the algorithm’s analysis is the theory of permutation cycles. The proof of optimality can even be seen as implicitly constructing what’s known as Foata’s Transition Lemma, a classic bijection between two canonical representations of permutations.

Sometimes seeing classic combinatorial ideas applied to a different and less intuitive setting makes you realize just how elegant and subtle those ideas actually are. For me that’s exactly what the 100 Prisoners Problem does. It reminds me that sometimes the key to fully appreciating mathematical beauty is to look at it the wrong way.