## Drunken sailor

**Moderators:** jestingrabbit, Moderators General, Prelates

### 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?

### Re: Drunken sailor

With no Real Justification:

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

**Spoiler:**

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:**

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

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

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

### Re: Drunken sailor

**Spoiler:**

### Re: Drunken sailor

Goplat wrote:Spoiler:

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.

### Re: Drunken sailor

Caesar wrote:Goplat wrote:Spoiler:

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.

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

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.

### Re: Drunken sailor

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

### 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

[math]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)[/math]

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:

[math]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)[/math]

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 [math]nf(1)=\frac{(n-1)f(1)+f(n+1)}{2}[/math][math]2nf(1)=(n-1)f(1)+f(n+1)[/math][math]f(n+1)=(n+1)f(1).[/math]

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

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

### Who is online

Users browsing this forum: No registered users and 11 guests