Transcript CMSC 203 / 0202 Fall 2002

CMSC 203 / 0201
Fall 2002
Week #9 – 21/23/25 October 2002
Prof. Marie desJardins
September1999
TOPICS
 Permutations
 Combinations
 Binomial theorem
 Discrete probability
 Probability theory
September1999
October 1999
MON 10/21
PERMUTATIONS AND COMBINATIONS
(4.3)
September1999
Concepts/Vocabulary
 Permutation, r-permutation
 P(n, r) = n! / (n-r)!
 r-combination
 C(n, r) = (n choose r) = n! / (r! (n-r)!)
 Pascal’s identity
 (n+1 choose k) = (n choose k-1) + (n choose k)
 Pascal’s triangle
 Binomial theorem
 (x+y)n = j=0n (n choose j) xn-j yj
September1999
October 1999
Examples
 Exercise 4.3.1: List all the permutations of {a,b,c}.
 Exercise 4.3.2: How many permutations are there
of the set {a,b,c,d,e,f,g}?
 How many permutations of a set of size k?
 Exercise 4.3.3: How many permutations of {a,b,c,d,e,f,g}
end with a?
September1999
October 1999
Examples II
 Exercise 4.3.19: A club has 25 members.
 (a) How many ways are there to choose four members
of the club to serve on an executive committee?
 HINT: Which individual is in each of the four positions
doesn’t matter
 (b) How many ways are there to choose a president,
vice president, secretary, and treasurer of the club?
 HINT: Which individual is in each of the four positions
does matter
 Proof of binomial theorem (page 256)
September1999
October 1999
WED 10/23
DISCRETE PROBABILITY (4.4)
** HOMEWORK #6 DUE **
** UNGRADED QUIZ TODAY!**
September1999
Concepts / Vocabulary
 Experiment, sample space, event
 Laplace’s probability – p(E) = |E| / |S|
 OK for finitely many equally likely outcomes
 p(~E) = 1 – P(E)
 p(E1  E2) = p(E1) + p(E2) when E1, E2 are disjoint
September1999
October 1999
Examples
 Exercise 4.4.31: A roulette wheel has 38 numbers
(18 red, 18 black, and 0 and 00, which are neither
black or red). The probability that when the wheel
is spun it lands on any particular number is 1/38.
What is the probability that the wheel …





(a) …lands on a red number?
(b) … lands on a black number twice in a row?
(c) … lands on 0 or 00?
(d) … does not land on 0 or 00 five times in a row?
(e) … lands on a number between 1 and 6, inclusive, on
one spin, but does not land between them on the next
spin?
September1999
October 1999
Examples II
 Example 4.4.10 (an apparent paradox): You
choose what’s behind Door #1. Before showing
you what’s there, the host tells you that Door #2 is
a losing door. Should you stick with Door #1 or
switch with Door #3?
 A door is a door is a door, isn’t it…? Shouldn’t the
probability that the prize is behind Door #1 and the
probability that the prize is behind Door #3 both be ½,
since there are two doors left? (Exercise 4.4.35)
 Why does telling you something about Door #2 tell you
anything about Door #3??
September1999
October 1999
Examples III
 Exercise 4.4.34: Two events E1 and E2 are called
independent if p(E1E2) = p(E1) p(E2). If a coin is
tossed three times, which of the following pairs of
events are independent:
 (a) E1: the first coin comes up tails; E2: the second coin
comes up heads.
 (b) E1: the first coin comes up tails; E2: two, but not
three, heads come up in a row.
 (c) E1: the second coin comes up tails; E2: two, and not
three, heads come up in a row.
September1999
October 1999
FRI 10/11 - MON 10/14
PROBABILITY THEORY (4.5)
September1999
Concepts and Vocabulary
 Axioms of probability: for a set of mutually exclusive
outcomes sS,
 0  p(s)  1
 sS p(s) = 1




Event: set of outcomes
Conditional probability p(E|F) = p(EF) / p(F)
Independence p(EF) = p(E) p(F), or p(E|F) = p(E)
Bernoulli trials (2 outcomes)
 Binomial distribution b(k:n, p) = (n choose k) pk qn-k
 Random variables, expected values
 Independent random variables, variance
September1999
October 1999
Examples
 Dice rolling:
 Find the probability of each outcome when a biased die
is rolled, if rolling a 2 or 4 are each three times as likely
as rolling each of the other four numbers on the die.
 What is the probability of rolling a 7 with two ordinary
dice?
 Exercise 4.5.5: Suppose a pair of dice is loaded. The
probability that a 4 appears on the first die is 2/7 (other
outcomes are 1/7), and the probability that a 3 appears
on the second die is 2/7 (other outcomes are 1/7). What
is the probability of rolling a 7 with these two dice?
September1999
October 1999
Examples II
 Independence
 Exercise 4.5.10: Show that if E and F are independent events, then
~E and ~F are also independent events.
 Exercise 4.5.11: If E and F are independent events, prove or
disprove that ~E and F are necessarily independent events.
 Conditional probability
 Exercise 4.5.15: What is the conditional probability that exactly four
heads apppear when a fair coin is flipped five times, given that the
first flip came up heads?
 Exercise 4.5.17: What is the c.p. that a random bit string of length 4
contains at lest 2 consecutive 0s, given that the first bit is a 1?
September1999
October 1999
Examples III
 Bernoulli trials: Exercise 4.5.26: Find each of the
following probabilities when n independent
Bernoulli trials are carried out with probability of
success p.




(a) the probability of no successes
(b) the probability of at least one success
(c) the probability of at most one success
(d) the probability of at least two successes
September1999
October 1999
Examples IV
 Random variables and expected values:
 Exercise 4.5.31: What is the expected sum of the numbers that
appear on two dice, each biased so that a 3 comes up twice as
often as each other number?
 Exercise 4.5.32: What is the expected value of a $1 lottery ticket
when the purchaser wins $10,000,000 iff the ticket contains the six
winning numbers chosen from the set {1,2,3,…,50} (and nothing
otherwise)?
 Exercise 4.5.33: The 203 final exam contains 50 T/F questions (2
points each) and 25 multiple-choice questions (4 points each).
 Linda answers a T/F question correctly with probability .9, and a
multiple-choice question with probability .8. What is her expected
score on the final?
 What is the expected score of Emily, who hasn’t studied at all
and answers T/F questions correctly with probability .5, and
multiple-choice questions correctly with probability .25?
September1999
October 1999