May 26, 2017

Let's go on a mathematical adventure! We'll look at a couple of seemingly different things which are all actually related. First we'll look at calculating probabilities for slot machines, then we'll draw some spiffy triangles which make our lives easier. To finish off we'll look at a general and very nice rule for expanding $(x + y)^n$, where n can be any positive integer.

Imagine playing a simple slot machine which has a 5% chance (probability) of you winning a single game. You have enough coins for 10 games. You wonder "what's the probability for me winning *exactly* 3 of these 10 games?". We can figure this out using some methods from probability theory and the information above.

Let's give the $5\%$ probability a name. Let's call it $p$. We say that $p = 5/100 = 0.05$. In probability theory, probabilities range between $0$ and $1$, not $0$ and $100$, so we make sure to divide percentages by $100$. Furthermore, we assign the number of games we can play to $n = 10$. The number of games we hope to win is assigned to $k = 3.$ Finally we also calculate the probability of *loosing* a single game. Since we had $p = 0.05$, the probability of loosing is one minus $p$, let's call this $q = 1 - p = 1 - 0.05 = 0.95$. You can think of this as subtracting the probability of winning a single game, $5\%$, from the maximum probability possible, $100\%$.

The probability of winning 3 out of 10 games can be calculated using what's known as the *binomial probability mass function*, the bin pmf. We'll explore it in detail below:

\[{n \choose{k}} \cdot p^k \cdot q^{n - k} = {10 \choose{3}} \cdot 0.05^3 \cdot 0.95^7\]

If you're unfamiliar with the $n \choose{k}$ bit, don't fear. This bit (factor) has the dry name *binomial coeffecient*, which simply states that it is a number in the binomial pmf. This coefficient is very nifty and can be used to figure out how many ways you can order $k$ things among a total of $n$ things. For us it represents how many ways we can arrange winning $k=3$ games out of a total of $n=10$ games. We do this because we do not know which of the 10 games we will win, so we must take into account that any 3 games of the total 10 can be won, in any order. You can think of it like this: Let W denote winning a single game and L loosing it. Then one possible order of winning 3 out of 10 games is: WWWLLLLLLL. But another one is WWLWLLLLLL. Yet another one is WWLLWLLLLL. And WLWLWLLLLL. And LLLLWWLLLW. The total number of ways to arrange the Ws and Ls is denoted $n \choose{k}$, or more specifically $10 \choose{3}$. This is equivalent to the number of ways 3 out of 10 games can be won.

Now, ${n \choose{k}}$ is just mathematical notation, it doesn't tell us much unless we know how to calculate it. One way is to list all possible WWWLLLLLLL-combinations and count them, but this is tedious and error-prone. A purely algebraic way is

\[ \begin{aligned} {n \choose{k}} &= \frac{n!}{k!(n - k)!} \\ \\ {10 \choose{3}} &= \frac{10!}{3!7!} = \frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot(7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)} = \frac{3628800}{30240} = 120 \end{aligned} \]

You might not be familiar with the ! in the expression above. It's called the factorial and is simply the number in front of the ! multiplied by all numbers smaller than itself, all the way down to 1. For example $8! = 8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$.

So, now we can go back to our probability and swap ${10 \choose{3}}$ with $120$:

\[{n \choose{k}} \cdot p^k \cdot q^{n - k} = {10 \choose{3}} \cdot 0.05^3 \cdot 0.95^7 \] \[ = 120 \cdot 0.05^3 \cdot 0.95^7 = 120 \cdot 0.000125 \cdot 0.6983 \approx 0.0105\]

This means that if we have a slot machine with a 5% chance of winning and we want to win 3 out of 10 games, then this will occur with a 0.0105 probability, which corresponds to 1.05%. Not a great outlook in other words!

You probably wonder why we take $0.05$ to the power of $3$ ($0.05^3$) and $0.95$ to the power of $7$. Recall that $0.05^3$ means that we take $0.05$ times itself three times, i.e. $0.05^3 = 0.05\cdot0.05\cdot0.05$. In probability theory you can take two or more unrelated events and multiply their probabilities together in order to find the probability of all of them occurring. This is exactly what we're doing here, the probability of winning 3 games is the probability of winning 1 game multiplied by itself 3 times. We can do this since the events are unrelated; winning one game does not affect the outcome of the next. Using the same idea we multiply the probability of loosing a game, $0.95$, with itself 7 times in order to find the probability of loosing 7 games. We then multiply the probability of winning 3 games with the probability of loosing 7 games, $0.05^3\cdot0.95^7 = 0.00008729$. This is the probability of winning 3 and loosing 7 games, but this can be done in ${10 \choose{3}} = 120$ different ways! So we just multiply the probability of the wins and losses with the number of ways it can happen, i.e. $120\cdot0.05^3\cdot0.95^7 = 0.0105$, which is our final probability.

