Chapter 4

Random Variables
A first Course in Probability
Prof. Hsin-Lung Wu
 4.1 Random variables
• Frequently, when an experiment is performed, we are
interested mainly in some function of the outcome as
opposed to the actual outcome itself.
• For instance, in tossing dice, we are often interested
in the sum of the two dice and are not really
concerned about the separate values of each die.
• That is, we may be interested in knowing that the sum
is 7 and may not be concerned over whether the
actual outcome was (1, 6), (2, 5), (3, 4), (4, 3), (5, 2),
or (6, 1).
 4.1 Random variables
• In flipping a coin, we may be interested in the total
number of heads that occur and not care at all about
the actual head–tail sequence that results.
• These quantities of interest, or, more formally, these
real-valued functions defined on the sample space,
are known as random variables.
 4.1 Random variables
• EXAMPLE 1a
• Suppose that our experiment consists of tossing 3 fair
coins. If we let Y denote the number of heads that
appear, then Y is a random variable taking on one of
the values 0, 1, 2, and 3 with respective probabilities
• P{Y = 0} = P{(T, T, T)} = 1/8
• P{Y = 1} = P{(T, T,H), (T,H, T), (H, T, T)} = 3/8
• P{Y = 2} = P{(T,H,H), (H, T,H), (H,H, T)} = 3/8
• P{Y = 3} = P{(H,H,H)} = 1/8
 4.1 Random variables
• EXAMPLE 1b
• Three balls are to be randomly selected without
replacement from an urn containing 20 balls numbered 1
through 20. If we bet that at least one of the balls that are
drawn has a number as large as or larger than 17, what is
the probability that we win the bet?
 4.1 Random variables
• Solution. Let X denote the largest number selected. Then
X is a random variable taking on one of the values 3, 4, . . .
, 20. Furthermore, if we suppose that each of the
possible selections are equally likely to occur, then
 4.1 Random variables
• EXAMPLE 1c
• Independent trials consisting of the flipping of a coin
having probability p of coming up heads are continually
performed until either a head occurs or a total of n flips is
made. If we let X denote the number of times the coin is
flipped, then X is a random variable taking on one of the
values 1, 2, 3, . . . , n with respective probabilities
4.1 Random variables
 4.1 Random variables
• As a check, note that
 4.1 Random variables
• EXAMPLE 1e
• Suppose that there are N distinct types of coupons and that
each time one obtains a coupon, it is, independently of
previous selections, equally likely to be any one of the N
types. One random variable of interest is T, the number of
coupons that needs to be collected until one obtains a
complete set of at least one of each type. Rather than
derive P{T = n} directly, let us start by considering the
probability that T is greater than n.
 4.1 Random variables
• To do so, fix n and define the events A1,A2, . . . ,AN as
follows: Aj is the event that no type j coupon is contained
among the first n coupons collected, j = 1, . . . ,N.
• Hence,
 4.1 Random variables
• Now, Aj will occur if each of the n coupons collected is not
of type j. Since each of the coupons will not be of type j
with probability (N − 1)/N, we have, by the assumed
independence of the types of successive coupons,

• Also, the event Aj1Aj2 will occur if none of the first n

coupons collected is of either type j1 or type j2.
• Thus, again using independence, we see that
 4.1 Random variables
• The same reasoning gives
• and we see that, for n > 0,

• The probability that T equals n can now be obtained from

the preceding formula by the use of
P{T = n} = P{T > n − 1} − P{T > n}
 4.1 Random variables
• Another random variable of interest is the number of
distinct types of coupons that are contained in the first n
selections—call this random variable Dn.
• To compute P{Dn = k}, let us start by fixing attention on a
particular set of k distinct types, and let us then determine
the probability that this set constitutes the set of distinct
types obtained in the first n selections.
 4.1 Random variables
• Now, in order for this to be the situation, it is necessary
and sufficient that, of the first n coupons obtained,
• A: each is one of these k types.
• B: each of these k types is represented.
• We have
 4.1 Random variables
• Finally, as there are possible choices for the set of k
types, we arrive at
 4.1 Random variables
• For a random variable X, the function F defined by
F(x) = P{X  x}, − < x < 
is called the cumulative distribution function, or, more
simply, the distribution function, of X.
• Thus, the distribution function specifies, for all real values
x, the probability that the random variable is less than or
equal to x.
 4.1 Random variables
• Now, suppose that a  b. Then, because the event {X  a}
is contained in the event {X  b}, it follows that F(a), the
probability of the former, is less than or equal to F(b), the
probability of the latter.
• In other words, F(x) is a nondecreasing function of x.
 4.2 Discrete random variables
• A random variable that can take on at most a countable
number of possible values is said to be discrete.
• For a discrete random variable X, we define the
probability mass function p(a) of X by p(a) = P{X = a}
• The probability mass function p(a) is positive for at most a
countable number of values of a.
• That is, if X must assume one of the values x1, x2, . . . ,
then p(xi)  0 fori = 1, 2, . . . and p(x) = 0 for all other
values of x.
 4.2 Discrete random variables
• It is often instructive to present the probability mass
function in a graphical format by plotting p(xi) on the y-
axis against xi on the x-axis.
• For instance, if the probability mass function of X is p(0)
=1/4, p(1) = ½ , p(2) = ¼ .
 4.2 Discrete random variables
• EXAMPLE 2a
• The probability mass function of a random variable X is
given by p(i) = cλi/i!, i = 0, 1, 2, . . . , where λ is some
positive value.
• Find (a) P{X = 0} and (b) P{X > 2}.
 4.2 Discrete random variables
• Solution. Since , we have
which, because , implies that
• ceλ =1 or c = e−λ.
• Hence,
 4.2 Discrete random variables
• The cumulative distribution function F can be expressed in
terms of p(a) by
• If X is a discrete random variable whose possible values
are x1, x2, x3, . . . , where x1 < x2 < x3 < · · · , then the
distribution function F of X is a step function.
• That is, the value of F is constant in the intervals [xi−1, xi)
and then takes a step (or jump) of size p(xi) at xi.
 4.2 Discrete random variables
• For instance, if X has a probability mass function given by
• p(1) = ¼ , p(2) = ½ , p(3) = 1/8, p(4) = 1/8, then its
cumulative distribution function is
 4.3 Expected value
