Abstract

• A probabilistic algorithm is an algorithm where the result and/or the way the result is obtained depend on chance. These algorithms are also sometimes called randomized algorithms.

• In some applications the use of probabilistic algorithms is natural, e.g. simulating the behavior of some existing or planned system over time. In this case the result by nature is stochastic. In some cases the problem to be solved is deterministic but can be be transformed into a stochastic one and solved by applying a probabilistic algorithm (eg. numerical integration, optimization). For these numerical applications the result obtained is always approximate, but its expected precision improves as the time available to use the algorithm increases. The techniques of applying probabilistic algorithms to numerical problems were originally called Monte Carlo methods (Metropolis and Ulam, Los Alamos in 1940s).