Easy math puzzles

Quote: ThatDonGuy

My Answer

I'll go with the obvious answer: I expect him to be on the sidewalk.

Since the sidewalk runs north-south, the distance from the sidewalk will be the difference between the number of steps east and the number of steps west. However, since these are equally likely with each step, the expected number of steps east equals the expected number of steps west.

For that matter, since the expected number of steps north equals the number of steps south, I expect him to be at his starting location.

link to original post

Disagree

Quote: Ace2

Here’s another easy one:

A drunkard starts walking on a straight sidewalk that runs north-south. His goal is to walk northward, but for each step he’s equally likely to go one foot directly north, south, east or west.

After 10,000 steps, how far off the sidewalk would you expect him to be?

Closed form solutions only.
link to original post

The answer is (10,000/π)^.5 =~ 56.419 steps from the sidewalk. That’s technically an approximation though a very accurate one. The formula comes from integrating the normal curve times x from zero to infinity then multiplying times two. This gives the expected distance from the mean.

The exact answer (shown to ten digits) of 56.41825312 can be obtained via Markov chain, though that’s not a closed form solution.

If you were to start searching for the drunkard, the best place to start would be at the sidewalk since you don’t know which side of it he’s on, but you’d be an average of ~56 steps away from it when you found him. The chance of him being on the sidewalk is <1%

The issue of where to start to search can be an issue in Orienteering. The concept of the sport is you're given a map of, typically, a forest and you have to find a series of controls. Let's say you're trying to find a point on a footpath that runs East-West but is due North of where you are. You're good at following a compass heading but have an in-built error, so the point you reach on the footpath follows a normal curve. Assuming you're trying to pick the fastest option, I suspect your optimal choice is to aim towards one side, say slightly West of North, and then turn East when you reach the footpath. At some stage you recognise your likely error and need to turn back on yourself. etc. (In the original puzzle you could only be whole degrees out and never greater than 4SDs.)

Quote: Ace2

The answer is (10,000/π)^.5 =~ 56.419 steps from the sidewalk. That’s technically an approximation though a very accurate one. The formula comes from integrating the normal curve times x from zero to infinity then multiplying times two. This gives the expected distance from the mean.

The exact answer (shown to ten digits) of 56.41825312 can be obtained via Markov chain, though that’s not a closed form solution.
link to original post

Technically, an approximation isn't one either.

The closest to a "closed form solution" that I got was this:
Each step has probability 1/4 of adding 1 to the number of steps to the left of the sidewalk, 1/4 of subtracting 1, and 1/2 of keeping it the same.
Let (m, n, 10,000 - (m + n)) represent the number of steps to the left, the number to the right, and the number forward/backward, with each one being >= 0 and <= 10,000.
The number of steps away from the sidewalk is |m - n|, and the probability of that particular triple is C(10,000, m) C(10,000 - m, n) (1/4)^10,000, or C(10,000, m) C(10,000 - m, n) / 2^20,000.
The solution is the sum over all m from 0 to 10,000 of (the sum over all n from 0 to (10,000 - n) of ( |m - n| C(10,000, m) C(10,000 - m, n) ) ), divided by 2^20,000.
However, I could not find a way to simplify that.