• One of the most important concepts in probability theory
is that of the expectation of a random variable.
• If X is a discrete random variable having a probability
mass function p(x), then the expectation, or the expected
value, of X, denoted by E[X], is defined by
 4.3 Expected value
• Another motivation of the definition of expectation is
provided by the frequency interpretation of probabilities.
• This interpretation assumes that if an infinite sequence of
independent replications of an experiment is performed,
then, for any event E, the proportion of time that E occurs
will be P(E).
• Now, consider a random variable X that must take on one
of the values x1, x2, . . . xn with respective probabilities
p(x1), p(x2), . . . , p(xn), and think of X as representing our
winnings in a single game of chance.
 4.3 Expected value
• That is, with probability p(xi) we shall win xi units i = 1, 2,
. . . , n.
• By the frequency interpretation, if we play this game
continually, then the proportion of time that we win xi will
be p(xi).
• Since this is true for all i, i = 1, 2, . . . , n, it follows that
our average winnings per game will be
 4.3 Expected value
• EXAMPLE 3a
• Find E[X], where X is the outcome when we roll a fair die.
• Solution. Since p(1) = p(2) = p(3) = p(4) = p(5) = p(6) =
1/6, we obtain
 4.3 Expected value
• EXAMPLE 3b
• We say that I is an indicator variable for the event A if

• Find E[I].
• Solution. Since p(1) = P(A), p(0) = 1 − P(A), we have
• E[I] = P(A)
• That is, the expected value of the indicator variable for the
event A is equal to the probability that A occurs.
 4.4 Expectation of a function of a
random variable
• Suppose that we are given a discrete random variable
along with its probability mass function and that we want
to compute the expected value of some function of X, say,
g(X).
 4.4 Expectation of a function of a
random variable
• EXAMPLE 4a
• Let X denote a random variable that takes on any of the
values −1, 0, and 1 with respective probabilities P{X =
−1} = .2 P{X = 0} = .5 P{X = 1} = .3
• Compute E[X2].
 4.4 Expectation of a function of a
random variable
• Solution. Let Y = X2. Then the probability mass function
of Y is given by
• P{Y = 1} = P{X = −1} + P{X = 1} = .5
• P{Y = 0} = P{X = 0} = .5
• Hence, E[X2] = E[Y] = 1(.5) + 0(.5) = .5

• Note that .5 = E[X2]  (E[X])2 = .01

 4.4 Expectation of a function of a
random variable
• Proposition 4.1.
• If X is a discrete random variable that takes on one of the
values xi, i  1, with respective probabilities p(xi), then, for
any real-valued function g, E[g(X)] = i g(xi)p(xi)
 4.4 Expectation of a function of a
random variable
• Before proving this proposition, let us check that it is in
accord with the results of Example 4a.
• Applying it to that example yields
• E{X2} = (−1)2(.2) + 02(.5) + 12(.3)
• = 1(.2 + .3) + 0(.5)
• = .5
 4.4 Expectation of a function of a
random variable
• Proof of Proposition 4.1: Suppose that yj, j  1, represent
the different values of g(xi), i  1.
• Then, grouping all the g(xi) having the same value gives
 4.4 Expectation of a function of a
random variable
• EXAMPLE 4c Utility
• Suppose that you must choose one of two possible actions,
each of which can result in any of n consequences,
denoted as C1, . . . ,Cn. Suppose that if the first action is
chosen, then consequence Ci will result with probability pi,
i = 1, . . . , n, whereas if the second action is chosen, then
consequence Ci will result with probability qi, i = 1, . . ., n,
where i pi = i qi = 1.
 4.4 Expectation of a function of a
random variable
• The following approach can be used to determine which
action to choose:
• First, identify the least and the most desirable
consequences—call them c and C, respectively; give
consequence c the value 0 and give C the value 1.
• Consider any of the other n − 2 consequences, say, Ci.
 4.4 Expectation of a function of a
random variable
• To value this consequence, imagine that you are given the
choice between either receiving Ci or taking part in a
random experiment that either earns you consequence C
with probability u or consequence c with probability 1 − u.

• Your choice will depend on the value of u.

 4.4 Expectation of a function of a
random variable
• On the one hand, if u = 1, then the experiment is certain to
result in consequence C, and since C is the most desirable
consequence, you will prefer participating in the
experiment to receiving Ci.
• On the other hand, if u = 0, then the experiment will result
in the least desirable consequence c — so in this case you
will prefer the consequence Ci to participating in the
experiment.
 4.4 Expectation of a function of a
random variable
• As u decreases from 1 to 0, it seems reasonable that your
choice will at some point switch from participating in the
experiment to the certain return of Ci, and at that critical
switch point you will be indifferent between the two
alternatives.
• Take that indifference probability u as the value of the
consequence Ci.
Consequence C1 =C C2 C3 … Cn-2 Cn-1 Cn = c
Value 1 u(C2) u(C3) u(Cn-2) u(Cn-1) 0

Can be computed from C1,C2,…,Cn without pi’s and qi’s.

 4.4 Expectation of a function of a
random variable
• In other words, the value of Ci is that probability u such
that you are indifferent between either receiving the
consequence Ci or taking part in an experiment that returns
consequence C with probability u or consequence c with
probability 1 − u.
• We call this indifference probability the utility of the
consequence Ci, and we designate it as u(Ci).
 4.4 Expectation of a function of a
random variable
• To determine which action is superior, we need to evaluate
each one.
• Consider the first action, which results in consequence Ci
with probability pi, i = 1, . . . , n.
• We can think of the result of this action as being
determined by a two-stage experiment.
• In the first stage, one of the values 1, . . . , n is chosen
according to the probabilities p1, . . . , pn; if value i is
chosen, you receive consequence Ci.
 4.4 Expectation of a function of a
random variable
• However, since Ci is equivalent to obtaining consequence
C with probability u(Ci) or consequence c with probability
1 − u(Ci), it follows that the result of the two-stage
experiment is equivalent to an experiment in which either
consequence C or consequence c is obtained, with C being
obtained with probability
 4.4 Expectation of a function of a
random variable
• Similarly, the result of choosing the second action is
equivalent to taking part in an experiment in which either
consequence C or consequence c is obtained, with C being
obtained with probability

