Probabilistic Analysis and Randomized Algorithms

What is Probabilistic Analysis?

Those algorithms which we want to take the analysis of algorithm with help of probability this type of analysis is called Probabilistic Analysis. Probabilistic analysis goals to measure the probability that a given problem or algorithm fulfils a needed property. It is most commonly used in such algorithms model where random input is matter.

“In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm.”

1 https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms

To achieve a probabilistic analysis, we must use knowledge of making assumptions about, the distribution or scattering of the inputs. When we analyze our algorithm, calculate an average-case running time, where we take the average for the circulation of our different possible inputs. Thus, we are, in effect, averaging the running time over all possible inputs. When reporting such a running time, we will refer state it as the average-case running time.

The Problems where we can Apply Probabilistic Analysis:

We must be very cautious in deciding on the distribution of inputs. For some problems, we may wisely assume something about the set of all possible inputs, and then we can use probabilistic analysis as a technique for constructing an ef?cient or fast algorithm and as a means for gaining understanding into a problem. For other problems, we cannot describe a sensible input distribution, and in these cases, we can’t deal with the probabilistic analysis.

Randomized Algorithm

An algorithm that uses random input to adopt what to do next everywhere in its logic is called Randomized Algorithm e.g., in Randomized Quick Sort, we use random input to pick the next pivot in the array.

“A randomized algorithm is an algorithm that hires a degree of randomness as part of its logic.”2

https://en.wikipedia.org/wiki/Randomized_algorithm

Randomized Algorithm

To use probabilistic analysis, we need to know something about the distribution of the inputs. In many instances, we know very little about the input distribution. Even if we do know something about the distribution, we may not be able to model this knowledge computationally. Yet we often can use probability and randomness as a tool for algorithm design and analysis, by making the behavior of part of the algorithm random.