Please note that we asked for the probability of winning *exactly* 3 of 10 games, not 3 or more. If we wish to calculate the probability of winning 3 or more out of 10 games, we'd have to calculate the probability of winning exactly 3 games, and the probability of winning exactly 4 games and 5 and 6 and so on up to 10. We'd then have to add these probabilities up. If you do this you'll end up with a probability of $0.0115$, which is only slightly higher than the one for winning exactly 3 games. This is because the probability of winning 4 games is very small, winning 5 even smaller. Adding them up doesn't do much in this case.

Above we had

\[{n \choose{k}} = \frac{n!}{k!(n - k)!} = {10 \choose{3}} = \frac{10!}{3!7!} = \frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot(7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)}\]

For big values of $n$ or $k$ the fraction becomes *very* lenghty. We can make our lives easier by canceling factors in the fraction:

\[{10 \choose{3}} = \frac{10\cdot9\cdot8\cdot\sout{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}}{3\cdot2\cdot1\cdot\sout{(7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)}} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1} = \frac{720}{6} = 120\]

The general result of this cancellation is usually given as an explicit formula, which is handy for doing the calculation by hand (har har):

\[{n \choose{k}} = \frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-k+1)}{k!}\]

Try to see how ${10 \choose{3}} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1}$ would fall out of this formula. The numerator in the formula says that we should start at $10$ and then multiply it with all numbers smaller than itself all the way down to $n - k + 1 = 10 - 3 + 1 = 8$. It is especially useful when $n$ is big and $k$ is small, since we get way fewer factors than with our previous formula. For situations where $n$ is big and $k$ is close to $n$, it gives little help since just a few factors will cancel. Note that $k$ can never be bigger than $n$ nor can any of $n$ or $k$ be less than zero.

There is another, more graphic and mnemonic-y way of finding the value of a specific binomial coefficient. Let's draw Pascal's triangle!

\[ \begin{aligned} & & & & & & & & & & & 1 & & & & & & & & & &\\ & & & & & & & & & & 1 & & 1 & & & & & & & & &\\ & & & & & & & & & 1 & & 2 & & 1 & & & & & & & &\\ & & & & & & & & 1 & & 3 & & 3 & & 1 & & & & & & &\\ & & & & & & & 1 & & 4 & & 6 & & 4 & & 1 & & & & & &\\ & & & & & & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & & & & &\\ & & & & & 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 & & & &\\ & & & & 1 & & 7 & & 21 & & 35 & & 35 & & 21 & & 7 & & 1 & & &\\ & & & 1 & & 8 & & 28 & & 56 & & 70 & & 56 & & 28 & & 8 & & 1 & &\\ & & 1 & & 9 & & 36 & & 84 & & 126& & 126& & 84 & & 36 & & 9 & & 1 &\\ & 1 & & 10 & & 45 & & 120& & 210& & 252& & 210& & 120& & 45 & & 10 & & 1 \end{aligned} \]

Finding $10 \choose {3}$ using Pascal's triangle goes as follows: Count the rows from the top, starting at $0$ for the first row, $1$ for the second and so on until you reach $10$. For the specific triangle above, this will be the last row. On that row, start counting the columns from left or right, again starting at $0$. Do this until you reach $3$. You should now be staring at the value of ${10 \choose {3}} = 120$.

Drawing your own Pascal's triangle is very easy. Start with the top triangle consisting only of 1:s:

\[ \begin{aligned} & & 1 &\\ & 1 & & 1 \end{aligned} \]

Add a new row at the bottom with 3 numbers. Let the numbers in this new row be the sum of the numbers diagonally above them. Numbers on the edges (furthest to the left or right) should be 1.

\[ \begin{aligned} & & & 1 & &\\ & & 1 & & 1 &\\ & 1 & & 2 & & 1 \end{aligned} \]

Repeat.

\[ \begin{aligned} & & & & 1 & & &\\ & & & 1 & & 1 & &\\ & & 1 & & 2 & & 1 &\\ & 1 & & 3 & & 3 & &1 \end{aligned} \]

