# Problem Set 2: Probability

These are draft notes extracted from subtitles. Feel free to improve them. Contributions are most welcome. Thank you!
Please check the wiki guide for some tips on wiki editing.

Contents

## 01 Relative Probabilities 1

Let's suppose we have a fair coin and we flipped it four times.I'd like you to tell me what is the probability that there is exactly one headdivided by the probability that only the very first flip is a head.Please enter your answer here.

## 02 Relative Probabilities 1 Solution

The correct answer is 4.To see this, note that for the first flip to be only a head, the following is the only sequence possible.For the numerator to be true, there are three more possibilities.

Note:
Here's a detailed solution:

What's being asked is the ratio of the probabilities:

There are 4 possibilities for exactly one head: (H, T, T, T), (T, H, T, T), (T, T, H, T), (T, T, T, H)

P(\text{Exactly One Head}) = 4 \cdot ( \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} )

There is one possibility for first flip is the only head: (H, T, T, T)

P(\text{First Flip is Only Head}) = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2}

Note that if you calculate the ratio, the fractions cancel out and all that remains is 4, therefore:

## 03 Relative Probabilities 2

Now, I'd like to tell me the ratio of the probability of exactly one head to the probability ofthe first flip being heads regardless of the other flips.

## 04 Relative Probabilities 2

And the answer is 0.5, 1/2.To see this, recall that there were four possibilities for the numerator--all equally likely,and if the first flip is heads and we have no other restrictions, the last three flips can be anything.So each one has two possibilities and 222=8 and 4/8=0.5.

Note:
Here's a detailed solution:

The following ratio of probabilities is being asked:

P(\text{Exactly One Head}) = 4 \cdot ( \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} )

For P(\text{First Flip is Head}), there are the following possibilities (8 possibilities):

(H, T, T, T), (H, T, T, H), (H, T, H, T), (H, T, H, H), (H, H, T, T), (H, H, T, H), (H, H, H, T), (H, H, H, H)

Or reasoning in a different way (Easier to visualize with a tree diagram):

First Flip:                                          H
/                 \
Second Flip:                               H                   T
/       \            /     \
Third Flip:                           H         T         H        T
/  \       /  \      /  \    /  \
Fourth Flip:                       H    T     H    T    H   T    H   T

• The first flip has to be Heads and the remaining flips can be anything.

• For the second flip you have 2 possibilities (Heads or Tails), therefore 2 possibilities.

• For each of the possibilities for the second flip, you have two possibilities for the third flip as well, therefore 2 \times 2.

• For each of the possibilities for the third flip, you have two possibilities for the fourth flip as well, therefore 2 \times 2 \times 2 = 8.

Think about all the paths you can choose if you start from the top of the diagram and want to go to the bottom.

The probability of first flip is heads is therefore:

P(\text{First Flip is Heads}) = 8 \cdot ( \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2})

Note that if you calculate the ratio, the fractions cancel out (as in the first question) and all that remains is \frac{4}{8}:

## 05 Same Coin

Let's assume there are two coins equally distributed, same probability of having each.The first type of coins are fair. The second type of coins have a probability of heads of 0.9--90%.Let's assume you and I both flip a coin. When I flipped, I get the following sequence.When you flipped, you get the following sequence.So please write in this box the probability that we flipped coins of the same type.

## 06 Same Coin Solution

And the answer is 0.523, 52.3%To see this, first, recognize that these two sequences have the same probability.The probability with a fair coin of this sequence is 0.125,whereas with our loaded coin, the probability is 0.081.So, the probability of either of these sequences of flips is 12.5% if the coin is fairand only 8.1% if the coin is loaded.So, to figure out the probability that the coin is fair, we'll just use Bayes' Rule.Note that the 0.5 simply represents that there's an equal or 50%chance of having coin 1 versus coin 2.And this expression equals 0.6080 and so the probability that we have the same coin is simplythe probability that we both have type 1 or fair coins, plus the probability ofmy having coin 2 times the probability of your having coin 2.And since the probabilities are the same, since the underlying probabilities were the same for each flip,we have 0.608² plus (1-0.608)² and evaluating this expression gives us our answer.

Note:
Here's a detailed solution. These are the given probabilities:

What you want is the probability of both coins being of the same type (fair or loaded) given the evidence (flips). Let's start with the case where both coins are fair:

P(Coin1=\text{Fair}|Flips=HHT)

P(Coin2=\text{Fair}|Flips=THH)

Applying Bayes' rule:

