Probabilistic Analysis of Algorithms

Probability Theory has always been one area of study that has made more than its fair share of students cringe. However, its importance in the field of Computer Science, especially Algorithm Design and Artificial Intelligence cannot be emphasized enough.

Here’s a question I recently encountered as part of my selection process as an Intern for Microsoft: Consider Randomized QuickSort for a set of ‘n’ numbers. What is the probability that we always get the worst-case scenario for this algorithm?

Now you may want to try this on your own first as it is deceptively simple.

Here’s the solution: By the analysis and design of QuickSort, we get the worst-case scenario when we select either the least or greatest element in the array of n numbers, as the pivot. Thus the probability for n numbers is 2/n. Now we take the remaining n-1 numbers (Divide and Conquer) and similarly the worst-case is obtained when we select the first or last element. Thus the new probability is 2/(n-1). This continues on until we have just 2 elements left, which then gives the probability of 2/2.

Here’s the smart part: When we analyze Randomized QuickSort, we notice that the selection of the pivot in the recurrence is independent of the pivot selection in the outer equation. Thus, since the probabilities are independent, we can multiply all our earlier probabilities to give us [ 2/n * 2/(n-1) * 2/(n-2) *…* 2/2 ] = [ 2^(n-1)/n! ] (The n-1 as we have n-1 2s in the numerator) .

And thus we have the answer!! Pretty simple, huh? All we needed to know was what is the worst-case criteria for QuickSort and that pivot selection is independent of the pivot selection in the recurrence.

Similarly, probability theory plays a big part in Bayes Networks, which are essentially Probability Distributions in a graph, which is a core topic in AI. Knowing about total probability, Joint Probability and Bayes Rule really helps in the inference of Bayes Nets. Combine that with Variable Independence, Explaining Away Effect and Enumeration and you’ve got yourself a Smart System.

Just because all this seems simple, doesn’t necessarily mean Probability theory is simple. It does tend to get a tad bit confusing at times, but with ample practice, one should find himself/herself being able to predict the future!

Eviva!