• Since C is preferable to c, it follows that the first action is

preferable to the second action if
 4.4 Expectation of a function of a
random variable
• In other words, the worth of an action can be measured by
the expected value of the utility of its consequence, and
the action with the largest expected utility is the most
preferable.
 4.4 Expectation of a function of a
random variable
• Corollary 4.1. If a and b are constants, then
E[aX + b] = aE[X] + b

• Proof.
 4.4 Expectation of a function of a
random variable
• The expected value of a random variable X, E[X], is also
referred to as the mean or the first moment of X.
• The quantity E[Xn], n  1, is called the nth moment of X.

• By Proposition 4.1, we note that

 4.5 Variance
• Although E[X] yields the weighted average of the possible
values of X, it does not tell us anything about the variation.
• For instance, although random variables W, Y, and Z
having probability mass functions determined by
 4.5 Variance
• All have the same expectation 0.
• Because we expect X to take on values around its mean
E[X], it would appear that a reasonable way of measuring
the possible variation of X would be to look at how far
apart X would be from its mean, on the average.
• One possible way to measure this variation would be to
consider the quantity E[|X − μ|], where μ = E[X].
 4.5 Variance
• However, it turns out to be mathematically inconvenient to
deal with this quantity, so a more tractable quantity is
usually considered—namely, the expectation of the square
of the difference between X and its mean.
• Definition
• If X is a random variable with mean μ, then the variance of
X, denoted by Var(X), is defined by Var(X) = E[(X − μ)2]
 4.5 Variance
• An alternative formula for Var(X) is derived as follows:
 4.5 Variance
• EXAMPLE 5a
• Calculate Var(X) if X represents the outcome when a fair
die is rolled.
• Solution. It was shown that E[X] = 7/2.
• Also,

• Hence, Var(X) = 91/6 – (7/2)2 = 35/12.

 4.5 Variance
• A useful identity is that, for any constants a and b,
• Var(aX + b) = a2Var(X)
• Proof: Let μ = E[X].
• E[aX + b] = aμ + b. Therefore,
• Var(aX + b) = E[(aX + b − aμ − b)2]
• = E[a2(X − μ)2]
• = a2E[(X − μ)2]
• = a2Var(X)
 4.5 Variance
• The square root of the Var(X) is called the standard
deviation of X, and we denote it by SD(X).
• That is,
 4.6 The Bernoulli and Binomial
random variables
• Suppose that a trial, or an experiment, whose outcome can
be classified as either a success or a failure is performed.
• If we let X = 1 when the outcome is a success and X = 0
when it is a failure, then the probability mass function of X
is given by
• p(0) = P{X = 0} = 1 − p
• p(1) = P{X = 1} = p (6.1)
• where p, 0 … p … 1, is the probability that the trial is a
success.
 4.6 The Bernoulli and Binomial
random variables
• A random variable X is said to be a Bernoulli random
variable if its probability mass function is given by
Equations (6.1) for some p ∈ (0, 1).
 4.6 The Bernoulli and Binomial
random variables
• Suppose now that n independent trials, each of which
results in a success with probability p and in a failure with
probability 1 − p, are to be performed.
• If X represents the number of successes that occur in the n
trials, then X is said to be a binomial random variable with
parameters (n, p). Thus, a Bernoulli random variable is
just a binomial random variable with parameters (1, p).
 4.6 The Bernoulli and Binomial
random variables
• The probability mass function of a binomial random
variable having parameters (n, p) is given by
 4.6 The Bernoulli and Binomial
random variables
• EXAMPLE 6a
• Five fair coins are flipped. If the outcomes are assumed
independent, find the probability mass function of the
number of heads obtained.
• Solution. If we let X equal the number of heads
(successes) that appear, then X is a binomial random
variable with parameters n = 5, p = 12.
 4.6 The Bernoulli and Binomial
random variables
• Hence, by Equation (6.2),
 4.6 The Bernoulli and Binomial
random variables
• EXAMPLE 6b
• It is known that screws produced by a certain company
will be defective with probability .01, independently of
each other. The company sells the screws in packages of
10 and offers a money-back guarantee that at most 1 of the
10 screws is defective. What proportion of packages sold
must the company replace?
 4.6 The Bernoulli and Binomial
random variables
• Solution. If X is the number of defective screws in a
package, then X is a binomial random variable with
parameters (10, .01).
• Hence, the probability that a package will have to be
replaced is

• Thus, only .4 percent of the packages will have to be

replaced.
 4.6 The Bernoulli and Binomial
random variables
• EXAMPLE 6e
• Consider a jury trial in which it takes 8 of the 12 jurors to
convict the defendant; that is, in order for the defendant to
be convicted, at least 8 of the jurors must vote him guilty.
If we assume that jurors act independently and that,
whether or not the defendant is guilty, each makes the
right decision with probability θ, what is the probability
that the jury renders a correct decision?
 4.6 The Bernoulli and Binomial
random variables
• Solution. The problem, as stated, is incapable of solution,
for there is not yet enough information. For instance, if the
defendant is innocent, the probability of the jury’s
rendering a correct decision is

• whereas, if he is guilty, the probability of a correct

decision is
 4.6 The Bernoulli and Binomial
random variables
• Therefore, if α represents the probability that the
defendant is guilty, then, by conditioning on whether or
not he is guilty, we obtain the probability that the jury
renders a correct decision:
 4.6 The Bernoulli and Binomial
random variables
• EXAMPLE 6f
• A communication system consists of n components, each
of which will, independently, function with probability p.
The total system will be able to operate effectively if at
least one-half of its components function.
• (a) For what values of p is a 5-component system more
likely to operate effectively than a 3-component system?
• (b) In general, when is a (2k + 1)-component system better
than a (2k − 1)-component system?
 4.6 The Bernoulli and Binomial
random variables
• Solution. (a) Because the number of functioning
components is a binomial random variable with
parameters (n, p), it follows that the probability that a 5-
component system will be effective is

• whereas the corresponding probability for a 3-component

system is
 4.6 The Bernoulli and Binomial
random variables
• Hence, the 5-component system is better if
10p3(1 − p)2 + 5p4(1 − p) + p5 > 3p2(1 − p) + p3
which reduces to p>1/2.

• (b) In general, a system with 2k + 1 components will be

