Page 519 - Discrete Mathematics and Its Applications

498 7 / Discrete Probability

In Exercise 27 we consider the two children problem, intro- variable equal to the number of products that need to be
duced in 1959 by Martin Garnder is his Mathematical Games purchased to obtain at least one of each type of card and
column in Scientific American. A version of the puzzle asks: let X j be the random variable equal to the number of ad-
“We meet Mr. Smith as he is walking down the street with a ditional products that must be purchased after j different
young child whom he introduces as his son. He also tells us cards have been collected until a new card is obtained
that he has two children. What is the probability that his other for j = 0, 1,...,n − 1.
child is a son?” We will show that this puzzle is ambiguous, n−1
a) Show that X = j = 0 X j .
leading to a paradox, by showing that there are two reasonable b) Show that after j distinct types of cards have been ob-
answers to this problem and we will describe how to make the tained, the card obtained with the next purchase will
puzzle unambiguous.
be a card of a new type with probability (n − j)/n.
∗ 27. a) Solve this puzzle in two different ways. First, answer
c) Show that X j has a geometric distribution with pa-
the problem by considering the probability of the gen-
rameter (n − j)/n.
der of the second child. Then, determine the probabil-
d) Use parts (a) and (c) to show that E(X) =
ity differently, by considering the four different possi- n
n 1/j.
bilities for a family of two children. j=1
n
b) Show that the answer to the puzzle becomes unam- e) Use the approximation j=1 1/j ≈ ln n + γ , where
biguous if we also know that Mr. Smith chose his γ = 0.57721 ... is Euler’s constant, to find the ex-
walking companion at random from his two children. pected number of products that you need to buy to get
c) Another variation of this puzzle asks “When we meet one card of each type if there are 50 different types of
Mr. Smith, he tells us that he has two children and cards.
at least one is a son. What is the probability that his 34. The maximum satisfiability problem asks for an as-
other child is a son?” Solve this variation of the puzzle, signment of truth values to the variables in a compound
explaining why it is unambiguous. proposition in conjunctive normal form (which expresses
28. In 2010, the puzzle designer Gary Foshee posed this prob- a compound proposition as the conjunction of clauses
lem: “Mr. Smith has two children, one of whom is a son where each clause is the disjunction of two or more vari-
born on a Tuesday. What is the probability that Mr. Smith ables or their negations) that makes as many of these
has two sons?” Show that there are two different answers clauses true as possible. For example, three but not four
to this puzzle, depending on whether Mr. Smith specifi- of the clauses in
cally mentioned his son because he was born on a Tues- (p ∨ q) ∧ (p ∨¬q) ∧ (¬p ∨ r) ∧ (¬p ∨¬r)
day or whether he randomly chose a child and reported
its gender and birth day of the week. [Hint: For the first can be made true by an assignment of truth values to p, q,
possibility, enumerate all the equally likely possibilities
and r. We will show that probabilistic methods can pro-
for the gender and birth day of the week of the other child.
vide a lower bound for the number of clauses that can be
To do, this consider first the cases where the older child
made true by an assignment of truth values to the vari-
is a boy born on a Tuesday and then the case where the
ables.
older child is not a boy born on a Tuesday.]
a) Suppose that there are n variables in a compound
29. Let X be a random variable on a sample space S. Show proposition in conjunctive normal form. If we pick
2
that V(aX + b) = a V(X) whenever a and b are real a truth value for each variable randomly by flipping
numbers. a coin and assigning true to the variable if the coin
30. Use Chebyshev’s inequality to show that the probability comes up heads and false if it comes up tails, what
that more than 10 people get the correct hat back when is the probability of each possible assignment of truth
a hatcheck person returns hats at random does not ex- values to the n variables?
ceed 1/100 no matter how many people check their hats. b) Assuming that each clause is the disjunction of ex-
[Hint: Use Example 6 and Exercise 43 in Section 7.4.] actly two distinct variables or their negations, what is
31. Suppose that at least one of the events E j , j = the probability that a given clause is true, given the
1, 2,...,m, is guaranteed to occur and no more than two random assignment of truth values from part (a)?
can occur. Show that if p(E j ) = q for j = 1, 2,...,m c) Suppose that there are D clauses in the compound
and p(E j ∩ E k ) = r for 1 ≤ j< k ≤ m, then q ≥ 1/m proposition. What is the expected number of these
and r ≤ 2/m. clauses that are true, given the random assignment of
32. Show that if m is a positive integer, then the probability truth values of the variables?
that the mth success occurs on the (m + n)th trial when d) Use part (c) to show that for every compound proposi-
independent Bernoulli trials, each with probability p of tion in conjunctive normal form there is an assignment
n+m−1 n m
success, are run, is q p . of truth values to the variables that makes at least 3/4
n
33. There are n different types of collectible cards you can of the clauses true.
get as prizes when you buy a particular product. Suppose 35. What is the probability that each player has a hand con-
that every time you buy this product it is equally likely taining an ace when the 52 cards of a standard deck are
that you get any type of these cards. Let X be the random dealt to four players?