Monte Carlo

The computational algorithms which rely on repeated random sampling to compute their results such algorithm are called as Monte-Carlo algorithms. 

OR

The random algorithm is Monte-carlo algorithms if it can give the wrong answer sometimes. 

Whenever the existing deterministic algorithm is fail or it is impossible to compute the solution for given problem then Monte-Carlo algorithms or methods are used. Monte-carlo methods are best repeated computation of the random numbers, and that’s why these algorithms are used for solving physical simulation system and mathematical system.

This Monte-carlo algorithms are specially useful for disordered materials, fluids, cellular structures. In case of mathematics these method are used to calculate the definite integrals, these integrals are provided with the complicated boundary conditions for multidimensional integrals. This method is successive one with consideration of risk analysis when compared to other methods.

There is no single Monte carlo methods other than the term describes a large and widely used class approaches and these approach use the following pattern.

1. Possible inputs of domain is defined.

2. By using a certain specified probability distribution generate the inputs randomly from the domain.

3. By using these inputs perform a deterministic computation. 
4.The final result can be computed by aggregating the results of the individual computation.

Produce correct or optimum result with some probability. These algorithms have deterministic running time and it is generally easier to find out worst case time complexity. For example this implementation of Karger’s Algorithm produces minimum cut with probability greater than or equal to 1/n² (n is number of vertices) and has worst case time complexity as O(E). Another example is Fermat Method for Primality Testing. Example to Understand Classification:

Consider a binary array where exactly half elements are 0
and half are 1. The task is to find index of any 1.  

A Las Vegas algorithm for this task is to keep picking a random element until we find a 1. A Monte Carlo algorithm for the same is to keep picking a random element until we either find 1 or we have tried maximum allowed times say k. The Las Vegas algorithm always finds an index of 1, but time complexity is determined as expect value. The expected number of trials before success is 2, therefore expected time complexity is O(1). The Monte Carlo Algorithm finds a 1 with probability [1 – (1/2)^k]. Time complexity of Monte Carlo is O(k) which is deterministic

Optimization of Monte-Carlo Algorithms:

• In general the Monte-carlo optimization techniques are dependent on the random walks. The program for Monte carlo algorithms move in multidimensional space around the generated marker or handle. It wanted to move to the lower function but sometimes moves against the gradient.
• In numerical optimization the numerical simulation is used which effective and efficient and popular application for the random numbers. The travelling salesman problem is an optimization problem which is one of the best examples of optimizations. 
• There are various optimization techniques available for Monte-carlo algorithms such as Evolution strategy, Genetic algorithms, parallel tempering etc.

We strongly recommend to refer below post as a prerequisite of this. Randomized Algorithms | Set 1 (Introduction and Analysis)