a Monte Carlo algorithm

Imagine a quick health screening that finishes in exactly five minutes every time, but occasionally gives a wrong reading. You like that it is always fast, and you live with the small chance of error — and you can repeat it to shrink that chance. A Monte Carlo algorithm trades the other way from Las Vegas: it commits to a fixed (often very fast) running time, but its answer is only probably right.

Precisely: a Monte Carlo algorithm uses randomness, runs within a fixed time bound, and returns an answer that is correct with at least some probability p; with probability 1 - p it may be wrong. A beautiful pattern is the one-sided test, where a 'yes' is always trustworthy but a 'no' might be a false negative (or vice versa). Freivalds' check for whether A times B equals C is like this: it picks a random vector r and tests whether A(Br) equals Cr; if the matrices are equal it always says equal, and if they differ it catches the difference with probability at least one-half. The key move is amplification: run k independent trials and combine them. With a one-sided test, a single 'caught it' on any trial settles the matter, so k runs drive the error down to at most (1/2)^k — ten runs already give error under one in a thousand.

Monte Carlo is the right model when speed and a firm time bound matter more than certainty, and when you can tolerate (and bound) a small error — primality testing (Miller-Rabin), equality checks via fingerprints, Karger's min-cut. The honest caveat: 'probably correct' is not 'correct.' You must state the error probability and, for two-sided error, remember that repetition needs a majority vote rather than a single lucky hit. Independence of the trials is essential; reusing the same random bits does not reduce error.