better than one with 2k − 1 components if (and only if) p >
1/2.
• To prove this, consider a system of 2k + 1 components and
let X denote the number of the first 2k − 1 that function.
 4.6 The Bernoulli and Binomial
random variables

• which follows because the (2k + 1)-component system will

be effective if either (i) X  k + 1;
• (ii) X = k and at least one of the remaining 2 components
function; or
• (iii) X = k − 1 and both of the next 2 components function.
 4.6 The Bernoulli and Binomial
random variables
• Since

• we obtain
 4.6 The Bernoulli and Binomial
random variables
• 4.6.1 Properties of Binomial Random Variables
• We will now examine the properties of a binomial random
variable with parameters n and p.
• To begin, let us compute its expected value and variance.
Now,
 4.6 The Bernoulli and Binomial
random variables

• where Y is a binomial random variable with parameters n

− 1, p.
• Setting k = 1 in the preceding equation yields E[X] = np.
 4.6 The Bernoulli and Binomial
random variables
• Setting k = 2 in the preceding equation, and using the
preceding formula for the expected value of a binomial
random variable yields

• Since E[X] = np, we obtain

Var(X) = E[X2] − (E[X])2
• = np[(n − 1)p + 1] − (np)2
• = np(1 − p)
 4.6 The Bernoulli and Binomial
random variables
• Summing up, we have shown the following:
• If X is a binomial random variable with parameters n and
p, then
• E[X] = np
• Var(X) = np(1 − p)
 4.6 The Bernoulli and Binomial
random variables
• Proposition 6.1. If X is a binomial random variable with
parameters (n, p), where 0 < p < 1, then as k goes from 0
to n, P{X = k} first increases monotonically and then
decreases monotonically, reaching its largest value when k
is the largest integer less than or equal to (n + 1)p.
 4.6 The Bernoulli and Binomial
random variables
• Proof. We prove the proposition by considering P{X =
k}/P{X = k − 1} and determining for what values of k it is
greater or less than 1. Now,
 4.6 The Bernoulli and Binomial
random variables
• Hence, P{X = k}  P{X = k − 1} if and only if
(n − k + 1)p  k(1 − p) or, equivalently, if and only if
k  (n + 1)p and the proposition is proved.
 4.6 The Bernoulli and Binomial
random variables
• 4.6.2 Computing the Binomial Distribution Function
• Suppose that X is binomial with parameters (n, p). The key
to computing its distribution function

• is to utilize the following relationship between

P{X = k + 1} and P{X = k}, which was established in the
proof of Proposition 6.1:
 4.6 The Bernoulli and Binomial
random variables
• EXAMPLE 6h
• Let X be a binomial random variable with parameters n =
6, p = .4. Then, starting with P{X = 0} = (.6)6 and
recursively employing Equation (6.3), we obtain
 4.7 The Poisson random variables
• A random variable X that takes on one of the values 0, 1,
2, . . . is said to be a Poisson random variable with
parameter λ if, for some λ > 0,

• Equation (7.1) defines a probability mass function, since

 4.7 The Poisson random variables
• The Poisson random variable has a tremendous range of
applications in diverse areas because it may be used as an
approximation for a binomial random variable with
parameters (n, p) when n is large and p is small enough so
that np is of moderate size.
 4.7 The Poisson random variables
• To see this, suppose that X is a binomial random variable
with parameters (n, p), and let λ = np. Then

• Now, for n large and λ moderate,

 4.7 The Poisson random variables
• Hence, for n large and λ moderate,
• In other words, if n independent trials, each of which
results in a success with probability p, are performed, then,
when n is large and p is small enough to make np
moderate, the number of successes occurring is
approximately a Poisson random variable with parameter λ
= np.
• This value λ (which will later be shown to equal the
expected number of successes) will usually be determined
empirically.
 4.7 The Poisson random variables
• Some examples of random variables that generally obey
the Poisson probability are as follows:
1. The number of misprints on a page (or a group of pages)
of a book
2. The number of people in a community who survive to age
100
 4.7 The Poisson random variables
• Each of the preceding, and numerous other random
variables, are approximately Poisson for the same
reason—namely, because of the Poisson approximation to
the binomial.
• For instance, we can suppose that there is a small
probability p that each letter typed on a page will be
misprinted.
• Hence, the number of misprints on a page will be
approximately Poisson with λ = np, where n is the number
of letters on a page.
 4.7 The Poisson random variables
• EXAMPLE 7a
• Suppose that the number of typographical errors on a
single page of this book has a Poisson distribution with
parameter λ = 1/2. Calculate the probability that there is at
least one error on this page.
 4.7 The Poisson random variables
• Solution. Letting X denote the number of errors on this
page, we have
 4.7 The Poisson random variables
• EXAMPLE 7b
• Suppose that the probability that an item produced by a
certain machine will be defective is .1. Find the probability
that a sample of 10 items will contain at most 1 defective
item.
 4.7 The Poisson random variables
• Solution. The desired probability is

• whereas the Poisson approximation yields the value e−1 +

e−1  0.7358.
 4.7 The Poisson random variables
• EXAMPLE 7c
• Consider an experiment that consists of counting the
number of α particles given off in a 1-second interval by 1
gram of radioactive material. If we know from past
experience that, on the average, 3.2 such α particles are
given off, what is a good approximation to the probability
that no more than 2 α particles will appear?
 4.7 The Poisson random variables
• Solution. If we think of the gram of radioactive material as
consisting of a large number n of atoms, each of which has
probability of 3.2/n of disintegrating and sending off an α
particle during the second considered, then we see that, to
a very close approximation, the number of α particles
given off will be a Poisson random variable with
parameter λ = 3.2. Hence, the desired probability is
 4.7 The Poisson random variables
• Before computing the expected value and variance of the
Poisson random variable with parameter λ, recall that this
random variable approximates a binomial random variable
with parameters n and p when n is large, p is small, and λ
= np.
• Since such a binomial random variable has expected value
np = λ and variance np(1 − p) =λ(1 − p)  λ (since p is
small), it would seem that both the expected value and the
variance of a Poisson random variable would equal its
parameter λ.
 4.7 The Poisson random variables
• We now verify this result:
 4.7 The Poisson random variables
