The Trouble of Bowling Turkeys: A Look Into the Probability of States

23 minutes

Anyone who’s ever gone out casually bowling with friends has probably had an experience that goes something like this: you go up for your turn, set yourself up for the shot, and then boom: gutterball. And yet later, in an ironic twist of fate, you end up getting a strike for a turn you barely try. While professionals have strikes down to a science, for you a strike usually happens out of nowhere. In fact, it’s almost as if the harder you try for a strike, the more nervous you get and likely to fail. In bowling, there is a special move called the “Turkey” which is achieved when players get a strike three times in a row. Even if you were intentionally trying to get a strike each bowl, with the same technique each time, it feels as if your chances drop with each strike you get. By the time you try for the third, you’re so nervous of messing up that your chances drop to near zero. But of course, you keep trying. So the question becomes: if your chances of getting a strike decreases with every strike, on average how many tries will it take to bowl a Turkey?

To solve this problem, we’ll explore a mathematical technique I like to call the probability of states. This technique opens up a wide range of probability problems, ranging from flipping coins, playing games, and color sequences, and will eventually take us to an introduction of Markov Chains, one of probabilities most useful tools.

A Curious Look At Coins

Before we tackle the troubled Turkey, let’s simplify the problem a bit and consider a coin puzzle: on average how many coin flips does it take to get two heads in a row? Some of you may think the puzzle is easy: a head comes up with 1/2 probability, so the probability of getting two heads in a row is (1/2) x (1/2) = (1/4). So you should get two heads in a row about every 4 flips. Unfortunately this isn’t the full story, otherwise I wouldn’t have written this post. It treats the act of getting two coins flips as a single action. If we treated every two coin flips as a single “turn” and then asked “on average how many turns does it take to get a double heads?” then this would be correct. But we aren’t counting it this way: it’s two distinct coin flips. In the first approach, if you don’t get a double head, you’ve only wasted one turn. But in our approach, you may get one head on your first flip, but your next flip could be a tails. In that case you’d have to start over, because you need two heads in a row. Now you’ve wasted two turns. The number of flips required goes up.

In fact, this is the same issue that makes the original Turkey trickery so hard to answer. Every time we mess up getting the next heads or the next strike, we have to start over. How can we analyze a process that resets all the way back to square one? The trick is to realize that when we do mess up, the entire process remains the same. We may have added some “failed” turns under our belt, but we’ve gone back to the same state.

So what is a state? A state can be thought of as a general point in the process categorized only by your next moves. For example, when you flip a coin and it lands on heads, you only need another heads. This is the same every time you get a heads and still need one more. We can therefore think of the position right after getting one heads as a “state”. When we’re in this state, all of our flips from before don’t matter. All that matters is that we just need one more heads. Keep in mind that while this is a nice way of thinking of it, technically this state does rely on a previous flip: our most recent flip that came up heads. Therefore, a better definition of a state is the position you are in given your most recent move. But for coins and Turkeys, however you want to think of it is the same.

Let’s take another look at the coin puzzle. When we intially start, we need to get two heads in a row. This is the same case whenever we mess up and have to start over. Therefore, this is a state in which whenever we enter it, we need to get two heads in a row. Let’s call this the “start over” state and denote it as $S_0$ .

Now let’s flip a coin. Depending on the result, we can enter one of two states. If we flip heads, we enter the “heads” state in which we only need one more heads. Let’s call that $S_1$ . If we flip tails, we still need two heads in a row, so this is the “start over” state $S_0$ . When we’re at $S_1$ , our paths split again. If we flip heads, that means we got two heads in a row. Since there’s nothing left to get, we’re done, and we enter what I’ll call the “win” state. But if we flip tails, we have to start over, so we enter $S_0$ again. The diagram below gives a nice visualization of the entire process.

Now, our original question was to find out on average how many coin flips it takes to win the game. The beauty of rephrasing the process in terms of states is that now all information about our next moves is always the same at each state. It doesn’t matter if you just started flipping coins or if you’re 238 flips deep: if you justed flipped a heads (hence, at $S_1$ ) you only ever need one more heads, so the average number of flips it takes to finish from that point on should always be the same. Therefore, the average number of flips it takes to get two heads in a row only depends on the state we are in.

