3 ms·
Let's pose the problem mathematically. Initial state is (0, forwards). State (0, *) transitions to (1, forwards) For k > 1, state (k, forwards) transitions to
by im3w1l 6y ago
Let's pose the problem mathematically. Initial state is (0, forwards).
State (0, *) transitions to (1, forwards)
For k > 1, state (k, forwards) transitions to (k+1, forwards) with 5/8 probability and to (k-1, backwards) with probability 3/8.
For k > 1, state (k, backwards) transitions to (k+1, forwards) with 1/8 probability and to (k-1, backwards) with probability 7/8.
My intuition is that this very much resembles a biased walk so it should take exponential time. But there is the "momentum" to take into account.
Edit: It looks like we can use https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expected_number_of_steps https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...
- gbrown 6y agoCame here for this - I knew there must be an analytical solution involving Markov chains.
- tetha 6y agoI'm pretty sure this can be modeled with markov chains. Your vertices would be (x, y, f), f being facing. Edges are along the lines of (x, y, 0) - (x+1, y, {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y, 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1, {0,1,2,3}\2). Probabilities are modeled in the video and need to be rotated 4 times for the four facings. After that, I just don't recall my eigenvector calculation anymore. It feels like a good markov exercise, though.