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 , we want to find the smallest set of vertices such that every edge is covered by the set . This means that for each edge , at least one of or is in .

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 whose size is guaranteed to be within a factor of of optimal.

The algorithm. To build our set , we repeatedly find some edge that is not yet covered, and we add both and to our set . That’s the entire algorithm.

At first sight, this seems like a crazy algorithm. Why would we put both and into , when we only need one of or in order to cover the edge ?

The answer to this question is simple. If we define to be the optimal solution to the vertex-cover problem, then must contain at least one of or . By placing both of and into our set , we guarantee that at least half the elements in our set also appear in . That means that, once our algorithm finishes, we are guaranteed that .

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 and drop it in a random position on a hardwood floor whose boards have the same width :

 

 

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

Does this mean we can drop thousands of needles (or, for safety-sake, popsicle sticks) to accurately estimate ? 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:

(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 popsicle-stick drops, and ended up estimating to about…. . 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 data points is roughly .

Ok, so dropping popsicle sticks clearly isn’t the best way to estimate . But I’m hoping I can convince you that it is one of the combinatorially coolest. And that’s because the formula for 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 needles, glued together to form a regular -gon. Here’s an example for :

 

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

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

When is very large, our -gon starts to closely resemble a circle with circumference . The height of the -gon corresponds with the diameter of the circle, and is therefore roughly (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 -gon on the hardwood floor, the total number of crossings will always be almost exactly the same (up to )! In particular, the total number of crossings by needles in the -gon is just twice the height of the -gon, i.e., . Since the expected number of crossings can be expressed as , it follows that, as grows large, approaches . Hence the formula .

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 , which is astronomically small when you consider that there are fewer than 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 -th prisoner walks in the room, they begin by opening the -th box. They then look at the number which they just revealed, and use that to decide which box to open next, opening the -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 in it, think of the box as having an arrow pointing from the box to the -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 -th prisoner starts by opening the -th box. They then continue to open each box in the cycle until they get to the box containing the number . Notice that the arrow from the box containing the number actually goes back to the -th box, the very first box the prisoner opened. In other words, the box containing is guaranteed to be the last box in the cycle. It follows that the -th prisoner will win the game if and only if the cycle containing the -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 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 . The remaining 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

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

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

But that’s just the total number of permutations divided by . In other words, if you pick a permutation at random, then the probability of there being a cycle of length is .

The same is true if we replace with any of the numbers . The probability of there being any cycle of length greater than 51, and the prisoners therefore losing the game, is exactly

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 -th Harmonic number , which is defined to be

satisfies . Notice that the probability of the prisoners losing the game can be written as . Plugging in the approximation for , we get that the probability of some prisoner losing is roughly

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 -th prisoner comes into the room, and all the previous prisoners have won the game so far. The -th prisoner wishes to find the box containing the number . 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 -th prisoner will also win the game! In other words, if the box containing 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.

 

The Combinatorics of Boarding an Airplane

I’ve spent a lot of time at airports recently. And whenever I’m at an airport I find myself thinking about combinatorial problems having to do with airplanes. While flying from SFO to BOS recently, I stumbled across something I found really surprising.

Suppose people board a plane in a random order. Each person has a seat number assigned to them, and whenever someone gets to their seat, they pause for a moment to put their luggage in the overhead bin.

Whenever someone is pausing for their luggage, they prevent anyone in back of them from passing. Suppose that it takes each person time to walk by a given seat, and time to put away their luggage once they get to their seat. The question is:

How long will it take for everyone to sit down?

In the worst case the passengers are arranged in decreasing numerical order. This means everyone will have to wait on everyone in front of them, and boarding will take time roughly . If, on the other hand, the passengers arrive in the correct (increasing) order, then they’ll each be able to walk straight to their seats, boarding in time .

But what if the passengers arrive in a random order? Then how much parallelism do we get?

The answer, as it turns out, is quite a lot. In fact, the expected time to board the plane will be

This has some pretty weird consequences. For example, it means that for any fixed and , and for a large enough plane-size , the boarding time will become dominated by the time necessary to walk down to the end of the plane. The time spent waiting on people to put their luggage overhead becomes a non-issue!

A Simplifying Assumption:  To make our analysis easier, we’ll make a simplifying assumption that turns out not to affect the outcome of the analysis. In particular, we’ll treat each of the passengers as though they don’t take any space in the aisle. For example, if one passenger is paused at seat , and there are there are some passengers waiting behind him that want to get past seat , then that won’t stop the passenger behind them from getting to seat .

On top of this, we’re already making the simplifying assumption that each row has only one seat. It turns out that both of these assumptions can be removed without changing the end result. I’ll talk about this more at the end of the post.

The Combinatorics:  The key insight to analyze the algorithm is this: Think of the people as a permutation of seat numbers. If the longest decreasing subsequence in the line of people has length , then it turns out the time to board the plane will be within a factor of two of .

To see this, consider some person as they walk to their seat. Let be the final person on whom waits before gets to their seat. Then the total time spends waiting on others will be at most greater than the total time that spends waiting on others. Similarly there is some person who is the last person on whom waits; and spends at most time more in total waiting than does . Continuing like this, we can find a subsequence of people

such that the right-most person in the sequence doesn’t have to wait at all, and such that each person spends at most longer than waiting. This means that our original person spends time at most waiting on others.

The sequence of people also has the property that their seat numbers are in decreasing order. So what we’ve really shown is that if is the length of the longest decreasing subsequence in the permutation of people, then no person will have to wait for time more than , and everyone will have boarded after time .

On the other hand, it’s not hard to see that the left-most person in the length- decreasing sequence will require time at least to board the plane; and that the left-most person in the entire line will require time at least to board. This means that the true boarding time will be within a factor of two of .

So the real question becomes: On average, how large is , the length of the longest decreasing subsequence in a random permutation?

Bounding the longest decreasing subsequence: We’ll start by considering a different question. For a given length , how many different decreasing subsequences of length should we expect in our permutation? (We count two subsequences as different even if they differ in only a single element.)

This is easy to compute by linearity of expectation: Each -element subsequence has a probability of being in decreasing order. And there are different -element subsequences. So the expected number of decreasing subsequences is

A useful fact about is that it’s at least as large as . So the expected number of decreasing -element subsequences is at most

When , this reduces to at most .

Of course, if the expected number of -element decreasing subsequences is so small, then so is the probability of any such subsequence appearing.

So with extremely high probability, no decreasing subsequence will be of length more than . And this implies that the expected length is also at most .

What about a lower bound? We’ve just shown that the expected length of the longest decreasing subsequence is at most . But is that tight?

For this, we can use a classical result from permutation combinatorics. The Erdös-Szekeres Theorem says that any permutation of length must either contain either a decreasing or an increasing subsequence of length . For a random permutation, this means that with probability at least , there will be a decreasing subsequence of length .  So the expected length of the longest decreasing subsequence is at least .

The full version of the problem:  Near the beginning of the post I mentioned we were making two assumptions: (1) That passengers don’t take up any space in the aisle; and (2) that each row has a single seat.

Removing these assumptions makes the problem considerably harder. But it turns out the end conclusion is basically the same. A 2009 math paper on the topic analyzed the problem in its full complexity, and found that as long as each person takes up roughly one row worth of space in the aisle, and the number of seats in each row is constant,  the boarding time remains

 

 

The (Almost) Secret Algorithm Researchers Used to Break Thousands of RSA Keys

RSA encryption allows for anyone to send me messages that only I can decode. To set this up, I select two large random primes and (each of which is hundreds of bits long), and release their product online for everyone to see; is known as my public key. In addition, I pick some number which shares no factors with or and release it online as well.

The beauty of RSA encryption is that using only the information I publicly released, anyone can encode a message they want to send me. But without knowing the values of and , nobody but me can decode the message. And even though everyone knows my public key , that doesn’t give them any efficient way to find values for or . In fact, even factoring a 232-digit number took a group of researchers more than 1,500 years of computing time (distributed among hundreds of computers).

On the surface, RSA encryption seems uncrackable. And it might be too, except for one small problem. Almost everyone uses the same random-prime-number generators.

A few years ago, this gave researchers an idea. Suppose Bob and Alice both post public keys online. But since they both used the same program to generate random prime numbers, there’s a higher-than-random chance that their public keys share a prime factor. Factoring Bob’s or Alice’s public keys individually would be nearly impossible. But finding any common factors between them is much easier. In fact, the time needed to compute the largest common divisor between two numbers is close to proportional to the number of digits in the two numbers. Once I identify the common prime factor between Bob’s and Alice’s keys, I can factor it out to obtain the prime factorization of both keys. In turn, I can decode any messages sent to either Bob or Alice.

Armed with this idea, the researchers scanned the web and collected 6.2 million actual public keys. They then computed the largest common divisor between pairs of keys, cracking a key whenever it shared a prime factor with any other key. All in all, they were able to break 12,934 keys. In other words, if used carelessly, RSA encryption provides less than security.

At first glance this seems like the whole story. Reading through their paper more closely, however, reveals something strange. According to the authors, they were able to run the entire computation in a matter of hours on a single core. But a back-of-the-envelope calculation suggests that it should take years to compute GCD’s between 36 trillion pairs of keys, not hours.

So how did they do it? The authors hint in a footnote that at the heart of their computation is an asymptotically fast algorithm, allowing them to bring the running time of the computation down to nearly linear; but the actual description of the algorithm is kept a secret from the reader, perhaps to guard against malicious use. Within just months of the paper’s publication, though, follow-up papers had already discussed various approaches in detail, both presenting fast algorithms (see this paper and this paper), and even showing how to use GPUs to make the brute-force approach viable (see this paper).

There’s probably a lesson here about not bragging about things if you want them to stay secret. But for this post I’m not interested in lessons. I’m interested in algorithms. And this one turns out to be both relatively simple and quite fun.

Algorithm Prerequisites: Our algorithm will deal with integers having an asymptotically large number of digits. Consequently, we cannot treat addition and multiplication as constant-time operations.

For -bit integers, addition takes time. Using long multiplication, multiplication would seem to take time. However, it turns out there is an algorithm which runs in time .

Computing the GCD naively using the Euclidean algorithm would take time. Once again, however, researchers have found a better algorithm, running in time .

Fortunately, all of these algorithms are already implemented for us in GMP, the C++ big-integer library. For the rest of the post we will use Big-O-Tilde notation, a variant of Big-O notation that ignores logarithmic factors. For example, while GCD-computation takes time , in Big-O-Tilde notation we write that it takes time .

Transforming the Problem: Denote the set of public RSA keys by , where each key is the product of two large prime numbers (i.e., hundred digits). Note that is the total number of keys. Rather than computing the GCD of each pair of keys, we can instead compute for each key the GCD of it and the product of all the other keys . If a key shares exactly one prime factor with other keys, then this provides that prime factor. If both prime factors of are shared with other keys, however, then the computation will fail to actually extract the individual prime factors. This case is probably rare enough that it’s not worth worrying about.

The Algorithm: The algorithm has a slightly unusual recursive structure in that the recursion occurs in the middle of the algorithm rather than at the end.

At the beginning of the algorithm, all we have is the keys,

The first step of the algorithm is to pair off the keys and compute their products,

Next we recurse on the sequence of numbers , in order to compute

Our goal is to compute for each key . The key insight is that when is odd, can be expressed as

and that when is even, can be expressed as

To see why this is the case, one can verify that the term on the right side of the GCD is guaranteed to be a multiple of , while also being a divisor of . This, in turn, implies that the GCD-computation will evaluate to exactly , as desired.

Computing each of the ‘s in terms of the ‘s and ‘s completes the algorithm.

Bounding the Running Time: Let denote the total number of bits needed to write down . Each time the algorithm recurses, the total number of bits in the input being recursed on is guaranteed to be no more than at the previous level of recursion; this is because the new inputs are products of pairs of elements from the old input.

Therefore each of the levels of recursion act on an input of total size bits. Moreover, the arithmetic operations within each level of recursion take total time at most . Thus the total running time of the algorithm is also (since the recursion levels can be absorbed into the Big-O-Tilde notation).

If we unwrap the running time into standard Big-O notation, we get

Is it practical? At first glance, the triple-logarithmic factor might seem like a deal breaker for this algorithm. It turns out the actual performance is pretty reasonable. This paper found that the algorithm takes time roughly 7.65 seconds per thousand keys, meaning it would take a little more than 13 hours to run on 6.2 million keys.

One of the log factors can be removed using a slightly more clever variant of the algorithm, which avoids GCD computations at all but the first level of recursion (See this paper). The improved algorithm takes about 4.5 seconds per thousand keys, resulting in a total running time of about 7.5 hours to handle 6.2 million keys.

So there we go. A computation that should have taken years is reduced to a matter of hours.  And all it took was a bit of clever recursion.

Fibonacci Formulas For Fantastic Fun

The Fibonacci numbers are the sequence , and satisfy the recurrence . They also have a beautiful formula,

This seemingly complicated formula actually has a very simple explanation.

Consider the set of number sequences of the form that satisfy the recurrence . I call the set “” because it turns out to form a vector space. That is, given any two sequences and in , their sum satisfies the same Fibonacci-style recurrence as they do, as does any scalar multiple of .

Notice that is not, however, a very complicated vector space. Because each number sequence in satisfies the Fibonacci-recurrence, each number sequence is entirely determined by its first two entries. Consequently, has dimension two.

If you look at the first few terms of the Fibonacci numbers, you might notice that they seem to grow at a roughly exponential rate. Consequently, one might hope that has a two basis elements of the form and of the form . Indeed, if did, then we would get for free that, for some constants ,

Fortunately, such and do exist and are easy to find. In order for to satisfy the recurrence , we need that . Applying the quadratic formula, we get values for and ,

The Two-Envelope Paradox Explained

The two-envelope paradox is a great example where seemingly correct math results in a bizarre conclusion. Not only that, but the paradox is so confusing that even well-trained mathematicians and computer scientists sometimes disagree on the source of the issue.

The Paradox: Consider two identical envelopes, each of which contains some positive amount of money, and one of which contains twice as much money as the other. You are given an envelope at random, and you open it to find dollars. Then you’re given a choice: either keep the dollars you have, or trade and get the money in the other envelope.

So how much money do you expect to make or lose if you swap envelopes? With probability , the other envelope contains dollars, meaning you would make dollars. The rest of the time, the other envelope contains dollars, meaning that you lose dollars. Thus the expected amount of money that you’ll make by swapping is:

a positive amount! If follows that you should always swap envelopes.

But Wait a Second…: This, of course, is nonsense. The strategy of always swapping envelopes is equivalent to the strategy of never swapping envelopes, since both strategies give you a random envelope. So it can’t be that, in general, swapping is a better strategy than not swapping.

The question is, where did we go wrong? That is, which part of the argument above can’t be made mathematically rigorous?

The Source of the Confusion: The first thing to notice is that is a random variable, meaning it’s the result of a random process and doesn’t always take the same value. But in order for a random variable to be well defined, it must be over a probability space. So the question is, what probability space is over?

The paradox is very careful not to specify. But there are two natural answers one might try:

• Option 1: is a random positive rational number.
• Option 2: The probability space doesn’t matter for the argument.

It turns out that Option 1 isn’t actually valid. There is no probability space that is uniform over the positive rationals. So that leaves us with option 2. This means that the argument should work, regardless of the initial distribution used for the values in the envelopes. To make our lives easier, let’s pick a distribution. One envelope has dollar and the other has dollars.

With This Simplification, The Issue Becomes Obvious: Once we know the value of , it’s no longer the case that the other envelope has a fifty-percent chance of having dollars and a fifty-percent chance of having dollars. Indeed, the case where the other envelope has dollars only happens when , in which case the profit of dollars is actually just a profit of a single dollar. The case where the other envelope has dollars, on the other hand, only happens when , in which case the loss of dollars is actually just a loss of a a single dollar.

But Where Did the Analysis Formally Go Wrong? In the analysis in the paradox, the expected profit is expressed in terms of :

But that’s nonsensical math. The left side of the equation is a fixed value, while the right side is a random variable, expressed as a function of . The types on the two sides of the equation just don’t agree. To do the math properly, we would have to write,

The Takeaway: The reason people so frequently disagree on the cause of the paradox is simple. It’s because the aspect of the paradox that makes it confusing (namely, that the probability distribution for is unspecified) is different from the aspect of the paradox that makes it wrong (namely, that an expectation is expressed as a random variable). Like any good magic trick, it’s all about the misdirection.