Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 5

This chapter introduces probabilistic analysis and randomized algorithms.
The authors define probabilistic analysis as use of probability in the analysis of an algorithm. This is very helpful in finding the average-case behaviour of an algorithm.
A randomized algorithm is defined as an algorithm whose behaviour is defined not only by its input but by values produced by a random-number generator.

The authors then define Indicator Random Variable $I\{A\}$ associated with an event $A$ in a sample space $S$ as follows:
$$ I\{A\} =
\begin{cases}
1 & \text{ if A occurs} \\
0 & \text{ if A does not occur.}
\end{cases}
$$

The author then prove following lemma which shows that the expected value of an indicator random variable associated with an event A is equal to the probability that A occurs:
Given a sample space $ S $ and an event $ A $ in the sample space $ S $, let $ X_A = I\{A\} $. Then $ E[X_A] = Pr\{A\} $.

The authors then try to make distinction between randomized algorithms and probabilistic analysis. Non-randomized algorithms are deterministic, i.e. they generate the same behaviour again and again given the same input. Randomized algorithm's behaviour may vary even if the same algorithm is called many a times with the same input. The authors provide two ways to randomize an algorithm:

1. Randomly generate a priority for each input and sort the inputs in the order of their priority
2. Randomly permute the input array.

The authors then discuss the problem of birthday paradox. How many people must there be in a room so the probability of two having the same birthday (not the year) is 50% or higher. The authors prove that the required number of people is $ \sqrt{\text{Number of Days in Year}} $.

The authors then elaborates on the problem of tossing $n$ balls into $b$ bins. Without proof, the authors answer following problems:

• How many balls fall in a given bin? The expected number of balls that fall in the given bin is $ n/b $.
• How many balls needs to be tossed; on an average; until a given bin contains a ball? The expected number of tosses is $b$.
• How many balls needs to be tossed until every bin contains one ball? The expected number of tosses is $ b \times (\lg b + O(1)) $.

The authors then discuss the problem of getting the longest streak of heads while flipping a fair coin. The authors prove that in a series of n flips, the expected length of the longest streak of heads is $ \Theta (n) $.

The authors then discuss one more randomized algorithm of hiring a candidate.