Hello again!
The problems for this assignment are all in Chapter V, Section 8, Problems for Solution, pages 140–145.
Remember that I am trying to indicate how you would read a book like this on your own. So I am going to go through and tell you how I would decide whether each problem is worth doing right now. (They’re probably all worth doing sometime, but life, and our class, are short.)
As before, I will indicate which ones I think are most central to do. If you are running low on time, you could do just those. I will also indicate which ones are an interesting challenge. If you are finding the central ones easy, you could spend more time on the challenging ones.
The writing up of problems is probably getting long! It is OK if you do not write all solutions in detail. What I will ask you to do is use your judgement: which questions do you need to write up fully, in order to demonstrate to me (and yourself!) that you know what is going on? If you have made a list of “main ideas” of the chapter, then the problems you choose to write up in detail should reflect that list: at least one problem for each main idea, that shows that you understand it.
Remember that you can check your answers at the back! There were several times I thought I understood something, saw that my answer disagreed with the author’s, and then realized what I was misunderstanding.
Assignment (8. Problems for Solution, pages 140–145)
Problem 1: This is a good question for using the most basic concepts/formulas about conditional probability. However, it does use some slightly tricky combinatorics (counting how many ways something can happen). I am trying to de-emphasize combinatorics—not because it isn’t fun or important, but for lack of time. (It will be covered in the Discrete Math class in Spring.) In this book, combinatorics is discussed in Chapter II, which we skipped for now.
So, I would suggest trying this problem. But if you are short on time, or if you get confused by the combinatorics, you can skip it.
Problem 2: This one is central, and everyone should do it. It addresses the same central concepts as Problem 1, but involves less combinatorics.
Problems 3 and 4: These problems cover some similar ground to Problems 1 and 2, but they use more combinatorics. If you like combinatorics already, or you want to spend time learning it more, go for it and do these problems. There’s more detail about how to do such problems in Chapter II. But if you are short on time, you can safely skip them.
Problem 5: Skip it, it refers to Chapter II which we skipped for now.
Problem 6: This one is super-important, and everyone should do it. It addresses a very important idea we will be using often. (See Section 1 Example (d).) I would recommend you write it up in detail.
Problem 7: Recommended. Very similar to Problem 6. (If you had to ask for help on Problem 6, be sure to write up Problem 7, to be sure you get this idea.)
Problem 8: This refers to combinatorics from Chapter II that we skipped. It is possible to do it by using the Table from Chapter II that the author refers to, and that is worthwhile. But if you’re short on time you can skip it.
On the other hand, if you are interested in combinatorics, this is a really interesting combinatorial question. If you want to learn how to do it, look at the section in Chapter II that contains the Table the author refers to.
Problem 9: Not as central as Problems 6 and 7, but worthwhile and recommended.
Problem 10: Also worthwhile and recommended. You will need the trick for adding up infinite series that I discussed in the Chapter I Assignment, Problem 4.
Once you find the answer, I want to make a comment and suggestion. Go do the problem, I’ll wait!
OK, did you get the answer? Notice that the game is more likely to end in an odd number of throws, than it is to end in an even number of throws. Why is that??
If you have time, I’d recommend doing a generalization of this problem. Instead of the game ending when you roll a 1, with a 1/6 chance, suppose that the game-ending event happens with some probability p. Let q=1-p be the probability that the game doesn’t end on a particular roll (in the original problem, q=5/6). Now, solve the problem again in terms of p and q. What happens to your solution if p is large (close to 1)? Does that make sense? What happens to your solution if p is small (close to 0)? Does that make sense?
(This is something I do when I am reading a book like this. It’s not just doing the problems, but also trying to understand the answers. The first time I did this problem, it didn’t make sense to me that game should be more likely to end in an odd number of throws. When I was thinking about why that is true, I came up with the generalization above. That way I could see more clearly what happens, if p is really tiny.)
Problem 11: I would start by answering this problem when k=1. Your answer should be in the form of an infinite series. HOWEVER, it is not going to be easy to get your answer in the form the author gives it, so don’t knock yourself out trying to do that. This should be enough to get the main idea; you could skip the rest.
If you are looking for a challenge problem, try k=2 next, then k=3, to get a sense of the pattern. Your answers will still be infinite series. In order to sum the series to get the answer the author gives, you will need to either use some fairly fancy reasoning along the lines of Chapter I Assignment Problem 4, or you will need to use some calculus. If you are interested, ask me for hints!
Problem 12: Only try this one if you did the rest of Problem 11. Otherwise you can safely skip it.
Problem 13: This one is important, and everyone should do it. Part (a) should be not too hard. Part (b) is tricky. Give it a good try, but if you are stuck we can discuss it in class. It illustrates a subtle and important point (which we’ll also come back to in Examples (d) and (e)). Part (c) should be not too hard if you’ve figured out part (b) (it’s a generalization to show what is going on, like I was doing in Problem 10).
Problem 14: This is not directly testing any main concepts of the chapter, so you could safely skip it. However, it is interesting, and it introduces the important idea of recursion, which we will use later, so if you have time it is worth trying! But if you are short on time, skip it for now, there are other more important problems. (Note that the author forgets to state an assumption: he is assuming that, in each individual game, both players have probability 1/2 to win.)
Problems 15, 16, and 17: Problem 15 is pretty easy (you could do it if you have time), but looking ahead, the main point seems to be applying this to exponentials (which we haven’t done yet) and a thing from Chapter IV (which we skipped). So you could skip these three problems safely. (They aren’t directly testing any main concepts of the chapter.)
Problem 18: This is another good problem, of the same sort as Problems 6 and 7. Recommended, unless you are super-short on time.
Problem 19: This problem is to prove an interesting and surprising fact about Polya’s urn model. I’d like everyone to try at least part of it, as explained below.
When I did this problem, I started by trying to understand the statement first. I started to do that by picking specific numbers. The simplest numbers that made it not TOO simple were b=r=c=1. In this case, on the first draw, there is one black and one red ball in the urn, and the probability of black is 1/2. The problem is saying that the probability of black on EVERY turn is 1/2! This doesn’t seem right!
So I started trying it out. Here is what I would recommend:
- First, assume b=r=c=1. This makes it easier to picture. Figure out the probability of getting a black on the second draw. (Note that we are assuming we don’t know what the first draw was!) Can you get the answer 1/2, as the problem claims?
- If you can do that successfully, then try to find the probability of black on the third draw in a similar way.
- Now generalize: rather than b=r=c=1, do the probability as a formula in b, r, and c. Find the probability of black on the first draw, on the second draw, and on the third draw.
There is a subtle thing (in my opinion) going on here: can you express what it is?
Now, the way to make this a proof that works for any draw is to use “mathematical induction”. (In math, we just call this “induction”; the “mathematical” in the name is to distinguish it from a loosely related but different idea in philosophy.) I am not assuming that you know about induction for this class, so you could stop the problem here if you like.
If you’ve seen induction before, and you’re looking for a challenge problem, you can go ahead and try to make a proof.
If you haven’t seen induction before, and want to learn about it, here’s the idea. We want to establish that, IF the claim is true for any draw n, THEN it is true for the next draw n+1 —without specifying what draw we are on (without specifying n). If we can establish that “relative” result, then this will prove it for all n, as follows. We know the claim is true for the first draw (we checked), so it must be true for the second. Since the claim is true for the second draw, by our relative result again (with n=2), the claim must be true for the third draw. And so on. We will have done infinitely many steps all at once! If you’d like to learn more, you can read about induction in Richard Hammack, Book of Proof, Chapter 10 (the same book I referred you to for Preamble Assignment #1).
Problems 20 through 25: These are getting more deeply into the Polya urn model than I have the patience to go right now! Also, they seem to be using more about the binomial coefficients, which we’ll talk more about in Chapter VI. Let’s skip all these problems for now (with the understanding that it might be good to return to them someday).
Problem 26: This is a good example of how three events can be pairwise independent, and yet all three together are not independent. It’s not too hard, and worth doing to understand this point.
Problems 27 through 40: We are skipping the sections on genetics, so we can skip these problems safely. If you’re interested in biology, you might want to take a look at Sections 5, 6, and 7, and try some problems, but otherwise, we’re done!
