9
$\begingroup$

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the number of steps approaches infinity.

enter image description here

However, if further limiting rules are added, the probability of the point reaching distance $d$ from the startpoint is altered.

What is the expected distance $d$ from the startpoint given the following rules:

1) The point may not "go back on itself" (eg, if move #3 is up, move #4 cannot be down)

2) The random walk finishes if the point "crashes into" any previous path it has taken (ie, it cannot take a path it has taken previously)?

(Clearly the minimum number of steps is 4.)

$\endgroup$
13
  • $\begingroup$ This problem is hard because you cannot use the Markov property. Did you try a simulation? $\endgroup$
    – Lost1
    Commented Jul 4, 2014 at 12:32
  • $\begingroup$ Not yet - no access to a computer at the moment $\endgroup$
    – martin
    Commented Jul 4, 2014 at 12:44
  • $\begingroup$ But you can meet a vertex twice? $\endgroup$
    – draks ...
    Commented Jul 4, 2014 at 12:51
  • 2
    $\begingroup$ How do you count the distance for the walks that already crashed? $\endgroup$
    – Did
    Commented Jul 4, 2014 at 13:02
  • $\begingroup$ @ Draks, yes that is ok - no crash there $\endgroup$
    – martin
    Commented Jul 4, 2014 at 13:34

1 Answer 1

1
$\begingroup$

Rule 1 doesn't affect the process much:

Given a standard random walk of the form you initially describe, recursively removing backtracks (e.g. the subsequence ULRRLD would get removed) yields a walk following rule 1, and importantly, does not introduce any bias into the process (i.e. the three available options (under rule 1) are equally likely also in this "standard random walk with backtracks removed" process.

It does affect the time taken, speeding up the process by a surprising factor of 3. This is because every non-backtracking step taken in the standard process has an equal chance $p$ of being undone due to later backtracking, which is $p = 1/(1+3(1-p)) = 1/(4-3p)$, so $3p^2-4p+1=0$, and we get $p=1/3$. (The solution $p=1$ is not an attracting point of the original recursion.) So 1/3 of the steps will be annulled due to backtracking by another 1/3 of the steps, leaving only the remaining 1/3 in the reduced path that follows rule 1.

It also affects the set of "already taken" points and segments, which will affect the "time to crash".

Rule 2 has a big effect on the process, and since it involves remembering the entire path history, it belongs to a class of questions that generally do not have closed-form solutions.

However, we can still get a strong bound on the expected distance, because it cannot exceed the expected running time. Even just considering crashes due to going around a square (three consecutive right turns, or three consecutive left turns), we can get a bound (using a method like this) on the expected survival time of less than 20, and thus the expected distance when it crashes will be much less than 20.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .