Page 516 - Discrete Mathematics and Its Applications

7.4 Expected Value and Variance 495

RESULTS linearityofexpectations:E(X 1 + X 2 +···+ X n ) = E(X 1 ) +
E(X 2 ) + ··· + E(X n ) if X 1 , X 2 ,...,X n are random vari-
The probability of exactly k successes when n indepen-
k n−k
dent Bernoulli trials are carried out equals C(n, k)p q , ables
where p is the probability of success and q = 1 − p is the If X and Y are independent random variables, then E(XY) =
probability of failure. E(X)E(Y).
Bayes’ theorem: If E and F are events from a sample space Bienaymé’s formula: If X 1 ,X 2 ,...,X n are independent ran-
S such that p(E) = 0 and p(F) = 0, then dom variables, then V(X 1 + X 2 + ··· + X n ) = V(X 1 ) +
V(X 2 ) + ··· + V(X n ).
p(E | F)p(F)
2
p(F | E) = . Chebyshev’sinequality:p(|X(s) − E(X)|≥ r) ≤ V(X)/r ,
p(E | F)p(F) + p(E | F)p(F)
where X is a random variable with probability function p

E(X) = p(X = r)r. and r is a positive real number.
r∈X(S)

Review Questions

1. a) Define the probability of an event when all outcomes and it is equally likely that this element is any of
are equally likely. the n elements in the list?
b) What is the probability that you select the six winning 8. a) What is meant by a Bernoulli trial?
numbers in a lottery if the six different winning num- b) What is the probability of k successes in n independent
bers are selected from the first 50 positive integers? Bernoulli trials?
2. a) What conditions should be met by the probabilities c) What is the expected value of the number of successes
assigned to the outcomes from a finite sample space? in n independent Bernoulli trials?
b) What probabilities should be assigned to the outcome 9. a) Whatdoesthelinearityofexpectationsofrandomvari-
of heads and the outcome of tails if heads comes up ables mean?
three times as often as tails? b) How can the linearity of expectations help us find the
expected number of people who receive the correct
3. a) Define the conditional probability of an event E given
an event F. hat when a hatcheck person returns hats at random?
10. a) How can probability be used to solve a decision prob-
b) Suppose E is the event that when a die is rolled it
lem, if a small probability of error is acceptable?
comes up an even number, and F is the event that
b) How can we quickly determine whether a positive in-
when a die is rolled it comes up 1, 2, or 3. What is the
teger is prime, if we are willing to accept a small prob-
probability of F given E?
ability of making an error?
4. a) When are two events E and F independent?
11. State Bayes’ theorem and use it to find p(F | E) if
b) Suppose E is the event that an even number appears p(E | F) = 1/3, p(E | F) = 1/4, and p(F) = 2/3,
when a fair die is rolled, and F is the event that a 5 where E and F are events from a sample space S.
or 6 comes up. Are E and F independent?
12. a) What does it mean to say that a random variable has a
5. a) What is a random variable?
geometric distribution with parameter p?
b) What are the possible values assigned by the random b) What is the mean of a geometric distribution with pa-
variable X that assigns to a roll of two dice the larger rameter p?
number that appears on the two dice?
13. a) What is the variance of a random variable?
6. a) Define the expected value of a random variable X. b) What is the variance of a Bernoulli trial with proba-
b) What is the expected value of the random variable X bility p of success?
that assigns to a roll of two dice the larger number that 14. a) What is the variance of the sum of n independent ran-
appears on the two dice? dom variables?
7. a) Explain how the average-case computational com- b) What is the variance of the number of successes when
plexity of an algorithm, with finitely many possible n independent Bernoulli trials, each with probability p
input values, can be interpreted as an expected value. of success, are carried out?
b) What is the average-case computational complexity 15. What does Chebyshev’s inequality tell us about the prob-
of the linear search algorithm, if the probability that ability that a random variable deviates from its mean by
the element for which we search is in the list is 1/3, more than a specified amount?