Drunken sailor

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Drunken sailor

Let's say there is a drunken sailor that is one step away from his home. His is so hammered though, that the probability of him making a step forwards is exactly 1/2 and the probability of him making a step backwards is also 1/2. He can only go forwards or backwards, he never dies, gives up or sobers up, all his steps have exactly the same length and he has infinite space behind him. What is the probability that he never gets home?

bane2571
Posts: 46
Joined: Tue Oct 14, 2008 11:15 pm UTC

Re: Drunken sailor

With no Real Justification:
Spoiler:
I would say he is Gaurunteed to get home, albeit after an extremely long time. Given that there is always a small chance he will hit enough forward steps to get home on any given run of forward steps.

That answer seems intuitive, but I may be missing somehting.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Drunken sailor

You are correct, but for the wrong reason.
Spoiler:
Suppose instead the drunken sailor could go forward, backward, right, left, up, and down. Now no matter where he goes, there is always a small chance that his next sequence of steps will take him home. However, it is no longer certain that he will eventually get home. This is an example of a random walk on an infinite lattice, which is recurrent in one or two dimensions, but not in three.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Goplat
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: Drunken sailor

Spoiler:
0. Yes, he gets home 100% of the time. Proof:

Let f(x) = the probability of never getting home when starting x steps away from home. f(0) = 0, obviously. For x > 0, f(x) = .5*f(x-1) + .5*f(x+1), since there is a 50% chance of going each way.

Using the formulas above it can be shown that f(2) = 2*f(1), f(3) = 3*f(1), f(4) = 4*f(1), and so on. Now suppose that f(1) is nonzero: Eventually, there is an x where f(x) > 1, which is nonsense (how can any probability be more than 1?) So, reductio ad absurdum, f(1) = 0.

karkaputto
Posts: 29
Joined: Fri Aug 21, 2009 4:54 am UTC
Contact:

Re: Drunken sailor

Spoiler:
this is the opposite of gambler's ruin http://en.wikipedia.org/wiki/Gambler%27s_ruin so yeah, like people said, he's guaranteed to get home

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Drunken sailor

Goplat wrote:
Spoiler:
0. Yes, he gets home 100% of the time. Proof:

Let f(x) = the probability of never getting home when starting x steps away from home. f(0) = 0, obviously. For x > 0, f(x) = .5*f(x-1) + .5*f(x+1), since there is a 50% chance of going each way.

Using the formulas above it can be shown that f(2) = 2*f(1), f(3) = 3*f(1), f(4) = 4*f(1), and so on. Now suppose that f(1) is nonzero: Eventually, there is an x where f(x) > 1, which is nonsense (how can any probability be more than 1?) So, reductio ad absurdum, f(1) = 0.

I think this proof is incorrect. If the probability of getting home is indeed greater than zero if the "one step away"-sailor can go up, down, left and right too, then you're calculation would mean that he might not get home even if he is already home. F(0) would be f(1,0,0)/8+f(0,1,0)/8+f(0,0,1)/8+f(-1,0,0)/8+f(0,-1,0)/8+f(0,0,-1)/8 = f(1,0,0) >0

You can't calculate f(x) that way. Imagine a game, where you flip a coin once. You win if you get heads and lose if you get tails. With an fair coin the probability of winning would be 1/2. But the probybility of winning, when you already got heads is not 1/4 but 1.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Drunken sailor

Caesar wrote:
Goplat wrote:
Spoiler:
0. Yes, he gets home 100% of the time. Proof:

Let f(x) = the probability of never getting home when starting x steps away from home. f(0) = 0, obviously. For x > 0, f(x) = .5*f(x-1) + .5*f(x+1), since there is a 50% chance of going each way.

Using the formulas above it can be shown that f(2) = 2*f(1), f(3) = 3*f(1), f(4) = 4*f(1), and so on. Now suppose that f(1) is nonzero: Eventually, there is an x where f(x) > 1, which is nonsense (how can any probability be more than 1?) So, reductio ad absurdum, f(1) = 0.

