Randomized Algorithms and Probability

A randomized algorithm is an algorithm that makes at least one decision based upon a random choice, rather than a fixed rule.

At first glance, it may seem surprising (or even unbelievable) that incorporating an element of chance into an algorithm can result in a correct and efficient algorithm, but as we will see in this chapter, there are many situations where randomness is extremely effective.

Randomized algorithms generally depend upon the laws of probability, and therefore before we begin studying randomized algorithms, it makes sense to formally define some of the terms and concepts of probability.

• An experiment is any procedure that can be repeated any number of times, and has a well-defined set of outcomes. (In order to be interesting from a statistical perspective, the result of the procedure is generally not known in advance.)
• An sample outcome (often denoted s) is a member of the set of outcomes of an experiment.
• The sample space (often denoted S) is the complete set of all possible sample outcomes of an experiment.
• An event is any set of sample outcomes. When the outcome of an experiment is a member of this set, the event is said to occur.
• Two events are independent if the occurance of one of the events is not related to the occurance of the other. For example, if we flip a fair coin twice, then the event ``first flip is heads'' is independant of the event ``second flip is heads''. However, the events ``first flip is heads'' and ``first flip is tails'' are not independent, because the occurance of one of these events depends on whether the other has occured. In this case, the correspondance is absolute- but this is not always the case.
• A trial is the actual ``execution'' of an experiment. For example, the procedure of tossing a coin and observing whether the result is heads or tails is an experiment, but the act of actually flipping the coin is a trial.
• A population is the set of all unique trials. This set may be infinite. For example, the population of all coin tosses is infinite, because we can perform as many unique trials as we like by flipping the coin repeatedly. In other situations, the population may be finite- for example, if our experiment is to ask a person enrolled in S-Q whether their last name contains the letter 'e', then the set of unique trials is the set consisting of one trial for each person enrolled in the course.
• A sample is a set of trials. A random sample is a set of trials selected at random from the population.

For example, consider the act of rolling a 6-sided die. The procedure consisting of rolling the die and reporting which face is visible is the experiment; and each time we actually perform this procedure we are performing a trial. We can roll the die as often as we like, and every time we roll the die the outcome (i.e. which side of the die is showing) must be one of the 6 sides. Each possible side of the die is a possible sample outcome, and these six possibilities constitute the entire sample space.

We can define a number of possible events for this experiment- for example, rolling any particular number, or rolling an odd number, or rolling a number less than four.