• Since we have shown that E[X] = λ, we obtain
Var(X) = E[X2] − (E[X])2 = λ
• Hence, the expected value and variance of a Poisson
random variable are both equal to its parameter λ.
 4.7 The Poisson random variables
• Poisson distribution with parameter np is a very good
approximation to the distribution of the number of
successes in n independent trials when each trial has
probability p of being a success, provided that n is large
and p small.
• It remains a good approximation even when the trials are
not independent, provided that their dependence is weak.
 4.7 The Poisson random variables
• The matching problem (Example 5m of Chapter 2) in
which n men randomly select hats from a set consisting of
one hat from each person.
• From the point of view of the number of men who select
their own hat, we may regard the random selection as the
result of n trials where we say that trial i is a success if
person i selects his own hat, i = 1, . . . , n.
• Defining the events Ei, i = 1, . . . , n, by
Ei = {trial i is a success}
 4.7 The Poisson random variables
• It is easy to see that
P{Ei} = 1/n and P{Ei|Ej} = 1/(n − 1), j  i.
• Thus, we see that, although the events Ei, i = 1, . . . , n are
not independent, their dependence, for large n, appears to
be weak.
• Because of this it seems reasonable to expect that the
number of successes will approximately have a Poisson
distribution with parameter n * 1/n = 1, and indeed this is
verified in Example 5m of Chapter 2.
 4.7 The Poisson random variables
• The birthday problem in Example 5i of Chapter 2.
• We suppose that each of n people is equally likely to have
any of the 365 days of the year as his or her birthday, and
the problem is to determine the probability that a set of n
independent people all have different birthdays.
• A combinatorial argument was used to determine this
probability, which was shown to be less than ½ when n =
23.
 4.7 The Poisson random variables
• We can approximate the preceding probability by using
the Poisson approximation as follows:
• We have a trial for each of the pairs of individuals i
and j, i  j, and say that trial i, j is a success if persons i
and j have the same birthday.
• If we let Eij denote the event that trial i, j is a success, then,
whereas the events Eij, 1 … i < j … n, are not
independent (see Theoretical Exercise 21), their
dependence appears to be rather weak.
 4.7 The Poisson random variables
• Since P(Eij) = 1/365, it is reasonable to suppose that the
number of successes should approximately have a Poisson
distribution with mean = n(n − 1)/730.
• Therefore,

• To determine the smallest integer n for which this

probability is less than 1/2, note that
 4.7 The Poisson random variables
• Since P(Eij) = 1/365, it is reasonable to suppose that the
number of successes should approximately have a Poisson
distribution with mean = n(n − 1)/730.
• Therefore,

• To determine the smallest integer n for which this

probability is less than 1/2, note that
• It yields the solution n = 23.
 4.7 The Poisson random variables
• We want the probability that, among the n people, no 3 of
them have their birthday on the same day.
• Whereas this now becomes a difficult combinatorial
problem, it is a simple matter to obtain a good
approximation.
• Imagine that we have a trial for each of the triplets i,
j, k, where 1 … i < j < k … n, and call the i, j, k trial a
success if persons i, j, and k all have their birthday on the
same day.
 4.7 The Poisson random variables
• As before, we can then conclude that the number of
successes is approximately a Poisson random variable with
parameter

• Hence,
 4.7 The Poisson random variables
• This probability will be less than ½ when n is such that
• n(n − 1)(n − 2)  799350 log 2  554067.1 which is
equivalent to n  84.
• Thus, the approximate probability that at least 3 people in
a group of size 84 or larger will have the same birthday
exceeds 1/2.
 4.7 The Poisson random variables
• For the number of events to occur to approximately have a
Poisson distribution, it is not essential that all the events
have the same probability of occurrence, but only that all
of these probabilities be small.
• The following is referred to as the Poisson paradigm.
 4.7 The Poisson random variables
• Poisson Paradigm. Consider n events, with pi equal to the
probability that event i occurs, i = 1, . . . , n.
• If all the pi are “small” and the trials are either independent
or at most “weakly dependent,” then the number of these
events that occur approximately has a Poisson distribution
with mean
 4.7 The Poisson random variables
• EXAMPLE 7d Length of the longest run
• A coin is flipped n times. Assuming that the flips are
independent, with each one coming up heads with
probability p, what is the probability that there is a string
of k consecutive heads?
 4.7 The Poisson random variables
• Solution. We will first use the Poisson paradigm to
approximate this probability.
• Now, if, for i = 1, . . . , n − k + 1, we let Hi denote the
event that flips i, i + 1, . . . , i +k − 1 all land on heads, then
the desired probability is that at least one of the events Hi
occur.
• Because Hi is the event that, starting with flip i, the next k
flips all land on heads, it follows that P(Hi) = pk.
 4.7 The Poisson random variables
• Thus, when pk is small, we might think that the number of
the Hi that occur should have an approximate Poisson
distribution.
• However, such is not the case, because, although the
events all have small probabilities, some of their
dependencies are too great for the Poisson distribution to
be a good approximation.
 4.7 The Poisson random variables
• For instance, because the conditional probability that flips
2, . . . , k + 1 are all heads given that flips 1, . . . , k are all
heads is equal to the probability that flip k + 1 is a head, it
follows that P(H2|H1) = p which is far greater than the
unconditional probability of H2.

• H1: HHHHHHHHHHHHHHH High dependence!

• H2: HHHHHHHHHHHHHHH Need new analysis!
 4.7 The Poisson random variables
• Note that there will be a string of k consecutive heads
either if there is such a string that is immediately followed
by a tail or if the final k flips all land on heads.
• Consequently, for i = 1, . . . , n − k, let Ei be the event that
flips i, . . . , i + k − 1 are all heads and flip i + k is a tail;
also, let En−k+1 be the event that flips n − k + 1, . . . , n are
all heads.
• E1: HHHHHHHHHHHHHHHT
• E2: HHHHHHHHHHHHHHHT
• En-k+1: HHHHHHHHHHHHHHH
 4.7 The Poisson random variables
• When pk is small, each of the events Ei has a small
probability of occurring.
• Moreover, for i  j, if the events Ei and Ej refer to
nonoverlapping sequences of flips, then P(Ei|Ej) = P(Ei); if
they refer to overlapping sequences, then P(Ei|Ej) = 0.

• Ei: HHHHHHHHHHHHHHHT Overlap!