P(Coin1=\text{Fair}|Flips=HHT) = \frac{P(Flips=HHT|Coin1=\text{Fair})\cdot P(Coin1=\text{Fair})}{P(Flips=HHT)}

P(Coin2=\text{Fair}|Flips=THH) = \frac{P(Flips=THH|Coin2=\text{Fair})\cdot P(Coin2=\text{Fair})}{P(Flips=THH)}

Where:

P(Flips=HHT) = P(Flips=HHT|\text{Coin1 = Fair})\cdot P(\text{Coin1 = Fair}) + P(Flips=HHT|\text{Coin1 = Loaded})\cdot P(\text{Coin1 = Loaded})

P(Flips=THH) = P(Flips=THH|\text{Coin2 = Fair})\cdot P(\text{Coin2 = Fair}) + P(Flips=THH|\text{Coin2 = Loaded})\cdot P(\text{Coin2 = Loaded})

These are the "normalizers", calculated using the rule of total probability.

Therefore:

P(Coin1=\text{Fair}|Flips=HHT) = \frac{P(Flips=HHT|Coin1=\text{Fair)}\cdot P(Coin1=\text{Fair)}}{[P(Flips=HHT|\text{Coin1 = Fair)}\cdot P(\text{Coin1 = Fair})] + [P(Flips=HHT|\text{Coin1 = Loaded})\cdot P(\text{Coin1 = Loaded})]}

P(Coin2=\text{Fair}|Flips=THH) = \frac{P(Flips=THH|Coin2=\text{Fair)}\cdot P(Coin2=\text{Fair)}}{[P(Flips=THH|\text{Coin2 = Fair)}\cdot P(\text{Coin2 = Fair})] + [P(Flips=THH|\text{Coin2 = Loaded})\cdot P(\text{Coin2 = Loaded})]}

Substituting:

P(Coin1=\text{Fair}|Flips=HHT) = \frac{(0.5\cdot0.5\cdot0.5)\cdot(0.5)}{[(0.5\cdot0.5\cdot0.5)\cdot0.5]+[(0.9\cdot0.9\cdot0.1)\cdot0.5]} = 0.6068

P(Coin2=\text{Fair}|Flips=THH) = \frac{(0.5\cdot0.5\cdot0.5)\cdot(0.5)}{[(0.5\cdot0.5\cdot0.5)\cdot0.5]+[(0.1\cdot0.9\cdot0.9)\cdot0.5]} = 0.6068

So, the probabilities are the same and that's the reason the TA omitted the calculations for the second coin.

Observation: The value 0.608 given in the answer video is actually incorrect, but since it is just an intermediate result, the TA didn't notice his mistake.

Note also that since P(Coin1=\text{Fair}) = P(Coin1=\text{Loaded}) = 0.5 and P(Coin2=\text{Fair}) = P(Coin2=\text{Loaded}) = 0.5 the TA has chosen to put the 0.5 in evidence and that's the reason 0.5 is multiplying the denominator in the answer video.

These probabilities are independent, so to find the probability of both Coin1 and Coin2 being fair is simply the product:

P(Coin1=\text{Fair}|Flips=HHT, Coin2=\text{Fair}|Flips=THH) = = P(Coin1=\text{Fair}|Flips=HHT) \cdot P(Coin2=\text{Fair}|Flips=THH) = 0.6068 \cdot 0.6068 = (0.6068)^2

P(\text{Both Fair}) = (0.6068)^2

Let's now calculate the probabilities for the case where both coins are loaded:

Since these are complementary probabilities and they must always add up to one.

These probabilities are also independent, so to find the probability of both Coin1 and Coin2 being loaded is simply the product:

P(\text{Same Type of Coin}) = P(\text{Both Fair}) + P(\text{Both Loaded}) = (0.6068)^2 + (1-0.6068)^2 = 0.523

## 08 Many Flips Solution

And the answer is, the probability of every sequence becomes small.This is true because there become more and more sequences.Every time you flip a coin, you double the number of sequences.And they have varying probabilities but they are always more against the probability,always goes down and always multiplying in a number less than 1.That's why this assumption is important.The probability of every number of heads become small.This is a little trickier that this is also true because as the number of flips increases,the number of heads must increase even if we're assuming some low probability for it.So, it becomes farther and farther away from what we expect.The probability of every proportion of heads also becomes small.This is a little trickier but the thing to remember is--every proportion of heads, corresponds to a given exact number of heads.Now that exact number of heads changes as, let's say,I double the number of flips, I also double the number of heads I need. But, that's going to always be a smaller number, since again that probability has to be divided into the chance that I could just have one more head or one less head which is going to be an ever so slightly different proportion.Now, this statement is not true.The probability of every range of proportions can't become small.The range of all proportions is a range and we know that has to stay at one, So, that can't be true and the probability of some ranges of proportions become small.Well, this will also be true--consider something improbable like getting the proportion--a proportion below 10% on a fair coin.That's going to tend to become rare and rare and rare as you flip it more times,because the same rare or unlikely event has to keep repeating itself.

