Monte carlo methods vs Markov chains | Hacker News Reader

Monte carlo methods vs Markov chains

blog.wolfram.com

36 pointsmathola1613 comments

Or presumably you could go one further and solve for the fundamental matrix which gives total probabilities (given unlimited steps) of ending at either end of the plank ('absorbing' states which you don't come back from). see: http://www.math.dartmouth.edu/archive/m20x06/public_html/Lec...

You could also solve it analytically by diagonalizing and setting all of the eigenvalues less than the maximum eigenvalue to zero.

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).

How random is RandomChoice[]? For everyday applications I figure it wouldn't matter, but when taking ~160,000 steps (as with MC methods) we could possibly observe a non-uniform pdf for the sailor's steps.

If it's something like the Mersenne Twister (in Python) then very very random. The period is something like 2^19937-1, and it passes a lot of tests to see whether or not it looks random.

Of course, in a big random system there are some states that simply won't be reached by any random number generator with a finite period. Once you start looking at combinations and permutations, you can a get staggeringly large number of states. But in practice, this shouldn't matter for any problem where Monte Carlo methods make sense - if your answer is very sensitive to whether or not you have sampled a state that only crops up one in a squillion times, you shouldn't use Monte Carlo.

Thanks for the answer!

With a fair bit of hand waving it's also possible to present the law of large numbers and the central limit theorem in the same way. Can also look at Metropolis-Hastings as modifying a suitable random walk to get the steady state that we want.

here's a nicer 2d drunkard's walk simulation that i put together in scratch in a few minutes...

http://scratch.mit.edu/projects/electric_mouse/1002199

Markov chain Monte Carlo!

Having worked with them for a few years now, can I just say I hate the term Monte Carlo Method. Although I can understand that calling them "random number simulations" is not nearly as cool.

In Australia, Monte Carlo is a kind of biscuit. If you tell most people you do Monte Carlo simulations, they will think you design biscuits. Which actually sounds cooler than "insurance", "safety systems", or "math".

In the US a biscuit is a "cookie" and if you tell people that you do Monte Carlo simulations but not the kind related to biscuits they will smile politely and slowly back away from you...

Reply on news.ycombinator.com