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 behaviour 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.
There are also a number of discrete problems for which only an exact result is acceptable (eg. sorting and searching) and where the introduction of randomness influences only on the ease and efficiency in finding the solution. For some problems where trivial exhaustive search is not feasible probabilistic algorithms can be applied giving a result that is correct with a probability less than one (eg. primality testing, string equality testing). The probability of failure can be made arbitrary small by repeated applications of the algorithm.
One incentive for using probabilistic algorithms is that their application does not normally require sophisticated mathematical knowledge. Further, the programming is often rather trivial which means that an acceptable approximation can be obtained quickly. One can say that the use of probabilistic algorithms sometimes allow that theoretical knowledge and analytical work is compensated for by making extensive simple machine computations. In some other cases the probabilistic algorithms are the simplest and even the most efficient available and for some problems no other feasible algorithm is known to exist (eg. primality testing).
Topics to be covered include: pseudo and quasi random numbers, calculation of integrals, optimization, simulation, and probabilistic algorithms for discrete problems.
Brassard, G. and P. Bratley: Algorithmics - Theory and Practice, Prentice-Hall, 1988. (Chapter 8)Harel, D.: Algorithmics - The Spirit of Computing, 2nd Edition, Addison-Wesley, 1992. (Chapter 11)
Knuth, D.E.: The Art of Computer Programming, Vol 2 Seminumerical Algorithms, Addison-Wesley, 1969. (Chapter 3)
Motwani, R. and P. Raghavan: Randomized Algorithms, Cambridge University Press, New York, 1995.
Törn, A.: Simulation Modelling, Reports on CS and Math., Ser. B, No 12, Åbo Akademi University, 1991.
Törn, A. and A. Zilinskas: Global Optimization, Lecture Notes in Computer Science 350, 1978.
Scientific Articles