When does a Randomized Algorithm perform best?

 When does a Randomized Algorithm perform best?

What is a Randomized Algorithm?

Basically, we use a random algorithm that typically gives any random number or value as an input to our executing program to decide what to do next anywhere in our logic.

This algorithm is used to reduce the time complexity, memory used or space complexity, in a standard algorithm to guide its behavior, and also achieve good performance in “Average Case” over all possible choices of random value.

Fig 1.

This figure (Fig 1.) clearly specifies that whenever our logic stuck, a random value is given to our algorithm as an input or with input to get an output.

Classification of Randomized Algorithm

1. Las Vegas algorithm: It was introduced by László Babai in 1979, this randomized algorithm produces either correct output, or no output when no result is found, but it cannot guarantee a time constraint. Time complexity is not fixed (not deterministic), it can vary for the same input. It somehow guarantees an upper bound in the worst-case scenario.

   
   
   Las Vegas happens almost every time we try to find something. Suppose the Las Vegas algorithm is a task in which we have to find something which is lost in our house somewhere. In this situation, we know what we have to find and we simply start searching for it at any random place in our house. What will be the result? Either you will find it or else you don’t. There is no chance of finding the wrong thing and also if you are lucky you may find it very earlier or if you are not then you will be spending countless hours to no avail. What makes this a Randomized Las Vegas is that the user knows what exactly they want, so once the thing is found there is no probability of wrong answer and error. Similarly, if the user’s allotted time for that process is over then this algorithm will terminate the process saying that the solution was not found.

We can say it in short - Las Vegas is a randomized algorithm that uses the random input to give the correct output or no output, but the is finite and may vary for the same input.

Let’s consider a simple example that is Randomized Quick Sort.

What is Randomized Quick Sort?

Let’s first, see in short what is Randomized Quick sort. It uses the divide and conquers procedure, in which suppose you have an array of size n, you will select any element as a pivot element then it will divide the array into two subarrays. Elements that are larger than the pivot element will be moved to the right side of the pivot element and that are smaller will be moved to the left side. In the given Fig. 2, the pivot element selected is 4.

Fig. 2

Continuing this divide and conquer procedure recursively to left and right subarray till we have subarrays size as 1, we will get a sorted array. The average time complexity of the quick sort algorithm is O (n log n). We won’t be explaining the whole Quick sort here, what matters is the analysis of the partitioning procedure and how will be selecting the pivot element. You can select any element, but first, let’s talk about the deterministic approach that the selecting first or last element as the pivot element. Let’s consider the first element. Considering the best case, when we do the divide and conquer procedure we will get two subarrays of the same size. But what about the worst case? The worst-case scenario occurs when the array members are sorted out (shown in Fig. 3). The left subarray will remain empty for each iteration, and the right subarray will contain all the elements except the pivot. Therefore, in each step, we will need to divide the array in sizes n, n-1, n-2, n-3, ..., which adds to the O (n²) -complexity of time.

Fig. 3

The reverse will occur when the pivot is the last element. The worst-case scenario would be if the array members are sorted out in descending order (shown in Fig. 4). The left subarray will remain empty for each iteration, and the right subarray will contain all the elements except the pivot. So, here again, O (n²) will be the time complexity.

Fig. 4

How to deal with this situation? This can be solved if you avoid the deterministic approach. So, instead of using the first or last element, we will randomly select something (another element) that will be a pivot. If the algorithm selects pivots randomly, the algorithm will generate balanced subarrays regardless of input arrays.

Even if you choose a pivot randomly, your subarrays members may not fit well. However, the chances of this happening will be very small compared to choosing the first or the last elements. In fact, there is a very slight deviation from the average case while using random pivots and you can check out the proven possible guaranteed analysis of the randomized quick sort from here if you like. You can also exercise yourself by producing the same random arrays.

2. Monte Carlo Algorithm: Introduced by Stanislaw Ulam in the late 1940s, this randomized algorithm is a probabilistic algorithm, which may not provide the right answer but the running time of these algorithms is fixed. There is also the possibility that the answer is correct.

To understand the algorithm of the Randomized Monte Carlo let's take a simple example of a program. Suppose we have the array a[ ] of size n and elements as the numbers x1, x2, x3,… .xn.

2. Representation of array: a [x1, x2, x3,… .xn]. Also, a function to check how many real numbers are in the list. This function displays 1 as an output where the number is real else 0 if the number is a complex number. Let us consider the case that our size of the array is as large as 1 lac, now we cannot take each element in the list and decide whether it is real or not. Here the algorithm of Monte Carlo comes into the picture, which will allow us to randomly select some numbers let's say 500 numbers from the list, and we will confirm the output and get the probability of output that this percentage of numbers are real. Let us assume that any of the 500 random numbers selected were all real so that we would get output 1 out of all numbers, and it gives a 100% chance that all numbers are a real number in that 1 lac-size list. But it might be wrong, maybe numbers other than those random numbers could be complex numbers as well. So here, the Monte Carlo algorithm may give you the wrong output, but it has a time limit that checks only 500 numbers instead of 1 lac. The drawback of failure chances can be overcome by repeatedly taking another 500 numbers, and counting their chances. In short, Monte Carlo, a randomized algorithm is an algorithm that has the probability to produce an incorrect result, but the running time is fixed.

