Open problems concerning card games

I’m glad to say that editorial work on the Princeton Companion is within a whisker of being completed (about three articles remain to be edited), so although I don’t quite feel that I have the leisure to give proper attention to this blog, which will be obvious from some of the messages that I haven’t got round to deleting, I can at least write a quick post. It starts with a conversation I had a couple of years ago. I was waiting for a plane to take me from Mykonos to Athens. The plane was severely delayed, but the situation could have been a lot worse as I had Persi Diaconis for company. He told me the not very surprising fact that it was not known what the probability of a win is in the game known as Patience in the UK and Solitaire in the US. (I’m talking about the one where you start by putting down a row of seven cards with just the first one face up, then on top of all but this first one a row of six cards with just the first one face up, and so on.) To be clear about the probability he is asking for, he simplifies the game by letting you see what all the cards are, so that you can play optimally and don’t have to worry about probabilities.

Probability paradox II

I had an email from Noga Alon a couple of days ago, who told me about a much better version of the paradox I discussed in an earlier post. Some of the comments relating to that post also allude to this better version. The reason it is better is that one can no longer object to it on the grounds that it assumes the existence of a probability distribution with impossible properties.

Removing the magic from Stirling’s formula

Another topic on the syllabus for the probability course I am giving is Stirling’s formula. This was lectured to me when I was an undergraduate but I had long since forgotten the proof completely. In fact, I’d even forgotten the precise statement, so I had some mugging up to do. It turned out to be hard to find a proof that didn’t look magic: the arguments had a “consider the following formula, do such-and-such, observe that this is less than that, bingo it drops out” sort of flavour. I find magic proofs impossible to remember, so I was forced to think a little. As a result, I came up with an argument that was mostly fully motivated, but there is one part that I still find mysterious. On the other hand, it looks so natural that I’m sure somebody can help me find a good explanation for why it works. When I say “I came up with an argument” what I mean is that I came up with a way of presenting an existing argument that doesn’t involve the pulling of rabbits out of hats, except in the place I’m about to discuss.

A paradox in probability

This is the first of what I hope will be several posts related to the course I am giving this term on probability.

The following is a well-known paradox. You are presented with two envelopes and told that one contains a sum of money and the other contains twice as much. You are invited to choose an envelope but are not told which is which. You choose an envelope, and are then given the chance to change your mind if you want to. Should you?

One argument says that it cannot possibly make any difference to the expected outcome, since either way your expected gain will be the average of the amounts in the two envelopes (so the expected change by switching is zero). But there is another argument that goes as follows. Suppose that the amount of money in the envelope you first choose is . Then the other envelope has a 50% chance of containing and a 50% chance of containing , so your expectation if you switch is —so you should switch.

I tried this out for real in my first lecture, and the student who was given the choice decided to switch. Rather irritatingly, he got more money as a result. Of course, the second argument is incorrect, but the reasons are somewhat subtle. My purpose in putting up a post about it is not so much to invite solutions to the paradox as to see whether it prompts anyone to give me their favourite probabilistic paradoxes. (I’ve just done Simpson’s paradox, so that one wouldn’t be new.)

General news—February 2008

Not entirely surprisingly, my hibernation is going to go on for longer than I had hoped. The reason for this is quite simple: there is a major push to get the Princeton Companion to Mathematics finished within the next couple of months or so, and if I spend time blogging then it won’t happen. There has also been a delay with the Tricks Wiki, but that may be less severe because I am not the main bottleneck for that (though there are a few things I need to do before it can be up and running). This term I am giving a first course on probability. I had planned a few blog entries on that too, and I hope I’ll have time for some in due course.

General news — December 2007

As I predicted in an earlier post, my rate of posting has (temporarily) gone right down. This is partly for the reasons I said—I am very busy with a final push to finish the Princeton Companion to Mathematics, and busy in general—but also for another reason. I was going to keep personal matters rigorously excluded from this blog but since my secret is out (see the comments on Examples First II on November 17th) I may as well also mention that I have a five-week-old son, Octave, who doesn’t leave much time for blogging given that my other commitments won’t go away. So this isn’t a proper post but just a way of saying that my blog hasn’t died: it’s just hibernating. Meanwhile, I can at least briefly mention that a “Tricki”—that is, a Wiki-style website devoted to theorem-proving techniques—will almost certainly exist in the near future. Remarkably, my earlier post on this idea led to an offer of technical help that will be enough to turn it from a fantasy into a reality. And that’s saying something, since my own technical ability in this area is basically zero. I’ve seen a prototype and it looks great. Probably we’ll get a small site up and running and I’ll then ask for comments about how it could be improved before we throw it open. (We still haven’t decided what policy to adopt about who can edit what, but we are actively thinking about it.) And that’s it from me until 2008.

Examples first II

It’s what blogging is all about I suppose, but I have been surprised in several different ways by the comments on my previous post. To begin with, I was so sure of the principle I was advocating that I thought that all I’d have to do was explain it briefly and then anybody who read it would instantly agree with it. That was clearly pretty naive of me, and I certainly didn’t expect that some people would be actively hostile to the idea (though I suspect that their real target was not precisely the same as what I was putting forward). But I was also surprised by the number of interesting further points and qualifications that were made, which I will now try to use to articulate a more nuanced version of the principle.

My favourite pedagogical principle: examples first!

This post is about a very simple idea that can dramatically improve the readability of just about anything, though I shall restrict my discussion to the question of how to write clearly about mathematics. The idea is more or less there in the title: present examples before you discuss general concepts. Before I go any further, I want to make very clear what the point is here. It is not the extremely obvious point that it is good to illustrate what you are saying with examples. Rather, it is to do with where those examples should appear in the exposition. So the emphasis is on the word “first” rather than on the word “examples”.

If this too seems pretty obvious, I invite you to consider how common it is to do the opposite.

A paper on the ArXiV

Today I did something for the first time ever that I should have done many times before: I put a paper on the ArXiV. Since I’ve got a blog I thought I’d use it to give the paper a small plug and, more importantly, to let anybody who might already be familiar with the paper know that I have revised it quite a bit recently, for the better.

The paper itself is called “Hypergraph regularity and the multidimensional Szemerédi theorem.” At the bottom level, the basic idea of the paper is due to Ruzsa, Szemerédi and Rödl. Ruzsa and Szemerédi started the ball rolling with a short and very clever argument that showed that Szemerédi’s famous theorem on arithmetic progressions, in the case of progressions of length 3, could be deduced from Szemerédi’s almost as famous regularity lemma, a remarkable result that allows any graph to be partitioned into a bounded number of pieces, almost all of which “behave randomly.”

When are two proofs essentially the same?

A couple of years ago I spoke at a conference about mathematics that brought together philosophers, psychologists and mathematicians. The proceedings of the conference will appear fairly soon—I will give details when they do. My own article ended up rather too long, because I found myself considering the question of “essential equality” of proofs. Eventually, I cut that section, which was part of a more general discussion of what we mean when we attribute properties to proofs, using informal (but somehow quite precise) words and phrases like “neat”, “genuinely explanatory”, “the correct” (as opposed to merely “a correct”), and so on. It is an interesting challenge to try to be as precise as possible about these words, but I found that even the seemingly more basic question, “When are two proofs the same?” was pretty hard to answer satisfactorily. Since it is also a question on which we all have views (since we all have experience of the phenomenon), it seems ideal for a post. You may have general comments to make, but I’d also be very interested to hear of your favourite examples of different-seeming proofs that turn out, on closer examination, to be based on the same underlying idea (whatever that means).