Solutions Manual for the book Introduction to Probability 2015 PDF

Preview

Summary

Download Solutions Manual for the book Introduction to Probability 2015 PDF

Description

Solutions Manual for the book Introduction to Probability by Joseph K. Blitzstein and Jessica Hwang  c Chapman & Hall/CRC Press, 2015

Joseph K. Blitzstein and Jessica Hwang Departments of Statistics, Harvard University and Stanford University September 7, 2017

Contents

1 Probability and counting

1

2 Conditional probability

29

3 Random variables and their distributions

71

4 Expectation

93

5 Continuous random variables

135

6 Moments

167

7 Joint distributions

179

8 Transformations

237

9 Conditional expectation

261

10 Inequalities and limit theorems

291

11 Markov chains

311

12 Markov chain Monte Carlo

329

13 Poisson processes

333

iii

1 Probability and counting

Counting 1.

How many ways are there to permute the letters in the word MISSISSIPPI? Solution: The word has 4 S’s, 4 I’s, 2 P’s, and 1 M. Let’s choose where to put the S’s, then where to put the I’s, then where to put the P’s, and then the location of the M is determined. By the multiplication rule, there are ! ! ! 7 3 11 = 34650 4 4 2 possibilities. Alternatively, we can start with 11! and adjust for overcounting: 11! = 34650. 4!4!2!

2.

(a) How many 7-digit phone numbers are possible, assuming that the first digit can’t be a 0 or a 1? (b) Re-solve (a), except now assume also that the phone number is not allowed to start with 911 (since this is reserved for emergency use, and it would not be desirable for the system to wait to see whether more digits were going to be dialed after someone has dialed 911). Solution: (a) By the multiplication rule, there are 8 · 106 possibilities. (b) There are 104 phone numbers in (a) that start with 911 (again by the multiplication rule, since the first 3 digits are 911 and the remaining 4 digits are unconstrained). Excluding these and using the result of (a), the number of possibilities is 8 · 106 − 104 = 7990000.

3.

Fred is planning to go out to dinner each night of a certain week, Monday through Friday, with each dinner being at one of his ten favorite restaurants. (a) How many possibilities are there for Fred’s schedule of dinners for that Monday through Friday, if Fred is not willing to eat at the same restaurant more than once? (b) How many possibilities are there for Fred’s schedule of dinners for that Monday through Friday, if Fred is willing to eat at the same restaurant more than once, but is not willing to eat at the same place twice in a row (or more)? Solution: (a) By the multiplication rule, there are 10 · 9 · 8 · 7 · 6 = 30240 possibilities. (b) By the multiplication rule, there are 10 · 94 = 65610 possibilities, since Monday’s dinner can be at any of the 10 restaurants, and for Tuesday through Friday, each dinner can be at any of the 10 restaurants except the one where Fred ate on the previous night.

1

2 4.

A round-robin tournament is being held with n tennis players; this means that every player will play against every other player exactly once. (a) How many possible outcomes are there for the tournament (the outcome lists out who won and who lost for each game)? (b) How many games are played in total? Solution: n   (a) For each of the n2 unordered pairs of players, there is 1 game, so there are 2(2 ) possible outcomes for the tournament.   (b) There are n2 games played, as noted in (a).

5.

A knock-out tournament is being held with 2n tennis players. This means that for each round, the winners move on to the next round and the losers are eliminated, until only one person remains. For example, if initially there are 24 = 16 players, then there are 8 games in the first round, then the 8 winners move on to round 2, then the 4 winners move on to round 3, then the 2 winners move on to round 4, the winner of which is declared the winner of the tournament. (There are various systems for determining who plays whom within a round, but these do not matter for this problem.) (a) How many rounds are there? (b) Count how many games in total are played, by adding up the numbers of games played in each round. (c) Count how many games in total are played, this time by directly thinking about it without doing almost any calculation. Hint: How many players need to be eliminated? Solution: (a) There are n rounds, since each round cuts the number of remaining players in half. (b) There are 2n /2 = 2n−1 games in the first round, then 2n−2 games in the second round, and so on, until there are only 2 players left in the final round. Using the formula for the sum of a finite geometric series (see the math appendix), the total number of games is 1 − 2n 1 + 2 + 22 + · · · + 2n−1 = = 2n − 1. 1−2 (c) A much easier way to see that the number of games is 2n − 1 is to note that each game eliminates one player, and 2n−1 players need to be eliminated to leave one winner.

