News for hackers. Stuff that matters.
Re:Monte carlo methods vs Markov chains by dodo53 on Thursday June 09, 2011 @07:19AM (#2636710)
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...
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).

Re:Monte carlo methods vs Markov chains by achompas on Thursday June 09, 2011 @09:37AM (#2637064)
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.
Re:Monte carlo methods vs Markov chains by wisty on Thursday June 09, 2011 @10:39AM (#2637274)
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.

Re:Monte carlo methods vs Markov chains by achompas on Thursday June 09, 2011 @11:10AM (#2637376)
Thanks for the answer!
Re:Monte carlo methods vs Markov chains by dvse on Thursday June 09, 2011 @07:19AM (#2636709)
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.
Re:Monte carlo methods vs Markov chains by PaulHoule on Thursday June 09, 2011 @11:38AM (#2637496)
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

Re:Monte carlo methods vs Markov chains by guan on Thursday June 09, 2011 @11:13AM (#2637391)
Markov chain Monte Carlo!
Re:Monte carlo methods vs Markov chains by mrvc on Thursday June 09, 2011 @07:57AM (#2636797)
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.
Re:Monte carlo methods vs Markov chains by wisty on Thursday June 09, 2011 @11:30AM (#2637452)
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".
Re:Monte carlo methods vs Markov chains by evgen on Thursday June 09, 2011 @12:15PM (#2637659)
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...