• Ej: HHHHHHHHHHHHHHHT
• EiEj is impossible!
 4.7 The Poisson random variables
• Hence, in both cases, the conditional probabilities are
close to the unconditional ones, indicating that N, the
number of the events Ei that occur, should have an
approximate Poisson distribution with mean
 4.7 The Poisson random variables
• There will not be a run of k heads if and only if N = 0, thus
the preceding gives
 4.7 The Poisson random variables
• If we let Ln denote the largest number of consecutive
heads in the n flips, then, because Ln will be less than k if
(and only if) there are no head strings of length k, the
preceding equation can be written as

• Suppose that p = 1/2. Then the preceding gives

 4.7 The Poisson random variables
• Let j = log2n, and assume that j is an integer.
• For k = j + i,

• which implies that

 4.7 The Poisson random variables
• For instance,
 4.7 The Poisson random variables
• We now derive an exact expression for the probability that
there is a string of k consecutive heads when a coin that
lands on heads with probability p is flipped n times.
• With the events Ei, i = 1, . . . , n − k + 1, as defined earlier,
and with Ln denoting, as before, the length of the longest
run of heads,
 4.7 The Poisson random variables
• The inclusion–exclusion identity for the probability of a
union can be written as

• Let Si denote the set of flip numbers to which the event Ei

refers. (for instance, S1 = {1, . . . , k + 1}.)
• Now, consider one of the r-way intersection probabilities
that does not include the event En−k+1.
 4.7 The Poisson random variables
• That is, consider P(Ei1· · ·Eir ) where i1 < · · <ir < n−k+1.
• On the one hand, if there is any overlap in the sets Si1,..,Sir
then this probability is 0.
• On the other hand, if there is no overlap, then the events
Ei1,..,Eir are independent.
• Therefore,
 4.7 The Poisson random variables
• Determine the number of different choices of
i1<…<ir<n−k+1 for which there is no overlap in the sets
Si1,.., Sir.
• To do so, note first that each of the Sij , j = 1, . . . , r, refer
to k + 1 flips, so, without any overlap, they together refer
to r(k + 1) flips.
• Now consider any permutation of r identical letters a (one
for each of the sets Si1,.., Sir-1. ) and of n − r(k + 1)
identical letters b (one for each of the trials that are not
part of any of Si1,.., Sir-1, Sn−k+1).
 4.7 The Poisson random variables
• Interpret the number of b’s before the first a as the number
of flips before Si1, the number of b’s between the first and
second a as the number of flips between Si1 and Si2 , and so
on, with the number of b’s after the final a representing
the number of flips after Sir.
• <Si1> <Si2> <Si3> <Si4> <Sir>
bbbbbbbabbbbbbbabbbbbbabbbbbabbb……abbbbbbbb
 4.7 The Poisson random variables
• <Si1> <Si2> <Si3> <Si4> <Sir>
bbbbbbbabbbbbbbabbbbbbabbbbbabbb……abbbbbbbb

• Because there are permutations of r letters a and of

n − r(k + 1) letters b, with every such permutation
corresponding (in a one-to-one fashion) to a different
nonoverlapping choice, it follows that
 4.7 The Poisson random variables
• Next, consider r-way intersection probabilities of the form
P(Ei1· · ·Eir−1En−k+1), where i1 <…< ir−1 < n − k + 1.

• Now, this probability will equal 0 if there is any overlap in

Si1,…,Sir−1,Sn−k; if there is no overlap, then the events of
the intersection will be independent, so
 4.7 The Poisson random variables
• By a similar argument as before, the number of
nonoverlapping sets Si1,…,Sir−1,Sn−k will equal the number
of permutations of r − 1 letters a (one for each of the sets
Si1,…,Sir−1) and of n − (r − 1)(k + 1) − k = n − rk − (r − 1)
letters b (one for each of the trials that are not part of any
of Si1,…,Sir−1,Sn−k ).
• <Si1> <Si2> <Si3> <Si4> <Sir-1> <Sn-k>
bbbbbbbabbbbbbbabbbbbbabbbbbabbb……abbbbbbbba
 4.7 The Poisson random variables
• <Si1> <Si2> <Si3> <Si4> <Sir-1> <Sn-k>
bbbbbbbabbbbbbbabbbbbbabbbbbabbb……abbbbbbbba
• Since there are permutations of r − 1 letters a and
of n − rk − (r − 1) letters b, we have

• Putting it all together yields the exact expression, namely,

 4.7 The Poisson random variables
• From a computational point of view, a more efficient
method for computing the desired probability than the use
of the preceding identity is to derive a set of recursive
equations.
• To do so, let An be the event that there is a string of k
consecutive heads in a sequence of n flips of a fair coin,
and let Pn = P(An).
• We will derive a set of recursive equations for Pn by
conditioning on when the first tail appears.
 4.7 The Poisson random variables
• For j = 1, . . . , k, let Fj be the event that the first tail
appears on flip j, and let H be the event that the first k flips
are all heads.
• Because the events F1, . . . , Fk, H are mutually exclusive
and exhaustive (that is, exactly one of these events must
occur), we have
 4.7 The Poisson random variables
• Now, given that the first tail appears on flip j, where j < k,
it follows that those j flips are wasted as far as obtaining a
string of k heads in a row; thus, the conditional probability
of this event is the probability that such a string will occur
among the remaining n − j flips.
• Therefore, P(An|Fj) = Pn−j.
• Because P(An|H) = 1, the preceding equation gives
 4.7 The Poisson random variables
• Starting with Pj = 0, j < k, and Pk = pk, we can use the
latter formula to recursively compute Pk+1, Pk+2, and so on,
up to Pn.
• For instance, suppose we want the probability that there is
a run of 2 consecutive heads when a fair coin is flipped 4
times.
• Then, with k = 2, we have P1 = 0, P2 = (1/2)2.
• Because, when p = 1/2, the recursion becomes
 4.7 The Poisson random variables
• We obtain P3 = P2(1/2) + P1(1/2)2 + (1/2)2 = 3/8 and
P4 = P3(1/2) + P2(1/2)2 + (1/2)2 = ½ which is clearly true
because there are 8 outcomes that result in a string of 2
consecutive heads: hhhh, hhht, hhth, hthh, thhh, hhtt, thht,
and tthh.
• Each of these outcomes occurs with probability 1/16.
 4.7 The Poisson random variables