6.

There are 20 people at a chess club on a certain day. They each find opponents and start playing. How many possibilities are there for how they are matched up, assuming that in each game it does matter who has the white pieces (in a chess game, one player has the white pieces and the other player has the black pieces)? ways to determine who plays whom without considering color, Solution: There are 21020! ·10! by the multiplication rule or the result of Example 1.5.4 (Partnerships). For each game, there are 2 choices for who has the white pieces, so overall the number of possibilities is 210 · 20! 20! = 670442572800. = 10! 210 · 10! Alternatively, imagine a long table with 10 chessboards in a row, with 10 chairs on each

Probability and counting

3

side of the table (for the chess players to sit in). Chess pieces are set up at each board, oriented so that the white pieces are all on one side of the table and the black pieces are all on the other side of the table. There are 20! ways for the chess players to be assigned to chairs, and once the players are seated in their chairs, a configuration for the chess games has been determined. This procedure overcounts by a factor of 10! since, after matching up the players, we can permute the players on one side of the table in any way, as long as we also permute the players on the other side of the table in the same way. So again the number of possibilities is 20! . 10! 7.

Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points. (a) How many possible outcomes for the individual games are there, such that overall player A ends up with 3 wins, 2 draws, and 2 losses? (b) How many possible outcomes for the individual games are there, such that A ends up with 4 points and B ends up with 3 points? (c) Now assume that they are playing a best-of-7 match, where the match will end when either player has 4 points or when 7 games have been played, whichever is first. For example, if after 6 games the score is 4 to 2 in favor of A, then A wins the match and they don’t play a 7th game. How many possible outcomes for the individual games are there, such that the match lasts for 7 games and A wins by a score of 4 to 3? Solution: (a) Writing W for win, D for draw, and L for loss (for player A), an outcome of the desired form is any permutation of WWWDDLL. So there are 7! = 210 3!2!2! possible outcomes of the desired form. (b) To end up with 4 points, A needs to have one of the following results: (i) 4 wins and 3 losses; (ii) 3 wins, 2 draws, and 2 losses; (iii) 2 wins, 4 draws, and 1 loss; or (iv) 1 win and 6 draws. Reasoning as in (a) and adding up these possibilities, there are 7! 7! 7! 7! = 357 + + + 1!6! 4!3! 3!2!2! 2!4!1! possible outcomes of the desired form. (c) For the desired outcomes, either (i) player A is ahead 3.5 to 2.5 after 6 games and then draws game 7, or (ii) the match is tied (3 to 3) after 6 games and then player A wins game 7. Reasoning as in (b), there are 6! 6! 6! + + = 126 3!1!2! 2!3!1! 1!5! possibilities of type (i) and 6! 6! 6! + 1 = 141 + + 1!4!1! 3!3! 2!2!2! possibilities of type (ii), so overall there are 126 + 141 = 267 possible outcomes of the desired form.

4 8.

s (a) How many ways are there to split a dozen people into 3 teams, where one team  has 2 people, and the other two teams have 5 people each? (b) How many ways are there to split a dozen people into 3 teams, where each team has 4 people? Solution: (a) Pick any 2 of the 12 people to make the 2 person team, and then any 5 of the remaining 10 for the first team of 5, and then the remaining 5 are on the other team of 5; this overcounts by a factor of 2 though,   since there is no designated “first” team of 5. So the number of possibilities is 122 10 /2 = 8316. Alternatively, politely ask the 12 5 people to line up, and then let the first 2 be the team of 2, the next 5 be a team of 5, and then last 5 be a team of 5. There are 12! ways for them to line up, but it does not matter which order they line up in within each group, nor does the order of the 2 teams 12! = 8316. of 5 matter, so the number of possibilities is 2!5!5!·2 12! ways to divide the people into a (b) By either of the approaches above, there are 4!4!4! Team A, a Team B, and a Team C, if we care about which team is which (this is called a multinomial coefficient). Since here it doesn’t matter which team is which, this over 12! counts by a factor of 3!, so the number of possibilities is 4!4!4!3! = 5775.

9.

s (a) How many paths are there from the point (0, 0) to the point (110, 111) in the  plane such that each step either consists of going one unit up or one unit to the right? (b) How many paths are there from (0, 0) to (210, 211), where each step consists of going one unit up or one unit to the right, and the path has to go through (110, 111)? Solution:

