News for hackers. Stuff that matters.
Re:A ride that takes 10^20k years to complete in Roller Coas... by mgraczyk on Monday August 03, 2020 @11:54PM (#24046394)
The way to get a closed form solution for the expected time is to note that there are 2N + 1 states. N states for each notch and each direction, and one "final" absorbing state for the end of the maze. You can write a matrix A where the transition probability between states i and j is given by Aij. Then A^n gives the distribution over states after n steps.

It's been a while since I've done this, but I think the solution is something like the last index in the vector

   E[steps] = (I - A)^-1 * (1, 1, 1, 1 ...)
I-A is called the "fundamental matrix" of the markov chain described by Aij.

EDIT I wrote some numpy to verify that this solution matches the empirical growth rate of 1.4 found in the video: https://gist.github.com/mgraczyk/7917a3322f65fe60fa333da7936...

Re:A ride that takes 10^20k years to complete in Roller Coas... by dragontamer on Tuesday August 04, 2020 @08:01AM (#24049070)
> Then A^n gives the distribution over states after n steps.

Because its an A^n kind of problem, is this a good time to use Eigenvectors?

I'm kinda bad with my Linear Algebra. Just kinda checking myself if I'm following the concept.

Re:A ride that takes 10^20k years to complete in Roller Coas... by mgraczyk on Tuesday August 04, 2020 @01:03PM (#24052020)
A^n can be computed many ways, and it is not necessary to actually do any matrix multiplications. I think what you're referring to is diagonalizing the matrix A=PDP^1, then computing the matrix power of the diagonal matrix A^n = (PDP^-1)^n = P D^n P^-1.

I just let numpy figure it out for me, but if you want an analytical solution something like that may be necessary.