Note:
Here's a detailed explanation:

• "The probability of every sequence become small"

All the sequences (outcomes) are equally probable, i.e., P(Sequence) = \frac{1}{\text{Number of Outcomes}}. Example, if n=1 (n is the number of flips), the possible outcomes (sequences) are {(0), (1)} (two outcomes), therefore the probability of each outcome is \frac{1}{2}. If n=2, the possible outcomes are {(0, 0), (0, 1), (1, 0), (1, 1)} (four outcomes), therefore the probability of each outcome is \frac{1}{4}. The probability of every outcome does become smaller as we increase the number of flips n.

• "The probability of every number of heads become small"

• "The probability of every proportion become small"

Saying that "every proportion become small" is the same as saying that the number of Heads k is some fraction of n, e.g., k = \frac{n}{2}. That's a particular case of "The probability of every number of heads become small", which we already determined to be true. Therefore "the probability of every proportion become small" is also true.

• "The probability of every range of proportions become small"

That's easy to disprove. If you take the range of proportions that includes all possible proportions, that's also a range of proportions (in this range any proportion is allowed). The probability of this range of proportions is therefore equals to one and will always be one no matter the number of flips. Therefore doesn't increase, remains constant.

• "The probability of some range of proportions become small"

A range of proportions would be something like 1 \le k \le 3 (k is the number of Heads). That's the same as the sum of the probabilities for k=1, k=2 and k=3 for different values of n (n is the number of flips). We have figured out that the probabilities for each value of k become smaller as the number of flips increases, therefore the sum also decreases. The only case for which this isn't true is the range where all proportions are allowed, whose probability is always equals to one no matter the number of flips. Therefore the probability of some range of proportions decrease as the number of flips increases.

## 09 Is It Fair 1

Let's assume we have a fair coin and a loaded coin and the loaded coin has a probability of heads of 0.9.Let's assume that we know that the probability of actually having a loaded coin is zero.In which of these cases is the probability of being fair given the flips <0.5.Check all that apply. Note that 4 H 0 T means four head and zero tails.

Observation:
2H3T = (H, H, T, T, T), not all the outcomes with 2 Heads and 3 Tails, i.e.:
{(H, H, T, T, T), (H, T, H, T, T), (H, T, T, H, T), (H, T, T, T, H), (T, H, H, T, T), (T, H, T, H, T), (T, H, T, T, H), (T, T, H, H, T), (T, T, H, T, H), (T, T, T, H, H)} (10 possible outcomes).

## 10 Is It Fair 1 Solution

And in none of these cases is the probability of a fair coin given the data less than 0.5.We know this simply because the probability of having a loaded coin at all is zero. So if that doesn't make intuitive sense we can apply Bayes' Rule since P of loaded is zero. P of fair is one and so P of flips given fair is always going to be equal to P of flips because that's the only way you can get the flips. The alternative is zero and so this whole expression will always be one. You could also do this with the reverse in P of loaded and you'd see it would always come out to be zero because this term will be zero.

Note:
Being P(Coin=Loaded) = 0, this means that the coin is Fair. Since the coin fair, P(Coin=Fair|Flips) = 1, i.e., you already know that the coin is fair and that's independent of the flips. P(Coin=Fair|Flips) is always equal to one (no matter what the flips are) and therefore all statements are false.

## 11 Is It Fair 2

Now let me ask you if the probability of having a loaded coin is 0.1,what happens to the probability of fair given flips in each of these cases.Check all that have a probability of a fair coin of less than 0.5.

## 12 Is It Fair 2 Solution

Note:
Here are the calculations for this problem:

Bayes' Rule: P(B|A) = \frac{P(A|B) \times P(B)}{P(A)}

Therefore:

P(Coin=Fair|Flips) = \frac{P(Flips|Coin=Fair) \times P(Coin=Fair)}{P(Flips)}

Let's calculate the probabilities required for the calculations:

P(Coin=Fair) = 1 - P(Coin=Loaded) = 1 - 0.1 = 0.9

P(Flips=4H0T|Coin=Fair) = 0.5 \times 0.5 \times 0.5 \times 0.5 = (0.5)^4 = 0.0625

