Re:A ride that takes 10^20k years to complete in Roller Coas...
by nightcracker on Monday August 03, 2020 @08:04PM
(#24045006)
A precise analysis of how many steps it takes to solve this maze. I am assuming that each step takes exactly as long as any other, and that the character instantaneously turns at the start of its step. Analyzing the video this seems about right.
For each 'dead end unit' there are four states the character can be in after having just taken a step, s = {forward, backward, inside, facewall}. Let us look at the Markov chain transition probabilities if we are in state (n,s).
- (n,forward) has a 3/4 chance of going to (n,inside) and 1/4 chance of going to (n+1,forward).
- (n,backward) has a 1/4 chance of going to (n,inside) and a 3/4 chance of going to (n-1,backward).
- (n,inside) has a 100% chance to go to (n,facewall).
- (n,facewall) has a 50/50 chance of going to (n+1,forward) and (n-1,backward).
Assuming that big N indicates how many 'dead end units' we have, there are two exceptions:
- (0,s) always goes to (1,forward) for any s.
- (N+1,forward) always goes to itself, it is an absorbing state.
If we build up the transition matrix of the above, ensuring that any absorbing state is
at the end (we only have one absorbing state), we can take matrix Q as the rows/columns
that don't interact with the absorbing state. Then the sum of the first row of (I - Q)^(-1)
gives us our mean absorption times.
This makes me conjecture that modulo small effects at the start/end (and I've completely ignored the long middle piece), we have that the number of steps taken to solve a N 'dead end unit' maze is Ө(1.4^N). I've asked a question on the math stackexchange to see if someone can prove it formally: https://math.stackexchange.com/questions/3779234/mean-first-....
For each 'dead end unit' there are four states the character can be in after having just taken a step, s = {forward, backward, inside, facewall}. Let us look at the Markov chain transition probabilities if we are in state (n,s).
Assuming that big N indicates how many 'dead end units' we have, there are two exceptions: Without going into details too much, we can now apply some results from Markov chain theory (see here for more: https://www.dartmouth.edu/~chance/teaching_aids/books_articl...).If we build up the transition matrix of the above, ensuring that any absorbing state is at the end (we only have one absorbing state), we can take matrix Q as the rows/columns that don't interact with the absorbing state. Then the sum of the first row of (I - Q)^(-1) gives us our mean absorption times.
The code: https://gist.github.com/orlp/0c5fc7264f02e3d211d42da643163bb...
The results (in format N, expected time to solve, ratio with last):
This makes me conjecture that modulo small effects at the start/end (and I've completely ignored the long middle piece), we have that the number of steps taken to solve a N 'dead end unit' maze is Ө(1.4^N). I've asked a question on the math stackexchange to see if someone can prove it formally: https://math.stackexchange.com/questions/3779234/mean-first-....