Randomized Algorithms

An algorithm that makes use of random no’s to decide what step to take next is known as Randomized Algorithm. Generally, this randomness is used to decrease the space or time complexity in other standard algorithms. Also the algorithm takes a source of random no’s and makes random choices during execution. Even for a fixed input the behavior can vary .

How to assay Randomized Algorithms?

Some randomized algorithms have deterministic time complexity. For illustration, Karger’s algorithm has a time complexity of O(E). Such algorithms are called Monte Carlo Algorithm. and are easier to assay for worst case.
On the other hand, time complexity of other randomized algorithms (other than Las Vegas) is dependent on the value of arbitrary variables. These types of algorithms are called Las Vegas Algorithm. These algorithms are generally analyzed for the expected worst case. To compute anticipated time taken in the worst case, all possible values of the used arbitrary variable need to be considered in the worst case and time taken by every possible value needs to be evaluated. The expected worst case time complexity is the average of all evaluated times.

Design paradigms of randomized algorithm:

• Abundance of witnesses
• Fingerprint and hashing
• Foiling an adversary
• Random sampling
• Rapidly mixing Markov chains

Random Variables

Random variable is a function which maps from the set of sample space to set of real nos. The objective is to get an idea about the outcome of a particular situation where we are given probabilities of different results.

Classification

Randomized algorithms are classified in two categories.

Las Vegas:

These algorithms always produce correct or optimum result. Time complexity of these algorithms is based on an arbitrary value and time complexity is estimated as anticipated value. For illustration, Randomized QuickSort always sorts an input array and anticipated worst case time complexity of Quick Sort is O(nLogn).

Advantages:

• Fast algorithm
• Always produces the correct result for the same input.
• Execution time depends on the output of the randomizer.

Monte Carlo

Produce right or ideal outcome with some likelihood. They create random sample data based on a few known distribution for numerical experiments These algorithms have deterministic running time and it is for the most part more straightforward to figure out most worst scenario time complexity. For instance this execution of Karger’s Algorithm produces least cut with likelihood more noteworthy than or equivalent to 1/n2 (n is number of vertices) and has most worst scenario time complexity as O(E). Another model is Fermat Method for Primality Testing. Utilized by experts in different fields like assembling, innovative work, finance, transportation, oil and gas, finance, project the executives and so on.

Characteristics:

• Users should aware of the input distribution.
• Output should generate random samples.
• While performing the experiment the outcome must be known.

Advantages:

• Makes use of the computer to give statistical sampling for numerical experiments.
• Implementation of this algorithm is easy.
• Solution provided to problems is approx.
• Used for both deterministic and stochastic problems.

Disadvantages:

• Result is not accurate as this method is only the approximation of true values.
• Consumes time.

Flow chart:

Advantages:

Advantages of randomized algorithms

• This algorithm is simple and easy to implement.
• Any deterministic algorithm can be converted into a randomized algorithm.
• Performance
• Efficient
• Compared to any of the deterministic algorithms they use little execution time and space.
• Show superior asymptotic bounds

Disadvantages:

• Not always reliable.
• Many of the algorithms may not terminate.
• The quality depends on the quality of the random number generator used.
• Unlike others, this algorithm does not use single design principle.

Scope

• Number-theoretic algorithms Primality testing Monte Carlo_x0005_.
• Randomized algorithms can be used in Data structures, Sorting order statistics and searching computational geometry.
• Algebraic identities Polynomial and matrix identity verification Interactive proof systems.
• Randomized algorithms are best for Mathematical programming Faster algorithms.
• It can also be used in Graph algorithms, Minimum spanning trees, shortest paths finding algorithms, minimum cuts.
• Counting and enumeration Matrix permanent Counting combinatorial structures.
• Parallel and distributed computing deadlock avoidance distributed consensus.
• Probabilistic existence proofs Show that a combinatorial object arises with non zero probability among objects drawn from a suitable probability space.