Monday, August 11, 2008

What is the probability that ...

(I've been on vacation for the last 10 days on a Tauck Bus Tour of Canada with Heli-hiking.)

What is the probability that a bus tour has on it two people that know the proof that S2S is decidable? (Original Proof by Rabin is here. For reviews of several books on the topic see here.)
  1. Not a trick question. The bus tour was not organized by the Association of Symbolic Logic.
  2. The prob seems like it would be low. But this is not the right way to look at it.
  3. This did happen. Suzanne Zeitman was on the tour. I learned about the proof from her (excellent) writeup which, alas, is not online. It is incorporated in the book The Classical Decision Problem by Borger, Gradel, Gurevich.
  4. Should I be saying `WOW! that is so unlikely, yet it happend!'. No. Consider the following fictional conversation:

    BILL: The most amazing thing just happened! I just tossed a coin 40 times and got HHTTTHTHTHTHHTTTTHTHTHTTHTHHHTTHHTHTHHTH.

    LANCE: Why is that remarkable?

    BILL: Because the prob of that particular sequence is so small!
  5. The prob that someone the distance away from me which Suzanne Zeitman is (I have written some math reviews for her and been in some email contact) happens to be on the same bus trip as me may be low, but its not so low as to be astonished if it happens. This is my third bus trip and the first time it happened. Is the probably 1/3? I doubt that, but its not so low as to be notable.
  6. If before going on the trip I had said Gee, I wonder is someone who knows the proof that S2S is decidable will be on the tour? then THAT Would be notable.
  7. What is the prob that the maintainer of the Erdos-Number Website was, Jerry Grossman, was on the trip? This is a trick question-- Jerry Grossman is Suzanne Zeitman's husband.
  8. What is the prob that on the trip there were people who know, through their homeowners association, Steven Simpson an eminent logician who works on Reverse Mathematics, who I know. This did happen. Not a trick question, but again, not that notable.


  1. In response to point #4, the real question is: what is the probability that something would happen on your bus trip that you would find interesting enough to post about on your blog.

  2. What is the probability that the wealthiest, most technologically advanced nation in the world in 2008 will not broadcast one single Olympics event LIVE on TV? That's right, not even one in the west coast. To add insult to injury, they put the word "LIVE" on the screen when in fact it's a 3-hour delay. Do they really think that the average American IQ is that low? I guess so. Sorry for being slightly off-topic.

  3. The "bible code" claim runs along somewhat similar lines.


  4. to anon #2: no, they only think the average IQ of west coast Americans is that low...

  5. ALL of the Olympic broadcasts WERE live, unless you were watching a repeat airing.

    Both the east coast AND west coast feeds were shown at the exact same time. I know this because I have a satellite dish on which I could see the New York broadcast as well as the Los Angeles broadcast at the exact same time, and they were broadcasting the exact same thing.