Randomized Algorithms

Abhishektayde — Mon, 24 Apr 2023 19:55:48 GMT

Introduction

What exactly is a random algorithm?

The term “Randomized Algorithm” refers to an algorithm that uses random integers to choose the next step in any part of its logic.

Randomized algorithms base their judgements on a random source. By using a common algorithm, they are utilized to decrease the utilization of resources like time, space, or memory.

Given a specific input, a typical, deterministic algorithm will always result in the same output. To get to that output, it will always go through the same stages, therefore its behavior won’t alter across runs. A well-known chemical reaction might serve as an example of this in real life. Water molecules are always created from two molecules of hydrogen and one molecule of oxygen.

A deterministic algorithm aims to always provide an accurate solution that is completed rapidly (in polynomial time). A flowchart of its procedure looks like this:

Compare that to what one for a randomized algorithm looks like:

Here, the algorithm uses random numbers in addition to input to produce random decisions while running. The output for the same input can vary, meaning that it can behave differently between runs. RNGs are a prerequisite for these algorithms.

Be aware that this differs from probabilistic analysis of algorithms, which relies on random input to demonstrate that the algorithm is effective for the majority of inputs.

This may all be too theoretical. Let’s take a look at a randomized algorithm in action. Let’s say one wishes to know how many people feel about a particular issue. What would be the best course of action here?

It would take a long time to conduct such a survey by visiting each and every respondent. Instead, interviewing a random sample of people would produce the same results. This is a fair representation of the group known as random sampling. Since every member of the population has an equal chance of being chosen, it is a fair technique to draw a sample from a bigger group.

When is randomness useful?

Another question that arises is- When are randomized algorithms used?

They are employed if there are time or memory restrictions and when the best-case scenario will do. Therefore, randomized algorithms are used in areas like:

Number theoretic algorithms — Primality Testing
Data Structures — Searching, sorting, computational geometry
Algebraic Identities — Verification of polynomial and matrix identities
Mathematical Programming — Faster linear programming algorithms
Graph algorithms — Finding minimum spanning trees, shortest paths, minimum cuts
Counting and enumeration — Counting combinational structures
Parallel and distributed computing — Deadlock avoidance, distributed consensus
De-randomization — Randomness can be viewed as a resource, like space and time. De-randomization is then the process of removing randomness (or using as little of it as possible).

You may have encountered an early introduction to the value of algorithms while learning sorting algorithms, specifically in Quicksort. Finding a list that is already mostly sorted is the worst scenario for quick sort, increasing the time complexity to O(n2). By randomly rearranging the positions of the list’s members, Randomized Quicksort avoids this, and Quicksort can typically sort data in O(nlogn) time.

Amplification algorithms are used to increase the chance of correctness at the cost of runtime because randomized algorithms have the potential to provide incorrect results. This is possible as long as an algorithm’s success probability remains constant from run to run. The process of amplification involves repeatedly running an algorithm (using various random subsamples of the input) and taking the majority result.

There are two types of randomized algorithms:

1. Las Vegas algorithms

2. Monte-Carlo algorithms

Las Vegas Algorithms

Intuition

This algorithm, which is random, either consistently produces the correct result or doesn’t. However, because the time complexity varies on the input, it is unable to provide a time limit. But in the worst situation, it guarantees an upper bound.

Las Vegas algorithms show up almost every time someone searches for something. A Las Vegas algorithm is convinced it has found the appropriate solution when a problem is solved, but the path leading there may not have been clear-cut. To take a very general and simplified example, a Las Vegas algorithm may be thought of as the method a user employs when conducting an online search. Typically, the user would begin by using a search engine because personally browsing every website on the internet is quite time-consuming. The user will then go on their online search till they find a website that contains exactly what they are looking for. Clicking via links is a somewhat random activity, presuming the user is unaware of the precise contents of the website at the other end of the link. Similar to how she will stop the process knowing the answer was not found if she uses all the allotted time for web browsing.

Randomized Quicksort

Quicksort is a popular Las Vegas randomised sorting technique that sorts objects in place without using any additional memory. Due to the comparison-based nature of this method, the worst case scenario is when doing a pairwise comparison, which requires O(n2) time and grows exponentially as the square of the number of digits to be sorted. The runtime of this approach can be reduced to O(n log(n)) using randomization, though.

# Randomized Algorithms Pseudo Code

INPUT:

Array A with total n elements

def Randomized_quicksort(A):

If n = 1:

return A # Array A is already sorted.

Else:

i = Random number in range(1, n)

X = A[i] # the pivot element using random method

Partition A into elements < x, == x, and >x

Apply Quicksort on A[1 to i-1] and A[i+1 to n].

Combine all the data to obtain a sorted array.

If the pivot element selected at random is the first or final member in the array, the worst-case scenario for this technique is that it takes O(n²) time to sort n digits.

The anticipated runtime for randomized algorithms, i.e., Quicksort, where the pivot is selected randomly, and neither the smallest nor largest number in the array is chosen, is O(n log(n)).

Monte Carlo Algorithms :

Intuitive Explanation

Playing the Wheel of Fortune game can be done using a Monte Carlo randomization method. As shown in the image below, a player (or machine) randomly selects letters to come up with a solution as opposed to choosing them consciously. As a player reveals more letters, their confidence in their solution increases. If a player takes their time, other players will also estimate that the answer is “rising,” though. As a result, a Monte Carlo algorithm is given a predefined amount of time to discover the optimal solution by making a “guess” in light of the revealed information. If the Monte Carlo approach did not have enough time to find enough beneficial letters, there would be opportunity for error and potentially even a high chance of error. But if you set a time limit, you can control how long the algorithm runs and lessen the likelihood that someone else will make the right guess and take home the cash. The fact that there is only one correct answer distinguishes this game from a standard Monte Carlo method. The “good enough” answer is still one that gives a Monte Carlo algorithm an acceptable output.

How to analyze a randomized algorithm?

Correctness and complexity are the two factors you should take into account while analyzing a randomized algorithm. Correctness is the likelihood that the algorithm will provide a solution that is either acceptable or the correct solution. The complexity of an algorithm is measured by how much time or space it consumes on average or at its worst. Utilising methods from probability theory and statistics, such as expectation, variance, standard deviation, confidence intervals, and limits, you may measure these factors. For instance, you can use the Central Limit Theorem to demonstrate that the error of the approximation is bounded by a specific confidence interval with a specific probability in order to assess the accuracy of the pi estimate technique. The Markov Inequality can be used to demonstrate that the predicted number of trials is constrained by a certain function of the graph size and can be used to analyse the complexity of the Hamiltonian cycle method.

How to improve a randomized algorithm?

Depending on the algorithm’s type and objectives, there are several approaches of optimizing randomized algorithms. Derandomization is the process of removing or lowering randomness using deterministic simulations, preset options, or pseudorandom generators. This can improve the algorithm’s effectiveness, dependability, or simplicity. By rounding each fraction up or down with a probability, randomised rounding transforms a fractional solution into an integer solution while maintaining qualities like feasibility or optimality. Amplification is the process of repeating an algorithm or expanding its sample size to raise the likelihood of success or improve the approximation’s accuracy, hence lowering the algorithm’s error or variance.