20
$\begingroup$

Suppose there is a grid $[1,N]^2$. A person standing at some initial point $(x_0,y_0)$ walk randomly within the grid. At each location, he/she walks to a neighboring location with equal probability (e.g., for an interior point, the probability is $\frac{1}{4}$; for a corner, it's $\frac{1}{2}$.). Suppose there are $m$ absorbing barriers $B=\{(x_1,y_1),\cdots,(x_m,y_m)\}$ inside the grid. Once the person is on a barrier, the random walk process stops. I'd like to ask how to calculate the hitting probability and the expected number of steps for each barrier.

Edit: The problem can be transformed into a Markov chain. But the expected hitting time for each absorbing state is still not easy to calculate.

$\endgroup$
4
  • 2
    $\begingroup$ interesting question, where is it from and have you made any progress? $\endgroup$ Jan 20, 2020 at 19:26
  • 1
    $\begingroup$ This was endorsed in the Pearl Dive. $\endgroup$ Jul 13, 2021 at 7:28
  • $\begingroup$ Is the "expected number of steps for each barrier" conditioned on that barrier actually being the one hit? It seems to me like this would be solved by dynamic programming, by considering each barrier in a system with the other barriers removed. I believe there may be a theorem that since the state space is finite, iterating over the states in any fixed order will converge to the solution, but I'm not sure, it has been a while since I've done any dynamic programming. $\endgroup$
    – Joe
    Jul 13, 2021 at 12:51
  • $\begingroup$ @Joe Feel free to start with the case $m=1$ when your concern is moot (if I got it right). It looks like this problem must be enjoyed slowly :-) $\endgroup$ Jul 13, 2021 at 15:54

2 Answers 2

6
+500
$\begingroup$

As mentioned in the edit, this can be represented as a Markov chain - in particular, a discrete time Markov chain on a finite state space, which is absorbing.

For much of the answer below, my reference is "Grinstead and Snell's Introduction to Probability", currently located at this link https://math.dartmouth.edu/~prob/prob/prob.pdf

For such a Markov chain, the states which are not absorbing are called transient. If there are $t$ transient states (for the posted problem, $t=N^2 - m$) and $r$ absorbing states (for the posted problem, $r=m$), it is common to order the states so that the transient states are first, so that the probability transition matrix is in block form as:

$$ P = \begin{bmatrix} Q & R\\ 0 & I_r \end{bmatrix} $$

Here $Q$ is $t \times t$, $R$ is $t \times r$, $0$ is the $r \times t$ zero matrix, and $I_r$ is the $r \times r$ identity matrix.

It is known that the $i,j$ entry of the "fundamental" matrix $N = (I_t - Q)^{-1}$ is the expected number of times that the chain will visit transient state $j$ if it started in transient state $i$.

Therefore, the sum of the $i^\mathrm{th}$ row of $N$ is the expected number of steps before being absorbed, if starting in transient state $i$.

The probability of being absorbed into absorbing state $j$, $1\le j \le r$, if the chain started in transient state $i$, is the $i,j$ entry of $B = NR$.

As for "the expected number of steps for each barrier", if the chain starts in a transient state $i$ that has a nonzero probability of not hitting a particular absorbing state $j$, then I believe the interpretation of the "expected number of steps to hit that barrier" would be infinity, since there is a positive probability that it will never hit the barrier.

But, if we are conditioning on the event that the chain is absorbed into barrier $j$, starting from state $i$, then to find the "expected number of steps before being absorbed", you proceed as above with two modifications:

First, you would consider a chain of only the transient states with positive probability of being absorbed into absorbing state $j$, together with absorbing state $j$ (so $r=1$). Any transient states that could not be absorbed into absorbing state $j$ (such as a transient state surround by other barriers) would not be a part of this new chain. Neither would the other absorbing states.

Second, you would use conditional probabilities in your probability transition matrix for this chain, so that the rows still sum to one. For example, if a state used to have four neighbors, but one of them was a barrier that we know it doesn't transition to (since it eventually gets absorbed into a different barrier), then the conditional probability that the random walk transitions to each of those three remaining neighbors is $\frac{1}{3}$.

