Randomized Algorithm
Randomized algorithms are algorithms that makes random decision during their execution. Specifically, they are allowed to use variables, such that their value is taken from some random distribution.
It is not immediately clear why adding the ability to use randomness helps an algorithm.
A randomized algorithm A is an algorithm that at each new run receives, in addition to its input i, a new stream/string r of random bits which are then used to specify outcomes of the subsequent random choices (or coin tossing) during the execution of the algorithm.
Streams r of random bits are assumed to be independent of the input i for the algorithm A.
Repeated runs of a randomized algorithm with fixed input data will not, in general, produce the same results.
Outcomes, A(i, r), depend not only on i, but also on r.
Types of Randomized Algorithms
1. Monte Carlo Algorithms
Randomized algorithms that always has the same time complexity, but may sometimes produce incorrect outputs depending on random choices made.
Time complexity is deterministic, correctness is probabilistic.
2. Las Vegas Algorithm
Randomized algorithms that never produce incorrect output, but may have different time complexity depending on random choices made (including sometimes not terminating at all).
Time complexity is probabilistic, correctness is deterministic.
Advantages of Randomized Algorithm
There are several important reasons why randomized algorithms are of increasing importance.
- Randomized algorithms are often faster either from the worst-case asymptotic point of view or/and from the numerical implementations point of view;
- Randomized algorithms are often (much) simpler than deterministic ones for the same problem;
- Randomized algorithms are often easier to analyse and/or reason about especially when applied in counter-intuitive settings;
- Randomized algorithms have often more easily interpretable outputs, which is of interests in applications where analyst’s time rather than just computation time is of interest;
- Randomized algorithms have been recently surprisingly successful when dealing with huge-data matrix computation problems.
- Randomized numerical algorithms can often be organized better to exploit modern computer architectures.
Why use Randomization in Algorithms?
- To improve efficiency with faster runtimes. For example, we could use a randomized quicksort algorithm instead of the deterministic quicksort. Deterministic quicksort can be quite slow on certain worst case inputs (e.g., input that is almost sorted), but randomized quicksort is fast on all inputs.
- To improve memory usage. Random sampling as a way to sparsifying input and then working with this smaller input is a common technique.
- To make algorithms simpler. For example, see Karger’s min-cut algorithm in the next lecture.
- In parallel/distributed/streaming models of computation, randomization plays an even more critical role. In distributed computing, each machine only has a part of the data, but still has to make decisions that affect global outcomes. Randomization plays a key role in informing these decisions.
Applications of Randomized Algorithm
Few popular examples of the Randomized algorithms are:
- Min-Cut Algorithm
- Randomized Quick Sort Algorithm
- Karger’s Minimum Cut Algorithm
- Fisher-Yates Shuffle Algorithm
- The Subset Sum Problem
- Randomized Incremental Constructions in Geometry