10.

(a) Encode a path as a sequence of U ’s and R’s, like U RU RU RU U U R . . . U R, where U and R stand for “up” and “right” respectively. The sequence must consist of 110 R’s and 111 U ’s, and to determine the sequence we just need to specify where the R’s are   located. So there are 221 possible paths. 110 221 (b) There are 110 paths to (110, 111), as above. From there, we need 100 R’s and 100 ’s to get to (210, 211), so by the multiplication rule the number of possible paths is U221 200 · 100 . 110 To fulfill the requirements for a certain degree, a student can choose to take any 7 out of a list of 20 courses, with the constraint that at least 1 of the 7 courses must be a statistics course. Suppose that 5 of the 20 courses are statistics courses. (a) How many choices are there for which 7 courses to take?    (b) Explain intuitively why the answer to (a) is not 15 · 19 . 6

Solution:

    of these (a) There are 20 ways to choose 7 courses if there are no constraints, but 15 7 7 have no statistics courses. So there are ! ! 20 15 − = 71085 7 7 sets of 7 courses that contain at least one statistics course.   (b) An incorrect argument would be “there are 51 to choose a statistics course (let’s knock that  requirement out of the way, then we can choose any other 6 courses) and choices for the remaining 6 courses. This is incorrect since it’s possible (and then 19 6

Probability and counting

11.

often a good idea!) to take more than one statistics course. A possibility containing, for example, the statistics courses Stat   110  and Stat 111 together with 5 non-statistics , once with Stat 110 as the choice for the would be counted twice in 51 · 19 6 courses  5 term and once with Stat 111 as the choice. So it makes sense that the true answer 1     . is much less than 51 · 19 6 Let A and B be sets with |A| = n, |B| = m.

(a) How many functions are there from A to B (i.e., functions with domain A, assigning an element of B to each element of A)? (b) How many one-to-one functions are there from A to B (see Section A.2.1 of the math appendix for information about one-to-one functions)? Solution: (a) By the multiplication rule, there are mn functions f from A to B, since for each a ∈ A there are m possible ways to define f (a). (b) Now values can’t be repeated, so there are m · (m − 1) · (m − 2) · · · · (m − n + 1) possibilities for n ≤ m, and there are no possibilities for n > m. 12.

