mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-06-28, 01:19   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

32·71 Posts
Default 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.
MattcAnderson is offline   Reply With Quote
Old 2017-06-28, 01:54   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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.

Last fiddled with by science_man_88 on 2017-06-28 at 02:09
science_man_88 is offline   Reply With Quote
Old 2017-06-28, 02:35   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×23×29 Posts
Default

And what if the bar is one mile South of the North Pole?
retina is online now   Reply With Quote
Old 2017-06-28, 03:17   #4
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

32×71 Posts
Default

Hi Again,

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

Regards,
Matt
Attached Files
File Type: pdf Solution random walk.pdf (179.7 KB, 62 views)
MattcAnderson is offline   Reply With Quote
Old 2017-06-28, 05:08   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100001011102 Posts
Default

Quote:
Originally Posted by retina View Post
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?
Batalov is offline   Reply With Quote
Old 2017-06-28, 05:15   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10111011100112 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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.
retina is online now   Reply With Quote
Old 2017-06-28, 05:50   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

22×3×13×59 Posts
Default

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
Click image for larger version

Name:	Rando.png
Views:	66
Size:	15.9 KB
ID:	16340  
Uncwilly is online now   Reply With Quote
Old 2017-06-28, 11:29   #8
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

32×71 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Old 2017-06-28, 12:15   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×23×29 Posts
Default

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.

retina is online now   Reply With Quote
Old 2017-06-28, 13:53   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,987 Posts
Default

Quote:
Originally Posted by retina View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-28, 17:44   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

244148 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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".)
xilman is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 22:52.

Fri Jan 22 22:52:42 UTC 2021 up 50 days, 19:04, 0 users, load averages: 1.97, 2.12, 1.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.