The National Research Council is getting ready to release a new assessment of graduate-education programs in the U.S. The previous study, published in 1995, gave each Ph.D.-granting department a numerical score between 0 and 5, then listed all the programs in each discipline in rank order. For example, here’s the top-10 list for doctoral programs in mathematics (as presented by H. J. Newton of Texas A&M University):

 rank    school                 score   
    1    Princeton               4.94
    2    Cal Berkeley            4.94
    3    MIT                     4.92
    4    Harvard                 4.90
    5    Chicago                 4.69
    6    Stanford                4.68
    7    Yale                    4.55
    8    NYU                     4.49
    9    Michigan                4.23
   10    Columbia                4.23

Note that the scores of the first two schools are identical (to two decimal places), and the first four scores differ by less than 1 percent. Given the uncertainties in the data, it seems reasonable to suppose that the ranking could have turned out differently. If the whole survey had been repeated, the first few schools might have appeared in a different order. Doctoral candidates in mathematics are presumably sophisticated enough to understand this point. Nevertheless, the spot at top of the list still carries undeniable prestige, even when you know that the distinction could be merely an artifact of statistical noise.

The committee appointed by the NRC to conduct the new graduate-school study wants to avoid this “spurious precision problem.” They’ve adopted some jazzy statistical methods—mainly a technique called resampling—to model the uncertainty in the data, and they’ve also decreed that the results will be presented differently. There will be no sorted master list showing overall ranks in descending order. Instead the programs in each discipline will be listed alphabetically, and each program will be given a range of possible ranks. For example, a program might be estimated to rank between fifth place and ninth place. Let’s call such a range of ranks a rank-interval, and denote it {5, 6, 7, 8, 9} or {5–9}.

For a hypothetical set of 10 institutions, A through J, here’s what a set of rank-intervals might look like.

Acknowledging the uncertainty in your findings is commendable. But let’s be realistic. If you actually want to make use of these results—for example, if you’re a student choosing a grad-school program—the first thing you’re going to do is sort those bars into some sort of rank order, trying to figure out which school is best and how they all stack up against one another. In other words, you’re going to undo all the elaborate efforts the NRC committee has put into obscuring that information.

Below is one possible ordering of the bars. I have sorted first on the top of the rank-intervals, then, if two columns have the same top rank, I’ve sorted on the bottom rank. Other sorting rules give similar but not identical results. For example, sorting on the midpoints of the intervals would interchange columns B and F.

Question 1. Does sorting a set of rank-intervals by one of these simple rules yield a consistent and meaningful total ordering of the data? To put it another way, can you trust this attempt to reconstruct a ranking?

I hasten to add that this is not really a practical question about finding the best grad school. If you’re facing such a choice in real life, the NRC rank-intervals are not the only available source of information. But, for the sake of the mathematical puzzle, let’s pretend that all we know about schools A through J is embodied in those ranges of rankings.

It turns out that rank-intervals have some fairly peculiar behavior. Ranges of ratings are not a problem. If the NRC merely gave each school a fuzzy rating on the 0-to-5 scale, no one would have much trouble interpreting the results. But when you turn fuzzy ratings into fuzzy rankings, there are hidden constraints. For example, not all sets of rank-intervals are well-formed.

The set at left is impossible because there’s no one in last place. (We can’t all be above average.) The example at right is also nonsensical because D has no ranking at all. For a set of rank-intervals to be valid, there has to be at least one entry in each row and each column.

That’s a necessary condition, but not a sufficient one, as the two graphs below illustrate.

Do you see the problem with the example at left? Column B has a rank-interval of {1–2}, but in fact B can never rank first because A has no alternative to being first. The case at right is conceptually similar but a little subtler: If B is ranked third, then either first place or second place will have to remain vacant.

The underlying issue here is the presence of constraints or linkages within a set of rankings. Suppose you have calculated ratings and rankings of several schools, and then some new information turns up about one school. You can change the rating of that school without any need to adjust other ratings, but not so the ranking. If a school goes from third place to fourth place, the old fourth-place school has to move to some other rung of the ladder, and somebody has to fill the vacancy in third place. These interdependencies are obvious in a non-fuzzy ranking, but they also exist in the fuzzy case. You can’t just assign arbitrary rank-intervals to the items in a set and assume they’ll all fit together. This observation leads to a second question:

Question 2. What are the admissible sets of rank-intervals? How do we characterize them?

I have a partial answer to this question. It goes like this. Any ranking of k things must be a permutation of the integers from 1 through k. A permutation can be embodied in a permutation matrix—a square k × k matrix in which every row has a single 1, every column has a single 1, and all the other entries are 0. For example, here are the six possible 3 × 3 permutation matrices:

They correspond to the rankings (1, 2, 3), (1, 3, 2), (2, 1, 3), (3, 1, 2), (2, 3, 1) and (3, 2, 1).

Since a permutation matrix represents a specific (non-fuzzy) ranking, we can build up a set of rank-intervals by taking the OR-sum of two or more permutation matrices. What do I mean by an OR-sum? It’s just the element-by-element sum of the matrices using the boolean OR operator, ∨, instead of ordinary addition. OR has the following addition table:

                      0 ∨ 0 = 0
                      0 ∨ 1 = 1
                      1 ∨ 0 = 1
                      1 ∨ 1 = 1

For the first two 3 × 3 matrices shown above the arithmetic sum is:

whereas the OR-sum looks like this:

Every valid set of rank-intervals must correspond to an OR-sum of permutation matrices, simply because a set of rank-intervals is in fact a collection of permutations. The converse also holds: Any OR-sum of permutation matrices yields an admissible set of rank-intervals. Thus the OR-sums of permutation matrices—let’s call them ormats for brevity—are in one-to-one correspondence with the admissible sets of rank-intervals. (There’s just one catch when applying this idea to the NRC study. The columns of an ormat may well have “gaps,” as in the column pattern (0 1 1 0 0 1 1), which corresponds to the rank-interval {2–3, 6–7}. Will the NRC allow such discontinuous ranges in their grad-school assessments? Perhaps the issue will never come up in practice. In any case, I’m ignoring it here.)

Arithmetic sums of permutation matrices form an open-ended, infinite series; in contrast, there are only finitely many distinguishable OR-sums. The reason is easy to see: Ormats have k² entries, each of which can take on only two possible values, and so there can’t be more than \(2^{k^{2}}\) distinct matrices. Because of the various constraints on the arrangement of the entries, the actual number of ormats is smaller. For example, at k = 3 the \(2^{k^{2}}\) upper bound allows for 512 ormats, but there are only 49:

Thus we come to the next question.

Question 3. For each k ≥ 1, how many distinct ormats can we build by OR-ing subsets of k × k permutation matrices? Is there a closed-form expression for this number?

I have answers only for puny values of k.

   k       upper bound        # of ormats  
   1                 1                  1
   2                16                  3
   3               512                 49
   4            65,536              7,443
   5        33,554,432          6,092,721
   6    68,719,476,736                  ?

The tallies of ormats were calculated by direct enumeration, which is not a promising approach for larger k. (I note—to spare folks the bother of looking—that the sequence 1, 3, 49, 7443, 6092721 does not yet appear in the OEIS.)

To extend this series, we might try to exploit the internal structure and symmetries of the ormats. By sorting the columns and rows of the matrices, we can reduce the 49 3×3 ormats to just six equivalence classes, with the following exemplars:

