Can we algorithmically find expected hitting time for 2D random walk without simulating/approximating?

Question

Suppose we're given some absorbing boundary that encloses the origin/starting position, and we take a simple random walk (up/down/left/right with equal probability). For simplicity's sake say we have access to a function which tells us for (x,y) whether it's crossed the barrier

I know simulating this is straightforward, and calculating the expected time until hitting is pretty easy to numerically approximate - but is there a neat algorithmic way to get the exact answer?

I've tried to get something working with DP/DFS but the lack of base-case in the recursion seems to be stumping me. Not sure if there's a way to do this besides simulation/maybe some more in-depth math

Answer 1

Number the states inside the barrier, form the matrix A of transition probabilities (A[i,j] is the probability of going from state j to state i), solve the matrix equation A x + 1 = x for x (where 1 is the all-ones vector, equivalent to (A − I) x = 1 where I is the identity matrix). The element x[i] gives the expected time to absorption starting at i.