Four players, named A, B, C, and D, are playing a card game. A standard, well-shuffled deck of cards is dealt to the players (so each player receives a 13-card hand). (a) How many possibilities are there for the hand that player A will get? (Within a hand, the order in which cards were received doesn’t matter.) (b) How many possibilities are there overall for what hands everyone will get, assuming that it matters which player gets which hand, but not the order of cards within a hand? (c) Explain intuitively why the answer to Part (b) is not the fourth power of the answer to Part (a). Solution: 52 (a) There are 13 possibilities since player A gets 13 out of 52 cards, without replacement and with order not mattering. 52   (b) There are 13 possibilities for A’s hand. For each of these, there are 39 possibilities 13 26  for B’s hand. For each of these, there are 13 possibilities for C’s hand. After 3 hands have been determined, the 4th is also determined. So the number of possibilities is ! ! ! 52 39 26 52! = ≈ 5.36 × 1028 . 13 13 13 (13!)4 The expression with factorials could have been obtained directly by imagining shuffling the cards and giving the first 13 to A, the next 13 to B etc., and then adjusting for the fact that the order of cards within each player’s hand doesn’t matter. As Wikipedia remarks (at http://en.wikipedia.org/wiki/Bridge_probabilities as of December 1, 2014), “The immenseness of this number can be understood by answering the question ‘How large an area would you need to spread all possible bridge deals if each deal would occupy only one square millimeter? ’. The answer is: an area more than a hundred million times the total area of Earth.” (c) The answer to (b), though an extremely large number, is much smaller than the fourth power of the answer to (a) since cards This 39the 26 5252replacement. 5252  are dealt without 13 makes the number of possibilities 52 rather than 13 13 13 13 13 13 13 13 .

5

6 13.

A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. Thus, the superdeck has 52 · 10 = 520 cards, with 10 copies of each card. How many different 10-card hands can be dealt from the superdeck? The order of the cards does not matter, nor does it matter which of the original 10 decks the cards came from. Express your answer as a binomial coefficient. Hint: Bose-Einstein. Solution: A hand is determined by specifying how many times each of the 52 different cards occurs. Number the 52 cards in a standard deck as 1, 2, . . . , 52, and let xi be the number of times card i occurs in a hand (e.g., 3 for the Ace of Spades in the above example). Then the xi are nonnegative integers with x1 + x2 + · · · + x52 = 10. By Bose-Einstein, the number of solutions is ! ! 52 + 10 − 1 61 = ≈ 9.018 × 1010 . 10 10

14.

You are ordering two pizzas. A pizza can be small, medium, large, or extra large, with any combination of 8 possible toppings (getting no toppings is allowed, as is getting all 8). How many possibilities are there for your two pizzas? Solution: For one pizza, there are 4 · 28 = 210 possibilities. For two pizzas, there are 210  ways to choose two distinct kinds of pizza, and 210 possibilities with two copies of 2 the same kind of pizza. So the number of possibilities is ! 210 + 210 = 524800. 2 Alternatively, think of choosing 2 pizza types with replacement, where order doesn’t matter. Then Bose-Einstein gives the same answer: the number of possibilities is ! 210 + 2 − 1 = 524800. 2

Story proofs 15.

s Give a story proof that 

n k=0 k

Pn

 

= 2n .

  Solution: Consider picking a subset of n people. There are nk choices with size k, on the one hand, and on the other hand there are 2n subsets by the multiplication rule. 16.

s Show that for all positive integers n and k with n ≥ k,  ! ! ! n n n+1 + = , k k−1 k doing this in two ways: (a) algebraically and (b) with a story, giving an interpretation for why both sides count the same thing. Hint for the story proof: Imagine n + 1 people, with one of them pre-designated as “president”. Solution:

Probability and counting

7

(a) For the algebraic proof, start with the definition of the binomial coefficients in the left-hand side, and do some algebraic manipulation as follows: ! ! n n! n! n + = + k k−1 k!(n − k)! (k − 1)!(n − k + 1)! = = =

(n − k + 1)n! + (k)n! k!(n − k + 1)! n!(n + 1) k!(n − k + 1)! ! n+1 . k

(b) For the story proof, consider n + 1 people, with one of them pre-designated as “president”. The right-hand side is the number of ways to choose k out of these n + 1 people, with order not mattering. The left-hand side counts the same thing in a different way, by considering two cases: the president is or isn’t in the chosen group.  n  , since once we fix The number of groups of size k which include the president is k−1 the president as a member of the group, we only need n to choose another k − 1 members out of the remaining n people. Similarly, there are k groups of size k that don’t include the president. Thus, the two sides of the equation are equal. 17.

Give a story proof that n X k=1

for all positive integers n.

n k k

!2

! 2n − 1 , =n n−1

Hint: Consider choosing a committee of size n from two groups of size n each, where only one of the two groups has people eligible to become president. Solution: Imagine that there are n juniors and n seniors in a certain club. A committee of size n is chosen, and one of these people becomes president. Suppose though that the president n  must be a senior. Letting k be  nthe  number n  of seniors on the committee, there are k ways to choose the seniors, n−k = k ways to choose the juniors, and after these choices are made there are k choices of president. So the overall number of possibilities is the left-hand side of the identity. Alternatively, we can choose the president first (as any of the n seniors), and then choose any n − 1 of the remaining 2n − 1 people to form the rest of the committee. This gives the right-hand side of the identity. 18.

s (a) Show using a story proof that  ! ! ! k k+1 k+2 + + + ··· + k k k

n k

!

=

! n+1 , k+1

where n and k are positive integers with n ≥ k. This is called the hockey stick identity. Hint: Imagine arranging a group of people by age, and then think about the oldest person in a chosen subgroup. (b) Suppose that a large pack of Haribo gummi bears can have anywhere between 30 and 50 gummi bears. There are 5 delicious flavors: pineapple (clear), raspberry (red), orange (orange), strawberry (green, mysteriously), and lemon (yellow). There are 0 nondelicious flavors. How many possibilities are there for the composition of such a pack of

8 gummi bears? You can leave your answer in terms of a couple binomial coefficients, but not a sum of lots of binomial coefficients. Solution: (a) Consider choosing k + 1 people out of a group of n + 1 people. Call the oldest person in the subgroup “Aemon.” If Aemon is also the oldest person in the full group, then   there are nk choices for the rest of the subgroup. If Aemon is the...