15 Randomized Algorithms, Monte Carlo vs Las Vegas, Reducing Error Probability

Lecture from: 08.04.2025 | Video: Homelab

Let’s continue our discussion on randomized algorithms, focusing on how we define and analyze them, especially the common types: Las Vegas and Monte Carlo algorithms. We’ll also see how to improve their reliability by repetition.

Classical vs. Randomized Algorithms

Classical (Deterministic) Algorithms

Think of a standard algorithm you’ve learned, like MergeSort or Dijkstra’s.

• Input: It takes an input $\mathcal{I}$.
• Process: It performs a fixed sequence of operations based on $\mathcal{I}$.
• Output: It produces an output $\mathcal{A}(\mathcal{I})$.

Key characteristics of a classical algorithm:

• Correctness: The output $\mathcal{A}(\mathcal{I})$ is always precise and correct for a given input $\mathcal{I}$.
• Consistency: For the same input $\mathcal{I}$, the output $\mathcal{A}(\mathcal{I})$ is always the same. (The algorithm $\mathcal{A}$ behaves like a mathematical function.)
• Deterministic Runtime: For the same input $\mathcal{I}$, the runtime of algorithm $\mathcal{A}$ is always the same.
• Reproducibility: The behavior of the algorithm is entirely reproducible. Give it the same input, and you get the same steps, same output, same runtime.

Randomized Algorithms

Randomized algorithms introduce an element of chance into the process.

• Input: They take an input $\mathcal{I}$.
• Random Source: They also have access to a source of randomness, let’s call it $\mathcal{R}$. This could be a sequence of random bits, random numbers drawn from a distribution, etc.
• Process: The algorithm’s operations can depend on both $\mathcal{I}$ and the random values from $\mathcal{R}$.
• Output: The output is $\mathcal{A}(\mathcal{I},\mathcal{R})$.

Consequences of using randomness:

• The output now depends on both the input $\mathcal{I}$ and the specific random choices $\mathcal{R}$ made during execution.
• This means the output might be:
  • Sometimes correct.
  • Sometimes almost correct (e.g., a close approximation).
  • Sometimes fast (the runtime itself can be a random variable).
• Non-Reproducibility: Generally, if you run the algorithm twice with the same input $\mathcal{I}$ but with different random choices from $\mathcal{R}$ (which is typical unless you fix the random seed), you might get different outputs or different runtimes. However, the algorithm $\mathcal{A}$ is still a deterministic function if you consider the pair $(\mathcal{I},\mathcal{R})$ as its combined input.

The Random Source

Where does this randomness $\mathcal{R}$ come from?

• The random source provides random, independent bits or numbers, drawn according to some specified (often uniform) distribution.

Possible sources:

• Physical Random Number Generators: These leverage inherently random physical processes.

  • Examples: Lotto numbers, Geiger counters (radioactive decay), thermal noise in circuits, quantum phenomena. These are good sources of “true” randomness but can be slow or impractical for direct use in algorithms.

• Deterministic (Pseudo-)Random Number Generators (PRNGs): These are algorithms that produce a sequence of numbers that “look” random and pass many statistical tests for randomness, but are actually generated deterministically from an initial seed value.

  • Given a seed $s$, a PRNG produces a sequence $r_0(s),r_1(s),r_2(s),\dots$.
  • Advantage: If you know the seed, you can reproduce the exact same sequence of “random” numbers. This is invaluable for debugging randomized algorithms.
  • Caveat: PRNGs are not truly random. A sophisticated adversary who knows the PRNG algorithm and can observe enough output might predict future “random” numbers. The quality of PRNGs varies widely.

Our Assumption in Analysis

For theoretical analysis, we typically assume access to an ideal random source that provides perfectly random, independent bits/numbers as needed.

In practice, we use high-quality PRNGs. The potential discrepancy between theory (ideal randomness) and practice (pseudo-randomness) is something to be aware of, though often PRNGs are good enough for most applications.

Monte Carlo vs. Las Vegas Algorithms

Randomized algorithms are broadly categorized based on how randomness affects their correctness and runtime. The two main types are named after famous gambling locations: Monte Carlo and Las Vegas.

Monte Carlo Algorithms

