Home

  • Monte Carlo Method

    #1

  • Prerequisites to Monte Carlo Method (MCm)

    #2
    • Randomness (#3)
    • Law of Large Numbers (#4)
    • Probability Distribution (function) (#5)
    • Deterministic Computation (function) (#6)
    • Markov Chain (#7)

  • Randomness

    #3

    In Computer Science or related computational fields, there is no true randomness but pseudo-randomness. It is useful to have pseudo-random number generator as it would help to re-run the same set of experiments with same set of "random numbers". This is achieved by giving a "seed" to these random number generators.

  • Law of Large Numbers

    #4

    Running a single experiment multiple times and averaging the results is more likely to give us the accurate result.

    ie., The probability or accuracy will increase with the greater number of experiment runs.

  • Probability Distribution (function)

    #5

    For a defined domain (state space) of values, each value has equal likelihood of being picked.

  • Deterministic Computation (function)

    #6

    Computation/Function that will return same output for same input.

    Note: Same as a Pure Function in FP

  • Markov Chain

    #7

    A system is defined as a set of states.

    For Markov Chains, the system transitions from one state to another. The system/transition satisfies Markov Property

    Markov Property implies that the transition to next state does not depend on previous state but only current state. That is, it is said to be "Memoryless".

  • #8

    Goal of Monte Carlo Method/Experiments (MCm) is to run an experiment multiple times for a random set of inputs and to average out the results to find the most likely result we can expect in real life.

    This can be done an actual experiment or a simulation.

  • Pattern of Monte Carlo Methods

    #9

    Taken from wiki

    1. Define a domain of possible inputs
    2. Use Probability Distribution over the domain to select random inputs.
    3. Perform deterministic computations*
    4. Aggregate the results.

    * - ie., model the system/process as a pure function and evaluate using random inputs.

  • Programmatic explanation of the pattern

    #10
    1. Inputs = Ip :: List[value]
    2. Probability Distribution = pd :: Ip => value
    3. Deterministic Computation = fn :: value => result
    4. Aggregate the results = n iterations of fn(pd)

  • #11 Question

    How is MCm different from Law of Large Numbers (LoLN)?

  • #12

    MCm is not a single algorithm but a set of algorithms.

  • #13

    Prior to MCm, simulations would perform many (all?) deterministic computations and a random sample of results was used to determine the reliability of the simulations.

  • #14

    MCm inverts this. It starts with a random sample of inputs and then averages all the outputs of the deterministic computation to reduce error in the final result.

  • #15 Question

    What is a Markov Chain Monte Carlo Method? (MCMC)

  • Sawilowsky's definitions

    #16 Interesting

    Simulation: Simulation is an abstract/mathematical representation of a system (reality) Monte Carlo Method: Technique used to solve a mathematical/statistical problem Monte Carlo Simulation: Use Monte Carlo method with multiple sample of inputs to get a statistical/data driven model of an abstract system.

  • #17 Answer to: How is MCm different from Law of Large Numbers (Lo (#10)

    LoLN is a statistical method of computing values.

    MCm(sim) relies upon the principle of LoLN to guarantee that the final result it computes is the most likely result if the system plays out across the whole domain/state space.

  • #18 Answer to: What is a Markov Chain Monte Carlo Method? (MCMC) (#14)

    Markov Chain Monte Carlo method uses a set of inputs generated from a markov chain that represents the likely set of states.