For the last piece of the puzzle, we need to think of what an “average” means. At every point in the game, there are an infinite number of possible outcomes. We could get two heads right away, we could get 45 tails in a row and then two heads, we could alternate between heads and tails 147 times, etc. The “average” number of flips needed to win is basically the “average” number of flips in all these different outcomes. Why is this important? I’m glad you asked, mysterious reader I’m talking to. By using states, we’ve already neatly categorized all outcomes. For example, at $S_0$ , the only two outcomes possible in terms of states is either $S_0$ again or $S_1$ . Therefore, the average number of flips needed at $S_0$ is simply the average of the average number of flips needed at $S_0$ and $S_1$ . The only problem, though, is that in order to leave $S_0$ , we actually waste a flip. This means we need to add one to this average in order to keep the number of flips the same and for this calculation to make sense.

For reasons that we’ll see later, lets denote this “average number of flips” for $S_0$ as $E_0$ and for $S_1$ as $E_1$ . Our realization therefore gives the following result:

$E_0 = \frac{1}{2}E_1 + \frac{1}{2}E_0 + 1$

Doing the analysis for $S_1$ , we can either win the game or go back to $S_0$ . The number of flips required to win the game when we have already won the game is 0 (duh), so writing an equation for $E_1$ gives:

$E_1 = \frac{1}{2}(0) + \frac{1}{2}E_0 + 1$

This is just a system of two equations! There are number of different ways to solve this, but skipping the boring algebra, this solves to give that $E_1= 4$ and $E_0 = 6$ . We are interested in the answer for when we intially start the game, which is at $S_0$ , so this corresponds to $E_0$ . We’ve found our answer! The average number of flips it takes to get two heads in a row is 6.

This is the power of states. We essentially skipped any messy hassles with analyzing large sequences of heads or tails. By rephrasing the problem into states, we simplified the game down to only a few cases, giving us the ability to relate values to one another and create a system we can easily solve for. It almost feels like cheating. But before we can use this process to solve our Turkey tantalization, we need to formalize the idea a little bit. For example, what if there’s more than one state? What exactly do we mean by the “average” of states? What if the probabilities we are dealing with aren’t just 50/50? And why is it called the probability of states anyway?

Formalizing the Process

Remember when we defined what a state was we gave two separate definitions:

A state can be thought of as a general point in the process categorized only by your next moves. . . . a better definition of a state is the position you are in given your most recent turn. But for coins and Turkeys, however you want to think of it is the same.
– me.

The explanation for why this is true is because your most recent turn is all that is needed to determine your next moves. When it came to coins, the only thing that determined what you needed next was your most recent flip. For random reasons that defintely don’t foreshadow what is to come, this special property is called the Markov property. Formerly, the Markov property is the property in which future states only depend on your current state. The process only cares about your most recent move to determine the future and forgets all past moves (for this reason, it’s usually called a “memoryless” process). Our trick with the coin problem relied on this fact to compute our averages.

So how exactly does computing the averages work? In probability, the formal definition of this “average” is expected value. The expected value can be thought of as a weighted average of all possible outcomes, where each outcome is weighted by its probability of occuring (it should be clear soon that this weighting is where the “probability” in probability of states comes from). In math symbol jargon, we can write this as

$\displaystyle E[X] = \sum_{i=1}^{n}p_ix_i = p_1x_1 + p_2x_2 + p_3x_3 + \dots + p_{n-1}x_{n-1} + p_nx_n\;\;\;\;(*)$

Here, the variable we are dealing with is labeled as “ $X$ ” (think of $E[X]$ as the average number of flips). This variable has $n$ outcomes labeled “ $x_1, x_2, \dots x_n$ ” (think of each of these outcomes as corresponding to an event, such as flipping “heads, tails, heads, heads”, and each $x_1, x_2, \dots x_n$ represents the number of flips), and each outcome is weighted by a probability (in our example, this would be the probability of “heads, tails, heads, heads” happening). The idea behind expected value is that it averages outcomes by how likely they are. For example, getting “heads, tails, heads, heads” is more likely that getting 45 tails in a row and then two heads, so are expected value should be weighted so that its closer to 4 than to 47. This weighting was actually already used in the coin puzzle as coefficients for $E_0$ and $E_1$ , but it was harder to notice since the probabilities were both 1/2 and 1/2.

