Randomized algorithm

A computational procedure that uses random choices as part of its execution. Its output, running time, or both can vary across runs on the same input.

Monte Carlo algorithm: A randomized algorithm with bounded running time that may return an incorrect answer with limited probability. It trades a small chance of error for a predictable running-time bound.
Miller–Rabin primality test: A randomized test that identifies composite integers with a controllably small chance of error. It shows how repeated random tests can efficiently establish probable primality.
Expected value: The probability-weighted average of a random variable's possible values. Expected running time averages an algorithm's costs across its random choices.
Deterministic algorithm: An algorithm whose next step is fixed by its current state and input. Unlike randomized algorithms, it follows the same execution path for a given input.
Rabin–Miller primality test: A probabilistic primality-testing method developed independently by Michael Rabin and Gary Miller. Its practical efficiency helped establish randomized computation as a useful algorithmic method.
Las Vegas algorithm: A randomized algorithm that always returns a correct answer, while its running time may vary. It uses randomness to vary the cost, not the correctness of its answer.
Karger’s algorithm: A randomized contraction algorithm for finding a minimum cut in an undirected graph. Its chance of finding a minimum cut rises through repeated independent runs.
Tail bound: An inequality that limits the probability that a random variable deviates far from a central value. Tail bounds turn average-case guarantees into high-probability performance claims.
P (complexity class): The class of decision problems solvable by a deterministic algorithm in polynomial time. It is the deterministic counterpart to polynomial-time randomized computation.
Michael O. Rabin: An Israeli mathematician and computer scientist whose work includes probabilistic algorithms and automata theory. Rabin developed influential algorithms that made randomization central to computation.

Linked from 21 pages