9
$\begingroup$

Consider a random walk on the integer lattice in the plane. If a “particle” making a random walk arrives at a lattice point $p = (k_1,k_2)$ at the time $t$, then one of the four neighbors $(k_1±1, k_2 )$, $(k_1 , k_2 ± 1)$ of p is selected with equal probability $\frac{1}{4}$ . The particle moves to that neighbor at time $t + 1$. Let $D$ be a region in the plane (a square or a half plane for example), and let $B$ denote its boundary. Let $p$ be a point of $D$, and let $b$ be a boundary point. We’ll denote by $P_p(b)$ the probability that a random walk starting at $p$ exits at $b$, i.e., that $b$ is the first boundary point that is reached.

I was wondering if someone could help me answer some questions if the region in the plane that we are considering is a rectangle.

1) What is the probability that a particle starting at $p$ never reaches the boundary? 2) What is the “exit time”, the expected time for a particle starting at $p$ to reach the boundary? 3) How does the exit time depend on $p$?

$\endgroup$
  • $\begingroup$ 1) is easy. There is a nonzero probability that the first $n$ steps will be in the same direction. So if the region is rectangular, there is a nonzero probability that the walk will take you to an edge in the shortest way possible. And so the probability it never reaches the boundary is $0$. $\endgroup$ – alex.jordan Feb 18 '16 at 23:39
  • $\begingroup$ @alex.jordan Could you write me a solution for all 3 questions ? $\endgroup$ – user43418 Feb 19 '16 at 0:17
  • $\begingroup$ If someone could help me in any way with questions 2 and 3, that would be much appreciated $\endgroup$ – user43418 Feb 19 '16 at 0:59
  • $\begingroup$ I don't see an easy way to answer 2) and 3). I only commented on 1) because it was the only one I see as easy. If I had an answer for 2) and 3) I would probably try for the bounty. $\endgroup$ – alex.jordan Feb 19 '16 at 1:02
  • $\begingroup$ @alex.jordan Do you have maybe a direction that I could follow or things that I coud try ? $\endgroup$ – user43418 Feb 19 '16 at 1:13
3
+200
$\begingroup$

If the region is bounded,i.e., the number of points is finite, name the interior points as $p_1,\dots,p_n$. Let $t_1,\dots,t_n$ be the corresponding expected exit times. Let also $a_1,\dots,a_n$ denote the number of boundary points adjacent to each $p_i$. Now define the matrix $B=(b_{ij})$ as $b_{ij}=1$ if $p_i$ and $p_j$ are adjacent, and $b_{ij}=0$ otherwise (note that $b_{ii}=0$). Then $$ T=\frac 14(A+B(T+1)), $$ from which it follows that $$ T=(4 Id-B)^{-1}(A+B1), $$ where 1 is the vector of ones, $(T+1)_i=t_i+1$. For example, if $n=1$, then $A=(a_1)=(4)$, $B=0$ and so $T=(t_1)=(1)$.

If $n=2$, $A=\begin{pmatrix} 3\\ 3 \end{pmatrix}$ $B=\begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}$ and so $T=\begin{pmatrix} 4/3\\ 4/3 \end{pmatrix}$.

If $n=3$, $A=\begin{pmatrix} 3\\ 2\\ 3 \end{pmatrix}$ $B=\begin{pmatrix} 0&1&0\\ 1&0&1\\0&1&0 \end{pmatrix}$ and so $T=\begin{pmatrix} 10/7\\ 12/7\\ 10/7 \end{pmatrix}$.

If $n=4$ and you have a square, $A=\begin{pmatrix} 2\\ 2\\ 2\\2 \end{pmatrix}$ $B=\begin{pmatrix} 0&1&1&0\\ 1&0&0&1\\1&0&0&1\\ 0&1&1&0 \end{pmatrix}$ and so $T=\begin{pmatrix} 2\\2\\2\\2 \end{pmatrix}$.

