Re:Monte carlo methods vs Markov chains
by scythe on Thursday June 09, 2011 @08:51AM
(#2636925)
You could also solve it analytically by diagonalizing and setting all of the eigenvalues less than the maximum eigenvalue to zero.
[ Parent
| on HN ]
You could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.
Well, since you can walk back and forth across rows, you'll have to compute all of the probabilities for a given row at once by solving the resulting system of equations. This is generally quite simple.
For example, take a four-column, one-row version, with probability-of-falling like so:
* 0 0 0 0 *
1 x y y x 1
We have:x = 0 / 4 + 1 / 4 + y / 4 + x / 4
y = 0 / 4 + x / 4 + y / 4 + y / 4
giving the solutions x = 2/5 and y = 1/5. It is easier, of course, if you exploit the symmetry of the situation, as here (by writing x y y x instead of x y z w).