Author Archives: wilson.mark.c

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).

Popularizing (T)CS

The downturn in CS enrolments in universities this millennium has elicited several responses. In the theoretical CS community, there seems to be a strong feeling that many of the students we had were here for the wrong reasons, namely the internet bubble and associated overoptimism about job prospects (ironically, job prospects now are great for our graduates, but we are still (at Auckland) seeing a decline in enrolment).

The idea is that CS has a public relations problem compared to areas like biology and physics – it has been presented far too vocationally, and the big ideas have not been communicated in the way that they have in those fields. It frustrates me, for example, that the general education CS course in my department deals with very few big ideas, and a lot of “how to write XHTML” stuff. Of course, even many “computer scientists” think of CS as part of engineering, not science. Unlike E.W. Dijkstra, they apparently think that computer science is about computers, whereas the rest of us think that it is about information and computation, with computers being both tools to study these fundamental concepts and technological fruits of that study. Most of my immediate colleagues work in pretty applied areas as far as I can work out, with not much to excite a really good student, no matter how worthy the application.

Michael Mitzenmacher has a project to write a popular book aimed at inspiring high school students about theoretical CS. The CS Unplugged materials already address a younger audience. The latter was developed substantially in New Zealand, but seems relatively unknown here. In this country theoretical CS is relatively weak compared to both applied CS and mathematics, and public understanding of the issues above is probably even less than in the USA.

I would love to contribute more to spreading better information locally about the intellectual side of CS. Anyone in NZ reading this who wants to help should contact me, or better still, tell me about their great ideas that I can help with.

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.