Entrepreneurials‎ > ‎Jobs‎ > ‎Interview‎ > ‎Random Algorithm‎ > ‎

Monte-Carlo


Steps:
1. Define a domain of inputs
2. Generate inputs randomly
3. Perform a deterministic computation for each input
4.Aggregate the results of the individual computations into the final result

For example to estimate value of PI:
  1. Draw a square on the ground, then inscribe a circle within it. From plane geometry, the ratio of the area of an inscribed circle to that of the surrounding square is π / 4.
  2. Uniformly scatter some objects of uniform size throughout the square. For example, grains of rice or sand.
  3. Since the two areas are in the ratio π / 4, the objects should fall in the areas in approximately the same ratio. Thus, counting the number of objects in the circle and dividing by the total number of objects in the square will yield an approximation for π / 4.
  4. Multiplying the result by 4 will then yield an approximation for π itself.


Example Monte-Carlo in games:
One of the main problems that this approach has in game playing is that it sometimes misses an isolated, very good move. These approaches are often strong strategically but weak tactically, as tactical decisions tend to rely on a small number of crucial moves which are easily missed by the randomly searching Monte Carlo algorithm.

In case of What-if
input variable are manually chosen (such as best case, worst case, and most likely case), and the results recorded for each so-called “what if” scenario.
a comparison of a spreadsheet cost construction model run using traditional “what if” scenarios, and then run again with Monte Carlo simulation and Triangular probability distributions shows that the Monte Carlo analysis has a narrower range than the “what if” analysis. This is because the “what if” analysis gives equal weight to all scenarios.

Example:
Monte Carlo integration
Just like the way it calculated the value of PI above, it puts a bounding box around the function and the ratio of the numbers in the box within the function vs the total points will be the estimate of the integration.
Function approximation
Optimization (e.g. minima of a function)
Bayes net inference???
SLAM (Simultaneous localization and mapping)
Image segmentation
Radar return tracking














Comments