I think this proof is incorrect. If the probability of getting home is indeed greater than zero if the "one step away"-sailor can go up, down, left and right too, then you're calculation would mean that he might not get home even if he is already home. F(0) would be f(1,0,0)/8+f(0,1,0)/8+f(0,0,1)/8+f(-1,0,0)/8+f(0,-1,0)/8+f(0,0,-1)/8 = f(1,0,0) >0

You can't calculate f(x) that way. Imagine a game, where you flip a coin once. You win if you get heads and lose if you get tails. With an fair coin the probability of winning would be 1/2. But the probybility of winning, when you already got heads is not 1/4 but 1.

The recurrence relation f(x) = .5*f(x-1) + .5*f(x+1) is indeed only valid for x non-zero (or just x>0 for the one-sided one-dimensional version) because it describes the probability in terms of the situation after the next move. Clearly x=0 is a special case because that is the boundary, a position where no more moves are made. Goplat clearly defined f to be 0 at x=0, and stated that the relation only holds elsewhere.

You claim the solution method is false because the recurrence relation does not hold at x=0. The solution method however explicitly uses the fact that the relation does not hold at x=0.

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Drunken sailor

Yes, you're right. I'm sorry, I should have read more carefully.

Edit: But I still don't get it. How can I show that f(2)=2*f(1)? Whenever i use the formulae f(n)=(f(n-1)+f(n+1))/2 I substitute an unknown term with another unknown term.

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

Re: Drunken sailor

Why does a proof like this work in one or two dimensions, but fail in three, as skeptical scientist says?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Drunken sailor

Ralp wrote:Why does a proof like this work in one or two dimensions, but fail in three, as skeptical scientist says?

2 dimensions is really just 2 copies of the 1 dimensional problem running at the same time, namely one copy with forward steps of (1/2, 1/2) the other with forward steps of (1/2, -1/2). You need to do a little bit more work, but that's the gist of why 1 dimension working implies 2 dimensions working. Note that there is no way to do this for 3 dimensions, since there are 6 options which is not a power of 2.

Let's try to use the proof in 3d and see what goes wrong:

For points not equal to 0, we have
$f(x,y,z) = \frac{1}{6}\bigl(f(x+1, y, z) + f(x -1, y, z) + f(x, y+1, z) + f(x, y-1, z) + f(x, y, z+1) + f(x, y, z-1)\bigr)$

Now, the next step is to rearrange this so that we can write a bigger term in terms of smaller terms.

Let's try that:
$f(x+1, y, z) = 6f(x,y,z) - \bigl( f(x -1, y, z) + f(x, y+1, z) + f(x, y-1, z) + f(x, y, z+1) + f(x, y, z-1)\bigr)$

Oh, damn, when i try to make one component smaller, I get 2 terms with another one bigger! There's no way to make this recurrence relate bigger terms to only smaller ones (measured by the sum of elements). However, in the 1d case, this did work, because there are no other components to get bigger. It's a strictly 1d proof. And 2d works because it's really just 1d twice.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Drunken sailor

Caesar wrote:Yes, you're right. I'm sorry, I should have read more carefully.

Edit: But I still don't get it. How can I show that f(2)=2*f(1)? Whenever i use the formulae f(n)=(f(n-1)+f(n+1))/2 I substitute an unknown term with another unknown term.

Take n=1, and substitute f(0)=0.

In general for n>1, if you assume f(n-1)=(n-1)f(1) and f(n)=nf(1), you can apply the same formula to get $nf(1)=\frac{(n-1)f(1)+f(n+1)}{2}$$2nf(1)=(n-1)f(1)+f(n+1)$$f(n+1)=(n+1)f(1).$
Since f(0)=0=0f(1) and f(1)=1f(1), by induction f(n)=nf(1) for all n.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson