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.
Best Answer
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$.