Let’s consider the example of Karger’s algorithm for Min Cut

The basic function of the Karger Algorithm is if we have given the graph and we want to divide that graph into two graphs.

Example: Suppose we have a graph (G) (Fig. 5) and we have to divide the graph into two graphs s1 and s2.

Fig. 5 

 

If we want to divide that graph (G) into 2 graphs we need to find the minimum number of edges so that we can subtract/remove them so that the graph G is converted into two graphs s1 and s2.

Fig 6.

 

In the picture above (Fig. 6) you can see that after removing edges a1 and a4 we now have two graphs one with the name s1 with vertex 0 and the second s2 graph where we have three vertices with the name 1,2 and 3. In the above example like you, all can see we removed 2 edges, so in the given graph (G) there are 2 edges that need to be removed if we want to convert it to graphs s1 and s2. How to remove edges? & How contraction is done? and what is a contraction? which we need to understand first before we go to the Karger Algorithm section.

 

Contraction: We combine two vertices and consider them as a single vertex.

 

Suppose we have a graph (G) (Fig. 7).

Fig. 7

 

For contraction, if we want to remove vertex 1 we will be merging it with vertex 3 and (3,1) will be considered as a single vertex. Like this (Fig. 8);

Fig. 8

 

And the edges that went from Vertex 2 to Vertex 1 will now go from Vertex 2 to Vertex (3,1). Edge q1 from Vertex 1 to Vertex 3 will be permanently removed and the front edge from Vertex 2 to Vertex 3 will remain as it is.

This is how the contraction is done. All of this is necessary in order to learn how the Karger Algorithm really works.

 

Karger Algorithm for finding Min-Cut

The basic use of this algorithm is to randomly select any edge and then contradict it to another vertex and this process will continue until two vertices are left. Eventually, we will find the minimum number of edges needed to separate the two graphs.

 

Consider the same example (Fig. 9) of the dividing graph (G) into two graphs S1 and S2.

Fig. 9

 

To convert the given graph into a graph of S1 and S2 we will randomly select any edge and then delete it as this time we will remove the q5 edge connecting Vertex 0 and 3. Then our graph will look like this (Fig. 10),

Fig. 10

 

Here we have made a contraction as mentioned earlier, and we should continue with this contraction until we have only two vertices left. Therefore, in this case, we will choose a random edge and connect the two vertices.

Fig. 11

 

As here in the given graph (Fig. 11) there are only two vertices left and the number of edges connecting these two is 2, so here we conclude that at least three edges we need to remove in order to convert this Graph G into Graph S1 and S2.

But in this case, it has given the correct output but there are other cases where it will also give us the wrong result as a random algorithm to be able to select different edges at different times to contradict and therefore can  gave us the wrong output.

Fig. 12

 

Here, we will select 4 as a random margin and then remove them.

Fig. 13

 

Then again, we will select a2 as a random edge and subtract it against vertices 2 and 3 and the graph will look as shown (Fig. 14) in the graph diagram below,

Fig. 14

 

With only two vertices left, we will rule out the Karger algorithm here. In view of the above conclusion, it tells us that we should remove 2 edges. But it should be 3 as we have already proved.

So, this was an example of the Monte Carlo algorithm for wrong output which means that this type of algorithm may or may not give the right result.

 

Let’s summarize what we understood till now!

We use a randomized algorithm that usually assigns any random number or value as an input to our executing system.

Specifically, we use the Las Vegas algorithm when we need the right output and reduce the complexity of time by using random numbers as input. But it does not guarantee performance within certain time limits. Monte Carlo, on the other hand, is a probabilistic algorithm that can produce incorrect output but only works for a limited period of time.

 

References:

[1] Randomized algorithms. GeeksforGeeks. (n.d.). Retrieved June 9, 2022, from https://www.geeksforgeeks.org/randomized-algorithms/ 

[2] Randomized algorithms. Brilliant Math & Science Wiki. (n.d.). Retrieved June 9, 2022, from https://brilliant.org/wiki/randomized-algorithms-overview/

[3] What is the DIFFERENC between Monte Carlo and Las Vegas algorithm and where we use them in Rabin-Karp algorithm? Quora. (n.d.). Retrieved June 9, 2022, from https://www.quora.com/What-is-the-differenc-between-Monte-Carlo-and-Las-Vegas-algorithm-and-where-we-use-them-in-rabin-karp-algorithm 

[4] Wikimedia Foundation. (2022, April 19). Randomized algorithm. Wikipedia. Retrieved June 9, 2022, from https://en.wikipedia.org/wiki/Randomized_algorithm