Enumerating just these reduced sets of matrices should make it possible to reach larger values of k, but I have not pursued this idea. (Furthermore, the two-dimensional sorting of matrices looks to be a curiously challenging task in itself.)

By the way, I think the number of ormats will approach the \(2^{k^{2}}\) upper bound asymptotically as k increases. Many of the features that disqualify a matrix from ormathood—such as all-zero rows or columns—become rarer when k is large. I have tested this conjecture by generating random (0,1) matrices and then counting how many of them turn out to be ormats.

For k = 1 through 5 the results are in close agreement with the actual counts of ormats, and up to k = 10 the trend is clearly upward. But continuing this inquiry to larger values of k will depend on a positive answer to the next question.

Question 4. Given a square matrix with (0,1) entries, is there an efficient algorithm for deciding whether or not it is an OR-sum of permutation matrices, and thus an admissible set of rank-intervals?

The question asks for a recognition predicate—a procedure that will return true if a matrix is an ormat and otherwise false. If efficiency doesn’t matter, there’s no question such an algorithm exists. At worst, we can generate all the k × k ormats and see if a given matrix is among them. But that’s like saying we can factor integers by producing a complete multiplication table. It just won’t do in practice. Isn’t there a quick and easy shortcut, some distinctive property of ormats that will let us recognize them at a glance?

If we could replace the OR-sum with the ordinary arithmetic sum, the answer would be yes. Permutation matrices have the handy property that all rows and columns sum to 1. An arithmetic sum of r permutation matrices has rows and columns that all sum to r. (It is a semi-magic square.) The converse is also true (though harder to prove): If a matrix of nonnegative integers has rows and columns that all sum to r, it is a sum of r permutation matrices. This fact yields a simple test: Sum the rows and the columns and check for equality.

Unfortunately, the trick won’t work for ormats, because the boolean OR operation throws away even more information than summing does. Because 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1, infinitely many sets of operands map into the same result, and there’s no obvious way to recover the operands or even to determine how many permutation matrices entered into the OR-sum.

Maybe there’s some other clever trick for recognizing ormats, but I haven’t found it. Let me make the question more concrete. Below are three (0,1) square matrices. Two of them are ormats but the third is not. Can you tell the difference?

If it’s so hard to recognize an ormat, how did I count the ormats among a bunch of randomly generated (o,1) matrices? By hard work: I reconstructed the set of permutations allowed by each matrix. Visualize a permutation as a path threading its way through the matrix from left to right, connecting only non-zero elements and touching each column and each row just once. When you have drawn all possible permutation paths, check to see if every non-zero element is included in at least one path; if so, then the matrix is an ormat. Note that this is not an efficient recognition procedure. In the worst case (namely, an all-ones matrix), there are k! permutations, so this method has exponential running time. But k! is better than \(2^{k^2}\); and, besides, for sparse matrices the number of permutations is much smaller than k!. The 10 × 10 matrix presented as an example at the start of this post gives rise to 580 permutations, a manageable number. Here’s what they look like, plotted as a spider web of red paths across the bar chart.

Every nonzero site is visited by at least one permutation path, so this set of rank-intervals is indeed valid.

This process of lacing permutations through a matrix finally brings me back to Question 1, about how to make sense of the NRC’s fuzzy ranking scheme. Let’s take a small example:

Examining the graph above shows that A must rank either first or second—but which is more likely? In the absence of more-detailed information, it seems reasonable to assume the two cases are equally likely; we assign them each a probability of 1/2. Similarly, B has the rank-interval {1–3}, and so we might suppose that each of these three cases has probability 1/3. Continuing in the same way, we assign probabilities to every element of the matrix.

But wait! This can’t be right; our probabilities have sprung a leak. Any proper set of probabilities has to sum to 1. Our procedure assures that each column obeys this rule, but there is no such guarantee for the rows. In row 1, we’re missing one-sixth of our probability, and in row 2 we have an excess of 1/2; row 4 comes up short by 1/3.

Is there any self-consistent assignment of probabilities for the elements of this matrix? Sure. As a matter of fact, there are infinitely many such assignments, including this one:

I’ll return in a moment to the question of how I plucked those particular numbers out of the air, but note first what they imply about the ranking of items A through D. For item A, with the rank-interval {1–2}, the odds are two-to-one that it ranks first rather than second. B has the behavior we expected from the outset, with probability uniformly distributed over the three cases. But if you pick either C or D, each with the rank-interval {2–4}, your chance of getting second place is only 1/6, and half the time you’ll be in last place.