<random tangent> One neat property that can directly be seen from (*) is that expected value preserves scaling. That is, if we instead wanted to find $E[2X]$ , then all the outcomes of $X$ would just be scaled by 2, giving us that $2E[X]$ . This works for any real number $c$ , meaning that $E[cX]=cE[X]$ . <random tangent over>

However, the problem with using (*) exactly is that in the coin problem there are an infinite number of possible flip sequences, so our $n$ would be infinity. An infinite sum of infinitely many sequence combinations, all multiplied by their probabilites. By all means, you could give that a try, but I think it would be better to find an easier way of going about things. The key is to utilize linearity of expectation, a useful property of expected values. If we think of formula (*) above, the whole equation is linear. This linearity allows us to break down expectations easily. But to show this, we need a different definition for expected value. Let’s instead think of $X$ as a function that inputs events and outputs numerical outcomes. In our above coin example, think of this as X(“heads, tails, heads, heads”) = 4, meaning for the event “heads, tails, heads, heads”, $X$ computes the number of total flips. Futhermore, let the probability of an event $s$ occuring be $P(s)$ . Now we can index formula (*) by events $s$ rather than numerical outcomes, giving:

$\displaystyle E[X] = \sum_{s}X(s)P(s)$

Here, the sum symbol $\sum_{s}$ simply means to sum over all possible events $s$ . This is the exact same equation, just written differently. Why is this useful? Good question, disembodied voice in my head. Consider another variable $Y$ that we add to $X$ . That is, for every event $s$ , we find $(X+Y)(s) = X(s) + Y(s)$ . Then calculating for $E[X + Y]$ gives:

$\displaystyle E[X + Y] = \sum_{s}(X(s) + Y(s))P(s)$

Since we indexed by event, we can use the same probability $P(s)$ for both outcomes, because it’s the same event, reducing are need to focus on so many different probabilities like in (*). This allows us to then distribute:

$\displaystyle E[X + Y] = \sum_{s}X(s)P(s) + \sum_{s}Y(s)P(s)$

giving our definition again, now in terms of $X$ and $Y$ . This leaves us with:

$\displaystyle E[X + Y] = E[X] + E[Y]$

Probably what was expected (haha, get it?), but still neat! In fact, this process can be easily extending to any number of variables, not just two. This result is known as the linearity of expectation, and is commonly dubbed one of the most important formulas in all of probability. This is because there isn’t really any restriction on what $X$ and $Y$ could be, allowing us to use this in a variety of different ways, one of which being the probability of states technique.

Let’s revist the coin example, this time with a more formal approach. Suppose $X$ is the number of coin flips until gettting two heads in a row. This variable is different depending on what flips we get, but we are interested in finding $E[X]$ , the expected number of coin flips until gettting two heads in a row. Notice how $X$ can be broken into two other variables: $X_0$ , the number of coin flips until gettting two heads in a row after already flipping a tails, and $X_1$ , the number of coin flips after already flipping a heads. Since we can only flip either heads or tails, this covers all possible events. But $X$ isn’t just the sum of these two variables, because only either $X_0$ or $X_1$ can happen. It’s more of an average… a weighted average of course! (bet you were waiting for that to come back!) Now in this case the probabilities are still only (1/2) and (1/2), but we’ll later see how this can be extended to a more complicated weighted average. The last thing to consider is that both $X_0$ and $X_1$ don’t count the first flip, because both already assumes you’ve already flipped a heads or tails. So we need to add 1. Using linearity of expectation, this gives us that

$E[X] = E[\frac{1}{2}X_1 + \frac{1}{2}X_0 +1] = E[\frac{1}{2}X_1] + E[\frac{1}{2}X_0] + E[1]$

Now we can use the fact that expected value preserves scaling (haha, tangent not so random now, eh?) and the fact that $E[1] = 1$ , because the expected value of the constant 1 is just 1. This gives:

$E[X] = \frac{1}{2}E[X_1] + \frac{1}{2}E[X_0] + 1$

