## Saturday, July 23, 2016

### Morning Math 2016 - Part I

I had the privilege of doing another summer of morning math at PCMI. This year Darryl and Bowen wrote and facilitated problem sets focused on "Probability and Big Data." You can find the problem sets here. Spoiler alert for the rest of this post if you are thinking about doing the math yourself (which will be way more fun than reading a summary of my thinking!).

I'm having a hard time tidily describing what I learned and what questions I still have. So instead, I want to map out the evolution of my thinking around one problem. One of the questions that we followed over the course of the whole three weeks was if you are flipping a coin, how many times do you need to flip the coin in order to get heads twice in a row?

A warm-up: What is the average number of flips until you get heads?

Looking at this tree, we can create the following series:
$$1*\frac{1}{2}+2*\frac{1}{4}+3*\frac{1}{8}+…$$
Here the whole numbers represent the number of flips and the fraction is the probability of getting your first H at that flip. Adding about 10 numbers in this sequence we determined that it sums to 2.

What is the average number(or expected value) of flips until you get two heads in a row?
So now our tree diagram gets a whole lot more complicated.
Here are the observations based on the tree diagram:

 # of flips Probability of having gotten HH Probability of not getting HH 2 $$\frac{1}{4}$$ $$\frac{3}{4}$$ 3 $$\frac{1}{4}+ \frac{1}{8}= \frac{3}{8}$$ $$\frac{5}{8}$$ 4 $$\frac{1}{4}+\frac{1}{8}+\frac{2}{16}=\frac{8}{16}$$ $$\frac{8}{16}$$ 5 $$\frac{1}{4}+\frac{1}{8}+\frac{2}{16}+\frac{3}{32}=\frac{19}{32}$$ $$\frac{13}{32}$$ 6 $$\frac{1}{4}+\frac{1}{8}+\frac{2}{16}+\frac{3}{32}+\frac{5}{64}=\frac{43}{64}$$ $$\frac{21}{64}$$

It’s interesting to note that the numerators in the “new” component of the HH and in the total for the not HH both follow the Fibonnaci sequence. I’m not sure why this is yet.

Based on this pattern, I can create the following series, but I still don’t know how to find the sum. And the pattern of the probabilities is harder to describe than when we were just trying to get one H.
$$2*\frac{1}{4}+3*\frac{1}{8}+4*\frac{2}{16}+…$$

Next a re-framing of the question and a new representation of a steady-state diagram (this is the language from Day 12, but it first shows up in Day 2. I’ve added the arrows between states.)

Let a(n) be the probability of being in the 0 state, b(n) be the probability of being in the 1 state, and c(n) be the probability of being in the 2 state, where n is the number of flips.
We can write a recursive formula as follows to determine the distribution after any number of flips based on the distribution before the flip.
$$a(n) = .5*a(n-1)+.5b(n-1)+0*c(n-1)$$
$$b(n) = .5*a(n-1)+0*b(n-1)+0*c(n-1)$$
$$c(n) = 0*a(n-1)+.5b(n-1)+1*c(n-1)$$

We can then translate this into a matrix and do some multiplication to tell us what the distribution between states is after a certain number of flips. All of these decimals here can either be interpreted as the probability that you’ll be in each state, or the % of people who are in each state if you were running n simultaneous games. I found situations where each conception was more helpful to my thinking.

The decimal that is the bottom entry of each of the vectors is equivalent to the HH fractions found in the tree diagram above.  But we still don’t have a way to find the value of the sum. Matrix multiplication can primarily be used to show us that if we flip forever, eventually there is a 100% of having gotten HH. (Duh.)

So let’s look at a modified version of the steady state diagram (also from the Day 12 problem set, with additions by me).

Now we can rewrite our sequence from above:
$$EV=2*.25+(2+EV)*.25+(1+EV)*.5$$
So this is showing us that you can get HH in 2 flips ¼ of the time, ¼ of the time after 2 flips you have to start over, so that’s 2 flips plus whatever the expected value is, and ½ of the time you have to start over after 1 flips, so that will take 1 flip plus whatever the expected value is. Now you just have to solve for the expected value!
$$EV = .5 +.5 + .25EV + .5 + .5EV$$
$$EV = 1.5 + .75EV$$
$$EV-.75EV = 1.5$$
$$.25EV = 1.5$$
$$EV = 6$$
On average, it will take 6 flips to get HH.

Finally, we found that one way to think about the expected value of the number of trials it will take for a specific occurrence in the inverse of the probability of that occurrence. For example, with 1/2 chance of flipping a heads, on average it will take 2 flips to get heads. There are 4 possible combinations when you flip twice, so you could say that the probability of getting HH is 1/4 and thus the # of flips it would take is 4. But this would only make sense if you were repeatedly flipping two coins and recording what you got. I think the fact that the sequence of flips is continuous explains why this reasoning does not work and the expected value is not 4.