• Correctness/Quality: The correctness or quality of the output is a random variable. The algorithm might produce an incorrect answer or an answer of varying quality with some probability.

• Runtime: Typically, the runtime of a Monte Carlo algorithm is not dependent on the random choices (or is bounded deterministically). It usually runs for a predetermined number of steps.

• Goal:

  • Always (or predictably) fast.
  • Mostly correct or provides a good quality answer with high probability.

Las Vegas Algorithms

• Runtime: The runtime is a random variable. It might finish quickly on some random choices, and slowly on others.

• Correctness/Quality: The correctness or quality of the output is not dependent on the random choices. If the algorithm produces an answer, that answer is guaranteed to be correct.

• Goal:

  • Always correct/good (when an answer is given).
  • Mostly fast (i.e., the expected runtime is good, or it finishes quickly with high probability).

Alternative View of Las Vegas Algorithms

Sometimes, a Las Vegas algorithm is designed such that it might explicitly output ”???” (or “I don’t know”) instead of a correct answer if it gets “unlucky” with its random choices within a certain time bound. The guarantee is that if it does give an answer other than ”???”, that answer is correct.

This leads to two common operational modes for Las Vegas algorithms:

1. Repeat until an answer: If the algorithm can output ”???”, you simply run it repeatedly until it gives a definite (and thus correct) answer. The analysis then focuses on the expected number of repetitions.
2. Abort after fixed time: Run the algorithm for a predetermined maximum time. If it produces an answer within this time, great. If not, it aborts and outputs ”???“.

A Las Vegas algorithm whose runtime is a random variable can be converted into one that sometimes outputs ’???’ by imposing a runtime cutoff (e.g., based on Markov’s inequality applied to its runtime).

Reducing Error Probability

One of the powerful features of randomized algorithms is that we can often decrease the probability of an undesirable outcome (like getting no answer, or getting a wrong answer) by simply running the algorithm multiple times.

Reducing “Failure to Answer” for Las Vegas Algorithms

Recall that a Las Vegas algorithm is always correct if it provides an answer, but it might sometimes fail to do so, perhaps by outputting a special symbol like ”???” or by exceeding a time limit.

Goal

Suppose we have a Las Vegas algorithm $\mathcal{A}$. For any input $\mathcal{I}$, it gives a correct answer with a probability of at least $\epsilon$. This means the probability of it outputting ”???” is at most $1-\epsilon$. Our goal is to construct a new algorithm, ${\mathcal{A}}_{\delta }$, that gives a correct answer with an even higher probability, specifically at least $1-\delta$, where $\delta$ is some small target failure probability.

Idea: Repetition

The natural approach is to run the original algorithm $\mathcal{A}$ multiple times. If any of these runs gives a definite answer, we can use it. But how many repetitions are enough?

Theorem: Amplifying Success for Las Vegas Algorithms

Let $\mathcal{A}$ be a randomized algorithm that never gives a false answer. However, it might sometimes output ”???” (indicating no answer found). Let $Pr[\mathcal{A}(\mathcal{I})\text{ provides a correct answer}]\ge \epsilon$ for any input $\mathcal{I}$.

For any desired overall failure probability $\delta >0$:

Construct a new algorithm ${\mathcal{A}}_{\delta }$ as follows:

1. Repeatedly call $\mathcal{A}$.
2. If any call to $\mathcal{A}$ returns a value different from ”???”, then ${\mathcal{A}}_{\delta }$ immediately stops and returns that value.
3. If $\mathcal{A}$ has been called $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$ times and all calls have resulted in ”???”, then ${\mathcal{A}}_{\delta }$ stops and outputs ”???“.

Then, the probability that ${\mathcal{A}}_{\delta }$ provides a correct answer for input $\mathcal{I}$ is at least $1-\delta$. That is, $Pr[{\mathcal{A}}_{\delta }(\mathcal{I})\text{ correct}]\ge 1-\delta$.

Proof

The algorithm ${\mathcal{A}}_{\delta }$ fails to provide a correct answer if and only if every one of its $N$ independent calls to $\mathcal{A}$ results in ”???“.

The probability that a single call to $\mathcal{A}$ results in ”???” is $Pr[\text{single call fails}]\le 1-\epsilon$.