• Another use of the Poisson probability distribution arises
in situations where “events” occur at certain points in time.
• One example is to designate the occurrence of an
earthquake as an event.
• Let us suppose that events are indeed occurring at certain
(random) points of time, and let us assume that, for some
positive constant λ, the following assumptions hold true:
 4.7 The Poisson random variables
• 1. The probability that exactly 1 event occurs in a given
interval of length h is equal to λh + o(h), where o(h) stands
for any function f (h) for which limh→0 f (h)/h = 0.
• 2. The probability that 2 or more events occur in an
interval of length h is equal to o(h).
• 3. For any integers n, j1, j2, . . . , jn and any set of n
nonoverlapping intervals, if we define Ei to be the event
that exactly ji of the events under consideration occur in
the ith of these intervals, then events E1,E2, . . . ,En are
independent.
 4.7 The Poisson random variables
• We show that, under assumptions 1, 2, and 3, the number
of events occurring in any interval of length t is a Poisson
random variable with parameter λt.
• Let us call the interval [0, t] and denote the number of
events occurring in that interval by N(t).
• To obtain an expression for P{N(t) = k}, we start by
breaking the interval [0, t] into n nonoverlapping
subintervals, each of length t/n.
 4.7 The Poisson random variables
• P{N(t) = k}
= P{k of the n subintervals contain exactly 1 event and the
other n − k contain 0 events} [denoted by P(A)]
+
P{N(t) = k and at least 1 subinterval contains 2 or more
events} [denoted by P(B)]
4.7 The Poisson random variables
 4.7 The Poisson random variables
• Since assumptions 1 and 2 imply that
P{0 events occur in an interval of length h}
= 1 − [λh + o(h) + o(h)] = 1 − λh − o(h), we see from the
independence assumption (number 3) that
4.7 The Poisson random variables
 4.7 The Poisson random variables
• Thus, from Equations (7.2), (7.3), and (7.4), by letting
n→, we obtain
 4.7 The Poisson random variables
• EXAMPLE 7e
• Suppose that earthquakes occur in the western portion of
the United States in accordance with assumptions 1, 2, and
3, with λ = 2 and with 1 week as the unit of time.
• (a) Find the probability that at least 3 earthquakes occur
during the next 2 weeks.
• (b) Find the probability distribution of the time, starting
from now, until the next earthquake.
 4.7 The Poisson random variables
• Solution. (a) From Equation (7.5), we have
 4.7 The Poisson random variables
• (b) Let X denote the amount of time (in weeks) until the
next earthquake.
• X will be greater than t if and only if no events occur
within the next t units of time.
• From Equation (7.5), P{X > t} = P{N(t) = 0} = e−λt so the
probability distribution function F of the random variable
X is given by
 4.7 The Poisson random variables
• 4.7.1 Computing the Poisson Distribution Function
• If X is Poisson with parameter λ, then

• Starting with P{X = 0} = e−λ,

 4.8 Other discrete probability
distributions
• 4.8.1 The Geometric Random Variable
• Suppose that independent trials, each having a probability
p, 0 < p < 1, of being a success, are performed until a
success occurs.
• If we let X equal the number of trials required, then
P{X = n} = (1 − p)n−1p n= 1, 2, . . . (8.1)
• Any random variable X whose probability mass function is
given by Equation (8.1) is said to be a geometric random
variable with parameter p.
 4.8 Other discrete probability
distributions
• EXAMPLE 8a
• An urn contains N white and M black balls. Balls are
randomly selected, one at a time, until a black one is
obtained. If we assume that each ball selected is replaced
before the next one is drawn, what is the probability that
• (a) exactly n draws are needed?
• (b) at least k draws are needed?
 4.8 Other discrete probability
distributions
• Solution. If we let X denote the number of draws needed
to select a black ball, then X satisfies Equation (8.1) with p
= M/(M + N). Hence,
 4.8 Other discrete probability
distributions
• EXAMPLE 8b
• Find the expected value of a geometric random variable.

• Solution. With q = 1 − p, we have

 4.8 Other discrete probability
distributions
• EXAMPLE 8c
• Find the variance of a geometric random variable.
• Solution. To determine Var(X), let us first compute E[X2].
With q = 1 − p, we have
 4.8 Other discrete probability
distributions
• Using E[X] = 1/p, the equation for E[X2] yields
 4.8 Other discrete probability
distributions
• 4.8.2 The Negative Binomial Random Variable
• Suppose that independent trials, each having probability p,
0 < p < 1, of being a success are performed until a total of
r successes is accumulated. If we let X equal the number of
trials required, then
 4.8 Other discrete probability
distributions
• Any random variable X whose probability mass function is
given by Equation (8.2) is said to be a negative binomial
random variable with parameters (r, p).
• Note that a geometric random variable is just a negative
binomial with parameter (1, p).
 4.8 Other discrete probability
distributions
• EXAMPLE 8d
• If independent trials, each resulting in a success with
probability p, are performed, what is the probability of r
successes occurring before m failures?
 4.8 Other discrete probability
distributions
• Solution. The solution will be arrived at by noting that r
successes will occur before m failures if and only if the rth
success occurs no later than the (r + m − 1)th trial.
• This follows because if the rth success occurs before or at
the (r + m − 1)th trial, then it must have occurred before
the mth failure, and conversely.
• Hence, from Equation (8.2), the desired probability is
 4.8 Other discrete probability
distributions
• EXAMPLE 8e The Banach match problem
• At all times, a pipe-smoking mathematician carries 2
matchboxes—1 in his left-hand pocket and 1 in his right-
hand pocket. Each time he needs a match, he is equally
likely to take it from either pocket. Consider the moment
when the mathematician first discovers that one of his
matchboxes is empty. If it is assumed that both
matchboxes initially contained N matches, what is the
probability that there are exactly k matches, k = 0, 1,..,N,
in the other box?
 4.8 Other discrete probability
distributions
• Solution. Let E denote the event that the mathematician
first discovers that the righthand matchbox is empty and
that there are k matches in the left-hand box at the time.
• Now, this event will occur if and only if the (N + 1)th
choice of the right-hand matchbox is made at the (N + 1 +
N − k)th trial.
• Hence, from Equation (8.2) (with p = 1/2, r = N + 1, and n
= 2N − k + 1), we see that
 4.8 Other discrete probability