Then you would have $$P' = \begin{bmatrix} Q' & R'\\ 0 & 1 \end{bmatrix}$$ You would solve for $N' = (I - Q')^{-1}$, and the expected number of steps before being absorbed, starting from transient state $i$, is the sum of the $i^\mathrm{th}$ row of $N'$.

$\endgroup$
2
  • $\begingroup$ When starting the bounty I was hoping somebody would post answers in special cases. May be that was asking too much? Anyway, thanks for playing :-) $\endgroup$ Jul 20, 2021 at 9:20
  • $\begingroup$ When starting to think about the problem, I was thinking that I would have to try to answer a special case, but I learned that the problem could be solved in general, which is neat. In fact, it would be the same answer in higher dimensions, as long as the state space was finite :-) $\endgroup$
    – Joe
    Jul 20, 2021 at 14:08
2
$\begingroup$

Here is another approach using discrete convolution. (1) First deduce the initial point $(x_0,y_0)\in [1,N]^2$, (2) then convolute with respect to a random-walk kernel, (3) read the values from the barriers, (4) set values at the barriers to zero, (5) repeat. Every iteration of this process represents one step taken. This implies that the barrier wise read values at the stage (3) are the hitting probabilities for each barrier. The expectation value of steps taken before hitting a barrier is a sum of probabilities to hit that barrier multiplied by the steps taken. This method is easy to apply, but requires some work to handel the boundary of the grid. For this the grid is split into a inside-, border-, and corner areas. For each we apply different convolution kernel, and then sum the results together. \begin{align} &I = \begin{bmatrix} 0 & 1/4 & 0\\ 1/4 & 0 & 1/4\\ 0 & 1/4 & 0 \end{bmatrix} &R = \begin{bmatrix} 0 & 1/3 & 0\\ 1/3 & 0 & 1/3\\ 0 & 1/3 & 0 \end{bmatrix} &C = \begin{bmatrix} 0 & 1/2 & 0\\ 1/2 & 0 & 1/2\\ 0 & 1/2 & 0 \end{bmatrix} \end{align} A letter "I" stands for inside, "R" for border, and "C" for corner. Here is an example: The grid is $A := [1,4]^2\subset\mathbb{N}^2$, the initial state is represented by a point $(2,2)$, and the barrier is $B := \{(2,3), (4,4)\}$. The initial situation in a matrix representation is: \begin{align} A \equiv \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & B_1 & 0 & 0\\ 0 & 0 & 0 & B_2 \end{bmatrix} \end{align} To separate inside-, border, and corner areas, one can mask the grid with zeros such a way, that only the required area have non-zero values. \begin{align} A_I := A \circ \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} Is the inside are \begin{align} A_R := A \circ \begin{bmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 \end{bmatrix} \end{align} is the border area \begin{align} A_C := A \circ \begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 \end{bmatrix} \end{align} is the corner area. The binary-operator $\circ$ is the Hadamard product, which multiplies two matrices together element-wise. Now use the convolution to calculate the state after the first step. $A_0 = A$ \begin{align} A_1 = I * A_I + R* A_R + C* A_C \end{align} After cutting out the edges this becomes \begin{align} A_1' = \begin{bmatrix} 0 & 1/4 & 0 & 0\\ 1/4 & 0 & 1/4 & 0\\ 0 & 1/4 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} From this we read that the probability to hit barrier $B_1 = (2,3)$ is $P_{11} = 1/4$ and to $B_2$ it is $P_{2,1} = 0$. To iterate this prosess, set the barrier to zero $a_{23}' = 0$, $a_{4,4}' = 0$ \begin{align} A_1'' := \begin{bmatrix} 0 & 1/4 & 0 & 0\\ 1/4 & 0 & 1/4 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align}

and repeat

\begin{align} A_2 = I * (A_1'')_I + R* (A_1'')_R + C* (A_1'')_C \end{align} Cut the edges to get \begin{align} A_2' = \begin{bmatrix} 2/12 & 0 & 2/12 & 0\\ 0 & 3/12 & 0 & 1/12\\ 1/12 & 0 & 1/12 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} Read the values from the barriers $P_{12} = 0$, and $P_{22} = 0$, set the values to zero, iterate. Eventually this process terminates, and results to sequences of probabilities for the barrier. \begin{align} P_{B_1} &= (P_{11}, P_{12}, P_{13},\dots)\\ P_{B_2} &= (P_{21}, P_{22}, P_{23}, \dots) \end{align}

The expectation value of the number of steps to hit $B_1$ is $$\mathbb{E}(n|B_1) = \sum_{n=1}^\infty n P_{1n}$$ Similar result holds for $B_2$

Note that the basic idea is simple, but the example was lengthy. Some efficient code could calculate this process quite fast for a reasonable sized grids. Also this method can be extended to a higher dimensions.

$\endgroup$

You must log in to answer this question.

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