Monte carlo methods vs Markov chains

http://blog.wolfram.com/2011/06/08/what-shall-we-do-with-the-drunken-sailor-make-him-walk-the-plank/

by mathola16 • 15 years ago

36 13 15 years ago

blog.wolfram.com

dvse• 15 years ago

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.

dodo53• 15 years ago

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

mrvc• 15 years ago

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.

wisty2• 15 years ago

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

evgen• 15 years ago

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

scythe2• 15 years ago

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

a1k0n• 15 years ago

You could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.

scythe2• 15 years ago

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

achompas2• 15 years ago

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.

wisty2• 15 years ago

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.

achompas2• 15 years ago

Thanks for the answer!

guan• 15 years ago

Markov chain Monte Carlo!

PaulHoule• 15 years ago

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

Monte carlo methods vs Markov chains

Related Stories