If $n=9$ and you have a square, $A=\begin{pmatrix} 2\\1\\ 2\\1\\0\\1\\ 2\\1\\2 \end{pmatrix}$ $B=\left( \begin{array}{ccccccccc} 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ \end{array} \right)$ and so $T=\left( \begin{array}{c} \frac{11}{4} \\ \frac{7}{2} \\ \frac{11}{4} \\ \frac{7}{2} \\ \frac{9}{2} \\ \frac{7}{2} \\ \frac{11}{4} \\ \frac{7}{2} \\ \frac{11}{4} \\ \end{array} \right)$.

The region doesn't need to be a square or a rectangle.

For some infinite regions one can compute the expected exit times. In the case of the half plane, it is not possible, the expected time cannot be finite, because then $t_k=k t_1-4 \binom{k}{2}$ leads to a contradiction. If you have an infinitely long rectangle of height $n+2$ (so you have $n$ nontrivial rows of points), then you have $t_1=2n$ and $t_k=k t_1-4 \binom{k}{2}$ for $k=2,\dots,n$.

${\textbf{ Edit:}}$ Justification of the formulas.

The expected time is computed using the sum over the possible paths from a point to the boundary of the product of the probability of a certain path to be realized multiplied by the time you need to travel through the path, which in this case is just the length of the path. Since the number of path is infinite, this infinite sum can converge or not.

Assume the expected time $t_i$ converges at the point $p_i$. Then you can divide the set of paths starting from $p_i$ in four subsets, corresponding to the four neighbors of $p_i$. If a neighbor is a boundary point, then its contribution to the infinite sum is $$ (\text{probability of starting the path in this direction})\cdot (\text{length of the path})=\frac 14\cdot 1=\frac 14. $$

This explains the summand $\frac 14 a_i$ in the expression of $t_i$, i.e., the summand $\frac 14 A$ in the formula for $T$.

If a neighbor of $p_i$, call it $p_j$, is not a boundary, then every path starting at $p_i$ with the first step going to $p_j$, corresponds uniquely to a path from $p_j$ to the boundary. So, if the path is $$ P=(p_i,p_j,p_{k_3},p_{k_4},\dots,p_{k_n}) $$ where $p_{k_n}$ is a boundary point, then the corresponding path from $p_j$ to the boundary is $$ \overline{P}=(p_j,p_{k_3},p_{k_4},\dots,p_{k_n}). $$ Now the expected exit time starting from $p_j$ is the sum over such paths $P$ of the product of the probability $Prob(P)$ of each path to be realized multiplied by the length $L(P)$ of the path.

Since $Prob(P)=\frac 14 Prob(\overline{P})$ and $L(P)=L(\overline{P})+1$, the contribution of all the paths starting at $p_i$ with first step $p_j$ is $$ \sum_{P}Prob(P)L(P)=\sum_{\overline{P}}\frac 14 Prob(\overline{P})(L(\overline{P})+1) =\frac 14 \left(\left(\sum_{\overline{P}} Prob(\overline{P})L(\overline{P})\right)+1\right)=\frac 14 (t_j+1) $$ which explains the contribution of $p_j$ to the expected exit time $t_i$, which is $\frac 14 b_{ij}(t_j+1)$, i.e., the summand $\frac 14(B(T+1))$ in the formula for $T$. Note that $\sum_{\overline{P}} Prob(\overline{P})=1$.

$\endgroup$
  • $\begingroup$ could you just show that $t_k$ leads to a contradiction ? $\endgroup$ – user43418 Feb 21 '16 at 0:46
  • $\begingroup$ Also, why are you saying that the region doesn't need to be a square or a rectangle ? This was just a case that I thought would be interesting to consider $\endgroup$ – user43418 Feb 21 '16 at 0:48
  • $\begingroup$ The contradiction arises, because any finite value of $t_1$ would lead eventually to $t_k<0$ for $k$ big enough, which is impossible. $\endgroup$ – san Feb 21 '16 at 1:59
  • $\begingroup$ I also think that squares or rectangles are the most interesting cases, but what I wanted to say is that the method works for any bounded region. $\endgroup$ – san Feb 21 '16 at 2:00
  • $\begingroup$ could you explain how you found $t_k$ and matrix $T$ expression $\endgroup$ – user43418 Feb 23 '16 at 17:53

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.