Counting in Terms of Proportions

Distributions

For any random event, like flipping a coin, each outcome has a value and a probability. A probability distribution describes every value and associated probability. For example, a single coin flip can take values Heads or Tails with a probability of exactly 1/2 for each; these two values and two probabilities make up the probability distribution of the single coin flipping event. This distribution is called a discrete distribution because there are a countable number of outcomes. A distribution with an uncountable number of outcomes is called a continuous distribution.

The concept of the probability distribution and the random variables which they describe underlies the mathematical discipline of probability theory, and the science of statistics. Andrey Kolmogorov was the first to attempt to formalize the discipline of probability theory.

To illuminate the idea of a probability distribution, think about the following example. Imagine there is Greek God who determines the outcome of any possible random event (like flipping a coin). To do this, for any event, he has a pot filled with every possible outcome to that event. He reaches into his pot and grabs an outcome to determine what is going to happen. A probability distribution tells you how likely it is for him to choose any given outcome. In the case of flipping heads, the only two outcomes in his pot are heads and tails. The probability that he pulls out either is 1/2. You can extend this illustration to any random event with ease.

Normal Distribution

The normal distribution, also called the Gaussian distribution, is an extremely important probability distribution in many fields. It is a family of distributions of the same general form, differing in their location and scale parameters (mean and variance). All normal distributions are symmetric and have bell-shaped density curves with a single peak. Abraham de Moivre developed the normal distribution as an approximation to the binomial distribution, and it was later used by Laplace in 1783 to study measurement errors and by Gauss in 1809 in the analysis of astronomical data.

Adam's Descendants

Adam was inches tall. He had two sons. One was inches tall; the other was inches tall. Each of his sons had two sons, with heights , and . Each of these sons, in turn, had two sons, for a total of eight descendants with heights , and ; and so on.

