September 17, 2013

Two drunk statisticians leave a bar ….

The below is posted on behalf of Mark Holmes from the Department of Statistics at The University of Auckland. Colleague James Curran read this piece on Wired Science  and challenged him to respond to the following:

Suppose that two drunk statisticians leave a bar (located in the middle of an infinite forest) together.  They stumble around at random and get lost.  Will they ever find each other again?

Mark, helpfully, rose to the bait (thanks, Mark!)  This is what he says:

Assuming 1) that the drunks will live (and stumble around drunk) forever, and that 2) the forest is two dimensional (i.e. there is infinite space to move in both N-S and E-W directions, and the drunks can’t climb infinitely high trees!)  then the answer is yes, they will meet each other again.

Perhaps the best way to explain this is to consider the difference between their locations.  If after n steps the first statistician is at position X_n and the second at position Y_n, then let’s look at D_n=X_n-Y_n.  The two drunks will meet at any time n when X_n=Y_n, which is the same as D_n=(0,0) (the position at time n has two coordinates since we are in two dimensions).

It turns out that D_n itself is essentially a simple random walk, and that the two drunks not only meet again, but they meet infinitely often, because D_n returns to (0,0) infinitely often.  The posh way of saying this is that “simple symmetric random walk in two dimensions is recurrent”.  It is perhaps not surprising that if instead of stumbling around an infinite forest they stumble along an infinite footpath (one dimensional), they will also meet each other infinitely often (“simple symmetric random walk in one dimension is recurrent”).  Note that if the bar is located instead in an infinitely high, wide and long mall they might never meet again (“simple symmetric random walk in three dimensions is not recurrent”).

If the above was good news for the drunks, there is some bad news.  Although they will meet each other again in finite time, the  “average” time it takes them to meet again is infinite.  This is true both in the forest and on the footpath.

If you are interested in the relevant calculations, ask a graduate student in probability (they should also be easy to find on the internet).  If you are satisfied that you understand that, try to solve the following:

 “A physicist, a probabilist and a statistician walk out of a bar…..”

Suppose that we have three independent random walkers instead of two.  The above discussion says that each PAIR of walkers will meet each other infinitely often (in two dimensions).  Will all three meet each other simultaneously?

 

… so, dear readers, let us have it!  Don’t be shy.

 

avatar

Julie Middleton is an Auckland journalist with a keen interest in the way the media uses/abuses data. She happens to be married to a statistician. See all posts by Julie Middleton »

Comments

  • avatar
    megan pledger

    People take a longer step with their dominant leg which means they walk in circles if they can’t tell where they are going (i.e. can’t see the sun/moon or go off towards a landmark). If they both walk perfect circles than they should meet up again (although when would depend on their walking speeds, stride lengths etc), if one walks an imperfect circle than s/he might spiral away from the other and they may never meet up (especially if one is righ-handed and the other left-handed and they both walk out of the bar forwards).

    11 months ago Reply

    • avatar
      Thomas Lumley

      That’s one of the ways in which the problem is unrealistic. There are others as well, such as the infinite forest.

      10 months ago Reply

  • avatar
    Martin Kealey

    I wonder if there’s any difference between meeting on “odd” or “even” steps?

    I suspect the trio will never meet again (mumble four-dimensional random walk mumble)

    11 months ago Reply

  • avatar
    Murray Jorgensen

    There’s a false assumption right at the beginning: “two drunk statisticians leave a bar”.

    10 months ago Reply

Add a comment

First time commenting? Please use your real first name and surname and read the Comment Policy.