distributions
• Since there is an equal probability that it is the left-hand
box that is first discovered to be empty and there are k
matches in the right-hand box at that time, the desired
result is
 4.8 Other discrete probability
distributions
• EXAMPLE 8f
• Compute the expected value and the variance of a negative
binomial random variable with parameters r and p.

• Y is a negative binomial random variable with r + 1.

 4.8 Other discrete probability
distributions
• Setting k = 1 in the preceding equation yields E[X] = r/p.
• Setting k = 2 in the equation for E[Xk] and using the
formula for the expected value of a negative binomial
random variable gives
 4.8 Other discrete probability
distributions
• 4.8.3 The Hypergeometric Random Variable
• Suppose that a sample of size n is to be chosen randomly
(without replacement) from an urn containing N balls, of
which m are white and N − m are black. If we let X denote
the number of white balls selected, then
 4.8 Other discrete probability
distributions
• A random variable X whose probability mass function is
given by Equation (8.4) for some values of n, N, m is said
to be a hypergeometric random variable.
 4.8 Other discrete probability
distributions
• EXAMPLE 8h
• An unknown number, say, N, of animals inhabit a certain
region. To obtain some information about the size of the
population, ecologists often perform the following
experiment: They first catch a number, say, m, of these
animals, mark them in some manner, and release them.
After allowing the marked animals time to disperse
throughout the region, a new catch of size, say, n, is made.
 4.8 Other discrete probability
distributions
• Let X denote the number of marked animals in this second
capture. If we assume that the population of animals in the
region remained fixed between the time of the two catches
and that each time an animal was caught it was equally
likely to be any of the remaining uncaught animals, it
follows that X is a hypergeometric random variable such
that
 4.8 Other discrete probability
distributions
• Suppose now that X is observed to equal i.
• Then, since Pi(N) represents the probability of the
observed event when there are actually N animals present
in the region, it would appear that a reasonable estimate of
N would be the value of N that maximizes Pi(N).
• Such an estimate is called a maximum likelihood estimate.
• The maximization of Pi(N) can be done most simply by
first noting that
 4.8 Other discrete probability
distributions
• Now, the preceding ratio is greater than 1 if and only if
(N − m)(N − n)  N(N − m − n + i) or, equivalently, if and
only if N  mn/i.
• Thus, Pi(N) is first increasing and then decreasing, and
reaches its maximum value at the largest integral value not
exceeding mn/i.
• This value is the maximum likelihood estimate of N.
 4.8 Other discrete probability
distributions
• EXAMPLE 8j
• Determine the expected value and the variance of X, a
hypergeometric random variable with parameters n, N, and
m.
• Solution.
 4.8 Other discrete probability
distributions
• Using the identities

• Y is a hypergeometric random variable with parameters n

− 1, N − 1, and m − 1.
 4.8 Other discrete probability
distributions
• Hence, upon setting k = 1, we have E[X] = nm/N.
• Upon setting k = 2 in the equation for E[Xk], we obtain
 4.9 Expected value of sums of
random variables
• For a random variable X, let X(s) denote the value of X
when s ∈ S is the outcome of the experiment. Now, if X
and Y are both random variables, then so is their sum.
• That is, Z = X + Y is also a random variable. Moreover,
Z(s) = X(s) + Y(s).
• Let p(s) = P({s}) be the probability that s is the outcome
of the experiment. Because we can write any event A as
the finite or countably infinite union of the mutually
exclusive events {s}, s ∈ A, it follows by the axioms of
probability that P(A)= sAp(s).
 4.9 Expected value of sums of
random variables
• Proposition 9.1. E[X] =sSX(s)p(s).
• Proof. Suppose that the distinct values of X are xi, i  1.
For each i, let Si be the event that X is equal to xi. That is,
Si = {s : X(s) = xi}. Then,

• The final equality follows because S1, S2, . . . are mutually

exclusive events whose union is S.
 4.9 Expected value of sums of
random variables
• EXAMPLE 9b
• Suppose that two independent flips of a coin that comes up
heads with probability p are made, and let X denote the
number of heads obtained. Because
• P(X = 0) = P(t, t) = (1 − p)2
• P(X = 1) = P(h, t) + P(t, h) = 2p(1 − p)
• P(X = 2) = P(h, h) = p2
• it follows from the definition of expected value that
• E[X] = 0 · (1 − p)2 + 1 · 2p(1 − p) + 2 · p2 = 2p
 4.9 Expected value of sums of
random variables
• Corollary 9.2. For random variables X1,X2, . . . ,Xn,
 4.9 Expected value of sums of
random variables
• EXAMPLE 9c
• Find the expected value of the sum obtained when n fair
dice are rolled.
• Solution. Let X be the sum. where Xi is the
upturned value on die i.
• Because Xi is equally likely to be any of the values from 1
to 6, it follows that
 4.9 Expected value of sums of
random variables
• EXAMPLE 9d
• Find the expected total number of successes that result
from n trials when trial i is a success with probability pi, i
= 1, . . . , n.
• Solution. Letting
 4.9 Expected value of sums of
random variables
• EXAMPLE 9e
• Derive an expression for the variance of the number of
successful trials in Example 9d, and apply it to obtain the
variance of a binomial random variable with parameters n
and p.
 4.9 Expected value of sums of
random variables
• Solution. Letting X be the number of successful trials, and
4.9 Expected value of sums of
random variables
 4.10 Properties of the cumulative
distribution function
• For the distribution function F of X, F(b) denotes the
probability that the random variable X takes on a value that
is less than or equal to b.
• Following are some properties of the cumulative
distribution function (c.d.f.) F:
 4.10 Properties of the cumulative
distribution function
• EXAMPLE 10a
• The distribution function of the random variable X is given
by F(x)
 4.10 Properties of the cumulative
distribution function
• EXAMPLE 10a The distribution function of the random
variable X is given by F(x). A graph of F(x) is presented in
Figure 4.8. Compute (a) P{X < 3}, (b) P{X = 1},
(c) P{X > 1/2}, and (d) P{2 < X  4}.
 4.10 Properties of the cumulative
distribution function
• Solution.