In the generation, there will be males, each with one of different heights: . Remember, problem solving is all about taking your past experience (in this case, from Pascal's Triangle) and applying it to new problems. You can think of the possible heights in the following triangular format.

The number of males in a given generation who have a certain height is given by the appropriate binomial coefficient (see lecture 8).

In this population, a particular height in the generation occurs with proportion:

In general, let be any set where each element has an associated probability . Any such distribution is called an unbiased binomial distribution (or an unbiased Bernoulli distribution).

As the number of elements gets larger, the shape of the unbiased binomial distribution converges to a normal (or Gaussian) distribution. This is a consequence of the central limit theorem and proves to be a huge time-saver in many circumstances.

Coin flipping in Manhattan

At each step, we flip a coin to decide which way to go (left or right). Each iteration takes us down a level.

What is the probability of ending at the intersection of Avenue i and Street n-i after n steps? There are different paths to level n, each equally likely.

The probability of i heads occurring on the path we generate is:

Random walk on a line

Start at the origin. At each point, flip an unbiased coin to decide whether to go right or left.

The probability that, in n steps, we take i steps to the right and n-i steps to the left (so we are at position 2i - n) is: .
Again, we get a normal, or Gaussian, distribution!

Probabilities and Counting

Say that we want to count the number of x's with property P. One way to do it is to ask "if we pick an x at random, what is the probability it has property P?" and then multiply by the number of x's. Why? The probability that a random x has property P is simply the number of x's with property P divided by the total number of x's. If we multiply this quantity by the total number of x's, we end up with the number of x's with property P.

For example, how many n-bit strings have an even number of 1's? Or, equivalently, if we flip a coin n times, how many different ways can we flip an even number of heads? We'll use our intuition from the previous paragraph.
What is the probability of flipping an even number of heads? Let us say that after n-1 flips, the probability is q. Then, after n flips it is ½q + ½(1 – q) = ½. Intuitively, this makes sense. Exactly half of all possible n-flip events have an even number of heads. If we multiply this by we will obtain the number of ways we can flip an even number of heads when flipping n times.

Binomial distribution with bias p

Consider again the Manhattan street map. Start at the top. At each step, flip a coin with probability p of heads to decide which way to go. What is the probability of ending at the intersection of Avenue i and Street (n – i) after n steps?

The probability of any fixed path with i heads (n – i tails) being chosen is: .

Example

How many n-trit strings have an even number of 0's?

This is equivalent to asking the number of ways to get an even number of heads from a coin with bias . Again, using the intuition from the first paragraph of "Probabilities and Counting," we can ask "what is the probability, , of getting an even number of heads" and then multiply this answer by the total number of ways to create an n-trit string ().

Then, . Say the probability was after n-1 flips. Then:
.
We can rewrite this as:

(The missing step above comes from the fact that which yields and .)
So, multiplying the above equation by we get that the final count is:

Poisson Processes

A Poisson process is a process which is used for modeling random events in time that occur independently of one another. Possible examples of such events include telephone calls arriving at a switchboard or webpage requests on a server.

Example

Let us consider the arrival times of buses as an example of a Poisson process.

* A bus arrives every 20 minutes.
* Every 10 minutes, there is a ½ chance of a bus arriving
* Every minute, there is a 1/20 chance of a bus arriving
* Every second, there is a 1/1200 chance of a bus arriving.
* . . .

We can then look at the distribution of number of buses in a given time period or work out the waiting time for next bus, and so on.

Some Probability Puzzles

These puzzles illustrate that probabilities in certain situations can be counterintuitive. While elementary probability can often be intuitive, sometimes we need to appeal to the principles of probability theory.

Puzzle 1: Teams A and B are equally good. In any one game, each team is equally likely to win. What is most likely length of a “best-of-7” games series?

Answering the question is equivalent to flipping a coin until we get either four heads or four tails. Is this more likely to take 6 or 7 flips?

It turns out that 6 and 7 flips are equally likely. To reach either outcome, after five flips, the score must be 3 to 2. So, on the next flip, we have a 50 percent chance that the series ends 4 to 2 and a 50 percent chance that it doesn't.

If we were to set up the problem on the Manhattan street map (as above), we would see that the number of steps to get to the desired outcome of four wins is equally likely to take 6 or 7 flips. This is shown in the image below:

Puzzle 2: One bag has two silver coins, another has two gold coins, and the third has one of each. One of the three bags is selected at random. Then one coin is selected at random from the two in the bag. It turns out to be gold. What is the probability that the other coin is gold?

Note that there are 3 choices of bag, 2 ways to order the bag contents, and 6 equally likely paths; this is shown below.

Given that we see a gold coin (G), 2/3 of remaining paths have a second gold.

Language of Probability

The formal language of probability is a very important tool in describing and analyzing probability distributions.

A (finite) probability distribution is a finite set of elements, where each element in has a positive real weight, proportion, or probability . The weights must satisfy the following condition:

For notational convenience, we will define . is often called the "sample space" and elements in are called "samples." For a given sample space, the weights must sum to 1.

Any set is called an event. The probability of event is Suppose, for example, that out of nine samples in a sample space, an event consists of four samples with the following probabilities: 0, 0.13, 0.17, and 0.1. The event probability is the sum of the sample probabilities, 0.4.

So, a (finite) probability distribution has a finite sample space , with elements having probability . If each element has equal probability, the distribution is said to be "uniform." Do not look too deeply into the semantics; these are descriptive words used to make the language of mathematics universal.

For example, in a sample space of nine samples with a uniform distribution, each sample would have a probability 1/9. An event consisting of four of these samples would have a probability .

Example:

A fair coin is tossed 100 times in a row. What is the probability that we get exactly half heads?

The sample space is the set of all outcomes . In other words, S represents all sequences of 100 tosses. We have a uniform probability distribution where for all x, . Each sequence in S is equally likely and, hence, has probability
What is the probability that we get exactly half heads? We are looking for the set of sequences with 50 heads and 50 tails. The event that we see half heads is . The probability of this event is:
, where .
So, the answer is about .

Example

Suppose we roll a white die and a black die. What is the probability that the sum is 7 or 11?

In this case, the sample space consists of all possible outcomes when two dice are rolled. The event that we are focusing on is = all pairs with or .

The probability of this event is = proportion of E in S = .

Example

There are 23 people in a room. Suppose that all possible assignments of birthdays to the 23 people are equally likely. What is the probability that two people will have the same birthday?

The sample space consists of all 23-member strings selected from 366 possible birthdays, pretending that it is always a leap year: . An event could be, the 23-element set . The event that we are looking for is . What is ?

We can instead start by looking for all sequences in W that have no repeated numbers. In other words, we look for the complement of .

This means that .
Thus, .

So, there is a better than even chance that two people in a room where 23 people are present have the same birthday.

Another way to calculate this probability is to look at the situation sequentially. For a party of one, there is no possibility of a coincidence. So, the probability of that particular date being a unique birthday is 366/366, or 1. For a second person to have a birthday that doesn't match that of the first, he or she must be born on any one of the other 365 days of the year. We obtain the probability of no match between the birthdays of two people by multiplying 366/366 times 365/366, which equals 0.9973. Hence, the probability of a match is 1 – 0.9973, or 0.0027, which is much less than 1 percent.

With two people, there are 364 unused birthdays. The probability that a third person has a birthday that differs from the other two distinct birthdays is 363/365. So, for three people, the chance of having no pair of matching birthdays is 366/366 x 365/366 x 364/366, or 0.9918. As the number of people brought into the group increases, the chance of there being no match decreases. By the time the crowd numbers 23 people, the probability of no matching birthdays is 0.49. Thus, the chance of at least one match within a group of 23 people is 0.51, or slightly better than 50 percent.

The reason the number is as low as 23 is that we are not looking for a specific match. It does not have to be two particular people or a given date. Any match involving any date or any two people is enough to create a coincidence. Indeed, there are 253 different pairings possible among 23 people, any of which could lead to a match.

More Language of Probability

The probability of event A given event B (or A conditioned on B) is written and is defined to be .

Though it is not generally good practice to illustrate sample spaces with venn diagrams, the idea of conditional probability is elucidated from the following illustration:

Think of as the proportion of that intersects .

Example

Suppose that we roll a white die and a black die. What is the probability that the white die is 1 given that the total is 7?

As in a previous example, we use the sample space S of all possible outcomes.

Event A is all outcomes in which the white die shows 1. Event B is all outcomes in which the two dice total 7. Note that the distribution is uniform.

Hence, .

Independence

Another important concept is independence. Two events, A and B, are independent if the fact that A occurs does not affect the probability of B occurring. To find the probability of two independent events that occur in sequence, find the probability of each event occurring separately, then multiply the probabilities.

More formally, A and B are independent events if .

In general, A1, A2, . . ., Ak are independent events if knowing the occurrence of any event does not change the probability of any of the others occurring.

Example

Let us return to the example of three bags containing silver and gold coins. One bag has two silver coins, another has two gold coins, and the third has one of each. One of the three bags is selected at random. Then one coin is selected at random from the two in the bag. It turns out to be gold. What is the probability that the other coin is gold?

Let be the event that the first coin is gold. . Let be the event that the second coin is gold. .

Note that G1 and G2 are not independent.

Example

In the famous Monty Hall problem, the game-show host hides a prize behind one of three doors chosen at random. You, as the contestant, select one of the three doors. The host opens one of the other doors and reveals that there is no prize behind that door. You can then decide to stay with your original selection or switch to the remaining door. What should you do?

The sample space . Each has probability .

and thus,

So, from above, we can see that you have a ~66% chance of choosing the incorrect door and you should thus change doors.

Why was this tricky? We are inclined to think: "After one door is opened, others are equally likely . . ." But the host's action is not independent of yours! You already knew that one of the doors wouldn't have a prize behind; nothing has changed!

Note: The logic behind this problem is clearer when we imagine the same game with 100 doors. You choose one door you think has the prize at random. The host then reveals 98 doors that do not have the prize behind them, leaving one door concealed. You now have the option to switch or stay. The probability that the door you chose contains the prize is still 1/100, but the probability that the other door contains the prize is 99/100. This problem is similar to the Three Prisoners Problem.