random walk

MattcAnderson · 2017-06-28, 01:19

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

science_man_88 · 2017-06-28, 01:54

Quote:

Originally Posted by MattcAnderson

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

not sure what the distribution is I would guess a bell curve ? as to the shortest I would get 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). as for the longest I think 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.

retina · 2017-06-28, 02:35

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

MattcAnderson · 2017-06-28, 03:17

Hi Again,

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

Regards,
Matt

Batalov · 2017-06-28, 05:08

Quote:

Originally Posted by retina

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

What's worse is what if the bar is $1 \pm {1 \over 2 k \pi}$ miles South of the North Pole?

retina · 2017-06-28, 05:15

Quote:

Originally Posted by MattcAnderson

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

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.

Uncwilly · 2017-06-28, 05:50

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?

MattcAnderson · 2017-06-28, 11:29

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

retina · 2017-06-28, 12:15

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 can filp [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.

CRGreathouse · 2017-06-28, 13:53

Quote:

Originally Posted by retina

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 think we're on an infinite plane with two distinguished orthogonal directions.

xilman · 2017-06-28, 17:44

Quote:

Originally Posted by CRGreathouse

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

I think we can also assume Euclidean geometry. (Just to nail down the meaning of the word "plane".)

2017-06-28, 01:19	#1
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2⁵×5² Posts	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 Last fiddled with by MattcAnderson on 2017-06-28 at 01:20 Reason: forgot about infinite flipping.

2017-06-28, 05:50	#7
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2·3·7·233 Posts	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? Attached Thumbnails

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
random comments, random questions and thread titles made for Google	jasong	Lounge	46	2017-05-09 12:32
Never fails...walk out the door and computer crashes	Chuck	GPU to 72	28	2013-11-27 04:29
Ryder Cup - A good walk spoiled?	davieddy	Hobbies	1	2010-10-21 11:21
About random number (random seed) in Msieve	Greenk12	Factoring	1	2008-11-15 13:56
A walk down memory lane....	petrw1	Lounge	0	2008-11-13 22:38

2017-06-28, 02:35	#3
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2²·1,549 Posts	And what if the bar is one mile South of the North Pole?

2017-06-28, 11:29	#8
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2⁵·5² Posts	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

2017-06-28, 12:15	#9
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2²·1,549 Posts	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 can filp [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.