How do you design a randomized algorithm for a problem that has no efficient deterministic solution?

1 What is a randomized algorithm?

A randomized algorithm is an algorithm that makes some decisions based on the outcome of a random process, such as tossing a coin, drawing a card, or generating a random number. A randomized algorithm can be classified into two types: Las Vegas and Monte Carlo. A Las Vegas algorithm always produces the correct answer, but its running time may vary depending on the random choices. A Monte Carlo algorithm may produce an incorrect answer with some probability, but its running time is fixed or bounded. Both types of algorithms can be useful for solving hard problems, depending on the trade-off between accuracy and efficiency.

4 How to analyze a randomized algorithm?

To analyze a randomized algorithm, you need to consider two aspects: correctness and complexity. Correctness refers to how likely the algorithm produces the correct answer or an acceptable answer. Complexity refers to how much time or space the algorithm uses on average or in the worst case. To measure these aspects, you need to use some tools from probability theory and statistics, such as expectation, variance, standard deviation, confidence intervals, and bounds. For example, to analyze the correctness of the pi estimation algorithm, you can use the Central Limit Theorem to show that the error of the approximation is bounded by a certain confidence interval with a certain probability. To analyze the complexity of the Hamiltonian cycle algorithm, you can use the Markov Inequality to show that the expected number of trials is bounded by a certain function of the graph size.

5 How to improve a randomized algorithm?

There are various methods for optimizing a randomized algorithm, depending on the type and the goal of the algorithm. Derandomization involves eliminating or reducing randomness through pseudorandom generators, deterministic simulations, or fixed choices, which can enhance the efficiency, reliability, or simplicity of the algorithm. Randomized rounding is used to convert a fractional solution into an integer solution by rounding each fraction up or down with some probability, preserving properties such as feasibility or optimality. Amplification is the process of repeating an algorithm or increasing its sample size to increase the probability of success or accuracy of the approximation, thus reducing the error or variance of the algorithm.

6 How to apply a randomized algorithm?

Randomized algorithms have various applications in computer science and mathematics, such as cryptography, data structures, machine learning, optimization, and computational geometry. Primality testing, minimum cut, and linear programming are some examples of problems that can be solved or approximated by randomized algorithms. Primality testing can be checked with the Miller-Rabin test; the Karger's algorithm can find a minimum cut; and the ellipsoid method or the interior point method can find an optimal solution for linear programming. These algorithms are much simpler and faster than their deterministic counterparts, which may suffer from numerical instability or exponential worst-case behavior.