News for hackers. Stuff that matters.
Re:A ride that takes 10^20k years to complete in Roller Coas... by hervature on Tuesday August 04, 2020 @02:52AM (#24047380)
I came here to see someone actually solve this rather than say "it's a Markov process, it has a solution". Here is my progress towards something:

First, using Taek's notation for the maze with the correction that entering and leaving an indent results in 2 steps rather than 1. The resulting set of equations are:

X_{0,f} = X_{1,f} + 2.5

X_{0,b} = X_{1,f} + 3

X_{k,f} = 0.625 X_{k+1,f} + 0.375 X_{k-1,b} + 2.5

X_{k,b} = 0.875X_{k-1,b} + 0.125 X_{k+1,f} + 1.5

X_{n,f} = 0.375 X_{n-1,b} + 2.5

Where the first index is the index of the current indent. Thus, n must be at least 1 but the first indent occurs at entry 0. The second index is the direction the maze goer is traveling in.

From here, we can easily get the growth rate of 1.4 which is 0.875/0.625 or more intuitively the ratio of momentum pushing you backwards vs. pushing you forwards. This is the root of the exponential growth.

Finally, I believe there is no "closed form" solution but this will be the solution of the linear system X = AX+b for the A and b shown above. I am able to convince myself that there is no nice solution because having the two dimensions (position and direction of travel) makes it impossible to rearrange the above equations and make a clever change of variable to make the telescoping sum look nice. To see this, realize that each term relies on 2 things and one those things doesn't rely on the first term.

Finally, here is some Python code that implements this:

"""

import numpy as np

n = 25

A = np.zeros((2n+1, 2n+1)) b = np.zeros((2n+1, 1))

# Setup A: the first n+1 entries will be the forward index and the last n entries will be the backwards movement

b_shift = n+1

## X_0

A[0,1] = 1 A[b_shift,1] = 1

## X_k

for k in range(1,n):

    # foward movement

    A[k,k+1] = 0.625
    A[k,k-1+b_shift] = 0.375

    # backward movement

    A[k+b_shift,k+1] = 0.125
    A[k+b_shift,k-1+b_shift] = 0.875
    
## X_n

A[n,n-1+b_shift] = 0.375

# Setup b

## X_0

b[0,0] = 2.5 b[b_shift,0] = 3

## X_k

for k in range(1,n): b[k,0] = 2.5 b[k+b_shift,0] = 1.5

## X_n

b[n,0] = 2.5

X = np.linalg.inv(np.identity(2n+1)-A) @ b

print(f"The number of steps from the beginning is for {n} cutouts: {X[0,0]}")

"""

There are no comments on this comment yet.