Randomized Algorithms

“Random numbers should not be generated with a method chosen at random” — Donald Knuth

Nowadays, we can see that after decades of research, a category of algorithms which is also called ‘Randomized Algorithms’ are now an important part of many areas of computer science. We are familiar with the very famous Stochastic Gradient Descent Algorithm, which is also a type of randomized algorithm.

What are Randomized Algorithms?

The term “Randomized Algorithm” refers to an algorithm that uses random integers to choose the next step in any part of its logic. So basically it uses random numbers to decide what to do next in its logic.

Brief about Randomized Algorithms

Randomized Algorithm uses randomness as a computing tool for algorithm design. That means the program logic is also going to consider randomness as one of the components and we have to use it for finding the solution to the given problem.

Randomized Algorithms are also called Probabilistic Algorithms.

A Randomized Algorithm makes use of a Randomizer (such as a random number generator). So, some of the decisions made in the algorithm depend on the output of the randomizer. The output of any randomizer might differ in an unpredictable way from run to run. And this output could also differ from run to run for the same input. Similarly, the execution time could also vary from run to run for the same input.

That is why, Randomized Algorithms depends on two factors:

1. Input given to the algorithm
2. Random choices as a part of logic

Basic structure

“Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin” — John von Neumann

Characteristics of Randomized Algorithms

• The output of the randomized algorithm depends on the random decisions taken by the Randomizer.
• The output is based on Probability. (take an example of tossing a coin).
• Neglect the negligible errors that occurred during the long run.

Generation of Random Numbers

A random number generator generates a random number.

There are two types of random numbers:

1. True random number : A true random number is generated based on radioactive delay, flipping of coins, etc. Generated number is not recreated again in future.
2. Pseudo random number : A pseudo random number is generated using software applications. It can be recreated if the formula is known. It is sufficient for most of the purposes.

“An algorithm must be seen to be believed” — Donald Knuth

Randomized Algorithms can be categorized into two classes:

1. Monte Carlo Algorithms
2. Las-Vegas Algorithms

Monte Carlo Algorithms

In Monte Carlo Algorithms, the algorithm produces mostly or probably correct output. That means, it may or may not produce correct output. The output might differ from run to run for the same input.

Monte Carlo Algorithms are polynomial time algorithms, because the running time is completed within polynomial time.

Example : Majority Element in the Array

Algorithm for Majority Element

Las Vegas Algorithms

In Las Vegas Algorithms, the algorithm always produces the correct output for the same input. They are probably fast algorithms. The Execution time of a Las Vegas algorithm depends on the output of the randomizer.

Example : Randomized Quicksort

Algorithm for Randomized Quicksort

“Programming is the art of algorithm design and the craft of debugging reliant code” — Ellen Ullman

Advantages of Randomized Algorithms

• Simplicity : Simple in nature. Uses pseudo random number generator
• Very Efficient : These algorithms are efficient as compared to deterministic algorithms. Deterministic Algorithms take a long time whereas Randomized Algorithms take less time to run.
• Computational Complexity : Computational Complexity is better than deterministic algorithms. It also helps to reduce both space as well as time complexity.

Disadvantages of Randomized Algorithms

• Quality : Randomized Algorithms depends on the quality of random number generator used as part of the algorithms
• Reliability : Some algorithms may lack certain guaranteed solutions. We may not firmly say that we will get the correct solution.
• Hardware Failure : Sometimes hardware may fail and we may not get the correct solution.

Applications of Randomized Algorithms

• Primality Testing :

Any integer greater than one is said to be prime if its only divisors are 1 and the integer itself. Given an integer n , the problem of deciding whether n is a prime is known as primality testing.

• Identifying the Repeated Element :

Consider an array a[ ] of size n that has n/2 distinct elements and n/2 copies of another element. The problem is to identify the repeated element.

Algorithm for Repeating Element

“The art of programming is the art of organizing complexity” — Edsger W. Dijkstra

Thus, Randomized algorithms play a very crucial role in the computation and also help us to get the most probable accurate results within less time and space complexity.

Thanks for reading this blog until the end, I’m really glad to find people who’re as motivated as I am about Computer Science (especially Machine Learning and DSA).