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.)
In the past few weeks I’ve had little time for bit-playing; I’ve been playing with atoms instead. I’ve been sorting and packing and toting atoms, then hauling them, rearranging them, offloading them, storing them. Lots and lots of atoms: maybe 1029. Bits are so much easier to handle. My bitly possessions—some hundreds of gigabytes—fit comfortably in a shirt pocket. My atomic chattels are a bulkier burden.
All this atom-pushing was done in the course of moving my household from Durham, North Carolina, to Cambridge, Massachusetts. I’ve moved before, but this time the experience was unusually physical. In vacating my Durham home, I carried all my belongings out of the house and onto a truck—and I did it without helpers and without the use of carts or dollies or other wheeled implements. In other words, everything I own (except a car) I have now lifted up, cradled in my arms, carried 50 feet or more, and set down again. It took a day and a half.
What a goofy thing to do, eh? I even turned away offers of help. I guess I’m just a do-it-yourself kind of guy. In a strange way the labor was worth it: The process gave me a vivid and visceral sense of how stuff accumulates over a lifetime—how my possessions possess me. Late in the afternoon of the second day, as I loaded up the last few items and shut the door of the truck, there was a bright glow of satisfaction and accomplishment.
Yet I never want to do it again. When I arrived in Cambridge, I did not refuse the generous help of a younger, stronger friend. (Thanks, Mici!)
The total weight of my load was roughly two and a half metric tons. At least two tons of that mass consisted of “information goods”—books, periodicals, manuscripts and proofs, file drawers full of paper documents, photographs, musical recordings in various formats, art works. And this was the residue remaining after a two-year effort to lighten my load, mainly by transforming atoms into bits. In particular, I had scanned 22 drawers full of files, converting paper into PDFs and then recycling all the cellulose.
Before I lug my belongings out of this dwelling, I vow to jettison another ton or more. If only I could figure out how to digitize my clothes or my pots and pans.
As for my new home, everyone knows that Cambridge is the intellectual capital of North America. But I didn’t quite realize how high the standard had become. The sign in the photo below is on the garden gate next door.
The literate local canines seem to comply with this order, since the gate is always closed.
Maybe Wolfram? Or Omohundro and Skiena?
Back in 1988, a contest sponsored by a major computer company asked for visions of a future personal computer. The winning team came from the University of Illinois at Urbana-Champaign. The faculty advisers were Stephen Wolfram and Stephen Omohundro (at far left in the photo above); the student members (from left to right) were Arch Robison, Steven Skiena, Bartlett Mel, Luke Young and Kurt Thearling. Their proposal of a device called the TABLET had eerie anticipations of the contraption that goes on sale this weekend.
Some quotes from the description of the TABLET:
This rectangular slab will weigh but a few pounds, and have no buttons or knobs to play with. The front surface will be a touch-sensitive display screen and will blink to life upon touching two corners.
The front surface of our computer is a high-resolution touchscreen that yields slightly to the touch. With this single input device, we can get a tremendous range of flexibility and options. We can use it to create an entirely soft interface.
A high-resolution color display can do more than just imitate a notebook page. It will be fast enough to support video…. It takes only a little more courage to predict a Global Positioning System (GPS) receiver on our machine, either as a clip-on or a built-in component.
If we can take our computer anywhere, we need to be able to use it anywhere. This brings us to communications capabilities. Through our national telephone network, we can access any person or machine within seconds.
It seems the UIUC prophets even saw Facebook coming over the horizon:
In addition to communicating with peripherals… we can also talk to other computers. Each machine can continually broadcast personal facts that users may wish the world to know: perhaps their name, image, interests, and marital status for openers.
And YouTube:
One interesting problem is who will appreciate all this new art? Some form of “shareware video” might arise.
Of course they didn’t get everything right. There’s the matter of the stylus and handwriting recognition (suggesting a foreknowledge of the Newton rather than the iPad). And it was all supposed to happen in the year 2000, so we’re a decade behind schedule.
Which computer company sponsored this contest? It was Apple, of course. The judges were Ray Bradbury, Alan Kay, Diane Ravitch, Alvin Toffler and Stephen Wozniak. (Steve Jobs was in exile at the time.) All of the prizes were paid in Macintosh merchandise.
The story of the 1988 predecessor of the iPad is told in Communications of the ACM, Vol. 31, No. 6, pp. 639–646. Included there is the first teardown photograph of an iPad (right). Note the wafer-scale integration. For those who can’t get past the ACM pay-wall, a slightly different telling of the story appears on Kurt Thearling’s web site. There’s also a brief account from the UIUC computer science department.
[Just to be clear: I am aware that there's a considerable difference between imagining an innovative device and actually building it.]
A few weeks ago I committed an act of deception. I needed a graph showing a few sets of data points, with curves fitted to them. This was strictly for show; neither the points nor the curves would mean anything; it just had to look good. So, out of laziness, I did it backwards: I drew a few arbitrary curves, chose some points on the curves, and then perturbed those points by small random displacements. The result is Figure 2 in Home Baked Graphics.
Apparently I have gotten away with this fakery, since no one has complained. But it nags at my conscience. The curves shown are not fitted to the given data points, but the other way around. And barring an extraordinary coincidence, we can’t expect the curves to give the best possible trend through the points.
I began to wonder: What if you iterate this process? In other words, you start out by generating a curve, say a simple quadratic:
You select a few points on the curve, in this case the five points with x coordinates equal to {1, 2, 3, 4, 5}. You perturb the y coordinates of these points by choosing random variates from a normal distribution with unit standard deviation:
Now you do a least-squares fit to the five selected points, generating a new quadratic:
At this stage you can start over, selecting five points on the new curve and randomly displacing them:
And a least-squares fit to those five purple points yields yet another quadratic curve:
So what happens if we continue in this way, repeatedly jiggling a few points on a curve and then fitting a new curve to the jiggled points? There’s a seeming hint of convergence in the three curves we’ve seen so far. They look like they might be approaching some fixed trajectory. Could that possibly be true?
I’ll post an update in a few days to say what more I’ve been able to learn about this question. If you just can’t wait, click here for a sneak peek.
The promised update (2010-04-02): You can’t fool anybody in this crowd, not even circa April 1. Of course there is no convergence to a limiting curve.
The butterfly above shows 100 quadratic curves, selected from 100,000 iterations of the least-squares fitting process, with that process applied at points whose x values are in the set {–5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5}. Clearly enough, the coefficients of the quadratic curves are wandering widely; in particular note that the x2 term can be either positive or negative, yielding curves that are concave upward or downward.
On the other hand, these are not just any old quadratic curves. They all have their apex (the point where f′(x) = 0) fairly close to the origin. Here’s a closer view:
(When Ros glanced at this graph on the screen, her comment was: “Bad hair day.”) And here’s a tracing of the wandering of the apex (taken from a different, longer, run of the program):
The path has the look of a classic random walk, but note that it’s confined to a narrow range of x values. What attractive force holds the apex in this region? It’s the decision to fit the curves to points in the interval –5 ≤ x ≤ 5. Here’s what happens if we instead fit to points in the range 100 ≤ x ≤ 110:
And note that without the symmetry-breaking x1 term, the curve would always be a parabola with its apex on the y axis; only the curve’s shape (or scale) and the height of the y intercept could vary.
This whole process of repeatedly fitting curves to data and then deriving new data from the fitted curves is weird and useless enough that it seems unlikely to appear anywhere in the universe outside my own idle mind. And yet…. Think of the Dow-Jones index, which is calculated as a weighted average of the prices of 30 selected stocks. They are not always the same 30 stocks. Indeed, recent years have seen quite a lot of turnover in the components of the Dow: AIG was replaced by Kraft Foods; General Motors was dropped in favor of Cisco Systems; Honeywell lost out to Chevron. Would it be too utterly cynical of me to suggest that what’s going on here resembles a process of fitting a curve to randomly chosen points, then choosing more points that lie near the curve?
Tom Siegfried, the editor of Science News, has published a blistering indictment of statistical methods in science and medicine. I am moved to speak for the defense.
Siegfried discusses a number of specific cases, mainly drawn from the biomedical literature, where faulty statistical reasoning has led to unreliable or erroneous conclusions. I don’t want to quibble over the particulars of those cases; I’ll concede that science provides plentiful examples of statistical analyses gone wrong. Indeed, I could add to Siegfried’s list. But I see these events mainly as failures to use the tools of statistics properly; Siegfried suggests that the problem goes deeper. If I understand him correctly, he believes that the tools themselves are defective and that science would be better off without statistics. Here is how he begins his essay:
For better or for worse, science has long been married to mathematics. Generally it has been for the better. Especially since the days of Galileo and Newton, math has nurtured science. Rigorous mathematical methods have secured science’s fidelity to fact and conferred a timeless reliability to its findings.
During the past century, though, a mutant form of math has deflected science’s heart from the modes of calculation that had long served so faithfully. Science was seduced by statistics, the math rooted in the same principles that guarantee profits for Las Vegas casinos. Supposedly, the proper use of statistics makes relying on scientific results a safe bet. But in practice, widespread misuse of statistical methods makes science more like a crapshoot.
It’s science’s dirtiest secret: The “scientific method” of testing hypotheses by statistical analysis stands on a flimsy foundation.
This argument strikes me as so totally wrong-headed that I have a hard time believing Siegfried is serious about it.
To begin with, the snide remarks about Las Vegas and crapshoots are off-target. The branch of mathematics with roots in the study of gambling is not statistics but the theory of probability. The two fields are closely allied, but they’re not identical. Early statistical ideas came out of astronomy and geodesy, with later developments in the social sciences, genetics and agriculture. If you really must find some vaguely disreputable locale for statistics, the apt choice is not the casino but the brewery (a notable Student of statistics worked for Guinness).
More disturbing than this minor historical flub is Siegfried’s vision of a lost golden age of “rigorous mathematical methods,” debased by the seductive wiles of statistics. I don’t believe there was any such fall from grace. Siegfried doesn’t tell us much about the nature of his prestatistical mathematical paradise, but since he mentions Galileo and Newton, I suppose he may be thinking of classical mechanics as an exemplar of lost innocence. It’s true that the study of planetary orbits and ballistic trajectories does offer up some pithy mathematical laws that purport to be exact descriptions of nature:
We don’t usually attach error bars to these expressions, or hedge our bets by saying “Force is equal to mass times acceleration within one standard deviation.” But where do such “exact” laws come from? When Galileo performed his experiments with balls rolling down an inclined plane, the measured data did not exactly conform to a parabolic trajectory. Likewise with Newton’s inverse-square law: No real-world observations precisely follow the form 1/r2–not unless the experiment has been fudged. Making the leap from experimental data to mathematical law requires a process of statistical inference, where we extract some plausible model from the data and attribute any departures from the model to measurement error.
In the time of Galileo and Newton, tools for statistical inference were crude; by the time of Gauss, they were much sharper. In 1801 the newly discovered planetoid Ceres was observed for 41 days before it was lost in the glare of the sun. Astronomers hustled to predict where and when it would reappear in the sky. Among all the attempts, the clear winner was the prediction of Gauss, whose advantage in this competition was not so much superior astronomy as superior statistics. His secret was the method of least squares, which he later backed up with a comprehensive theory of measurement error, introducing the idea of the normal distribution.
Later still, statistics had a role in showing that the “exact” mathematics of Newtonian celestial mechanics is not exact after all. It took careful observations–and careful statistical analysis of those observations–to quantify a tiny anomalous precession in the perihelion of Mercury, explained by general relativity but not by classical gravitation.
Statistics is no “mutant form of math”; it’s the way that science answers the fundamental and inescapable question, “How do we know what is true?” I really can’t imagine how science could survive without statistics. What would replace it? Divination?
Siegfried complains that statistical tools offer no certainty–that when a result is reported as statistically significant at the 1-sigma 2-sigma level (or in other words with a P value of 0.05), there’s still a 1-in-20 chance that it’s a meaningless fluke. Quite so; that’s essentially the definition of a 2-sigma P value. But the uncertainty is not some methodological malfunction. It reflects the true limits of our knowledge. The strength of statistical reasoning is that it makes those limits explicit.
Again, I’ll readily agree that standards of statistical practice should be strengthened, and that weak or faulty conclusions are too common in some areas of the published literature. But the claim that “any single scientific study alone is quite likely to be incorrect, thanks largely to the fact that the standard statistical system for drawing conclusions is, in essence, illogical” is, in essence, illogical. Yes, we have lies, damn lies and statistics. But we also have lies and damn lies about statistics.
All my closest friends know about my strange obsession with the mathematics of mattress flipping. A few thousand other people also know my secret, since I have written about it in an American Scientist column (HTML, PDF), which later became a chapter in a book.
To recapitulate: Fussy housekeepers rotate their mattress twice a year to ensure even wear. But a mattress has three axes of twofold symmetry (roll, pitch and yaw). Rotating around the same axis over and over will not cycle through all four possible states of the mattress, so you need to vary the procedure. Perhaps you do a roll one time and a yaw the next. But in the spring you may have forgotten which way you turned last fall. Thus the quest for a “golden rule” of mattress flipping:
A golden rule of mattress flipping would be some set of geometric maneuvers that you could perform in the same way every time in order to cycle through all the configurations of the mattress. Following this algorithm might entail extra physical labor on each occasion–perhaps making multiple flips or turns–but at least it would eliminate the mental effort of remembering.
The rules of this peculiar game forbid putting any marks on the mattress (which would break the symmetry). If we abide by this constraint, the multiplication table for the group of flip operations looks like this:
R, P and Y indicate half-turns around the roll, pitch and yaw axes; I is the identity or do-nothing operation. This table is bad news for golden rules. We already know that no single operation will cycle through all four states of the system, and the table shows that every combination of two operations is equivalent to some single operation. Hence there is no golden rule.
There the matter stood until a few days ago, when I received a letter from Tim Knoll:
I just completed reading your collection of columns entitled “Group Theory in the Bedroom” and I wanted to offer up an alternative solution to the mattress flipping problem. I believe if you add one more operation to the mattresses you can achieve your “golden rule.” What you need to add is a second bed to allow a shift operation in addition to the rotations. If you have the second bed oriented in the opposite manner as the first bed (with the first having the headboard facing north, the second facing south) you can simply have an operation of a non-rotating shift from the first (north-facing) bed to the second (south-facing) and then do a shift in addition to a rotate about the pitch axis from the south-facing bed to the north-facing bed. This mattress juggling should also achieve the desired results using the roll axis in the second step. I unfortunately can’t implement this method in my own apartment since it is equipped with one queen-sized bed and one full-sized bed, but my tests using an index card seemed accurate.
Ingenious, no? But is it truly a golden rule? I’m going to leave that question for readers to decide.
Knoll also points out that even if the new “shift” operation doesn’t yield a golden rule, it does succeed in getting two mattresses flipped with the same mental effort that would otherwise be needed for one mattress. This raises a further question: Why stop at two beds? What about mattress flipping in a barracks, where many beds are lined up in a row? And then there’s the job of flipping mattresses in the Hilbert Hotel, which has infinitely many beds. Does the mental effort per mattress go to zero in this limit?
A couple of commenters have asked what software package I use to create the graphs that appear in bit-player posts–illustrations like the one below, which is a slightly improved version of something I posted last week. Let’s call it Figure 1.
Prompted by these inquiries, I immodestly ask myself: Why do my graphs look so darn good? I immodestly answer: It’s not because of any packaged software! I don’t need a cake mix, or even a recipe. These are home-baked graphs, made from scratch out of locally grown organic pixels.
I have strong opinions about the aesthetics of scientific illustrations, and I could certainly spout off about the design elements of Figure 1, such as that putty-colored background, just dark enough to allow drop-out white grid lines, yet neutral enough to avoid competing with the data curves, which also have a distinctive color scheme on which I could discourse at length. Yes, I can talk the Tufte talk. But I think the commenters were really asking how I create the graphs rather than why they’re so elegant, and so I’m going to focus here on the practical programming problem.
Most of my experience in drawing pictures with a computer comes from the world of print publishing, where the final product is ink on paper rather than pixels on a screen. Compared with the online environment, print has some advantages, notably higher resolution (up to 1,000 dots per centimeter) and precise control over typography and color. But print also has obvious limitations: On a magazine page, there are no mouseovers or clickable buttons, and you can’t make a square knot twirl in 3D.
Thirty years ago, the big challenge for computer-generated illustrations was not how to draw the picture but how to get it out of the computer and onto the printing press. You couldn’t just export a PDF and place it in a Quark or InDesign document; none of those things existed. The only practical option was to print out the artwork, photograph it, and “strip” the negative into the page-size film that would be used to make the press plate. Because of this emphasis on printouts, most of the effort went into programming the printer rather than the computer.
The figure below is the first published computer-generated illustration I had a hand in creating. It appeared in Scientific American in 1983.
The array of 282 tiny bar graphs was produced with an Epson MX-80 dot-matrix printer, using escape codes to fire combinations of the eight pins in the printhead. Of course the MX-80 was a black-and-white device. The two-color illustration was created from two separate printouts. Also, the Epson letterforms were replaced with typeset characters.
The world of computer-generated illustrations changed dramatically with the arrival of PostScript, the “page description language” created by John Warnock and his colleagues at Adobe Systems (based in part on earlier work at Evans and Sutherland and Xerox PARC). PostScript was designed as a complete programming language rather than just a file format or a set of drawing commands. And something else set it apart as well: attention to details of graphic design. With most earlier software (such as programs based on the Apple Quickdraw library), trying to create publishable figures was an exercise in frustration. For example, the apparent weight of a line would vary depending on its orientation: lighter when vertical or horizontal, heavier when diagonal. PostScript allows very precise control over such niceties of presentation. To take another example, where lines meet the edge of a graph, you don’t want to have to choose between falling short and overshooting; PostScript provides the tools needed to make it look right.
(The version in the rightmost panel is created by allowing the colored lines to extend outside the background box, and then applying a clipping mask that cuts off all objects at the boundary of the box.)
Obsessing over minute details like these may seem comically fussy, but I believe that neatness counts in these matters. To some extent, illustration is an art of illusion. Graphs and diagrams work best when you can look through them rather than at them. The viewer should be seeing the underlying information or abstraction–the array of correlation coefficients, the function y = f(x), or whatever–rather than noticing the mechanics of how the drawing was constructed. A ragged edge is the kind of distraction that destroys the illusion.
Although PostScript was a giant step forward from the MX-80 command set, in the early years it was still just another printer language, not a computer language. The only way I could execute a PostScript program was to send it to a laser printer and wait to see what came out. Sometimes it was a long wait. I had no way of running a PostScript program on the computer itself. (Ghostscript came later.)
My first PostScript illustrations were created as hand-written PostScript programs; the same language was used both for doing the computations and for presenting the results. The faces at right were created in this way. (They were inspired by the work of Herman Chernoff and drawn to illustrate an American Scientist article by Robert Levine in 1990.) The dual role of the language caused me a moment of disorientation just now when I went looking for my records of this project. I found an EPS (encapsulated PostScript) file, which I knew was the finished illustration, but where was the source code? And then I remembered: It’s the same file! Open it up in Ghostscript or Adobe Illustrator and you see those silly faces smiling or scowling at you; open the same file in a text editor, and you see procedures for drawing elements of the faces:
/draweyes
{ newpath
dx dy eyewidth eyeheight 0 360 ellipse stroke
ex ey eyewidth eyeheight 0 360 ellipse stroke
} bind def
/drawpupils
{ fx fy pupilsize pupilsize 0 360 ellipse fill
gx gy pupilsize pupilsize 0 360 ellipse fill
} bind def
Bill Casselman, the graphics editor of the Notices of the American Mathematical Society, still favors this direct-to-PostScript methodology. He has written an excellent guidebook, taking you from the basics of PostScript through an elaborate library for rendering three-dimensional objects.
But here I part company from Casselman; I’d rather not do all my computing in PostScript. It’s not that I have anything against the language itself, but the development environment is not to my taste. I therefore adopted the modus operandi of writing a program in my language of choice (usually some flavor of Lisp) and having that program write a PostScript program as its output. After doing this on an ad hoc basis a few times, it became clear that I should abstract out all the graphics-generating routines into a separate module. The result was a program I named lips (for Lisp-to-PostScript).
Most of what lips does is trivial syntactic translation, converting the parenthesized prefix notation of Lisp to the bracketless postfix of PostScript. Thus when I write (lineto x y) in Lisp, it comes out x y lineto in PostScript. The lips routines also take care of chores such as opening and closing files and writing the header and trailer lines required of a well-formed PostScript program.
But the lips interface is low-level, confined to drawing individual dots, line segments, rectangles and the like. Assembling a complete graph out of these primitives is tedious. For example, the grid of white lines in Figure 1 would have to be drawn one line at a time, with each line specified by a sequence of commands such as
(newpath)
(moveto u v)
(lineto x y)
(stroke)
Before you can issue those commands, you have to calculate u, v, x and y. Clearly, a higher-level front end is needed; like everyone else, I call mine plot.
At the core of any plotting program is a simple operation: mapping points from an abstract user space to coordinates in a rectangular pane, the page space. In Figure 1, the y axis runs from 0 to 5000; values in this range have to be scaled to the dimensions of the graph, which is about 300 PostScript points, or 11 centimeters. Mathematically, the transformation is straightforward. Indeed, if I wished I could leave all the arithmetic to the PostScript interpreter, simply passing in the appropriate matrix elements for scaling and translation. This is an attractive option; it would allow plot to work entirely in user space. But a few niggling details get in the way. Consider the tick marks along the y axis in Figure 1. Their vertical positions are conveniently expressed in user coordinates: one tick every 500 units. But what about the length of the ticks–their horizontal extent? This dimension is purely concerned with the appearance of the graph and has nothing to do with the content; it ought to be expressed in unscaled units of points or pixels.
Here’s a possible solution: Let everything inside the rectangular frame of the graph–the area with the putty-colored background in Figure 1–go through the scaling engine, but define everything outside the frame, including the tick marks and the axis labels, directly in page coordinates. If you think this is the final answer, take a look at Figure 2:
In this nonsensical graph (constructed just for this occasion), data points are indicated by stars, crosses and diamonds. The positions of those glyphs ought to be defined in user space, but the drawing commands that create the shapes are properly defined in page coordinates. If we tried to draw the glyphs in user space, their size and shape would vary with position in the graph.
What’s the best way to deal with this messy situation? Is there some tidy solution that will reconcile the two coordinate systems and allow all dimensions to be treated uniformly? I don’t believe so; it’s just in the nature of graphs to mix up elements from these two disparate realms. We look through a window into a world of data or mathematical abstractions, but we also draw our own little doodles on the window itself.
Of course there are solutions; they’re just not as pretty as I would like. My own strategy for coping is to attach extra information to each geometric point, indicating whether or not the x and y coordinates are to go through the scaling transformation. This is less troublesome than it might seem; from the user’s point of view, it’s almost always invisible.
In writing the lips and plot programs, I walk a path that is already worn smooth by many earlier footsteps. I don’t know who wrote the first computer program for plotting data, but it probably came soon after the first program for producing data. Today we have hundreds of clever, comprehensive, well-designed and well-maintained programs for plotting and graphing. Gnuplot is very capable; Grace is one I’ve never used but I’ve heard good things about it; Mathematica, Sage, R, MATLAB, Octave and the like all have elaborate graphics facilities built in; the Python world, as usual, has an overabundance of options; there are a few libraries for my beloved Lisp; you can even do dataviz online.
All of which raises the question of why I bother to roll my own. I’ll never keep up–or even catch up–with the efforts of major software companies or the huge community of open-source developers. In my own program, if I want something new–treemaps? vector fields? the third dimension?–nobody is going to code it for me. And, conversely, anything useful I might come up with will never benefit anyone but me.
The trouble is, every time I try working with an external graphics package, I run into a terrible impedance mismatch that gives me a headache. Getting what I want out of other people’s code turns out to be more work than writing my own. No doubt this reveals a character flaw: Does not play well with others.
In any case, the time for change is coming. My way of working is woefully out of date and out of fashion. PostScript is a technology that even Adobe seems to regard as outmoded. And making ultraprecise PostScript graphs is quite silly when their destination is the web; before I can put them online, I have to convert them to low-res PNG images. Furthermore, a PostScript-based workflow loses out on all the interactive richness of the web. These are deathly still images. How can I expect to earn any web cred when my work is not even clickable, much less multitouch-enabled?
If I continue in my stubborn, do-it-yourself mode, I could replace the PostScript back end with one that generates SVG. This wouldn’t be a major undertaking. But is SVG the right answer? It’s been around for more than a decade and you still don’t see much of it in the wild. And there are horrid browser incompatibilities. I suspect that Javascript (and JQuery) has a brighter future. And if I can get over my abreaction to libraries, there are plenty of options. Advice anyone?
Update 2010-03-13: Many thanks for all the thoughtful comments. Herewith a few comments on comments:
Ron Renaud’s graphs using Javascript in a canvas element are really very pretty, and they give me renewed hope that web graphics can measure up to a print standard. But is the world quite ready for the canvas? This is a blog, after all. Lots of people get to it with an RSS reader, not a web browser.
Zvika requests a link to a higher-resolution PNG. I don’t know how to do that. I can make a larger PNG, but the resolution–the dots per centimeter–is really determined by the screen you’re looking at. Which is not to say that larger illustrations wouldn’t be a good idea. When I redesign these pages, I want to allow more room for bigger pictures.
Gary Reuben suggests Python Matplotlib and the ggplot2 package for R. The latter is new to me, and very impressive. I want to go read more about it.
Several other readers favor SVG. I’m okay with that. It looks easy to change my current software to generate SVG output instead of (or in addition to) PostScript. The question remaining for me is whether SVG on the web is something that browsers (and, again, RSS readers) can swallow without choking.
John Haugland mentions PDF as the successor to PostScript. I couldn’t possibly survive without PDF these days, but I don’t see it as an ideal medium for illustrations embedded in web pages. Reading PDFs within a browser requires a plugin, which some people refuse to install. (I’m one of those people.) Furthermore, because PDF is a binary format based on a directory of offsets to tables, it’s more trouble to write PDF files than either PostScript of SVG.
Nate mentions Processing, the graphics and animation language created by Casey Reas and Ben Fry. I’ve written about this before at bit-player and elsewhere. I’m a big fan, but Processing is essentially a front end to Java, and I have reservations about embedding Java applets in web pages. John Ressig’s reimplementation of the language in Javascript overcomes that problem, and one of these days I’ll get around to doing something serious with it.
Finally, Marc asks for a look at my Lisp code. I’m always shy about sharing such unfinished things, but here it is.
Update 2010-03-28: When commenter Zvika asked for higher-resolution graphics, my reply was unhelpful; let me now try to say something more useful.
Even though I can’t do anything to improve screen resolution, I can, as Zvika notes, provide a larger version of each image. The Wikipedia way of doing this, which Zvika mentions, is to link to a separate HTML page, which replaces everything on the page you’re currently reading. As a test, I’ve done this with Figure 1 above; click on that figure and you’ll be whisked away to a supersized version of the graph. To get back here, you’ll have to use your browser’s “back” button.
Another approach, adopted by, for example, the New York Times, is a pop-up window. I’ve done this with Figure 2 above; click on it and a new window with a bigger version will open in front of this page.
Personally, I dislike both of these strategies. I want to see the words and the pictures at the same time in the same context. I suppose I could implement (or swipe) some glitzy Ajaxian solution that expands the artwork box within the window. But I still feel the right solution is to redesign the pages so that there’s room for larger illustrations in the first place. (Admittedly I’ve been meaning to do that for more than a year.)
There’s also a question about how best to make use of a more spacious picture box. In the supersized Figure 1, the transformation is much like an optical enlargement, projecting the same information at larger scale. The overall dimensions are doubled, and so is the width of each line, the size of the type, and so on. This is probably the answer for those troubled by visual deficiencies (including my own presbymyopic eyes).
In Figure 2 I have enlarged the illustration by 150 percent but kept all the individual graphic elements (line weights, labels, the glyphs that mark data points) the same size. This kind of rescaling allows information to be read from the graph with greater precision.
Perhaps a middle way is sensible here. Indeed, maybe type should scale as the square root of graph size?