Doing this 7 more times should produce the big triangle we used to calculate $10 \choose {3}$ above. Huzzah!

Pascal's triangle is named after the French mathematician and physicist Blaise Pascal. He's known for Pascal's law, which describes transmission of fluid pressure. The SI-unit for pressure, Pascal, is named after him.

Have you ever memorized that $(x + y)^2 = x^2 + 2xy + y^2$? Maybe $(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$? How about memorizing $(x + y)^4$? Have no fear, the *binomial theorem* is here (also called *binomial expansion*). It is a theorem which can be used to calculate a binomial to any power. A binomial is just a polynomial with exactly two terms, hence the *bi* in the name. Examples are $(x + y)$, $(3x + 1)$, $(a + z)$ or whatever you like.

The binomial theorem looks very similar to the binomial probability mass function, in fact it looks just like a sum of several bin pmf:s. Here are two examples for different powers:

\[ \begin{aligned}\\ (x + y)^2 &= {2 \choose{0}}x^0y^2 + {2 \choose{1}}x^{1}y^{1} + {2 \choose{2}}x^{2}y^0 \\ \\ &= 1y^2 + 2xy + 1x^2 = x^2 + 2xy + y^2 \end{aligned} \]

\[ \begin{aligned}\\ (x + y)^3 &= {3 \choose{0}}x^0y^3 + {3 \choose{1}}x^1y^2 + {3 \choose{2}}x^2y^1 + {3 \choose{3}}x^3y^0\\ \\ &= 1y^3 + 3xy^2 + 3x^2y + 1x^3 = x^3 + 3x^2y + 3xy^2 + y^3 \end{aligned} \]

See the pattern? For the sake of consistency I start with the terms in the same order as in the bin pmf, but I flip everything around at the last equals sign to make them look like the rules you might have memorized. Also, recall that any number taken to the power of $0$ equals $1$, that's why $x^0 = 1$ and $y^0 = 1$ above vanish, multiplying with $1$ does nothing. Together with Pascal's triangle, binomial expansions to high powers can easily be "remembered". Let's do one to the power of $5$. Here's a Pascal's triangle with 6 rows:

\[ \begin{aligned} & & & & & & 1 & & & & &\\ & & & & & 1 & & 1 & & & &\\ & & & & 1 & & 2 & & 1 & & &\\ & & & 1 & & 3 & & 3 & & 1 & &\\ & & 1 & & 4 & & 6 & & 4 & & 1 &\\ & 1 & & 5 & & 10 & & 10 & & 5 & &1 \end{aligned} \]

Let's write out the binomial expansion using the pattern above, looking up binomial coefficients in the triangle

\[ \begin{aligned} (x + y)^5 &= {5 \choose{0}}x^0y^5 + {5 \choose{1}}x^1y^4 + {5 \choose{2}}x^2y^3 + {5 \choose{3}}x^3y^2 \\ \\ &+ {5 \choose{4}}x^4y^1 + {5 \choose{5}}x^5y^0 \end{aligned} \]

Note that all the binomial coefficients are on the form $5 \choose{n}$, meaning that all of them are on the 6:th, the last, row in the triangle. In fact, the coefficients can be read straight off this row:

\[ \begin{aligned} (x + y)^5 &= 1x^0y^5 + 5x^1y^4 + 10x^2y^3 + 10x^3y^2 + 5x^4y^1 + 1x^5y^0 \\ \\ &= 1y^5 + 5xy^4 + 10x^2y^3 + 10x^3y^2 + 5x^4y + 1x^5 \\ \\ &= x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5 \end{aligned} \]

Ta-da! You can now more easily remember how to write crazy-big binomial expansions. Drawing Pascal's triangle and doing all this might not be fast, but it's an easy enough way to remember it all. It's better to use dumb, slow methods and be correct than to use fast, smart methods and make silly mistakes.

One last thing. There's a shorter, more general way of writing the binomial theorem, using a sum-sign:

\[(x + y)^n = \sum\limits_{k=0}^n{n \choose{k}}x^ky^{n - k}\]

The $\sum$ says that we should start with $k = 0$ and calculate the stuff to the right of the $\sum$ using $k = 0$ and then set $k = 1$ and calculate the stuff again using that and do this again and again all the way until $k = n$. We then add all the calculated parts together. Try doing this for $n = 2$ and $n = 3$, the examples at the start of this section should fall out.

Thanks for reading! Please e-mail any corrections or comments to karl@zylinski.se or send me a tweet.