Simplifying the notation a bit, let’s let $E[X] = E$ , $E[X_0] = E_0$ and $E[X_1] = E_1$ . The last thing to realize is there really shouldn’t be anything different between $E_0$ and $E$ . The number of flips you are expected to take shouldn’t matter whether you just flipped tails or you’re just starting out. Either way, you have made no progress towards two heads in a row. This gives us the final equation:

$E_0 = \frac{1}{2}E_1 + \frac{1}{2}E_0 + 1$

Exactly what we had before! This is the mathematical intuition behind the probability of states: thinking in terms of expected value. You may find our original method, thinking in terms of states, quicker and more practical, and it is. That’s the method that the main technique uses. But seeing the process this way gives us a more concrete understanding of where it comes from (and, too be honest, makes all the math feel less fake). More importatnly, it allows us to better understand what we meant by “average” and extend the technique to beyond coin flips as we tackle the troublesome Turkey.

How To Bowl A Turkey

First, we need to assume some probabilities. Let’s say you’re actually not that bad at bowling, and can get a strike (1/2) of the time. But then you get more nervous, and immeditately after getting a strike you can only bowl a strike 1/3 of the time. And on your last bowl, you can only bowl a strike 1/5 of the time. For this problem, we will ignore actual bowling rules were you get two bowls per turn. For our purposes, if you don’t get a strike, it’s a wasted turn.

Now we split the problem into states (try looking away and guessing what these might be yourself! Or not. That’s your business). Now that you’re looking at the screen again: there is the state after getting a strike in your previous turn, $S_1$ , the state after having two strikes in a row, $S_2$ , and the state in which you start over from square one, $S_0$ . This gives us the following diagram:

wow, I really wish my diagram editor made loops look better

Let’s represent the expected value of bowls until getting a Turkey for each state as $E_0, E_1$ and $E_2$ respectively (For simplicity, we’ll refer to these values as if they are the states themselves, allowing us to say we are “at $E_0$ ” when we really mean “at $S_0$ “). When we’re at $E_0$ , we can either transition to $E_1$ by getting a strike with a 1/2 chance, or by staying where we are by missing with a (1/2) chance. This gives:

$E_0 = \frac{1}{2}E_1 + \frac{1}{2}E_0 + 1$

At $E_1$ , we can either transition to $E_2$ by getting a another strike now with a 1/3 chance, or by missing and returning to $E_0$ now with a 2/3 chance. Keep in mind this is now a true weighted average, and we average $E_2$ and $E_0$ by weighting them with their probabilities, giving:

$E_1 = \frac{1}{3}E_2 + \frac{2}{3}E_0 + 1$

Finally, at $E_2$ we can either bowl a third strike and bowl a turkey (therefore needing 0 more bowls) with a 1/5 chance, or miss and return to $E_0$ with a 4/5 chance, giving:

$E_2 = \frac{1}{5}(0) + \frac{4}{5}E_0 + 1$

Another system of linear equations, now with 3 variables. Like before, you can now solve for $E_0$ with a number of techniques. Try to solve the above equations yourself, then reveal the answer below by highlighting the text in the box with your cursor.

E₀ = 50, E₁ = 48, E₂ = 41. It takes about 50 bowls before getting a Turkey! Now if only I can figure out how to make a “click to reveal” text box on WordPress for free…

Of course, this is only true for the specific probabilities we assumed, but the process is the exact same with different values. Check out this program here and use the sliders to play around with the probabilities and see how the answer changes!

We can now generalize the technique: First, categorize the problem into a number of states, and see how they relate to each other. Next, create a system of equations for the expected values at each state. Each equation expresses an expected value as the average of the expected values of the states it can go to, weighted by probabilities, and then adding one. Finally, solve the system to find the needed expected value. And while we only used this for coin flips and bowling, any problem that requires getting some sequence in a row (like a sequence of heads or a sequence of strikes) can be solved with this trick. Congratulations! You have now mastered the probability of states technique.

Some Important Remarks

Here’s a couple of points before we conclude.

(1) Keep in mind that while in both our coin puzzle and Turkey tackling the expected value came out to a whole number, this isn’t always the case, which you can see by playing around with the sliders above. Expected value should not be thought of as a value that is possible, it is just an average. Therefore, if in the Turkey problem, you get an answer of 45.7, you shouldn’t think of it as “I will get a Turkey on approximately the 46th bowl”. Never round the expected value to a whole number! Instead, think of it as “If I was to bowl until I got a Turkey many, many times, on average it would take me 45.7 bowls to do so”.

