ClassicalProbability.tex

%        File: ClassicalProbability.tex
%     Created: Sat Jan 31 04:00 PM 2015 E
% Last Change: Sat Jan 31 04:00 PM 2015 E
%
\documentclass[12pt]{article}
\usepackage{amsmath,amssymb}
\title{Basic Combinatorics and Classical Probability\\ \large Addendum to Lecture \# 5}
\author{Econ 103}
\date{}
\begin{document}
\maketitle

\section*{Introduction}
In lecture I don't spend much time on Classical Probability since I expect that this material should be familiar from High School.
If you need a refresher, this document should help.
Since Classical Probability is all about counting, we'll start off with a short review of combinatorics.

\section*{Basic Combinatorics: Rules for Counting}
\subsection*{The Multiplication Rule}
When I visit Chipotle, I'm presented with a sequence of independent choices:
\begin{enumerate}
  \item Burrito, bowl, soft tacos, or crispy tacos? (4 options)
  \item White or brown rice? (2 options)
  \item Black or pinto beans? (2 options)
  \item Chicken, carnitas, steak, barbacoa, sofritas, or vegetables? (6 options) 
  \item Mild, medium or hot salsa? (3 options)
  \item Cheese? (2 options: yes/no)
  \item Guacamole? (2 options: yes/no)
\end{enumerate}
I've left off a number of the toppings, but you get the idea.
The question is: how many different meals could I order?
To answer this, we'll use a principle called the \emph{multiplication rule}.

Imagine a gigantic rectangular classroom, College Hall Room 200 perhaps, with 50 rows of seats, each containing 20 chairs.
Now suppose that I asked you to count the number of chairs in the room.
Would you visit each row individually and count each chair? 
Of course not: you'd simply multiply 50 by 20 to get 1000.
This is just a special case of the multiplication rule.

Let me phrase the question a little differently.
How many different ways could you choose where to sit if this lecture hall were completely empty?
We already know that the answer is 1000, but let's try getting it a different way.
The room is rectangular, so each chair is uniquely identified by its \emph{column} and \emph{row}.
Choosing a seat is equivalent to choosing a row and a column.
There are 50 ways to choose a row, and \emph{for each of these} there are 20 ways to choose a column.
This means that, if we want the total number of ways to choose, we need to repeatedly add the number 20 a total of 50 times.
But that's just the definition of multiplication, so the answer is 1000.

Now suppose I added one more choice: there are \emph{three} identical classrooms, each with 50 rows of 20 seats.
If all the seats are empty, how many ways are there to decide where you want to sit?
Well, we already know how to solve the problem for \emph{each} classroom so to find the total, we just need to add up this answer three times.
But again, that is simply the definition of multiplication, so our answer is $3 \times 20 \times 50 = 3000$.

Are you starting to see the pattern here?
This has nothing in particular to do with chairs in classrooms, but it's a basic feature of \emph{how we count things}: \textbf{if you have a series of independent decisions to make, the total number of ways to decide equals the product of the number of ways to make each individual choice}.
Stated more mathematically, if you have $k$ independent decisions to make and there are $n_1$ ways to make the first decision, $n_2$ ways to make the second decision, $\hdots$, and $n_k$ ways to make the $k^{th}$ decision, then there are $n_1 \times n_2 \times \cdots \times n_k$ total ways to decide.
The \emph{key requirement here} is that the decisions are \emph{independent}.
What I mean by this is that the number of ways to make a particular decision does not depend on what you chose in a \emph{separate decision}.
Going back to the classroom example, this is the same as requiring that each room have the same number of rows and columns of chairs.
Since the Chipotle example also has this structure, we can solve it as follows: $4 \times 2 \times 2 \times 6 \times 3 \times 2 \times 2 = 1152$.
That's a lot of possibilities!

If you find the multiplication rule confusing, try thinking about some other examples of how we count things in real life.
It's very important to have a good intuitive grasp of this idea since all the other rules of counting are really just special cases of the multiplication rule.

\subsection*{Example: Lining up for a Photo}
Suppose that you're taking a picture of your three best friends: Alice, Bob, Charlotte.
Feeling unimaginative, you decide to have them stand side-by-side in a line.
How many different ways are there to set up the picture?

Although it's very simple, this example raises an important point about counting that comes up over and over again in probability questions: before we can decide \emph{how many} of something we have, we need to be clear about what gets to ``count'' as a distinct object. 
In posing the question about taking a photograph, I am implicitly considering \emph{different orderings} of your four friends as different ways to set up the picture.
The key distinction here is whether or not order matters.
In this case it clearly does: we consider (Alice, Bob, Charlotte) to be a different ``item'' than (Charlotte, Bob, Alice).
In mathematics, this is like the difference between a \emph{set} and an \emph{ordered pair}: $(1,2)$ and $(2,1)$ are different points in the Cartesian coordinate system but $\left\{ 1,2 \right\}$ and $\left\{ 2,1 \right\}$ represent the same set since order doesn't matter in set theory.

Now back to our problem.
How can we use the multiplication rule here?
The trick is to break it into a series of decisions.
Essentially, we are trying to allocate three objects to three slots:
\begin{equation*}
  \underset{1}{\underbar{\quad}}\;
  \underset{2}{\underbar{\quad}}\;
  \underset{3}{\underbar{\quad}}\;
\end{equation*}
so our decisions are as follows:
\begin{enumerate}
  \item Who goes in slot \#1? (3 options)
  \item Who goes in slot \#2? (2 options)
  \item Who goes in slot \#3? (1 options)
\end{enumerate}
Using the multiplication rule, we see that there are $3 \times 2 \times 1 = 6$ possible ways to arrange your friends in the picture.
The key is noticing that, each time we make a decision in this example, we have one fewer person who could go in the next slot.
(This makes it a little different from the Chipotle example, although we can still apply the multiplication rule.)

If you find this confusing, try directly enumerating all of the possibilities.
This example is simple enough that it won't take too long.
First suppose that Alice is in position \#1.
Then there are two possibilities: either Bob is in position \#2 and Charlotte is in position \#3 or the reverse.
Now suppose that Bob is in position \#1.
Then there are two possibilities: either Alice is in position \#2 and Charlotte is in position \#3 or the reverse.
Finally, suppose that Charlotte is in position \#1.
Then there are two possibilities: either Alice is in position \#2 and Bob is in position \#3 or the reverse.
Counting up each of these possibilities, we get six as expected.

It's no accident that the answer to this question can be expressed as $3!$.
Using exactly the same reasoning as I gave above, we can reach the following general conclusion: \textbf{there are $k!$ ways to arrange $k$ objects in order}.

\subsection*{Permutations}
Permutations are almost exactly like the example from the preceding section in which we arranged three people in a line.
The difference is that in a permutation there are more people than there are slots in the photo.
Just as in the photo example, \emph{order matters}.
In particular, a permutation is \textbf{the number of ways to arrange $n$ objects in $k$ ordered positions}:
\begin{equation*}
  P^n_k = \frac{n!}{\left( n-k \right)!}
\end{equation*}
The reasoning behind this formula is best illustrated through an example.
Suppose 10 people are running a race.
How many different ways are there to award first, second and third place?
In this question there are $n=10$ objects and $k=3$ ordered positions.
To answer it, we again turn to the multiplication rule.
We have to make three decisions: who gets first place, who gets second place, and who gets third place.
There are 10 ways to make the first decision.
But after we've assigned someone first place, only 9 people remain.
Thus, there are 9 ways to award second place.
But after we've awarded second place, only 8 people remain.
Therefore, there are 8 ways to award second place.
Multiplying these together, we get $10 \times 9 \times 8 = 720$.
Now let's try using the formula:
\begin{equation*}
  P^{10}_{3} = \frac{10!}{\left( 10-3 \right)!} = \frac{10!}{7!}= 10 \times 9 \times 8
\end{equation*}
It works!
The formula is really just a general version of the same reasoning we just applied when counting how many ways to assign prizes in the race.
There are $n$ ways to assign an object to the first ordered position, $n-1$ ways to assign an object to the second ordered position, and so on, all the way up to $n-k$ ways to assign an object to the $k^{th}$ ordered position.
The formula for a permutation gives us \emph{precisely} the product of these numbers.

\subsection*{Combinations}
A combination is almost exactly like a permutation with \emph{one important difference}: for a combination, order \emph{doesn't matter}.
For example, suppose we have 10 people and want to form a committee with 3 members.
How many different committees can we form?
The trick first to figure out how many ways there are to arrange the members of a given committee in order, and then use this number to \emph{correct} the result that we would get if we used the formula for a permutation.

In the previous section, we saw that there are 720 ways to allocate 10 objects among 3 ordered positions.
This answer is \emph{larger} than the total number of committees with 3 members that we can form from a group of 10 people.
To see why, consider the committee $\left\{ Alice, Bob, Charlotte \right\}$.
This is the \emph{same} committee as $\left\{ Charlotte, Bob, Alice \right\}$ since order doesn't matter.
The permutation counts each of these possibilities separately since it assumes that order matters.
So how can we correct this?
There are $3!$ ways to arrange the members of the committee $\left\{ Alice, Bob, Charlotte \right\}$: 3 ways to choose who is in the first position time 2 ways to choose who is in the second position times 1 way to choose who is in the third position.
This is true for \emph{any committee with three members}.
It follows that the result we got by calculating the permutation is \emph{six times too large}: it counts each committee six times.
Thus, to get the correct answer, we simply need to divide the result for the permutation by 6, yielding $720/6=120$ distinct committees.

This is \emph{precisely} the reasoning we use to get the general formula for a combination:
\begin{equation*}
  {n\choose k} = \frac{P^{n}_{k}}{k!} = \frac{n!}{k!\left( n-k \right)!}
\end{equation*}
There are $P^{n}_{k}$ ways to arrange $n$ objects in $k$ ordered positions.
For each distinct collection of $k$ objects, there are $k!$ ways to arrange its members in order.
Thus, the permutation is too large by a factor of $k!$ to yield the combination.

\section*{Classical Probability: Equally Likely Outcomes}
Classical Probability is the name given to the special case in which all basic outcomes are equally likely.
Since basic outcomes are, by definition, mutually exclusive, it follows that to calculate the probability of any event $A$ we simply need to count how many of the basic outcomes are contained in $A$ and divide by the total number of basic outcomes.
We saw a few examples of this in class, but here I'll show you two more: one were
Remember from above that when we count things, we need to be clear about whether order matters.
The same goes when calculating classical probabilities since, in this case, probability is simply a matter of counting.
A common mistake that students sometimes make is to use a \emph{different} convention when counting the basic outcomes in $A$ than they used when counting the total number of basic outcomes.
Don't let this happen to you!
If you decide that order matters, your calculations for \emph{both} the numerator and the denominator should reflect this.
The same goes if you decide that order doesn't matter.
We looked at several examples in class, but I'll provide two more here in case you want more practice: one where the answer involves a permutation, and another where it involves a combination.

\subsection*{A Problem Involving a Permutation}
\begin{quote}
  A small museum only has space in its gallery for 4 paintings, arranged in a row from left to right.
  In the basement of the museum, however, there are 6 additional paintings.
  The new curator wants to mix things up, so she randomly selects 4 of the 10 paintings owned by the museum, shuffles them, and hangs them in the gallery.
  What is the probability that the gallery remains unchanged?
\end{quote}
This is a ridiculous example, but I designed it to be simple rather than realistic!
The first thing we need to do is count the basic outcomes.
These consist of all possible ways to allocate 10 paintings to 4 ordered positions: a permutation.
Thus, the denominator in our probability calculation will be $P^{10}_{4}=10\times 9 \times 8 \times 7 =5040$.
Each of these is equally likely, and only one of them corresponds to the exact same arrangement as we started with, so the probability is $1/5040 \approx 0.0002$.

\subsection*{A Problem Involving a Combination}
\begin{quote}
  What is the probability of getting a total of 3 heads when you flip a fair coin 5 times?
\end{quote}
To answer this question, we first need to identify the (equally likely) basic outcomes of this random experiment.
The sample space consists of all ordered sequences of five symbols, each of which is either $H$ or $T$.
There are 2 ways to choose the first, 2 ways to choose the second and so on leading to a total of $2^{5}=32$ sequences.
Each of these sequences has the same probability: $\left( 1/2 \right)^{5}=1/32$.
To find the numerator, we need to count the number of sequences that contain exactly three heads.
This is equivalent to asking how many ways there are to choose a committee of 3 members from a group of 5 people.
Once we decide where the three heads will be placed in the sequence, we're done: the rest of the positions will contain the tails.

So what's going on here?
We have five ordered positions, and we are trying to allocate the three heads.
But the \emph{heads themselves} are not distinguishable: all that matters is where they are \emph{placed}.
So while its true that the order of the \emph{sequences} matters, one we decide which spots will contain the heads, it doesn't matter \emph{how} we allocate the heads to these selected slots: an $H$ is an $H$ is an $H$.
If this doesn't make sense, remember: we only have a single coin here.
When allocating a given symbol, $H$ or $T$, to a given position in the sequence, there's no information beyond which symbol is where.
The symbols refer to outcomes for the same coin, which is different from our example with two dice from class.

Using this intuition, we see that there are ${5\choose 3}=10$ ways to allocate the three heads, so the probability of getting three heads in a sequence of five tosses of a fair coin is $10/32 = 0.3125$.
\end{document}