Category Archives: Research

Higher order asymptotics from generating functions

Alex Raichev and I have just submitted a journal article on this topic (read it on arXiv). The associated Maple 11 worksheets can be found on Alex’s site. We improve over previous work by Robin Pemantle and me, and derive explicit formulae for the entire asymptotic series obtained by approximating the coefficients of a generating function near a smooth point of the singular variety. The numerical results obtained show how well these approximations work in practice.

I heard a talk by Wojtek Szpankowski a few years ago where he quoted Ziv as saying that second order asymptotics were needed in information theory. Persi Diaconis told me years ago that the work with Robin is all very nice, but what about looking at approximations that work for moderately small values, not just asymptotic approximations. I hope that this paper will satisfy both needs.

Genius may not even need that much perspiration!

Malcolm Gladwell’s article  Annals of Innovation: In the Air: Reporting & Essays: The New Yorker  makes fascinating reading. Many inventions were made almost simultaneously in history, leading some to believe that they were inevitable and that geniuses differ from other people only in degree, not in kind. Nathan Myhrvold formed a company to systematize and make more efficient the process of inventions, with spectacular success so far. Highly recommended. Thanks to David Craigie for the tip (and I wonder when he will get around to having his own blog).

Journals we might need

Offhand I can think of 3 main purposes for scientific journals: rapid dissemination, archiving, and evaluation (correctness and importance). The first ceased long ago to be feasible, and preprint servers and newer technology such as blogs have largely taken over. The second is still important, and a decent job is being done by some commercial (and other) publishers.

The third is perhaps the most important. The main questions, according to G. H. Hardy, that a referee should ask are: is it true? is it new? is it interesting? In my experience not many papers pass all three of these tests.

The first of Hardy’s questions can be hard to answer: from my own experience as author and referee I know that errors can easily slip through. In mathematics, there may be some hope of eventually automating proof-checking, or perhaps using the idea of zero-knowledge proofs. In other fields, I am not sure what more can be done. It would be very interesting to know how many experimental results are never checked by anyone other than the author(s). It has been asserted that most published results are wrong.

The second test is more easily answered now with the advent of full-text searching. Provided the archives are readily available, modern search technology makes it less defensible than ever not to be aware of related literature when publishing. Referees can of course use this technology too.

The third test is a matter of taste, and rejecting a paper on the grounds that it is boring or trivial requires more skill and judgment on the part of the referee. Many rejection letters say, in effect: this paper is OK, but not good enough for this journal, or not of interest to “our readership” (whoever they are).

I suggest that papers that pass two of Hardy’s three tests should usually be published, and new journals be instituted if required. I only discuss mathematics here.
Results that are false, but new and interesting should appear in the Journal of Speculative Mathematics. To some extent, the arXiv can fulfil this function, but papers there often fail more than one of the three tests.

Results that are true, already known, but interesting (with a new and clearer proof) should appear in textbooks or the Journal of Expository Mathematics. There are already several expository journals, of course, such as the American Mathematical Monthly.

Results that are true, new, but boring should appear in the Journal of Necessary Mathematics. The Journal of Necessary Mathematics would be better than the recently introduced journal Rejecta Mathematica (which seems to be having trouble attracting submissions). JNM would contain lemmas that are likely to, or have already proven to be, useful building blocks in more interesting results. Often they are easy to believe but hard to prove nicely. Currently these are often relegated to appendices of papers, and never read. It would be far better for them to be archived systematically. At the very least, they would provide a nice resource for people looking to practice their expository skills – try to find a better proof, or an application.

An interesting(?) error

Michael Trick has a pointer to a piece at TierneyLab about an apparent error committed throughout the psychological literature. An example: monkeys are given a choice between red and blue M&Ms. The ones who chose red over blue are then given a choice between blue and green, and about 2/3 of them chose green.

Under the assumption that the monkeys like each colour equally, the conclusion was drawn that their first choice influences their second in an irrational manner (“blue was bad, so still is”). However, under the assumption that each monkey has a preference order for the colours, the observed data would be exactly as expected.

This is not the time to get started on a discussion of my prejudices about mathematics abuse and woolly thinking in the “soft” sciences and humanities. The link above should give lots of interesting reading.

Kidney exchanges

A relative of my wife needs a kidney transplant in the USA and the waiting list is long. Obviously many other people are in the same situation, and in order to shorten waiting times, the idea of kidney exchanges has become popular. Today BBC reports the first 6-way exchange. The mathematical and operational issues are interesting, as are the ethical ones.

Where now for A of A?

For the first time in several years I will not be attending the annual AofA workshop/conference. This year it is being held in Brazil at an inconvenient time for me. The scientific programme looks quite interesting.

I have never seen a full history of the field of analysis of algorithms (the SODA talk by Philippe Flajolet has some interesting comments). A rough summary of what I believe to be the case: before Knuth came along, people analysed algorithms by implementing them and guessing their asymptotic runtime via extrapolation. Knuth changed this by showing that serious classical mathematics could be brought to bear on analysis of algorithms, and that this ultimately led to models that would predict to high accuracy the real running time on large problems. Notwithstanding the fact that many researchers in the area of algorithms (the “big-O crowd”) are content with less precise estimates, I am sure they were happy that such analysis was possible.

Recently I have seen more and more examples of situations where this kind of analysis is called into question. The main problems seem to be caching and branch prediction, which ensure that the time to execute an “elementary” operation can vary wildly. A relatively small number of papers have appeared that discuss these issues (after all, it should not be beyond the wit of man to say something analytical in these situations) but the results are necessarily less precise than in the old days (for a start, even finding out the branch prediction algorithm used by chip makers is not trivial).  Let’s see where the next few years lead.

Bernard Chazelle to visit NZ

As part of the programme in Algorithmics sponsored by the NZIMA, Professor Bernard Chazelle of Princeton University (he also has his own Wikipedia article) will visit New Zealand to give some public talks in March 2009. I have found some of his writings very stimulating, if a little bewildering in their language. In particular his essay The Algorithm: Idiom of Modern Science is very persuasive. With luck, public appreciation of algorithms will be considerably higher after his visit than it is now!

Algorithms research in NZ

Last week I was at the NZIMA Algorithms meeting in Napier, which I helped to organize. There were 5 invited speakers, and all their talks (they gave 2 each) were worthwhile listening. I got the role of amateur cameraman and so most of the talks have full video footage, which I hope to make available on the web soon.

At a strategy session it was decided that we will try to create a more formal community for those researching in algorithms (interpreted broadly, from very pure to very applied). The mechanism will probably be to set up something like a Google group. Please contact me if you are interested in joining.