(2) For both examples, we skipped the algebra of solving the linear equations, mostly because this can already be solved by a variety of known techniques. More importantly, though, it can be really easily solved by computers. This is important because even if the problem was really complicated and had numerous equations, we don’t have to rely on hand computation for the last step. The technique of probability of states is mostly about forming the equations: we can let the robots do the messy algebra for us.

(3) Actually, the equations follow nice patterns in specific situations. You may have already seen in our Turkey example how for each state there were only two options: going to the next state, or going back to the beginning with oppositie probability. This is always the case for any problem dealing with “in-a-rows”. For this reason, the equations follow nice patterns and can actually be solved in general for any number of states or with any probabilities. It’s a nice exercise to solve for it if you wanna give yourself a challenge, but for completeness it’s provided below:

The expected value of getting something $n$ times in a row, where the probability of getting it on the first try is $p_1$ , the immediate second try $p_2$ , etc., up to $p_n$ is

$E = \frac{1}{p_np_{n-1}\dots p_3p_2p_1} + \frac{1}{p_np_{n-1}\dots p_3p_2} + \frac{1}{p_np_{n-1}\dots p_3} + \dots + \frac{1}{p_np_{n-1}} + \frac{1}{p_n}$

Try using $n=2, p_1 = \frac{1}{2}, p_2 = \frac{1}{2}$ for the coin problem and $n=3, p_1 = \frac{1}{2}, p_2 = \frac{1}{3}, p_2 = \frac{1}{5}$ for the Turkey problem.

(4) Not all problems follow this pattern. For example, lets say you were observing a sequence of colors Red, Blue, Green, and Yellow, and you were waiting until you observed the sequence “Blue, Green, Blue”. Now it’s no longer a single thing that is “in-a-row”, and the equations change a bit. For example, lets observe the state after getting a blue. If you get a red or yellow, you go back to the beginning, and if you get a green, you move to the next state: these two options are like before. But if you get another blue, you don’t start over, because you’re still in the state of getting a blue. This adds a third option, and complicates the problem. Our states diagram may look something like this:

As you can see, the equations no longer follow our neat pattern (try giving each color a probability (such that they add to 1) and see if you can form the equations yourself!). There is still a nice formula in these cases for finding the final expected value without dealing with multiple equations, but it requires a completely different approach. For now, if you want to impress your friends but don’t wanna deal with several equations, just stick to the “in-a-row” examples.

The Bigger Picture

The probability of states is just a name given for this technique that deals with expected values of separate states, but the actual math involved comes from much larger areas. For example, expected value is used extensively in probability and statistics, and the linearity of expactation is a famous and extremely powerful result. This is mainly because the formula allows you to ignore any dependency between two events, which makes it very easy to implement. The idea of states, however, comes from Markov chains, which is where the term Markov property comes from. Like most things in math, these were named after a really old guy named Markov, but unlike things in math, this happens to be the same guy who discovered it. Markov chains allow us to encode various states and how they interact with each other in the form of a matrix, which allows you to model systems very powerfully. Any system that can be divided into states and assumed to follow the Markov property can be modeled this way, which includes several processes in various topics such as chemical reactions, cell biology and DNA, economics and finance models, population growth, medical testing, and much much more. The specific technique of probability of states is more often called the hitting time in the study of Markov chains.

My hope is that by showing this technique, I not only gave you an idea about how to solve interesting puzzles dealing with sequences and games, but also an introduction into other core concepts of probability and statistics, and a starting ground for further research. That is, unless you get too caught up with trying to bowl that Turkey.

The Trouble of Bowling Turkeys: A Look Into the Probability of States

A Curious Look At Coins

Formalizing the Process

How To Bowl A Turkey

Some Important Remarks

The Bigger Picture

Author: Corbin

Leave a comment Cancel reply

A Curious Look At Coins

Formalizing the Process

How To Bowl A Turkey

Some Important Remarks

The Bigger Picture

Share:

Related

Author: Corbin

Leave a comment Cancel reply