News for hackers. Stuff that matters.
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.
Re:Monte carlo methods vs Markov chains by a1k0n on Thursday June 09, 2011 @11:37AM (#2637488)
You could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.
Re:Monte carlo methods vs Markov chains by scythe on Thursday June 09, 2011 @12:31PM (#2637716)
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).