6
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Regarding your first paragraph, you are correct and it's fixed on the question now. $\endgroup$ – orlp Aug 13 at 10:14

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.