2
$\begingroup$

Start at any point on a 2D plane. Go 1 unit forward, then flip a coin to turn left or right on the spot. Keep repeating.

When you go back to somewhere you've previously been, what is the expected number of steps that you have taken?

I don't have any clues as to where to start on this problem. Any help would be appreciated.

$\endgroup$
  • $\begingroup$ So this is on a 2D square lattice then? $\endgroup$ – Ian Oct 14 '17 at 1:31
  • $\begingroup$ @lan yes, on a 2D plane $\endgroup$ – Xiangyu Chen Oct 14 '17 at 1:36
  • 1
    $\begingroup$ Interesting question. Some simulations I did with a 100,000 walks each, indicates the answer is around $8 \pm 0.2$. $\endgroup$ – Jens Oct 15 '17 at 21:07
1
$\begingroup$

The answer is $8$.

Or rather, there are two strong indications that support this claim:

  1. My simulations show consistently that the answer is $8.0 \pm 0.2$
  2. An observed pattern, if it holds true for walks of any length, will result in the answer being exactly $8$.

I'm going to concentrate on point $2$ because it is (to me) mind-blowing!

Start a walk by taking one step in some direction, e.g. East. At the next step, turn Right. We could have turned Left, but all possible paths from turning Left would just have been mirror images of all possible paths from turning Right.

Now generate all possible paths from the current position. There are $2$ possible paths for the next (3rd) step. And $2$ possible paths for each of those paths, etc. At the 4th step, $1$ of the $4$ possible walks loops back upon itself. At the 5th step, $1$ of the $6$ possible remaining walks loops back upon itself. At the 6th step, $2$ of the $10$ possible remaining walks loops back upon itself. If we continue this forward for a while, we see the following pattern regarding steps taken and number of loop backs:

$4 \ : \ 1$

$5 \ : \ 1$

$6 \ : \ 2$

$7 \ : \ 3$

$8 \ : \ 5$

$9 \ : \ 8$

And we notice something about the number of loop backs at each stage, namely: The pattern of the number of loop backs is the Fibonacci series!!!

I know I shouldn't get too excited because the pattern above could break any time someone does a computer simulation (I did the above manually), but I feel confident the pattern will continue. I feel confident because if one calculates what the expected number of steps would be if the Fibonacci pattern above continues, one gets exactly the number $8$! See here for how to make this calculation (thank you @lulu!).

EDIT

A beautiful theory ruined by an ugly fact.

So I went ahead and did the computer simulation to check that the number of loop backs (intersections) continues to match the Fibonacci series and it does....for one more step. Then it deviates for a few steps, then gets back on track in steps $13$ and $14$ and then deviates permanently. See the comparison below:

enter image description here

If one computes the expected number of steps at each step, the "loop backs" surges ahead of the Fibonacci series at step $11$ and only starts falling behind at step $25$. Since we know that the Fibonacci series gives the answer $8$, I think we can conclude that the actual answer to the OP is slightly less than $8$.

$\endgroup$
  • $\begingroup$ Can I see your code? I found slightly different values. $\endgroup$ – Xiangyu Chen May 19 '18 at 20:13
  • $\begingroup$ @V.Chen: Yes, I had an error in my code. The correct sequence and the code can be found here. $\endgroup$ – Jens May 21 '18 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.