Quantifying Chance & Randomness

Before we start this section, I want to take the opportunity to caution readers that it is highly unlikely for both this and the next section to appear in your coding interviews. These sections are for enthusiasts and folks eager to have more of the flavor of the complexity theory. If your intent is preparation for interviews, then the previous sections should be most helpful. That being said, you are more than welcome to continue reading as knowing more is never a disadvantage :)

Probability

This section is a very brief introduction of probability. It's just enough to get the reader up to speed on the knowledge required to understand randomized algorithms and probabilistic analysis. Probability is defined as the likelihood of something happening. The mathematical study of probability describes the ways in which one can quantify the chances of an event taking place.

We start with the text book example of flipping a coin. When we flip a coin, it can land either on its head or its tail. Imagine the coin is unbiased and is equally likely to land either heads or tails. If we want to know what the chances are of the coin landing on its head, we will count the outcomes that result in heads and divide the count by the total number of possible outcomes. In the described scenario, there are only two outcomes possible; we get either heads or tails on a single flip. The list of all possible outcomes is called the sample space, denoted by S.

$$S = { H, T }$$

The sample space S consists of all the possible outcomes of the experiment we are interested in. Note that the events in the sample space are mutually exclusive, meaning that if the flip results in heads then it can't also be tails. If today is Friday then it can't be Sunday at the same time. The days of the week are mutually exclusive.

Note that at least one of the events in the sample space must happen, i.e. the probability

$$P(S) = 1$$

If you flip a coin then either heads or tails must show up.