Where do these numbers come from? Instead of starting with the assumption that probability is uniformly distributed over each rank-interval, assume that each possible permutation of the ranks is equiprobable. For this matrix there are six allowed permutations: (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (2, 1, 3, 4) and (2, 1, 4, 3). Observe that four of the six ordering put A first, and only two permutations place A second. We can also tally up such “occupation numbers” for all the other matrix elements:

Dividing these numbers by the total number of permutations, 6, yields the probabilities given above.

We can do the same computation for the 10 × 10 example matrix, which turns out to allow 580 permutations:

If you care to check, you’ll find that each column and each row sums to 580; dividing all the entries by this number yields a probability matrix with columns and rows that sum to 1 (also known as a doubly stochastic matrix).

This process of tabulating permutation paths recovers some of the information we would have gotten from the arithmetic sum of the permutation matrices—information that was lost in the OR-ing operation. But we get back only some of the information because we have to assume that each permutation included in the OR-sum appears only once. (This is just another way of saying that the allowed permutations are equiprobable.) There’s no particularly good reason to make this assumption, but at least it leads to a feasible probability matrix.

Is there any way of calculating the entries in the doubly stochastic matrix without explicitly tracing out all the permutation paths? I’m sure there is. I think the construction of the matrix can be approached as an integer-programming problem, and perhaps through other kinds of optimization technology. What seems less likely is that there’s some simple and efficient shortcut algorithm. But I could be wrong about that; there’s a lot of mathematics connected with this subject that I don’t understand well enough to write about (e.g., the Birkhoff polytope). I hope others will fill in the gaps.

Getting back to the assessment of grad schools—have we finally found the right way to understand those rank-intervals that the NRC promises to publish any day now? My sense is that a semi-magic square (or, equivalently, a doubly stochastic matrix) will give a less-misleading impression than a simple eyeball sorting on the spans or midpoints of the rank-intervals. But what a lot of bother to get to that point! How many prospective grad students are going to repeat this analysis?

Acknowledgment: Thanks to Geoff Davis of PhDs.org for introducing me to this story. PhDs.org will have the new ratings as soon as the NRC releases them, and may even find a way to make them intelligible! Disclaimer: I’ve done paid work for the PhDs.org web site (but this is not a paid endorsement).

Update 2010-07-27: If you’ve gotten this far, please read the comments as well. A number of commenters have provided important insights and context, which have helped me understand what’s going on in the matrices I’ve been calling ormats. But I’m still a bit murky about the best way to recognize and count them. I’m not sure that publishing my still-murky thoughts is terribly helpful, but maybe someone else will read what follows and give us a dazzling, gemlike synthesis.

For the ormat-recognition problem (Question 4 above), three basic approaches have been mentioned: enumerating the permutation paths through the matrix, examining matrix minors, and looking for perfect matchings in a bipartite graph defined by the matrix. It seems to me that all of these methods are doing the same thing.

Start with Barry Cipra’s method of minors. The basic operation is to choose a nonzero matrix element, then delete the row and the column in which that element occurs. You then apply the same operation to the remaining, smaller matrix.

In tracing permutation paths, we’re looking for sequences of nonzero elements, drawing one element from each column and each row. A way of organizing this search is to choose a nonzero element and then, after recording its location, delete the corresponding column and row, so that no other elements can be chosen from that column or row.

In the method based on Hall’s theorem, as explained by John R., we view the ormat as the adjacency matrix of a bipartite graph, where every nonzero element designates an edge connecting a row vertex to a column vertex. To find a matching, we delete an edge, along with the two vertices it connects (and also all the other edges incident on those vertices). Then we recurse on the smaller remaining graph. If you translate this operation on the graph back into the language of matrices, deleting an edge and its endpoints amounts to deleting a row and a column of the adjacency matrix.

I am not asserting that these three algorithms are all identical, but they all rely on the same underlying operation. To say more, we would need to consider the control structure of the algorithms—how the basic operations are organized, how the recursion works, all the details of the bookkeeping. I don’t trust myself to make those comparisons without trying to implement the three methods, which I have not yet done. However, at this point I just don’t see how any method can guarantee correct results without something resembling backtracking (or else exhaustive search through an exponential space). After all, we’re not looking for just one matching in the graph, or one decomposition into matrix minors, or one permutation path; we have to examine them all.

Here’s a further hand-wavy argument for the essential difficulty of the task. For a (0,1) matrix, the number of permutation paths that avoid all zero entries is equal to the permanent of the matrix. Computing the permanent of such a matrix is known to be #P-complete.

How I love to go out hunting on a bright Sunday morning—though it’s not my style to shoot furry/feathery/finny animals. My game is to get up early and stalk a wily factoid.

A posting from Mat Roberts, whose blog I’ve recently discovered, sent me out this morning to chase down a passage in How Long Is a Piece of String, a book by Rob Eastaway and Jeremy Wyndham:

The concept here seemed familiar, but the term “Lincoln Index” was new to me. Lincoln who? What index?

Google offered some useful clues. (Also a generous helping of false scents—books about Honest Abe that happen to have an index.) Without even clicking on a link I had the general context:

The Lincoln Index provides a way to measure population sizes of individual animal species. It is based on a capture/mark/ recapture method…

So we’re talking ecology and population biology. The original idea was not to catch the same typo twice but to catch the same furry/feathery/finny creature twice. Interesting. However, the first couple of web pages that Google sent me to (here and here) told me nothing about Lincoln. And, oddly, I found no Wikipedia entry for “Lincoln Index.” If it’s not in Wikipedia, does it exist?

With a little more poking around, I stumbled upon another clue that seemed promising: a mention of “the Lincoln-Pearson equation for estimating population size.” I was still in the dark about Lincoln, but Pearson is quite a familiar figure. Surely that’s Karl Pearson, the pioneering statistician, who did much of his work in the biological sciences and might very well have come up with a scheme for estimating population sizes.

Back at Google, though, searching for “Lincoln-Pearson” turned up nothing pertinent other than the page I’d come from (though I did learn that Karl Pearson “read in chambers in Lincoln’s Inn” during his early years studying law).

More beating the bushes. Eventually I realized I had wandered into a blind alley. Somebody needs to hire a pair of proofreaders: The formula is not “Lincoln-Pearson” but “Lincoln-Petersen.” Try those names at Google and you’ll get an abundance of useful pointers. (You’ll also learn that Abraham Lincoln died in Petersen’s Boarding House, across the street from Ford’s Theater. Google is not just a search engine but also a coincidence engine.)

The particular web page where I finally got the correct names (notes for a course at North Carolina State University) explains that capture-mark-recapture methods

are used extensively to estimate populations of fish, game animals, and many non-game animals. The approach was first used by Petersen (1896) to study European plaice in the Baltic Sea and later proposed by Lincoln (1930) to estimate numbers of ducks. Petersen’s and Lincoln’s method is often referred to as the Lincoln-Petersen Index, even though it is not an index but a method to estimate actual population sizes. (Should it not be the Petersen-Lincoln Estimate?)

I decided to pursue Petersen first—and immediately ran into a few further bibliographic brambles. Some citations spell the name “Petersen” and others “Peterson.” Some give the initials “C. G. T.” and others “C. G. J.” or “C. J. G.” The date might be 1895 or 1896 or 1897. Here’s what I believe to be a correct citation:

Petersen, C. G. J. 1896. The yearly immigration of young plaice into the Limfjord from the German Sea. Report of the Danish Biological Station to the Home Department 6:1–48.

Wikipedia identifies our elusive author as Carl Georg Johannes Petersen (1860-1928). He was a founder of the Danish Biological Station, which was not in fact a station but a mobile laboratory—a decommissioned naval vessel that was moved around from year to year. In 1895, Petersen took the station to the Limfjord, a chain of bays, lakes and channels cutting across the Jutland peninsula in northern Denmark. There he studied the plaice fishery. (Back to Wikipedia: “The European plaice is a right-eyed flounder belonging to the Pleuronectidae family.” But let’s not get started on right-eyed and left-eyed flatfish, or we’ll never get to the end of this.)

Petersen’s report is available online, scanned from a copy belonging to the library of the Marine Biological Laboratory and Woods Hole Oceanographic Institution, and hosted by the Biodiversity Heritage Library of the Internet Archive. A second surprise: The report is written in English. But on reading through it I find only vague and murky connections between the work Petersen reports and the mark-recapture method of estimating populations. There’s nothing resembling the E₁E₂/S formula.

Petersen does describe a series of capture/mark/recapture experiments. A few hundred plaice were caught and marked by attaching numbered buttons, then put back in the water. Fishermen who recaught the labeled fish in later months were asked to report them. But the purpose of this study was not to estimate the total population; instead, Petersen used before-and-after measurements of the marked fish to estimate their growth rate.

In a much larger experiment, some 82,580 plaice (somebody must have counted them!) were transplanted into the fjord, and 10,900 of the fish were marked by having a hole punched in their dorsal fin. The number of marked fish was recorded as the plaice were caught during the coming year. It’s not clear whether the aim of this project was to estimate the total population, but in any case it didn’t work. The fraction of marked fish in the transplanted batch was about 1/7, but the marked fraction in the subsequent catches was 1/5. Petersen remarks, “This result is very strange,” and I have to agree.

When Petersen did try to estimate the plaice population, he didn’t rely on a recapture scheme. He went out with seine nets designed to dredge up every bottom fish in a measured plot, then extrapolated from the density of fish per unit area.

The whole report is fascinating fishy stuff, but it leaves me wondering just how Petersen came to be given credit for the resampling idea. As far as I can tell, it’s not to be found in this paper.

Having chased down Petersen, I turned back to Mr. Lincoln. Without much trouble I was able to identify the work in question:

Lincoln, F. C. 1930. Calculating waterfowl abundance on the basis of banding returns. United States Department of Agriculture Circular 118:1–4.

The author was Frederick C. Lincoln, who was bird-bander-in-chief in the U.S. for some 25 years. The agency he founded has since migrated from the Department of Agriculture to the U.S. Geological Survey and become the Bird Banding Laboratory.

Google returns hundreds of works that cite Lincoln’s paper (including some quite far afield from population biology). But tracking down the USDA document itself was not so easy. If the USDA has it online, I wasn’t able to locate it. But a search of WorldCat eventually turned up an archive in the Hathi Trust Digital Library where you can page through Lincoln’s pamphlet in a copy scanned by Google at the University of Minnesota library.

Lincoln gives only a brief and informal account of the recapture idea, but the basic principle is stated clearly enough:

If in one season 5,000 ducks were banded and yielded 600 first-season returns, or 12 percent, and if during that same season the total number of ducks killed and reported by sportsmen was about 5,000,000, then this number would be equivalent to approximately 12 per cent of the waterfowl population for that year, which would be about 42,000,000.

It’s not hard to translate this formula from the language of duck hunters into the language of proofreaders. The first reader finds 5,000 typos and the second spots 5 million; 600 of these errors are common to both lists, and so the total number of typos is:

So that’s my reward for a morning spent out hunting: 42 million typos.

Does Frederick Lincoln deserve credit for the Lincoln Index? I’d say he has a good claim, except that Pierre Simon de Laplace had the same idea more than a century earlier. In 1802 Laplace applied his method to estimating the (human) population of France. But maybe that’s a story for another Sunday morning.

Epilogue. This is not really a story about typos, or about fish and ducks. It’s about finding things—about the phenomenal ease of chasing facts on the world wide web. Does a marked fish have any hope of escaping recapture there?

The school of philosophy called Antipodianism briefly flourished on the fringes of the Hellenistic world more than 2,000 years ago. The sect held that every person has an opposite number, a mirror image who inverts all our beliefs, feelings, actions and attitudes. If I smile, my antipodian counterpart frowns; when I wake, she sleeps. If I’m a Mac, she’s a PC. For every liberal Democrat there’s an antipodian Tea Party Republican. In this way the universe is held in balance. It’s an enforced equilibrium, which none of us has the power to upend, hard as we might try.

The earliest of the Antipodians believed that every such matched pair (commonly designated A and ∀) live at diametrically opposite points on the surface of the earth. This arrangement ensures that A and ∀ can never meet—thereby averting a cosmic catastrophe. A later quantum-field version of Antipodianism relaxed the geographic constraint by allowing for the creation and annihilation of A∀ pairs, but that idea never really caught on.

One day an Antipodian master was teaching an exchange student from New Zealand. The child was crafty.

“Is it not true,” she asked, “that A and ∀ always do the opposite thing?”

“Yes, antisymmetry demands it,” the master replied.

“If A walks north, ∀ must walk south?” the child asked.

Again the master assented.

“If A goes east, ∀ must go west?”

“Yes.”

“If A turns to the right, ∀ must turn to the left, no?”

The master agreed, although he sensed trouble coming.

“I’m afraid the universe is out of joint,” said the child. “If A goes north and turns to the right, while ∀ goes south and turns to the left, afterwards they are both walking east. They are doing the same thing.”

Needless to say, this was a moment of crisis in Antipodian doctrine. The Pythagoreans, you may recall, resolved a similar impasse by resorting to violence. When some upstart challenged their precept that “all is number” by showing that no known number can be the square root of 2, the Pythagoreans tossed the troublemaker out of the boat. But in this case the Antipodian master kept his calm.

“Ah my little Kiwi,” he said to the student. “You are clever but not wise. Your own statements refute your claim. Did you not begin by saying that A and ∀ always do the opposite thing? When A walks 10 paces north, ∀ walks 10 paces south. When A turns right, ∀ turns left. But now you would have us believe they both take a step forward, contradicting the most basic law of their nature. What really happens is that A walks forward and ∀ walks backward. Thus A goes eastward and ∀ westward, and all is well with the world.”

Through this brittle sophistry the master extricated himself from the classroom—though he may have had to walk backwards to make good his escape. He never taught again. The Kiwi student went on to a brilliant career studying the weak interactions of neutral K mesons. As for Antipodianism, it vanished without a trace.

Or maybe it left a tiny trace. I’ve never visited the antipodes, but I hear that corkscrews Down Under turn the other way.

The printed program for the recent STOC meeting in Cambridge announced the following talk:

Unfortunately, the fourth author could not be present (and he is not listed as an author on the paper itself), so the talk was given by Gregory Valiant.

Here is a motivating example. Take a tape measure, and go record the heights of a few thousand adults chosen at random. You’ll come back with a distribution that looks something like this:

How come the curve is so lumpy and lopsided? Isn’t height a variable with an approximately normal distribution? Of course it is. The problem is that we have mixed up two subpopulations—men and women—with different height distributions:

Question: Given the lumpy combined distribution, and the knowledge that it represents a mixture of exactly two normal distributions, can we somehow recover the component distributions? Specifically, can we determine the means and standard deviations and the Gaussian curves, as well as their relative weights, or contributions to the total?

The answer is yes. In a series of papers published in the 1950s and 60s, Henry Teicher (then at Purdue, now emeritus at Rutgers) proved a kind of unique-factorization theorem for distributions. He showed that no mixed distribution can be decomposed into two or more different sets of normal distributions, just as no composite whole number can be formed as the product of two or more distinct sets of primes. (Teicher’s theorem generalizes to many distributions other than normal ones. There are also a few caveats; for example, none of the component distributions can be pointlike, with a standard deviation of zero.) Teicher’s work implies that a mixed distribution is identifiable: If you can break it down into a set of primitive distributions, then that decomposition is unique.

If STOC were a mathematics meeting, that might be the end of the story. But STOC is the Symposium on the Theory of Computing, and the question here is not “Does a solution exist?” but rather “Can you solve it in polynomial time?” Teicher’s result offers no such guarantee. It turns out that his proof of identifiability depends on the behavior of the distributions far out in the tails. Measuring data frequencies in these sparsely populated outlying regions requires an exponentially large number of samples. But other approaches to the problem don’t run into this snag; Valiant and his colleagues show that “robust polynomial identifiability” is indeed possible.

A key idea in their proof goes back at least as far as the 1890s, to work done by the indefatigable statisticians W. F. R. Weldon and Karl Pearson. In 1892 Weldon spent a summer on the Bay of Naples, measuring various features on the carapaces of crabs. One such feature yielded a distinctively lumpy distribution much like the height curve shown above. Weldon thought that the asymmetry might signal the incipient splitting of the crab population into two races or species, each of which if taken individually would have a normal distribution. For help with the analysis of his data he turned to Pearson, who was able to identify two component Gaussian curves that sum up to the observed distribution. (The figure comes from Weldon’s 1893 paper; see below for references.)

Pearson’s method was based on calculating the first six statistical moments of the given distribution. (The nth moment of a distribution is the expectation value of \((x-\bar{x})^n\), where \(x\) is a random value drawn from the distribution and \(\bar{x}\) is the mean value.) The process called for solving a ninth-degree polynomial, which was a heroic feat in 1893.

Valiant et al. show that a procedure like Pearson’s will always succeed in the following sense: If two mixed distributions can be distinguished at all, then they can be distinguished by examining their first six moments, and those moments characterize the component Gaussians. Calculating the moments requires only a polynomial number of samples, and the running time of the overall algorithm is a polynomial function of various parameters such as the required accuracy. Moreover, the process can be extended from one-dimensional distributions to multidimensional Gaussians.

Although the algorithm has polynomial running time, that’s not a guarantee of practicality. (After all, this is a theory conference.) One stage of the process is essentially a brute-force search through a very large (though polynomially bounded) space of parameter values for the six moments.

Sources:

The STOC proceedings with the Kalai-Moitra-Valiant paper are now available online, but only by subscription. A PDF preprint is posted on Valiant’s web site; also an expanded version.

For Henry Teicher’s work see: “Identifiability of Mixtures,” The Annals of Mathematical Statistics 32(1):244–248 (1961) and “On the Mixture of Distributions,”  The Annals of Mathematical Statistics 31(1):55–73 (1960).

For Weldon and Pearson see: W. F. R. Weldon: “On Certain Correlated Variations in Carcinus maenas,“ Proceedings of the Royal Society of London 54:318–329 (1893) and Karl Pearson: “Contributions to the Mathematical Theory of Evolution,” Philosophical Transactions of the Royal Society of London A 185:71- 110 (1894).

My thanks to Virginia Gold and Irene Frawley at ACM, Lance Fortnow, Paul Oka, Jennifer Chayes and Christian Borgs, all of whom helped make it possible for me to attend some of the STOC sessions.

The snarXiv is a ran­dom high-energy the­ory paper gen­er­a­tor incor­po­rat­ing all the lat­est trends, entropic rea­son­ing, and excit­ing mod­uli spaces. The arXiv is sim­i­lar, but occa­sion­ally less ran­dom.

Inspiring! Soon bit-player, too, will be generated by a context-free grammar, and no one will know the difference.

The explosion and fire that destroyed the drilling rig Deepwater Horizon on the night of April 20 was a run-of-the-mill industrial accident. In saying this, I don’t mean to make light of the disaster, in which 11 workers perished. Nevertheless, it’s important to recognize that events like this one have happened before. They happen all the time. Just two weeks earlier, an explosion in a West Virginia coal mine killed 29 workers. A refinery fire in Anacortes, Washington, killed seven on April 2. In February six workers died in a natural gas explosion at a power plant under construction in Connecticut. In January, leaking phosgene gas killed an operator at a West Virginia chemical plant. Looking back a few years further, a 2005 fire at a BP refinery in Texas City, Texas, killed 15 workers and injured 170 more. There was another fatality at the same refinery in 2008. Texas City was also the site of a fertilizer explosion in 1947 that destroyed much of the port and left almost 600 dead. Then there’s the Bhopal catastrophe, where toxic fumes from an insecticide plant suffocated thousands of residents of nearby neighborhoods.

Still another accident that belongs in this sad catalogue is the destruction of the Piper Alpha platform in the North Sea oil fields. Piper Alpha was not a drilling rig but a production platform; it pumped oil and natural gas from completed wells to a terminal in the Orkney Islands. On the night of July 6, 1988, a huge explosion shattered the main part of the platform, and a subsequent fire consumed the rest; 167 crew members died. The apparent cause was a miscommunication: The night shift tried to start up a pump, not knowing that the day shift had removed a crucial valve for maintenance, leading to a massive leak of flammable gas.

It’s a bitter truth: Industrial accidents are business as usual. Death on the job is a cost that we (as a society) are evidently willing to accept and pay. When a mine collapses or a sugar refinery explodes, we read the story in the newspaper and we watch the film at 11, and then we grit our teeth and move on. The Deepwater Horizon sinking is just another in this long series of mishaps.

And yet it’s also totally different. This accident has consequences that reach beyond the workers and their families. A hole in the bottom of the ocean has been spewing hydrocarbons for six weeks. The rate of loss could well be a million gallons a day. Efforts to control the well are still under way, but if they fail the spill might go on for another three months. All that makes for a nightmare that doesn’t drop out of the news cycle after the first 24 hours.

In this respect, Deepwater Horizon may turn out to be not another Piper Alpha but another Three Mile Island. The 1979 accident at that nuclear power station had lasting consequences: We haven’t built another nuclear plant in the U.S. in the 30 years since. (There are other reasons for the long lassitude of the nuclear industry, but TMI was a major factor.) Likewise, in the aftermath of Deepwater Horizon, it seems a fair guess that we won’t be drilling another deep offshore well anywhere near the U.S. coastline for years to come, and maybe decades. Maybe never.

A moratorium on offshore drilling, enforced by economic as well as legal and political pressure, looks like a perfectly sensible response to the current situation. But we deserve more. By all means, let’s do whatever necessary to avoid repeating this particular mistake, but at the same time let’s address the broader issue of why things all over the industrial landscape keep blowing up and falling down.

Will we ever learn what happened on the Deepwater Horizon? There are certainly a lot of investigators trying to find out. Three Congressional committees have heard testimony already. A board of inquiry formed by the Coast Guard and the Minerals Management Service is holding its own series of hearings. So is a state panel in Louisiana. On May 11 President Obama asked the National Academy of Engineering to look into the cause of the accident, then on May 22 he appointed a special commission to carry out yet another investigation. Meanwhile the Justice Department is studying possible civil or criminal penalties.

For all that effort, we sure haven’t learned much yet. The well is leaking, but BP isn’t. It’s amazing how they’ve managed to keep the public and the press at a distance; the one art they seem to have mastered is secrecy. Even friendly trade publications (e.g., Oil and Gas Journal, Offshore) have so far failed to penetrate the security cordon. In the end, though, the story will come out. We’re going to learn why that blowout preventer didn’t prevent a blowout. But I’m not so confident we’ll learn how to prevent the next blowout.

The only blowout preventer I’ve ever seen up close and personal was on a drilling rig near Oklahoma City in 2004. At the time, I thought it was quite a brawny-looking piece of gear, with all those rings of torqued bolts clamping the flanges together, and the big red hydraulic rams like pincers clasping the pipe. Apparently, this unit is puny compared with the BOP stack installed on the Deepwater Horizon well (“five stories tall” in news accounts). Still, the principle of operation is the same: If the well “kicks”—meaning that gas and oil begin to push their way toward the surface—the rams close off the well and keep everything sealed tight. Some rams are meant to choke off the annular space around the drill pipe; some are “blind rams” used when no drill pipe is present in the bore; the last resort is a pipe ram or shear ram meant to crush or cut off the drill pipe.

It sounds foolproof, but evidently not. Controls can stick, valves can leak, parts can break. I’ve read speculation that the shear ram on the BOP beneath the Deepwater Horizon might have failed because it happened to strike a thicker-walled section of drill pipe where two lengths of tubing are threaded together; I really hope that’s not a serious concern, because it would mean that every BOP on the planet has a failure probability of 3 percent. (Drill pipe comes in 30-foot lengths, and the thickened sections are about a foot long.)

A 1997 article in Offshore lists a fascinating variety of other failure modes for deep-water wells. The article is by Larry H. Flak of Boots and Coots—a company often called in to deal with crises like this one. Flak is writing for an audience of oil-patch insiders, and I don’t follow all of his jargon. For example, there’s this wonderfully opaque passage:

Broached blowouts could happen with casing failure. Recently, an ultra-deepwater operator swabbed in a kick resulting in over 9,000 psi on the subsea BOPs. Fortunately, the casing was sound and set just on top of the sand. This allowed safe kick bullheading.

Even for those of us who have never bullheaded or swabbed in a kick, the message comes through: A lot can go wrong. A well is not just a hole in the ground; it’s a fairly complicated structure with multiple concentric layers of casing and drill pipe, which create several interconnected annular spaces; fluids under pressure can find many pathways to the surface. Flak points out that even the massive steel blades of a hydraulic ram can be torn to pieces by high-velocity streams of abrasive fluids, such as drilling mud. He concludes: “Blowout control options in ultra-deepwater are very limited. Blowout prevention is of paramount importance.”

When the story of the Deepwater Horizon accident is finally told, we’re going to hear at least two interpretations. In one telling, BP and its contractors were incompetent or negligent or criminally greedy; they screwed up. But the basic technology of offshore drilling is sound, and if only the companies had followed established industry practices and common sense, none of this mess would have happened. In the other version, BP and its contractors were incompetent or negligent or criminally greedy; they screwed up. But even if they had followed approved industry practices, a disaster like this was waiting to happen, because the technology of offshore drilling is fatally flawed. I really wish I knew which of these stories to believe. I worry that we lack the institutional means to decide between them.

•     •     •

I’m a great admirer of the National Transportation Safety Board. When an airliner crashes or a couple of commuter trains collide, the NTSB mounts a focused, scientific effort to understand the cause of the accident. Investigating accidents is all they do, and this turns out to be a key to their success; they are insulated from the responsibilities and temptations of regulating the industry, adjudicating legal culpability, assessing penalties or even enforcing their own safety recommendations. Separating the investigative and regulatory functions has worked brilliantly, and the board’s findings command wide respect. But the NTSB won’t be investigating the Deepwater Horizon blowout, because the event doesn’t fall within their statutory purview; it’s not a transportation accident. There’s also a Chemical Safety and Hazard Investigation Board (CSB), which has had a similar role in the chemicals industry since 1998. You might think that petroleum would count as a chemical substance, but as far as I can tell the CSB will also be sitting this one out. Their mission statement says: “The CSB conducts root cause investigations of chemical accidents at fixed industrial facilities.” The Deepwater Horizon wasn’t “fixed.”

So here’s my call for action: We need a single agency, modeled on the NTSB and the CSB, with authority to investigate all accidents involving industry or infrastructure—everything from well and refinery fires to water-main breaks, power blackouts, mine cave-ins, bridge and dam failures, boiler explosions and sewage spills. I believe we’re under a moral imperative to learn all we can from every such accident, in the hope of preventing a recurrence. A permanent, independent agency with investigative authority, in-house expertise and technical resources looks to me like the best way to reach this goal.

After the 2005 refinery fire in Texas City, BP hired James Baker III (the former Secretray of State) to convene a special of inquiry into the company’s safety practices and culture. The Baker panel report observed that BP had an admirable record on personal safety but cited deficiencies in process safety. Personal safety says: Wear your hardhat, your eye protection and your steel-toed boots when you go out in the plant to open a valve. Process safety says: Make sure you open the right valve, not the one that’s going to create a fireball that engulfs the whole plant. The report remarks: “BP mistakenly interpreted improving personal injury rates as an indication of acceptable process safety performance.” On April 20, BP executives flew out to the Deepwater Horizon to celebrate a personal safety milestone on the rig: no loss-of-work accidents in seven years. The executives were still on board when somebody turned the wrong valve.

Note: I have posted a PDF of the oil and gas chapter from my book Infrastructure: A Field Guide to the Industrial Landscape on the book’s web site.

Update 2010-06-21: A superb report on the failure modes of blowout preventers was published this morning in The New York Times. The article is by David Barstow, Laura Dodd, James Glanz,  Stephanie Saul and Ian Urbina. Nothing they say is reassuring.

Tomorrow I’ll be doing a gig on “The State of Things,” broadcast by North Carolina Public Radio. The main subject of discussion will be Scott Huler’s new book On the Grid; I’ll be present as supporting cast (call me a bit player) and will doubtless find a way to plug my own book Infrastructure.

If you’re within listening range of a North Carolina Public Radio station, tune in between noon and 1 p.m. Later in the day the audio should be available online.

Martin Gardner died over the weekend. He was 95 and living in Norman, Oklahoma, not too far from his birthplace in Tulsa.

Like many others, I grew up on Martin’s “Mathematical Games” column in Scientific American. Later I joined the staff of that magazine—but don’t imagine that Martin and I became office buddies. As a matter of fact, I never once saw him in the office. He worked at home. He attended none of our editorial meetings. We never had lunch together. Indeed, I never would have met him at all except for the coincidence that we lived a few blocks apart, and every now and then I would be called upon to deliver a package of urgent proofs. (By the way, his address in those days was on Euclid Avenue!)

Someone on the magazine staff described Martin as “a shy woodland creature,” and the tag stuck. Looking back, however, I think it tells only half the story. Yes, Martin was no schmoozer, and he preferred to stay out of the spotlight, both in person and in print. Most of his best-known columns reported on someone else’s discoveries—Conway’s game of life, RSA’s cryptosystem, Penrose’s tilings. He delighted in annotating other people’s work, as in his celebrated edition of Lewis Carroll. Yet he was anything but timid or retiring. In an argument, the shy woodland creature was a grizzly bear. He had strongly held opinions and philosophical convictions, and he knew the worth of his own work. He was a man of ideas, to be taken seriously, yet also a man who had fun with his ideas.

As a celebration of Martin’s peculiar genius, I would like to revive the little puzzle that formed the basis of his very first column, in January of 1957. (He had published a few articles in Scientific American earlier, but this was the first column to appear under the “Mathematical Games” title.)

On the bingo card above, choose any number, circle it, and cross out all the other numbers in the same column or row. Now select a second number from among those that remain unmarked, and again circle your choice and then cross out the rest of the column and row. Continue in this way until there are no unmarked numbers left to choose.

The sum of the circled numbers is 57. How did I know that? How did Martin construct the matrix?

Update 2010-05-29: Here is Martin’s own explanation of the 1957 puzzle:

Like most tricks, this one is absurdly simple when explained. The square is nothing more than an old-fashioned addition table, arranged in a tricky way. The table is generated by two sets of numbers: 12, 1, 4, 18, 0 and 7, 0, 4, 9, 2. The sum of these numbers is 57. If you write the first set of numbers horizontally above the top row of the square, and the second set vertically beside the first column [see Fig. 9], you can see at once how the numbers in the cells are determined. The number in the first cell (top row, first column) is the sum of 12 and 7, and so on through the square.

You can construct a magic square of this kind as large as you like and with any combination of numbers you choose. It does not matter in the least how many cells the square contains or what numbers are used for generating it. They may be positive or negative, integers or fractions, rationals or irrationals. The resulting table will always possess the magic property of forcing a number by the procedure described, and this number will always be the sum of the two sets of numbers that generate the table.

If you were an astute or lucky stock trader on the afternoon of May 6, you could have bought shares of Accenture PLC for a penny each and sold them a minute later for almost $40. Or you could have invested in Sotheby’s for about $30 a share and, if your timing was right, sold out at a price of $99,999.9999. Did you miss those moneymaking opportunities? Don’t kick yourself too hard. Those particular trades were canceled by the exchanges as “clearly erroneous errors.” But millions of other bizarre transactions were allowed to stand, even though prices were fluctuating wildly.

A preliminary report on these events was released last week by a joint committee of the Commodity Futures Trading Commission and the Securities and Exchange Commission. The report reads a lot like an inquiry into an airplane crash, evoking both horror and fascination. But whereas the investigators of aircraft accidents usually come up with a likely cause, the CFTC/SEC committee makes clear that they don’t yet understand what happened on May 6, and it seems possible we’ll never know.

Throughout that day, stock prices were trending lower, a decline attributed mainly to worries about the European economy. But those concerns can’t account for the extraordinary crevasse the market fell into and then climbed out of between 2:30 and 3:00 p.m. The Dow Jones Industrial Average (blue) and the Standard and Poor’s 500 index (green) both lost 6 or 7 percent of their value in less than 10 minutes, then gained it all back. If those price changes are extrapolated to all U.S. stocks, something like a trillion dollars went missing for half an hour. (The red line in the graph, labeled E-Mini S&P 500, refers to a stock futures contract, which I’ll discuss below.)

What could cause such rapid whipsawing? The first speculations implicated a “fat-finger trade”—a data-entry error. There have been several such events in recent years; for example, in 2005 a Japanese broker who meant to sell 1 share of stock at a price of 610,000 yen keyed in instructions to sell 610,000 shares at 1 yen. However, the committee finds no evidence of such goofs on May 6.

The committee also dismisses the Procter & Gamble theory, put forward by commentators on CNBC who noticed a particularly sharp break in the stock of that company (one of the 30 Dow components).

The decline in PG did not begin until 2:44 p.m., well after the broader market indices, which began their precipitous drop at approximately 2:40 p.m. Accordingly, early reports that an inordinately large trade in PG may have triggered the broad market decline do not appear well founded.

Various kinds of deliberate mischief have also been mentioned as possible causes. Maybe some secretive hedge fund has found a way to manipulate the market to its own advantage. Or a hacker might have infiltrated the computer networks that handle stock transactions. The glitch could even be an act of international terrorism. Again, the committee finds no signs of such malevolence but can’t entirely rule out the possibility.

The committee gives closer scrutiny to high-volume trading on the stock futures market, and in particular to the E-Mini S&P 500 futures, which offer a mechanism for betting on the value of the S&P 500 index a few weeks in the future. Traffic in S&P 500 futures was unusually heavy on May 6, and it spiked at the time of the big dip:

The price excursions were wide enough to trigger a “Stop Logic” system that halted trading for five seconds. Furthermore, transactions initiated by a single firm accounted for some 9 percent of the trading volume in the critical half-hour, and all of that firm’s activity was on the selling side. (The committee report does not name this firm, but others have identified it as Waddell & Reed, a mutual fund in Overland Park, Kansas.) So, do we blame it all on a mutual fund run amok in the KC suburbs? The committee thinks further investigation is warranted, but they also note that the same firm has made similar trades in the past, as have many other parties, all without causing a ripple in the wider market.

Two more items of Wall Street arcana that get a lot of attention in the report are stop-loss orders and stub quotes. A stop-loss order causes a stock to be sold automatically if the price falls below a specified threshold. Traders enter such orders in the expectation that the sale will take place at a price near the threshold level, but if prices are falling rapidly, there’s no assurance of that. For a few minutes on May 6, certain stop-loss orders had the effect not of stopping losses but of maximizing them. At the instant when the orders were executed, there were no purchase offers at any price higher than a penny, and so that’s the price the stocks sold for. The offers of $0.01 are thought to have been “stub quotes,” placed by brokers who act as market-makers and who are therefore obliged always to have both buy and sell orders in place. Stub quotes are a way of meeting this obligation at times when the broker doesn’t really want to be in the market. Trades are never supposed to be executed at the stub price, but that’s what happens if no one else is buying. (Transactions at $100,000 per share reflect stub quotes at the other end of the scale, for shares that no one else is willing to sell.)

•     •     •

If the Commodity Futures Trading Commission and the Securities and Exchange Commission don’t know what went wrong on May 6, then I’m sure I don’t know either. But a couple of points seem pretty obvious (which may be why the committee left them unstated).

First, whatever happened on May 6 must have been driven by the internal dynamics of the securities markets, not by events in the larger economy. No changes in the business prospects of Accenture PLC would justify 4,000 percent swings in the company’s market value within half an hour.

Second, there’s got to be some instability at work here—some positive feedback loop. A thousand-point dip in the Dow wasn’t just a freak coincidence, where millions of stockholders acting independently all chose to sell at the same moment, and then a few minutes later changed their minds and decided to buy. Rather, there must have been some mechanism whereby one trader’s decision to buy or sell induced other traders to do the same.

The committee report points out that stop-loss orders create one such destabilizing loop, which is hard-wired into the market machinery. If a stop-loss order on a particular stock is activated at $100, say, the sale of those shares might drive the market price down to $95, triggering more stop-loss orders and lowering the price still further, in a runaway cascade. More generally, any trading strategy that calls for following trends or tracking “market momentum” is susceptible to this kind of instability. For any one individual, selling out when the market sags may or may not be a prudent policy; but if everyone adopts such a rule, the outcome is certain disaster.

Positive feedbacks of some kind surely had a role in the crash of May 6, but they can’t be the whole story. If a wave of self-reinforcing selling accounts for the sudden dive in prices, what explains the equally sudden turnaround and recovery? And there’s an even deeper question. It’s not hard to dream up models in which every random fluctuation is amplified by positive feedback, but the result is an economy that experiences weird jolts and hiccoughs all the time. A useful theory of May 6 has to explain not only what happened on that day but also why it doesn’t happen routinely.

Some analysts have compared the May 6 event with the stock market crash of October 1987, which was even deeper than the recent dip, although it played out over a period of days rather than minutes. I have vivid memories of this event; I followed it on the radio (no CNBC in those days) and then I read the post-mortem reports. But apparently my memory is faulty in certain crucial details. The crash was blamed in large part on “program trading,” which I took to mean that computer programs were making buy and sell decisions in real time. The root of the problem, as I understood it then, was that multiple programs controlling large investments all shared the same basic logic, so that they would all react in the same way to changing market conditions. It turns out, though, that the computing machinery of the time was not up to operating in this online regime. Instead, the economic models were run in batch mode, and the trades were executed after the fact. There were people in the loop.

Today, in contrast, thousands of computers are plugged directly into the markets, and program trading is everywhere. The big hedge funds and other major players install their servers in colocation facilities next door to the major exchanges, as a way of reducing communication latency. For “high frequency traders,” transactions are routinely completed in about a third of a millisecond. From the point of view of these firms, the sudden market collapse on May 6 played out in slow motion. During the 10 minutes of tumbling prices, a trading rate of three transactions per millisecond allows time for 180,000 transactions.

Perhaps, then, the much-feared runaway automation of 1987 has finally caught up with us in 2010. Ironically, though, the CFTC/SEC report hints that if automated trading was behind the May 6 glitch, the problem might not be the presence of these traders but rather their sudden withdrawal from the market. Julie Creswell tells the story in The New York Times:

RED BANK, N.J. — Above the Restoration Hardware in this Jersey Shore town, not far from the Navesink River, lurks a Wall Street giant.

Here, inside the humdrum offices of a tiny trading firm called Tradeworx, workers in their 20s and 30s in jeans and T-shirts quietly tend high-speed computers that typically buy and sell 80 million shares a day.

But on the afternoon of May 6, as the stock market began to plunge in the “flash crash,” someone here walked up to one of those computers and typed the command HF STOP: sell everything, and shutdown.

According to Creswell, high-frequency traders account for between 40 and 70 percent of all the trading volume on U.S. securities markets, so the sudden departure of these market participants would certainly have a noticeable effect.

Almost everything about the stock market has changed utterly in the years since 1987. Back then, trading was done by guys in colorful blazers yelling at one another on the floor of the New York Stock Exchange. That trading floor still exists, but it’s a kind of Wall Street theme park, maintained for the benefit of visiting high school classes and CNBC cameras. Most of the actual trading in NYSE stocks is done across the river in Jersey City by electronic ”matching engines” that line up offers to sell with bids to buy. Once there were “specialists” in each stock who were expect to intervene with their own capital to damp out unwarranted price fluctuations. That role has not disappeared entirely, but in most modern markets no one has legal responsibility for maintaining stability. In 1987 most stocks could be bought and sold in only one venue; now, transactions are automatically routed to whatever exchange offers the best terms, including the ominously named “dark pools,” where shares change hands anonymously. Back then, brokerage fees and other transaction costs were high enough to discourage strategies such as high-frequency trading; now there is much less friction in the market. It’s a new world.

Even though the CFTC and the SEC have not yet sorted out the causes of the May 6 blip, they are already proposing remedies. The basic tool is the time out: When the market throws a tantrum, it will be told to sit in the corner for a few minutes. Many such rules already exist, some of them going back to 1987. The rationale is that a pause in trading will allow time for “additional liquidity to enter the market.” In other words, if everyone is selling in a panic, we wait a little while for some buyers to show up. Of course the pause might also allow time for more sellers to join the stampede.

A year ago, I was writing about the uneasy relations between economics and the engineering discipline known as control theory. That was in the context of macroeconomics, where the aim is to control cycles of boom and bust with a time scale of years or decades. The challenges of controlling securities markets are rather different: The time scale is much shorter, which means you have to act quicker, but on the other hand it’s much easier to measure what’s happening, to gather information second by second. But the biggest impediment to effective control is the same in both cases: It’s hard to control the dynamics of a system when you don’t understand those dynamics—when you can’t reliably predict what the system will do in the absence of control or how it will respond to control actions. Given the human element in economic affairs—including the likely presence of actors who will try to subvert any control strategy—it’s not clear that we can ever have that kind of predictive power.

The Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (better known as Abramowitz and Stegun) is a much-storied book. Not that it’s a book full of stories; truth is, there’s not much of a narrative thread running through those formulas, graphs and mathematical tables. But it’s a book with a story behind it.

The story began in the late 1930s, when the Mathematical Tables Project was launched in a factory building on the West Side of Manhattan. Supported by the Works Progress Administration, the Tables Project had dual aims: first, preparing high-quality tables of trigonometric functions, logarithms, and the like; and, second, providing work for unemployed New Yorkers. The 450 human computers hired for the project were chosen more on the basis of need than skill, and the work was done on a kind of numerical assembly line. According to David Alan Grier:

Each group was taught to perform a single arithmetic operation. One group knew how to add positive numbers, a second to subtract, and the third to multiply single digits. The last and most sophisticated group did long division.

I have to admit there’s a certain nightmare aspect to this scene. Working in a numbers factory sounds no more appealing than stamping sheet metal all day, although there was less danger of getting a finger crushed in the machinery.

A few years later, the Tables Project was swept up in war work; then, afterward, many of the key personnel moved to the National Bureau of Standards (now NIST, the National Institute of Standards and Technology). There they conceived the Handbook. Apparently the initial plan was a greatest-hits album of tables, but by the early 1950s the future of table-making was looking pretty dim. And so the project changed course and put more emphasis on the mathematical functions that lay behind the tables—familiar functions such logarithms, more specialized ones such as Bessel functions and some more recondite topics such as Mathieu functions and orthogonal polynomials. There were still tables listing numeric values of functions, but the Handbook also presented the mathematics you would need to evaluate (or approximate) the function for yourself.

The editors in charge of the Handbook were Milton Abramowitz and Irene Stegun, both veterans of the New York table office. They recruited about 30 young mathematicians to write chapters. In 1958 Abramowitz died suddenly; Stegun saw the project through to publication in 1964.

The Handbook seems an unlikely best-seller, but the U.S. government has distributed more than 150,000 copies, and editions from other publishers are estimated to bring the total copies in print to something near a million. (As a product of government work, the Handbook is not covered by copyright; there are scanned versions on the web.)

Announced last week is a new Handbook, officially retitled the NIST Handbook of Mathematical Functions. The ink-and-paper version, which I have not yet seen, is published by Cambridge University Press. Perhaps even more interesting is the web edition, called the NIST Digital Library of Mathematical Functions (DLMF), which I have just begun to explore. It is recognizably the same book as Abramowitz and Stegun, with the same terse style of presentation. But much has changed. The hundreds of pages of tables are finally gone; this is not the place to look up the sine of 23 degrees. But there are handsome color graphics now, and a new emphasis on methods of computation, including pointers to recommended software. And the selection of topics has expanded somewhat. For example, there are new chapters on the Painlevé equations and on functions whose argument is a matrix. Elsewhere, the Lambert W function (a personal favorite of mine) is a newcomer to the chapter on elementary functions.

Apart from the content, the DLMF is interesting as an experiment in presenting mathematics on the web. It’s the most ambitious project I’ve seen based on MathML, and it seems to work well, at least when viewed in recent versions of Firefox. (In other browsers I’ve tried, MathML gets garbled, but the equations can be displayed as images and are still quite readable in that format—even with an ancient version of Internet Explorer.) Here’s part of a page as seen in Firefox:

Mousing over the “i” icon at the right margin provides access to encodings of the equations in MathML or TeX and as PNG images, as well as definitions, cross-references and such. Very slick.

The editor in chief of the new Handbook is Frank W. J. Olver of the University of Maryland College Park and NIST, whom I have mentioned before both here at bit-player and in American Scientist. As a young mathematician, half a century ago, Olver wrote one of the Handbook chapters on Bessel functions. (As an even younger mathematician, in the 1940s, he worked with Alan Turing at the National Physical Laboratory in Britain.) There are three more principal editors: Daniel W. Lozier, Ronald F. Boisvert and Charles W. Clark, all of NIST, as well as a long roster of associate editors and domain experts. It’s too soon to say whether some combination of these names will eventually replace the moniker “Abramowitz and Stegun.”

Notes: The quotation above from David Alan Grier appears in “The Math Tables Project of the Work Projects Administration: The Reluctant Start of the Computing Era,” IEEE Annals of the History of Computing, Vol. 20, No. 3, 1998. Grier has also written a profile of Stegun in “Irene Stegun, the Handbook of Mathematical Functions, and the Lingering Influence of the New Deal,” American Mathematical Monthly, August-September 2006. Boisvert and Lozier have written a brief account of the history of the Handbook. (Oddly, the images in this PDF file are negatives.)