P(Flips=10H0T|Coin=Fair) = (0.5)^{10} = 0.0009765625

P(Flips=20H0T|Coin=Fair) = (0.5)^{20} = 9.5367431640625e-07

P(Flips=0H5T|Coin=Fair) = (0.5)^5 = 0.03125

P(Flips=2H3T|Coin=Fair) = \frac{10}{2^5} = 0.03125

P(Flips=4H0T) = (0.5)^4 \times 0.9 + (0.9)^4 \times 0.1 = 0.12186

P(Flips=10H0T) = (0.5)^{10} \times 0.9 + (0.9)^10 \times 0.1= 0.03574675026000001

P(Flips=20H0T) = (0.5)^{20} \times 0.9 + (0.9)^20 \times 0.1 = 0.012158523765941702

P(Flips=0H5T) = (0.5)^5 \times 0.9 + (0.1)^5 \times 0.1 = 0.028126

P(Flips=2H3T) = (0.5)^5 \times 0.9 + (0.9)^2 \times (0.1)^3 \times 0.1 = 0.028206000000000002

Finally the probabilities we need to check the statements:

P(Coin=Fair|Flips=4H0T) = \frac{0.0625 \times 0.9}{0.12186} = 0.4615952732644018 \lt 0.5

P(Coin=Fair|Flips=10H0T) = \frac{0.0009765625 \times 0.9}{0.03574675026000001} = 0.024587025215085937 \lt 0.5

P(Coin=Fair|Flips=20H0T) = \frac{9.5367431640625e-07 \times 0.9}{0.012158523765941702} = 7.059301781108519e-05 \lt 0.5

P(Coin=Fair|Flips=0H5T) = \frac{0.03125 \times 0.9}{0.028126} = 0.999964445708597 \gt 0.5

P(Coin=Fair|Flips=2H3T) = \frac{0.03125 \times 0.9}{0.028206000000000002} = 0.9971282705807275 \gt 0.5

## 13 Programming Challenge (Optional)

#FlipPredictor
#A coin is drawn at random from a bag of coins of varying probabilities
#Each coin has the same chance of being drawn
#Your class FlipPredictor will be initialized with a list of the probability of
#heads for each coin. This list of probabilities can be accessed as self.coins
#in the functions you must write. The function update will be called after every
#flip to enable you to update your estimate of the probability of each coin being
#the selected coin. The function pheads may be called and any time and will

from __future__ import division
class FlipPredictor(object):
def __init__(self,coins):
self.coins=coins
n=len(coins)
self.probs=[1/n]*n
#Write a function that returns
#the probability of the next flip being heads

def update(self,result):
#the probabilities of flipping each coin

#The code below this line tests your implementation.
#You need not change it
def test(coins,flips):
f=FlipPredictor(coins)
guesses=[]
for flip in flips:
f.update(flip)
return guesses

def maxdiff(l1,l2):
return max([abs(x-y) for x,y in zip(l1,l2)])

testcases=[
(([0.5,0.4,0.3],'HHTH'),[0.4166666666666667, 0.432, 0.42183098591549295, 0.43639398998330553]),
(([0.14,0.32,0.42,0.81,0.21],'HHHTTTHHH'),[0.5255789473684211, 0.6512136991788505, 0.7295055220497553, 0.6187139453483192, 0.4823974597714815, 0.3895729901052968, 0.46081730193074644, 0.5444108434105802, 0.6297110187222278]),
(([0.14,0.32,0.42,0.81,0.21],'TTTHHHHHH'),[0.2907741935483871, 0.25157009005730924, 0.23136284577678012, 0.2766575695593804, 0.3296000585271367, 0.38957299010529806, 0.4608173019307465, 0.5444108434105804, 0.6297110187222278]),
(([0.12,0.45,0.23,0.99,0.35,0.36],'THHTHTTH'),[0.28514285714285714, 0.3378256513026052, 0.380956725493104, 0.3518717367468537, 0.37500429586037076, 0.36528605387582497, 0.3555106542906013, 0.37479179323540324]),
(([0.03,0.32,0.59,0.53,0.55,0.42,0.65],'HHTHTTHTHHT'),[0.528705501618123, 0.5522060353798126, 0.5337142767315369, 0.5521920592821695, 0.5348391689038525, 0.5152373451083692, 0.535385450497415, 0.5168208803156963, 0.5357708613431963, 0.5510509656933194, 0.536055356823069])]

for inputs,output in testcases:
if maxdiff(test(*inputs),output)<0.001:
print 'Correct'
else: print 'Incorrect'