Insight 7 -- Montecarlo techniques

-
Monte Carlo Methods


Monte Carlo methods (aka experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. Their essential idea is using randomness to solve problems that might be deterministic in principle. Monte Carlo methods are typically used to solve problems which belongs to the following 'classes':

  • optimisation;
  • numerical integration;
  • generating draws from probability distribution.
In principle, Monte Carlo methods can be used to solve any problem having a probabilistic interpretation. In fact, since there is no known consensus on how Monte Carlo should be defined, we can say that a Monte Carlo method is just a technique to solve a mathematical/statistical problem whereas a Monte Carlo simulation is the actual Monte Carlo simulation/experiment (e.g. repeatedly sample from a specific population in order to compute the empirical mean and/or other statistics in interest). To put it simpler, pouring out a box of coins and then computing the ratio of coins that land heads versus tails is a Monte Carlo method of determining the behaviour of repeated coin tosses (this is not a Monte Carlo simulation). On the other hand, a Monte Carlo simulation example may be: drawing a large number of pseudo-random uniform variables from the interval [0, 1] at one time, or once at a large number of different times, and assigning values less than or equal to 0.5 as heads and greater than 0.5 as tails.

However, there's no formal standard definition of the Monte Carlo methods nor to describe the difference between a technique and a simulation. As pointed out by Kalos and Whitlock in 2008, the differences between a method and a simulation are not always easy to maintain. For instance, there exist situations for which both can be applied (i.e. is possible to simulate the experiment directly or, for example, by taking several different random samples). 


Random Numbers & Statistical Tests

The main idea behind the Monte Carlo simulation is that the results are computed based on repeated random sampling and statistical analysis. In order to be useful, the required random numbers don't need to be always truly random, although their unpredictability is vital for problem classes such as cryptographic applications and primality tests. The most used techniques to compute those random numbers are deterministic and thus outputs pseudorandom numbers which compared to truly random numbers may be efficiently reproduced.

The only requirements on the pseudorandom sequence of numbers is that they're random enough.
In other words, this means that they should pass a series of statical tests which serve as a measure to test how uniformly distributed the generated numbers are. In 2003, a professor of the Wayne State University published a list of the characteristics of a high quality Monte Carlo simulation:

  • the PRNG has certain characteristics (e.g. a long "period" before the sequence repeated)
  • the PRNG outputs values that pass tests for randomness
  • there are enough samples to ensure accurate results
  • samples are taken using the proper sampling technique and the used algorithm is valid for what is being modelled


Commenti

Posta un commento

Post popolari in questo blog

Welford Algorithm

-
Immagine
The variance is the expectation of the squared deviation of a random variable form its mean.  Informally, it measures how far a set of (random) numbers are spread out from their average value. The variance is the square of the standard deviation, the second central moment of a distribution and the covariance of the random variable with itself, and it is often represented by Var(X), σ 2 , s 2 . One of the most widely known formula for computing the variance is: where x-bar is the mean of the sample. The definition given above can be converted into an algorithm that computed the variance and the standard deviation in two passes: 1. Compute the mean                            (O(n)) 2. Compute the square differences       (O(n)) Output the variance Even though this algorithm seems working properly, it may become too expensive on some input instances. Just consider a sampling procedu...
Continua a leggere

Research 6 - Derivation of Chebyshev's inequality and its application to prove the (weak) LLN

-
Immagine
Chebyshev's Inequality In probability theory, the Chebyshev's inequality guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more distant than a certain value from the mean. In particular, the mentioned inequality states that no more than 1/k 2 of the distribution's values can be more than k standard deviations away from the mean. In other words, this mean that at least (1 - 1/k 2 ) of the distribution's values are within k standard deviations of the mean. The Chebyshev's inequality can be easily derived from the Markov's inequality, where the latter defines an upper bound for the probability that a non-negative random variable is greater than (or equal to) some positive integer constant. Remember the Markov's inequality where   a  > 0 and  X  is a nonnegative random variable The Chebyshev inequality follows by considering the random variable ( X - E ( X )) 2  and the constant a 2...
Continua a leggere

Research 7 -- Central Limit Theorem, LLN, and most common probability distributions

-
Immagine
Law of Large Numbers and CLT Intuitively, everyone can be convinced of the fact that the average of many measurements of the same unknown quantity tends to give a better estimate than a single measurement. The law of the large numbers (LLN) and the central limit theorem (CLT) formalise this general ideas through mathematics and random variables. Suppose X 1 , X 2 , ..., X n are independent random variables with the same underlying distribution. In this case, we say that the X i are independent and identically-distributed (or, i.i.d.). In particular, the X i have all the same mean μ and standard deviation σ. The average of the i.i.d. variables is defined as: The central limit theorem states that when an infinite number of successive random samples are taken from a population, the sampling distribution of the means of those samples will become approximately normally distributed with mean μ and standard deviation σ/ √N as the sample size becomes larger, irrespective of the sh...
Continua a leggere