Since the $N$ calls are independent, the probability that all $N$ calls fail is: $Pr[{\mathcal{A}}_{\delta }\text{ fails}]\le (1-\epsilon {)}^N$.

We want this failure probability to be at most $\delta$. So we need to find $N$ such that $(1-\epsilon {)}^N\le \delta$.

We know that for any real number $x$, $1-x\le e^{-x}$. Applying this with $x=\epsilon$: $(1-\epsilon {)}^N\le (e^{-\epsilon }{)}^N=e^{-\epsilon N}$.

So, we need $e^{-\epsilon N}\le \delta$.

Taking the natural logarithm of both sides (which is a monotonically increasing function, so it preserves the inequality): $\ln (e^{-\epsilon N})\le \ln \delta$ $-\epsilon N\le \ln \delta$

Multiplying by $-1$ (and reversing the inequality sign):

$\epsilon N\ge -\ln \delta$ $\epsilon N\ge \ln (1/\delta )$ $N\ge \frac{1}{\epsilon }\ln \left(\frac{1}{\delta }\right)$.

By choosing $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$, we satisfy this condition.

Therefore, $Pr[{\mathcal{A}}_{\delta }\text{ fails}]\le \delta$.

The probability that ${\mathcal{A}}_{\delta }$ provides a correct answer is $1-Pr[{\mathcal{A}}_{\delta }\text{ fails}]\ge 1-\delta$. This completes the proof.

Example: Number of Iterations

Let’s see how many iterations $N$ are needed for some practical values. Suppose our base Las Vegas algorithm $\mathcal{A}$ has a success probability $\epsilon =0.25$ (it finds an answer 1 out of 4 times on average). Then $N=\lceil (1/0.25)\ln (1/\delta )\rceil =\lceil 4\ln (1/\delta )\rceil$.

Key Observation: To decrease the failure probability by a constant factor (e.g., from ${\delta }_1$ to ${\delta }_1/10$), the number of required iterations $N$ increases only by an additive constant amount (${\epsilon }^{-1}\ln 10$). This makes boosting the success probability of Las Vegas algorithms very efficient.

Reducing Error for Monte Carlo Algorithms

For Monte Carlo algorithms, which may produce incorrect answers, reducing the error probability by simple repetition isn’t always straightforward.

General Case Limitation:

If a Monte Carlo algorithm is no better than random guessing (e.g., it flips a coin to decide between “JA” and “NEIN”, and its probability of being correct is exactly $1/2$), then simply repeating it and, say, taking a majority vote won’t improve things. The error probability remains $1/2$.

Error reduction for Monte Carlo algorithms is generally possible under two main conditions:

1. The algorithm exhibits one-sided error.
2. The algorithm’s probability of being correct is strictly greater than $1/2$ (i.e., it has some “edge” over random guessing).

Monte Carlo with One-Sided Error

This is common in decision problems where an error can only occur for one type of instance (e.g., it might falsely identify a “NO” instance as “YES”, but never a “YES” instance as “NO”).

Definition (One-Sided Error Example)

An algorithm $\mathcal{A}$ has one-sided error if, for a decision problem (JA/NEIN):

• If the input $\mathcal{I}$ is a JA-instance: $Pr[\mathcal{A}(\mathcal{I})\text{ outputs JA}]=1$. (It’s always correct).
• If the input $\mathcal{I}$ is a NEIN-instance: $Pr[\mathcal{A}(\mathcal{I})\text{ outputs NEIN}]\ge \epsilon$. (It’s correct with probability at least $\epsilon$). This implies it erroneously outputs JA with probability at most $1-\epsilon$.

(The roles of JA and NEIN can be swapped depending on the specific algorithm).

Theorem: Error Reduction for One-Sided Monte Carlo

Let $\mathcal{A}$ be a Monte Carlo algorithm with one-sided error as defined above: $Pr[\mathcal{A}(\mathcal{I})=\text{JA}\mid \mathcal{I}\text{ is JA-instance}]=1$. $Pr[\mathcal{A}(\mathcal{I})=\text{NEIN}\mid \mathcal{I}\text{ is NEIN-instance}]\ge \epsilon$.

For any desired overall error probability $\delta >0$:

Construct ${\mathcal{A}}_{\delta }$ as follows:

1. Repeatedly call $\mathcal{A}$.
2. If any call to $\mathcal{A}$ returns NEIN, then ${\mathcal{A}}_{\delta }$ immediately stops and returns NEIN.
3. If $\mathcal{A}$ has been called $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$ times and all calls have resulted in JA, then ${\mathcal{A}}_{\delta }$ stops and outputs JA.

Then, the probability that ${\mathcal{A}}_{\delta }$ gives the correct answer for input $\mathcal{I}$ is at least $1-\delta$. That is, $Pr[{\mathcal{A}}_{\delta }(\mathcal{I})\text{ correct}]\ge 1-\delta$.

Proof

We analyze the two cases for the true nature of input $\mathcal{I}$:

• Case 1: $\mathcal{I}$ is a JA-instance. According to the properties of $\mathcal{A}$, every call to $\mathcal{A}$ on a JA-instance will output JA. Therefore, ${\mathcal{A}}_{\delta }$ will either see $N$ consecutive JAs and output JA (rule 3), or it would have stopped earlier if NEIN was possible (but it’s not for JA-instances). So, ${\mathcal{A}}_{\delta }$ correctly outputs JA. $Pr[{\mathcal{A}}_{\delta }(\mathcal{I})\text{ correct}\mid \mathcal{I}\text{ is JA}]=1$.

• Case 2: $\mathcal{I}$ is a NEIN-instance. The algorithm ${\mathcal{A}}_{\delta }$ makes an error if it outputs JA when $\mathcal{I}$ is a NEIN-instance. This happens if and only if all $N$ independent calls to $\mathcal{A}$ outputted JA. For a NEIN-instance, the probability that a single call to $\mathcal{A}$ outputs JA (an error) is $Pr[\mathcal{A}(\mathcal{I})=\text{JA}\mid \mathcal{I}\text{ is NEIN}]\le 1-\epsilon$. So, $Pr[{\mathcal{A}}_{\delta }\text{ errs}\mid \mathcal{I}\text{ is NEIN}]\le (1-\epsilon {)}^N$. Using the same reasoning as in the Las Vegas proof, if we choose $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$, then $(1-\epsilon {)}^N\le \delta$. Thus, $Pr[{\mathcal{A}}_{\delta }(\mathcal{I})\text{ correct}\mid \mathcal{I}\text{ is NEIN}]\ge 1-\delta$.

Since ${\mathcal{A}}_{\delta }$ is correct with probability 1 for JA-instances and with probability at least $1-\delta$ for NEIN-instances, its overall probability of being correct is at least $1-\delta$.

Monte Carlo with Two-Sided Error (Correctness Probability $>1/2$)

Now, consider a Monte Carlo algorithm $\mathcal{A}$ that always gives a JA or NEIN answer, but it can be wrong in either direction. However, it’s better than a random guess: $Pr[\mathcal{A}(\mathcal{I})\text{ is correct}]\ge \frac{1}{2}+\epsilon$, for some $\epsilon >0$.

Theorem: Majority Vote for Two-Sided Error Amplification

Let $\mathcal{A}$ be a Monte Carlo algorithm such that $Pr[\mathcal{A}(\mathcal{I})\text{ correct}]\ge \frac{1}{2}+\epsilon$ for some $\epsilon >0$. For any desired overall error probability $\delta >0$:

Construct ${\mathcal{A}}_{\delta }$ as follows:

1. Call $\mathcal{A}$ a total of $N=\lceil 4{\epsilon }^{-2}\ln {\delta }^{-1}\rceil$ times independently.
2. ${\mathcal{A}}_{\delta }$ outputs the answer (JA or NEIN) that occurred most frequently among the $N$ trials (the majority vote). If there’s a tie, it can break it arbitrarily, e.g., output JA.

Then, $Pr[{\mathcal{A}}_{\delta }(\mathcal{I})\text{ correct}]\ge 1-\delta$.

Proof

We analyze a Monte Carlo algorithm $\mathcal{A}$ that returns the correct answer with probability at least $\frac{1}{2}+\epsilon$ for some known $\epsilon >0$. We define a new algorithm ${\mathcal{A}}_{\delta }$ which runs $\mathcal{A}$ independently $N$ times and returns the majority answer.

We show that:

Setup

Let:

