converting between Las Vegas and Monte Carlo algorithms
Picture two settings on the same machine. One setting always gives the right answer but takes an unpredictable amount of time; the other always finishes on a timer but might be wrong. It turns out you can often switch between these settings, trading a guarantee on time for a guarantee on correctness or back again. That switching is the conversion between Las Vegas and Monte Carlo.
Las Vegas to Monte Carlo is the easy direction: take an always-correct, variable-time algorithm and simply cut it off after a chosen time budget T. If it has finished, return its (correct) answer; if not, return a default guess or report failure. By Markov's inequality, if the expected time is mu, the chance of running past T = 2 mu is at most one-half, so you get a fast, fixed-time algorithm whose error probability you control by how generous T is — pure Monte Carlo. Monte Carlo to Las Vegas is possible when you can verify a candidate answer quickly: run the Monte Carlo algorithm, check whether its output is actually correct, and if not, run it again with fresh randomness; repeat until the check passes. Since each attempt succeeds with probability p, the expected number of attempts is 1/p, and every returned answer is verified — pure Las Vegas. For example, Karger's min-cut is Monte Carlo, but if you had a fast way to confirm a cut is minimum you could rerun until confirmed.
The lesson is a clean duality: a hard time bound and a hard correctness guarantee are two faces of the same randomized coin, and randomness lets you spend one to buy the other. The catch in the Monte Carlo to Las Vegas direction is real: it needs an efficient verifier for the answer, which does not always exist (you can check a sorted array instantly, but checking that a number is the true median, or that a cut is globally minimum, may be as hard as solving the problem). When no fast check exists, you are stuck with Monte Carlo's residual error.
Randomized quickselect (Las Vegas, finds the median, variable time) becomes Monte Carlo by stopping after, say, 4n comparisons and outputting whatever pivot region remains — usually right, occasionally not. Going the other way, a Monte Carlo 'guess the median' becomes Las Vegas only if you can verify a guess is the median quickly, which itself takes about as much work as finding it.
Cutting off time is always easy; buying back certainty needs a fast verifier.
The two directions are not symmetric. Las Vegas to Monte Carlo only needs a stopwatch and Markov's inequality; Monte Carlo to Las Vegas needs an efficient correctness check, and for many problems no such check is known.