8 ms·
Monte carlo methods vs Markov chains
- dvse 15y agoWith 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 15y agoOr 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/Lecture14.pdf http://www.math.dartmouth.edu/archive/m20x06/public_html/Lec...
- mrvc 15y agoHaving 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.
- wisty 15y agoIn 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 15y agoIn 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...
- scythe 15y agoYou could also solve it analytically by diagonalizing and setting all of the eigenvalues less than the maximum eigenvalue to zero.
- a1k0n 15y agoYou could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.
- scythe 15y agoWell, 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).
- achompas 15y agoHow 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.
- wisty 15y agoIf 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.
- achompas 15y agoThanks for the answer!
- guan 15y agoMarkov chain Monte Carlo!
- PaulHoule 15y agohere'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 http://scratch.mit.edu/projects/electric_mouse/1002199