Chapter 07 - Discrete Probability

Discrete Probability

An Introduction to Discrete Probability

Finite Probability

An experiment is a procedure that yields one of a given set of possible outcomes. The sample space of the experiment is the set of possible outcomes. An event is a subset of the sample space. Laplace’s definition of the probability of an event with finitely many possible outcomes will now be stated.

• Definition : If is a finite nonempty sample space of equally likely outcomes, and is an event, that is, a subset of , then the probability of is .

Probabilities of Complements and Unions of Events

We can use counting techniques to find the probability of events derived from other events.

• Theorem : Let be an event in a sample space . The probability of the event , the complementary event of , is given by
• Theorem : Let and be events in the sample space . Then

Probability Theory

Assigning Probabilities

Let be the sample space of an experiment with a finite or countable number of outcomes. We assign a probability to each outcome . We require that two conditions be met:

• (I) for each and
• (II) .

(Note that when the sample space is infinite, is a convergent infinite series.) This is a generalization of Laplace’s definition in which each of n outcomes is assigned a probability of . Indeed, conditions (I) and (II) are met when Laplace’s definition of probabilities of equally likely outcomes is used and is finite. Note that when there are possible outcomes, , the two conditions to be met are

• (I) for and
• (II) .

The function from the set of all outcomes of the sample space is called a probability distribution. To model an experiment, the probability assigned to an outcome should equal the limit of the number of times occurs divided by the number of times the experiment is performed, because this number grows without bound.

• Definition : Suppose that is a set with elements. The uniform distribution assigns the probability to each element of .
• Definition : The probability of the event is the sum of the probabilities of the outcomes in . That is, (Note that when is an infinite set, is a convergent infinite series.)

Note that the uniform distribution assigns the same probability to an event that Laplace’s original definition of probability assigns to this event. The experiment of selecting an element from a sample space with a uniform distribution is called selecting an element of at random.

• Theorem : If is a sequence of pairwise disjoint events in a sample space , then (Note that this theorem applies when the sequence consists of a finite number or a countably infinite number of pairwise disjoint events.)

Conditional Probability

In general, to find the conditional probability of given , we use as the sample space. For an outcome from to occur, this outcome must also belong to .

• Definition : Let and be events with . The conditional probability of given , denoted by , is defined as

Independence

• Definition : The events and are independent if and only if .

Pairwise and Mutual Independence

• Definition : The events are pairwise independent if and only if for all pairs of integers and with . These events are mutually independent if whenever , are integers with and .

Bernoulli Trials and the Binomial Distribution

Suppose that an experiment can have only two possible outcomes. For instance, when a bit is generated at random, the possible outcomes are and . When a coin is flipped, the possible outcomes are heads and tails. Each performance of an experiment with two possible outcomes is called a Bernoulli trial, after James Bernoulli. In general, a possible outcome of a Bernoulli trial is called a success or a failure. If is the probability of a success and is the probability of a failure, it follows that . Many problems can be solved by determining the probability of successes when an experiment consists of mutually independent Bernoulli trials. (Bernoulli trials are mutually independent if the conditional probability of success on any given trial is , given any information whatsoever about the outcomes of the other trials.)

• Theorem : The probability of exactly successes in independent Bernoulli trials, with probability of success and probability of failure , is .

Random Variables

A random variable is a function from the sample space of an experiment to the set of real numbers. That is, a random variable assigns a real number to each possible outcome.

• Definition : The distribution of a random variable on a sample space is the set of pairs for all , where is the probability that takes the value . The set of pairs in this distribution is determined by the probabilities for .

The Probabilistic Method

• Theorem : The Probabilistic Method If the probability that an element chosen at random from a does not have a particular property is less than , there exists an element in with this property.
• Theorem : If is an integer with , then .

Bayes’ Theorem

• Theorem : Bayes’ Theorem Suppose that and are events from a sample space such that and Then

Generalizing Bayes’ Theorem

Note that in the statement of Bayes’ theorem, the events and are mutually exclusive and cover the entire sample space (that is, ). We can extend Bayes’ theorem to any collection of mutually exclusive events that cover the entire sample space , in the following way.

• Theorem : Generalized Bayes’ Theorem Suppose that is an event from a sample space and that are mutually exclusive events such that . Assume that and for . Then

Expected Value and Variance

The expected value of a random variable is the sum over all elements in a sample space of the product of the probability of the element and the value of the random variable at this element. Consequently, the expected value is a weighted average of the values of a random variable. The expected value of a random variable provides a central point for the distribution of values of this random variable.

• Definition : The expected value, also called the expectation or mean, of the random variable on the sample space is equal to The deviation of at is , the difference between the value of and the mean of .

• Theorem : If is a random variable and is the probability that , so that , then

• Theorem : The expected number of successes when mutually independent Bernoulli trials are performed, where is the probability of success on each trial, is .

Linearity of Expectations

• Theorem : If with a positive integer, are random variables on , and if and are real numbers, then
  • (I) ,
  • (II) .

Average-Case Computational Complexity

Computing the average-case computational complexity of an algorithm can be interpreted as computing the expected value of a random variable. Let the sample space of an experiment be the set of possible inputs and let be the random variable that assigns to the number of operations used by the algorithm when given as input. Based on our knowledge of the input, we assign a probability to each possible input value . Then, the average-case complexity of the algorithm is This is the expected value of .

The Geometric Distribution

We now turn our attention to a random variable with infinitely many possible outcomes.

• Definition : A random variable has a geometric distribution with parameter if for , where is a real number with .
• Theorem : If the random variable has the geometric distribution with parameter , then .

Independent Random Variables

• Definition : The random variables and on a sample space are independent if Or in words, if the probability that and equals the product of the probabilities that and , for all real numbers and .

• Theorem : If and are independent random variables on a sample space , then .

Variance

The expected value of a random variable tells us its average value, but nothing about how widely its values are distributed. However, the random variable never varies from , while the random variable always differs from by . The variance of a random variable helps us characterize how widely a random variable is distributed. In particular, it provides a measure of how widely is distributed about its expected value.

• Definition : Let be a random variable on a sample space . The variance of , denoted by , is That is, is the weighted average of the square of the deviation of . The standard deviation of , denoted , is defined to be .

• Theorem : If is a random variable on a sample space , then .

• Corollary : If is a random variable on a sample space and , then .

• Theorem : Bienaymé’s Formula If and are two independent random variables on a sample space , then . Furthermore, if , with a positive integer, are pairwise independent random variables on , then .

Chebyshev’s Inequality

• Theorem : Chebyshev’s Inequality Let be a random variable on a sample space with probability function . If is a positive real number, then .