Randomized algorithms¶
Overview¶
Randomized algorithms are a class of computational techniques that leverage randomness or probabilistic methods to solve a variety of problems in computer science and mathematics. Unlike deterministic algorithms, which produce the same output for a given input every time, randomized algorithms introduce randomness into their computations, making their outcomes probabilistic in nature.
Not a paradigm like divide and conquer, etc. that guides the design of algorithms.
It is a technique that can be used in conjunction with other techniques to design algorithms.
Important Concepts¶
Pseudo Random Number Generators (PRNGs)
Pseudo-random number generators (PRNGs) are fundamental tools in randomized algorithms. They are deterministic algorithms that generate sequences of numbers that appear to be random but are generated by an initial seed value. PRNGs are used to introduce controlled randomness into algorithms, making them predictable for a given seed while appearing random for most practical purposes. When a real random number is required, a seed value is chosen from a source of true randomness, such as current time, etc.
It should exhibit similar statistical properties as a truly random sequence. Like generating a sequence of numbers that are in certain distribution, like uniform distribution, normal distribution, etc.
Random Sampling
Random sampling involves selecting a subset of elements from a larger dataset in a way that each element has an equal chance of being included. It is a fundamental technique in randomized algorithms used for tasks like estimating statistics, generating random permutations, and solving problems with large datasets.
Example of Randomized Algorithms¶
Genetic algorithms
Genetic algorithms are a class of randomized search algorithms inspired by the process of natural selection. Various randomized techniques are employed in steps including initialization, selection, crossover, and mutation to produce a population of candidate solutions to a given problem. The population is then iteratively improved by applying these steps to produce better solutions.
Monte Carlo Algorithms
A Monte Carlo algorithm is a randomized algorithm that leverages randomness to approximate solutions to problems, often in situations where deterministic methods are impractical or computationally expensive. These algorithms use random sampling techniques to estimate the desired solution, and their results are typically probabilistic in nature. Monte Carlo algorithms generate random inputs or samples and use statistical analysis to estimate properties of interest, such as probabilities, averages, or integral values. While they do not guarantee exact solutions, they are highly versatile and are applied to a wide range of problems in fields like physics, finance, computer science, and engineering, providing approximate answers with well-controlled levels of uncertainty.
Example: \(\pi\) approximation
Imagine you have a square piece of paper and a circular target inside it. You don’t know the value of π, but you want to estimate it using randomness. Here’s how the Monte Carlo Pi Approximation works:
Draw a square on a piece of paper and inscribe a circle within it, so the circle touches all four sides of the square.
Randomly throw a large number of tiny pebbles or darts onto the square.
Count how many pebbles landed inside the circle and how many landed outside but inside the square.
Now, the ratio of pebbles inside the circle to the total pebbles thrown is approximately equal to the ratio of the area of the circle to the area of the square. This ratio is π/4.
By multiplying the ratio you calculated by 4, you get an approximation of π.
The more pebbles you throw, the closer your approximation will be to the actual value of π. This simple experiment demonstrates how Monte Carlo methods use randomness to estimate important values or solve complex problems, making them a powerful tool in various fields, including science, engineering, and statistics.
Las Vegas Algorithms (FYI)
A Las Vegas algorithm is a randomized algorithm that, unlike its Monte Carlo counterpart, guarantees both correctness and efficiency with probabilistic methods. In Las Vegas algorithms, randomness is employed to improve the algorithm’s expected performance while ensuring that it always produces a correct result. These algorithms run until they find a correct solution, and the running time may vary depending on the input and random choices made during execution. If the algorithm doesn’t find a solution within a certain time frame, it restarts with a new random configuration, repeating this process until it succeeds. Las Vegas algorithms are particularly useful for solving problems with uncertain or variable computational complexity, providing a balance between guaranteed correctness and the advantages of randomness in algorithm design.
Randomized data structures (FYI)¶
Skip Lists
Bloom Filters
Randomized search trees