• $0<\epsilon \le \frac{1}{2}$

• $p:=\mathrm{Pr}[\mathcal{A}(I)\text{ correct}]\ge \frac{1}{2}+\epsilon$

• Let $X$ be the number of correct answers in $N$ independent runs of $\mathcal{A}(I)$.

• So $X\sim \text{Binomial}(N,p)$

• We want to bound:

  $$\mathrm{Pr}[{\mathcal{A}}_{\delta }(I)\text{ is incorrect}]=\mathrm{Pr}[X\le N/2]$$

Step 1: Expected Value of X

The expected number of correct runs is:

We now show that:

Step 2: Verifying the Chernoff Condition

We expand the right-hand side of (★):

So:

This holds for all $\epsilon \le \frac{1}{2}$, so (★) is valid.

Step 3: Applying Chernoff Bound

Using the Chernoff bound for the lower tail:

By (★), we have:

Step 4: Bounding the Exponent

We use:

So:

We want this to be at most $\delta$:

Thus, choosing:

ensures:

Final Conclusion

With this value of $N$, the amplified algorithm ${\mathcal{A}}_{\delta }$ satisfies:

This shows that any Monte Carlo algorithm with correctness probability $\ge \frac{1}{2}+\epsilon$ can be boosted to failure probability at most $\delta$ using:

independent repetitions and majority vote.

Randomized Algorithms for Optimization Problems

Randomized algorithms can also be applied to optimization problems (e.g., finding a maximum clique, minimum spanning tree, etc.).

Typical Scenario:

• The algorithm always produces a feasible (valid) solution.
• The quality of this solution is a random variable; it’s not necessarily the optimal one.

Suppose for a maximization problem, we want a solution with value at least $q(\mathcal{I})$ (our target quality for input $\mathcal{I}$). Assume our base randomized algorithm $\mathcal{A}$ achieves this target quality with at least probability $\epsilon$: $Pr[\text{Value from }\mathcal{A}(\mathcal{I})\ge q(\mathcal{I})]\ge \epsilon$.

Goal: Design an algorithm ${\mathcal{A}}_{\delta }$ that achieves quality $q(\mathcal{I})$ with a higher probability, at least $1-\delta$.

Theorem: Amplification for Optimization by Repetition

Let $\mathcal{A}$ be a randomized algorithm for an optimization problem (assume maximization without loss of generality). Suppose $Pr[\text{Value from }\mathcal{A}(\mathcal{I})\ge q(\mathcal{I})]\ge \epsilon$.

For any desired success probability $1-\delta$ (where $\delta$ is the failure probability):

Construct ${\mathcal{A}}_{\delta }$ as follows:

1. Call the original algorithm $\mathcal{A}$ a total of $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$ times independently.
2. ${\mathcal{A}}_{\delta }$ outputs the solution that has the best value among all $N$ solutions obtained.

Then, $Pr[\text{Value from }{\mathcal{A}}_{\delta }(\mathcal{I})\ge q(\mathcal{I})]\ge 1-\delta$.

Proof

The algorithm ${\mathcal{A}}_{\delta }$ fails to achieve a solution of quality at least $q(\mathcal{I})$ if and only if every one of the $N$ independent trials of $\mathcal{A}$ produces a solution with value less than $q(\mathcal{I})$.

The probability that a single trial of $\mathcal{A}$ fails to meet the target quality is $Pr[\text{Value from }\mathcal{A}(\mathcal{I})<q(\mathcal{I})]\le 1-\epsilon$.

Since the $N$ trials are independent, the probability that all $N$ trials fail is: $Pr[{\mathcal{A}}_{\delta }\text{ fails}]\le (1-\epsilon {)}^N$.

This is the same mathematical situation as in the Las Vegas amplification. By choosing $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$, we ensure that $(1-\epsilon {)}^N\le \delta$.

Therefore, the probability that ${\mathcal{A}}_{\delta }$ succeeds (i.e., at least one of the $N$ trials achieves the target quality, and thus the best of them does) is $Pr[\text{Value from }{\mathcal{A}}_{\delta }(\mathcal{I})\ge q(\mathcal{I})]\ge 1-\delta$.

This “repeat and take best” strategy is a common and effective way to boost the performance of randomized optimization algorithms.