Mean first hitting time of infinite Markov chain in the limit

Question

For (strictly optional) context, this video shows the source of the problem: calculating the expected time it takes for a NPC to walk through a very specific RollerCoaster Tycoon 2 maze.

Suppose we have an infinite Markov chain with the following structure:

\begin{align} P((0,n) &\to (1,0)) &=& &1\\\\ P((n,0) &\to (n+1,0)) &=& &1/4 \\ P((n,0) &\to (n,2)) &=& &3/4 \\ P((n,1) &\to (n-1,1)) &=& &3/4 \\ P((n,1) &\to (n,2)) &=& &1/4 \\ P((n,2) &\to (n,3)) &=& &1 \\ P((n,3) &\to (n+1,0)) &=& &1/2 \\ P((n,3) &\to (n-1,1)) &=& &1/2 \\ \end{align}

Based on explicit calculations I conjecture that as $n \to \infty$ the mean first hitting time of state $(n, 0)$ grows as $\Theta((7/5)^n)$. In fact, already for $n = 60/59$ we find a ratio of $\approx 1.400000010$.

Can we prove this?

Answer 1

I think the final transition should be $P((n, 3)\rightarrow (n-1,1))$, per the video, as you'll be facing the entrance of the maze again if you go in that direction (you also coded it this way in your gist).

The solution to this problem, in a sense, doesn't amount to anything other than the approach you described, which is that the system $(I-P)\mathbf{x}=\mathbf{1}$ characterizes the absorption times for the provided chain. In effect, we'd like to solve the system of equations specified above, but parameterized by $n$, where we inductively construct the chain as described.

I solve this in detail by hand by leveraging sympy to avoid some mechanical calculation (it doesn’t do anything magical); as a result, a jupyter notebook best describes the derivation, which I've linked here in part 1 and part 2. For this problem, it was convenient to simplify the problem space into a chain on $2n$ states ($k$-th tile looking forward and $k$-th tile looking backward) with weighted transitions.

Regardless, the general approach here is as follows:

1. Define the expected time-to-finish (from an RL perspective, cost-to-go comes to mind), assuming we start at state $S$ as $T(S)$.
2. Do one "Bellman expansion" of the value function $T(S)$. For every neighbor of $S$, $\mathcal{N}(S)$, this gives us a linear equation $T(S)=\sum_{N\in\mathcal{N}(S)}P(S\rightarrow N)\left(T(S\rightarrow N)+T(N)\right)$, where $T(S\rightarrow N)$ is the cost of doing a transition from $S$ to $N$ (in the base chain it's always $1$, but in the simplified one the weights differ).
3. For finite chains without structure, this gives us the the matrix formula you used in your code. However, in our case, we have a Markov chain that itself is inductively built by linking blocks in a topological chain. As long as each block (i.e., all four states $(k, \cdot)$) is transient, we'll be able to build up a set of transition equations linking $T(\mathbf{S})$ where $\mathbf{S}$ is the vector of states $S\in (k+1,\cdot)$ to $T(\mathbf{S'})$ for $S'\in (k,\cdot)$. This vector recurrence $T(\mathbf{S})=\mathcal{T}T(\mathbf{S}')$ can now be expanded analytically since the matrix $\mathcal{T}$ can be exponentiated analytically.

My constants differ a bit than the comment on your question, probably due to slightly different problem setup, but in any case this approach gets us to $\Theta\left(\left(\frac{7}{5}\right)^n\right)$.

Again, details (down to the code level!) in the links I mentioned above.