Random walk probability

Question

I encounter a problem:Consider a two dimensional map, with an x-axis (horizontal direction) and a y-axis (vertical direction). Coordinates on the map can therefore be represented as a two-dimensional vector (x, y). A tourist is standing at coordinates (0, 0), and is looking for the the tourist information centre, located at coordinates (−10, 30). However, the tourist is completely lost and instead of asking for directions, begins a random walk to search for the tourist information centre. The tourist moves one step at a time, either horizonally or vertically (but can not move diagonally). Steps can also be forwards (in a positive direction) or backwards (in a negative direction). Therefore, at every point, there are 4 possible moves the tourist can make. For instance, when standing at the origin (0,0), the tourist can move either to (0, 1), (0, −1), (1, 0) or (−1, 0), and has an equal probability of moving in each direction, thus a probability of 0.25 for each option. What is the probability that this tourist locates the tourist office in 1000 steps or less?

Aaron Montgomery gave the hint that the simulation is a good way to estimate the probability. Could any expert give a full code, like the C++ or R code, to help us better understand this kind of question? Thanks in advance.

Answer 1

Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $\vec{D}=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.

By an $n$-path, I mean a sequence $\vec{r}_1, \cdots, \vec{r}_n$ with each $\vec{r}=xe_1+ye_2$ being such that either $x=\pm 1$ and $y=0$ or $x=0$ and $y=\pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $\vec{D}$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.

Take an $n$-path. Let $N^x_{\pm}$ be the number of horizontal steps in $\pm$ directionrespectively. Similarly define $N_\pm^y$. Clearly, $$ N_+^x-N_-^x=X, \qquad N_+^y-N_-^y=Y, \qquad N_+^x+N_-^x+N_+^y+N_-^y=n $$ We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations $$ \begin{pmatrix} N_+^x\\ N_-^x\\ N_+^y\\ N_-^y \end{pmatrix}=\frac{1}{2}\begin{pmatrix} m+X\\ m-X\\ n-m+Y\\ n-m-Y \end{pmatrix} $$ Which obiously requires $m\geq |X|$, $n-m\geq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $\vec{D}$ are $$ \nu_m=\binom{n}{m}\binom{m}{N_+^x}\binom{n-m}{N_+^y}= \binom{n}{m}\binom{m}{\frac{m+X}{2}}\binom{n-m}{\frac{n-m+Y}{2}} $$ and the total number of $n$-paths ending at $\vec{D}$ are $$ \boxed{ N_n(X,Y)=\sum_{m\text{ is }(n,X,Y)\text{-admissible}} \binom{n}{m}\binom{m}{\frac{m+X}{2}}\binom{n-m}{\frac{n-m+Y}{2}}} $$ Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $m\geq 10$ and $1000-m\geq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10\leq m\leq 970$.

Answer 2

I'm not sure how you're getting the claim that $P((a + c) \leq 490$, or even quite what you mean by that, but I don't think there's any way to reduce the question in that way. Note that it could be the case that $a = 500, b = 470, c = 10, d = 20$ when the tourist finds the desired location, for instance. Conditions like this will be challenging to use because the tourist can overshoot the information center and come back to it, or maybe they just take a direct path for it, etc.

My advice: this question is going to be hard to answer analytically, so you should be looking for some sort of computational tactic here. What that looks like will depend on the tools that you're familiar with. Two possible options:

• Simulation. Simulate lots of these walkers and see how many actually find the information center within 1000 steps.
• Markov Chain methods. You could set up a Markov chain with state spaces corresponding to $[-1000, 1000] \times [-1000, 1000]$ (so, $\approx 4 \cdot 10^6$ states) and do the traditional tactics involving playing with a transition matrix. A good primer on this can be found in Doyle and Snell if you're unfamiliar with them. In fact, you don't even have to make a $2000 \times 2000$ grid, because if the walker ever gets too far away from the information center then they have reached a point of no return and can't get back. Setting up the transition matrix is the obnoxious part, but it wouldn't be too hard to write an algorithm to do that.

And of course, I certainly don't claim this to be an exhaustive list of possible ways to proceed -- butI do think that trying to get an exact answer will be horrifying at best.

EDIT: You asked for full code, but I am not going to provide that -- nor, I think, should anyone else. Coding this up is a great exercise, and it is absolutely worth doing yourself for the practice! (Also, to provide that code would feel too close to "doing someone's homework" for my taste.) To give a more comprehensive hint, here's what the pseudocode might look like:

set totalvisits = 0
set trials = 10000      % may be useful to experiment with a bigger number
for i = 1 to trials
{
  set x = 0, y = 0, visit = 0
  for n = 1 to 1000
  {
    generate random integer z in {1, 2, 3, 4}
    if z = 1, add 1 to x
    if z = 2, subtract 1 from x
    if z = 3, add 1 to y
    if z = 4, subtract 1 from y
    if x = -10 and y = 30, set visit = 1
  }
  totalvisits = totalvisits + visit
}
% The probability of visiting the info center is totalvisits / trials

Answer 3

In order to calculate the probability of reaching $v=(-10,30)$ in at most $1000$ steps, you need to add up the probabilities of reaching $v$ for the first times in $n$ steps for $n=40,41,\dots,1000$.

To this end, let $a_n$ be the number of ways to reach $v$ for the first time in $n$ steps. Computing $a_n$ directly seems difficult. There is a simple recursive program to do it, which when memoized takes $n^3$ time, but this is intractable when $n=1000$. Fortunately, $a_n$ is related to some other quantities which are easier to compute. Let $$ b_n = \text{# ways to walk from (0,0) to $v$ in $n$ steps}\quad\;\\ c_n = \text{# ways to walk from (0,0) to (0,0) in $n$ steps} $$ You can show that $$ b_n = \sum_{k=0}^n a_k c_{n-k}, $$ because in order to reach $v$ in $n$ steps, you need to reach $v$ for the first time in $k$ steps for some $0\le k\le n$, and then move from $v$ to $v$ for the remaining $n-k$ steps (which is the same as going from $(0,0)$ to $(0,0)$). The above can be solved for $a_n$: $$ a_n = b_n - \sum_{k=0}^{n-1}a_kc_{n-k} \tag1 $$ This gives a way to compute $a_n$, provided we can compute $b_n$ and $c_n$. Simply compute $a_0,a_1,\dots,a_n$ in that order, using previously computed values $a_k$ in the above formula each time. Computing $a_{n}$ takes $n$ loops with $O(n)$ summations each, for $O(n^2)$ operations, which is tractable when $n=1000$.

Fortunately, there are quick ways to compute $b_n$ and $c_n$ as well: $$ b_n = \begin{cases}\binom{n}{({n+(-10)+30})/2}\binom{n}{({n+(-10)-30})/2} & n\text{ is even}\\0 & \text{otherwise}\end{cases}\tag2 $$

$$ c_n = \begin{cases}\binom{n}{n/2}^2 & n\text{ is even}\\0 & \text{otherwise}\end{cases}\hspace{4cm}\tag3 $$

In summary, using $(1)$ gives you a recursive procedure to compute $a_n$, combined with the formulae in $(2)$ and $(3)$. This then allows you to compute the desired probability, $P=\sum_{n=40}^{1000} a_n\cdot (1/4)^n$. You should now have enough information to write a program to compute $P$.