random walk
 

Hi Mersennneforum,

Here is a puzzle that some of you will enjoy.

It is a modification of the 'drunkard's walk'.

A man leaves a bar and flips a coin. If it is heads, he walks one mile north. If it is tails, he goes one mile east. Then, given two possible locations, he flips a coin again. Heads, sends him only half a mile north and tails he goes half a mile east. The third flip of the coin only sends him a quarter of a mile in either of the two directions.

Assume the drunkard can filp a coin an infinite number of times.

The questions are what is the longest distance and the shortest distance that he travels as measured 'as the crow flies from the bar?

Also, what is the distribution of distances he travels?

Regards,
Matt

[QUOTE=MattcAnderson;462218]Hi Mersennneforum,

Here is a puzzle that some of you will enjoy.

It is a modification of the 'drunkard's walk'.

A man leaves a bar and flips a coin. If it is heads, he walks one mile north. If it is tails, he goes one mile east. Then, given two possible locations, he flips a coin again. Heads, sends him only half a mile north and tails he goes half a mile east. The third flip of the coin only sends him a quarter of a mile in either of the two directions.

Assume the drunkard can filp a coin an infinite number of times.

The questions are what is the longest distance and the shortest distance that he travels as measured 'as the crow flies from the bar?

Also, what is the distribution of distances he travels?

Regards,
Matt[/QUOTE]

not sure what the distribution is [SPOILER]I would guess a bell curve ?[/SPOILER] as to the shortest I would get [SPOILER]2 because the limit of 1+1/2+1/4... doh wrong he can go 1 mile east and 1 mile north and have distance sqrt(2). [/SPOILER] as for the longest I think [SPOILER] sqrt(8) because that's the diagonal of the square for which he can walk either the north or east side of if he does both ( taking the limit of it in both directions would take him to the far corner. [/SPOILER]

And what if the bar is one mile South of the North Pole? :shock:

Hi Again,

I don't have a full solution, but the attached file has some answers.

Regards,
Matt

[QUOTE=retina;462221]And what if the bar is one mile South of the North Pole? :shock:[/QUOTE]
What's worse is what if the bar is [TEX]1 \pm {1 \over 2 k \pi}[/TEX] miles South of the North Pole?

[QUOTE=MattcAnderson;462218]The questions are what is the longest distance and the shortest distance that he travels as measured 'as the crow flies from the bar?[/QUOTE]Insufficient information provided to answer this question.

I gave a hint already above. But the location (in both space and time) of the bar is important. Different terrains, different altitudes, even different days will all change the distance calculations.

I figured that 2.0 was the max and 1.414 was the min.
Ran 10000 simulations (and 8000 in a second run) and found that this is the case.
Attached is a histogram of the values. The separate run of 8000 gave an average of 1.624 and Std Dev of 0.179

It would be interesting to plot the actual points, but the should fall on/near the (0,2) to (2,0) line.

What if the first 2 were between north and east, then the next 2 are west and south?

Hi again,

Okay, lets assume the bar is in Paris. There is no need to march to the north pole and then try to walk east.

Regards,
Matt

The scenario as posted only shows two flips of the coin as actual actions. The third flip specifies a directional possibility but fails to say which flip maps to which direction, and also doesn't actually say if any action is taken, merely what would happen. And the following paragraph says the "drunkard [i]can[/i] [u]filp[/u] [sic] a coin an infinite number of times", but doesn't say how that relates to any previous actions, (or what a filp is).

So based upon that the maximal distance to two heads going North for 1.5 miles. And the minimal distance is tails then heads going East then North (from Paris) for marginally less than sqrt(5/4) miles, because there is a small curvature of the path when going East which I'm too lazy to work out just now. Plus lots of assumptions about how crows fly.

:devil:

[QUOTE=retina;462240]Insufficient information provided to answer this question.

I gave a hint already above. But the location (in both space and time) of the bar is important. Different terrains, different altitudes, even different days will all change the distance calculations.[/QUOTE]

I think we're on an infinite plane with two distinguished orthogonal directions.

[QUOTE=CRGreathouse;462271]I think we're on an infinite plane with two distinguished orthogonal directions.[/QUOTE]I think we can also assume Euclidean geometry. (Just to nail down the meaning of the word "plane".)