W02 Notes

Bayes’ Theorem

01 Theory

Theory 1

Bayes’ Theorem

For any events $A$ and $B$:

$$P[B|A]=P[B]\cdot \frac{P[A|B]}{P[A]}$$

Note: Bayes’ Theorem is sometimes called Bayes’ Rule.

Bayes’ Theorem - Derivation

Start with the observation that $AB=BA$, in other words event “$A$ AND $B$” equals event “$B$ AND $A$”.

Apply the multiplication rule to each product:

$$\begin{array}{cc}P[AB]& =P[A]\cdot P[B|A]\\ & \\ P[BA]& =P[B]\cdot P[A|B]\end{array}$$

Equate them and rearrange:

$$\begin{array}{cc}P[AB]=P[BA]\gg \gg & P[A]\cdot P[B|A]=P[B]\cdot P[A|B]\\ & \\ \gg \gg & P[B|A]=P[B]\cdot \frac{P[A|B]}{P[A]}\end{array}$$

The main application of Bayes’ Theorem is to calculate $P[A|B]$ when it is easy to calculate $P[B|A]$ from the problem setup. Often this occurs in multi-stage experiments where event $A$ describes outcomes of an intermediate stage.

Note: These lecture notes use alphabetical order $A$, $B$ as a mnemonic for temporal or logical order, i.e. that $A$ comes first in time, or that $A$ is the prior conditional from which it is easy to calculate $B$.

Link to original

02 Illustration

Example - Bayes’ Theorem - COVID tests

Bayes’ Theorem: COVID tests

Assume that 0.5% of people have COVID. Suppose a COVID test gives a (true) positive on 96% of patients who have COVID, but gives a (false) positive on 2% of patients who do not have COVID. Bob tests positive. What is the probability that Bob has COVID?

Solution

(1) Label events:

• Event $A_P$: Bob is actually positive for COVID
• Event $A_N$: Bob is actually negative; note $A_N=A_P^c$
• Event $T_P$: Bob tests positive
• Event $T_N$: Bob tests negative; note $T_N=T_P^c$

---

(2) Identify known data:

• Know: $P[T_P|A_P]=96\%$
• Know: $P[T_P|A_N]=2\%$
• Know: $P[A_P]=0.5\%$ and therefore $P[A_N]=99.5\%$

We seek: $P[A_P|T_P]$

---

(3) Translate Bayes’ Theorem:

Set $A=T_P$ and $B=A_P$ in Bayes’:

$$P[A_P|T_P]=P[A_P]\cdot \frac{P[T_P|A_P]}{P[T_P]}$$

We know all values on the right except $P[T_P]$

---

(4) Denominator: apply Total Probability (Division into Cases):

Observe that $T_P\cap A_P$ and $T_P\cap A_N$ are exclusive events, and that:

$$T_P=T_P\cap A_P\bigcup T_P\cap A_N.$$

Therefore:

$$P[T_P]=P[A_P]\cdot P[T_P|A_P]+P[A_N]\cdot P[T_P|A_N]$$

Plug in data and compute:

$$\gg \gg P[T_P]=\frac{5}{1000}\cdot \frac{96}{100}+\frac{995}{1000}\cdot \frac{2}{100}\gg \gg \approx 0.0247$$

---

(5) Plug in and compute:

$$\begin{array}{c}P[A_P|T_P]=P[A_P]\cdot \frac{P[T_P|A_P]}{P[T_P]}\\ \\ \gg \gg 0.96\cdot \frac{0.005}{0.0247}\gg \gg \approx 19\%\end{array}$$

Intuition - COVID testing

Some people find this low number surprising. In order to repair your intuition, think about it like this: roughly 2.5% of tests are positive, with roughly 2% coming from false positives, and roughly 0.5% from true positives. Only $1/5$ of all the positive results are true ones!

(This rough approximation assumes that $96\%\approx 100\%$.)

If two tests both come back positive, the odds of COVID are now 98%.

If only people with symptoms are tested, so that, say, 20% of those tested have COVID, that is, $P[A_P|T_P]=20\%$, then one positive test implies a COVID probability of 92%.

Link to original

Practice exercise

Inferring bin from marble

There are marbles in bins in a room:

• Bin 1 holds 7 red and 5 green marbles.
• Bin 2 holds 4 red and 3 green marbles.

Your friend goes in the room, shuts the door, and selects a random bin, then draws a random marble. (Equal odds for each bin, then equal odds for each marble in that bin.) He comes out and shows you a red marble.

What is the probability that this red marble was taken from Bin 1?

Solution

(1) Label events:

• Event $B_1$: friend chooses Bin 1.
• Event $B_2$: friend chooses Bin 2.
• Event $R$: friend draws a red marble.
• Event $G$: friend draws a green marble.

Answer will be $P[B_1|R]$.

---

(2) Identify knowns:

• Know $P[R|B_1]=7/12$.
• Know $P[G|B_1]=5/12$.
• Know $P[R|B_2]=4/7$.
• Know $P[G|B_2]=3/7$.
• Know $P[B_1]=P[B_2]=1/2$.

---

(3) Apply Bayes’ Theorem for $P[B_1|R]$::

$$P[B_1|R]=P[R|B_1]\cdot \frac{P[B_1]}{P[R]}$$

Division into Cases for the denominator:

$$P[R]=P[B_1]\cdot P[R|B_1]+P[B_2]\cdot P[R|B_2]$$

---

(3) Plug in data and compute:

$$\begin{array}{c}P[R]\gg \gg \frac{1}{2}\cdot \frac{7}{12}+\frac{1}{2}\cdot \frac{4}{7}\gg \gg \frac{97}{168}\\ \\ P[B_1|R]\gg \gg \frac{7}{12}\cdot \frac{1/2}{97/168}\gg \gg \frac{49}{97}\end{array}$$

Link to original

Independence

03 Theory

Theory 1

Two events are independent when information about one of them does not change our probability estimate for the other.

Independence

Events $A$ and $B$ are independent when these (logically equivalent) equations hold:

• $P[B|A]=P[B]$
• $P[A|B]=P[A]$
• $P[BA]=P[B]\cdot P[A]$

Note that the last equation is symmetric in $A$ and $B$:

• Check: $BA=AB$ and $P[B]\cdot P[A]=P[A]\cdot P[B]$
• This symmetric version is the preferred definition of the concept of independence.

Multiple-independence

A collection of events $A_1,\dots ,A_n$ is mutually independent when every subcollection $A_{i_1},\dots ,A_{i_k}$ satisfies:

$$P[A_{i_1}\cdots A_{i_k}]=P[A_{i_1}]\cdots P[A_{i_k}]$$

A potentially weaker condition for a collection $A_1,\dots ,A_n$ is called pairwise independence, which holds when all 2-member subcollections are independent:

$$P[A_i{A}_j]=P[A_i]\cdot P[A_j]\text{for all}i\ne j$$

One could also define $3$-member independence, or $n$-member independence. Plain ‘independence’ means any-member independence.

Link to original

04 Illustration

Practice exercise

Independence and complements

Prove that these are logically equivalent statements:

• $A$ and $B$ are independent
• $A$ and $B^c$ are independent
• $A^c$ and $B^c$ are independent

Make sure you demonstrate both directions of each equivalency.

Solution

(1) Assume $P[AB]=P[A]\cdot P[B]$ and show $P[A{B}^c]=P[A]\cdot P[B^c]$:

Divide $A$ into the $B$ cases:

$$P[A]=P[AB]+P[A{B}^c]$$

Apply the assumption:

$$\gg \gg P[A]=P[A]\cdot P[B]+P[A{B}^c]$$

Algebra:

$$\gg \gg P[A](1-P[B])=P[A{B}^c]$$

Negation rule:

$$\gg \gg P[A]\cdot P[B^c]=P[A{B}^c]$$

---

(2) Assume $P[A{B}^c]=P[A]\cdot P[B^c]$ and show $P[AB]=P[A]\cdot P[B]$:

Reason the same way as above, but apply the new assumption to break up the second term instead of the first.

---

(3) Show that $P[A{B}^c]=P[A]\cdot P[B^c]$ and $P[A^c{B}^c]=P[A^c]\cdot P[B^c]$ are equivalent:

To do this, simply notice that in the first equivalence we can replace $A$ with $B^c$ and $B$ with $A$. Use $AB=BA$ too.

Link to original

Example - Checking independence by hand

Independence by hand: red and green marbles

A bin contains 4 red and 7 green marbles. Two marbles are drawn.

Let $R_1$ be the event that the first marble is red, and let $G_2$ be the event that the second marble is green.

(a) Show that $R_1$ and $G_2$ are independent if the marbles are drawn with replacement.

(b) Show that $R_1$ and $G_2$ are not independent if the marbles are drawn without replacement.

Solution

(a) With replacement.

Identify knowns:

• Know: $P[R_1]=\frac{4}{11}$
• Know: $P[G_2]=\frac{7}{11}$

Now compute both sides of independence relation:

$$P[R_1{G}_2]=P[R_1]\cdot P[G_2]$$

The right side is $\frac{4}{11}\cdot \frac{7}{11}$.

For $P[R_1{G}_2]$, we have $4\cdot 7$ ways to get $R_1{G}_2$, and ${11}^2$ total outcomes. So left side is $\frac{4\cdot 7}{{11}^2}$, which equals the right side.

---

(b) Without replacement. This is a bit harder.

(1) Identify knowns:

Know: $P[R_1]=\frac{4}{11}$ and therefore $P[R_1^c]=\frac{7}{11}$

We seek: $P[G_2]$ and $P[R_1{G}_2]$

---

(2) Find $P[G_2]$ using Total Probability (Division into Cases):

$$\begin{array}{c}{G}_2=G_2\cap R_1\bigcup G_2\cap R_1^c\\ \\ \gg \gg P[G_2]=P[R_1]\cdot P[G_2|R_1]+P[R_1^c]\cdot P[G_2|R_1^c]\end{array}$$

Find RHS factors by counting, then compute:

$$\gg \gg P[G_2]=\frac{4}{11}\cdot \frac{7}{10}+\frac{7}{11}\cdot \frac{6}{10}\gg \gg \frac{70}{110}$$

---

(3) Find $P[R_1{G}_2]$ using multiplication rule:

$$P[R_1{G}_2]=P[R_1]\cdot P[G_2|R_1]\gg \gg \frac{4}{11}\cdot \frac{7}{10}\gg \gg \frac{28}{110}$$

---

(4) Compare both sides:

Left side: $P[R_1{G}_2]=\frac{28}{110}$.

Right side:

$$P[R_1]\cdot P[G_2]=\frac{4}{11}\cdot \frac{70}{110}=\frac{28}{121}$$

But $\frac{28}{110}\ne \frac{28}{121}$ so $P[R_1{G}_2]\ne P[R_1]\cdot P[G_2]$ and they are not independent.

Link to original

Tree diagrams

05 Theory

Theory 1

A tree diagram depicts the components of a multi-stage experiment. Nodes represent sources of randomness.

An outcome of the experiment is represented by a complete path taken from the root (left-most node, only one option) to a leaf (right-most node, many options). The branch chosen at a given node represents the outcome of a “sub-experiment.” So a complete path encodes the outcomes of all sub-experiments along the way.

Each branch emanating from a node is labeled with a probability value. This is the probability that the sub-experiment of that node has the outcome of that branch. (In the example, $0.8=P[A|B_1]$.) This is also the conditional probability of the branch’s right node, given its left node as known.

Therefore, branch values from any given node must sum to 1.

The probability of a given outcome is the product of the probabilities along each branch of the path from the root to that outcome.

For example, for outcome $A{B}_1$, we have $P[A{B}_1]=P[A]\cdot P[B_1|A]$.

Generally, remember that

$$\begin{array}{cc}P[ABCD]& =P[ABC]\cdot P[D|ABC]\\ & \\ & =P[AB]\cdot P[C|AB]\cdot P[D|ABC]\\ & \\ & =P[A]\cdot P[B|A]\cdot P[C|AB]\cdot P[D|ABC]\end{array}$$

This overall outcome probability may be written at the final leaf. (Not to be confused with the branch value of the last branch.)

One can also use a tree diagram to remember quickly how to calculate certain probabilities.

For example, what is $P[A]$ in the diagram?

• Answer: add up the path probabilities for all paths terminating in $A$. We obtain:

$$0.24+0.36+0.18\gg \gg 0.78$$

For example, what is $P[B_1|N]$?

• Answer: divide the leaf probability of $B_{1}N$ by the total probability of $N$. We obtain:

$$P[B_1|N]=\frac{0.06}{0.06+0.04+0.12}\approx 0.27$$Link to original

06 Illustration

Example - Tree diagrams: Marble transferred, marble drawn

Marble transferred, marble drawn

Setup:

• Bin 1 holds five red and four green marbles.
• Bin 2 holds four red and five green marbles.

Experiment:

• You take a random marble from Bin 1 and put it in Bin 2 and shake Bin 2.
• Then you draw a random marble from Bin 2 and look at it.

Questions:

(a) What is the probability you draw a red marble?

(b) Supposing that you drew a red marble, what is the probability that a red marble was transferred?

Solution

Construct the tree diagram:

Identify sub-experiments, label events, compute probabilities:

---

(a) Compute $P[D_R]$:

Add up leaf numbers for $D_R$ at leaf:

$$P[D_R]=\frac{25}{90}+\frac{16}{90}=\frac{41}{90}$$

---

(b) Compute $P[T_R|D_R]$:

Conditional probability definition:

$$\begin{array}{c}P[T_R|D_R]=\frac{P[T_R{D}_R]}{P[D_R]}\\ \\ \gg \gg \frac{25/90}{41/90}\gg \gg \frac{25}{41}\end{array}$$

Interpretation: value of desired path over value of all possible paths.

Link to original

Counting

07 Theory

Theory 1

In many “games of chance,” it is assumed based on symmetry principles that all outcomes are equally likely. From this assumption we infer a rule for the probability measure $P[-]$.

$$P[A]=\frac{|A|}{|S|}$$

In words: the probability of event $A$ is the number of outcomes in $A$ divided by the total number of possible outcomes.

When this formula applies, it is important to be able to count the total outcomes as well as the outcomes that satisfy various conditions.

Permutations

Permutations count the number of ordered lists one can form from a set of items. For a list of $r$ items taken from a total collection of $n$ items, the number of permutations is:

$$P(n,r)=\frac{n!}{(n-r)!}$$

Why is this formula true?

There are $n$ choices for the first item. Then $n-1$ for the second item, after the first has been chosen and removed from the set of possibilities. Then $n-2$ for the third, then …, then $n-r+1$ for the $r^{\text{th}}$ item. So the total number of possibilities is the product:

$$n(n-1)(n-2)\cdots (n-r+1)$$

We can express this with factorials using a technical observation:

$$\begin{array}{c}\frac{n!}{(n-r)!}=\frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)(n-r-1)\cdots 1}{\phantom{n(n-1)(n-2)\cdots (n-r+1)}(n-r)(n-r-1)\cdots 1}\\ \\ \gg \gg n(n-1)(n-2)\cdots (n-r+1)\end{array}$$

Combinations

Combinations count the number of subsets (ignoring order) one can form from some items. For a subset of $r$ items taken from a total collection of $n$ items, the number of combinations is:

$$C(n,r)=\left(\genfrac{}{}{0px}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$

This formula can be derived from the formula for permutations.

The set of possible permutations can be partitioned into combinations: each combination determines a subset. By additionally specifying an ordering of the elements in a chosen subset, we obtain a permutation. For a given subset of $r$ elements taken from $n$ items, there are $r!$ ways to determine an ordering of them in a list. Therefore, the number of permutations must be a factor of $r!$ times the number of combinations. (For every combination of size $r$, there are $r!$ ways to order the items in a list.)

The notation $\left(\genfrac{}{}{0px}{}{n}{r}\right)$ is also called the binomial coefficient because it provides the coefficient values of a binomial expansion:

$${(x+y)}^n=\sum _{i=1}^n\left(\genfrac{}{}{0px}{}{n}{i}\right)x^{n-i}{y}^i$$

For example:

$${(x+y)}^4=x^4+4x^{3}y+6x^2{y}^2+4x{y}^3+y^4$$

There are also higher combinations that give multinomial coefficients:

Multinomial coefficient

The general multinomial coefficient is defined by the formula:

$$\left(\genfrac{}{}{0px}{}{n}{r_1,r_2,\dots ,r_k}\right)=\frac{n!}{r_1!r_2!\cdots r_k!}$$

where $r_i\in \mathbb{N}$ and $r_1+r_2+\cdots +r_k=n$.

The multinomial coefficient measures the number of ways to partition $n$ items into subsets with sizes $r_1,r_2,\dots ,r_k$, respectively.

Notice that $\left(\genfrac{}{}{0px}{}{5}{\mathrm{3,2}}\right)=\left(\genfrac{}{}{0px}{}{5}{3}\right)$, so we have already defined these values (i.e. with $k=2$) when we defined binomial coefficients. But when $k>2$, the formula gives new values. They correspond to the coefficients in multinomial expansions. For example, $k=3$ gives the coefficients for ${(x+y+z)}^n$.

Link to original

08 Illustration

Practice exercise

Counting teams with Cooper

A team of 3 student volunteers is formed at random from a class of 40. What is the probability that Cooper is on the team?

Solution

There are $\left(\begin{array}{c}39\\ 2\end{array}\right)$ teams that include Cooper, and $\left(\begin{array}{c}40\\ 3\end{array}\right)$ teams in total. So we have:

$$P=\frac{39!}{2!37!}/\frac{40!}{3!37!}=\frac{3}{40}$$

Link to original

Example - Counting VA license plates

Counting VA license plates

VA license plates have three letters (with no I, O, or Q) followed by four numerals. A random plate is seen on the road.

(a) What is the probability that the numerals occur in strictly increasing order?

(b) What is the probability that at least one number is repeated?

Solution

(a) Numerals in increasing order.

(1) Count total plates:

• Have $23\cdot 23\cdot 23$ options for letters.
• Have $10\cdot 10\cdot 10\cdot 10$ options for numbers.

Thus ${23}^3\cdot {10}^4$ possible plates.

---

(2) Count ways to have 4 numerals that occur in increasing order:

There are $\left(\genfrac{}{}{0px}{}{10}{4}\right)$ ways to choose 4 distinct numerals from 10 options.

For each choice of four distinct numerals (i.e. for each combination), there is exactly one ordering that’s increasing.

Therefore, there are $\left(\genfrac{}{}{0px}{}{10}{4}\right)$ ways to have 4 numerals that occur in increasing order.

---

(3) Count ways to have a list of 3 letters (excluding I, O, Q).

There are 26 total letters, 3 are excluded, thus 23 options for each letter.

Repetition is allowed, thus we have $23\cdot 23\cdot 23={23}^3$ total ways.

---

(3) Compute probability:

Total count of desired plates (taking the product of possibilities):

$${23}^3\cdot \left(\genfrac{}{}{0px}{}{10}{4}\right)$$

Let $E$ label the event that a plate has increasing numerals. The counting formula for probability is:

$$P[E]=\frac{|E|}{|S|}$$

Evaluate using our data:

$$P[E]\gg \gg \frac{{23}^3\cdot \left(\genfrac{}{}{0px}{}{10}{4}\right)}{{23}^3\cdot {10}^4}\gg \gg \frac{\frac{10!}{4!6!}}{10000}\gg \gg \frac{21}{1000}$$

---

(b) At least one number repeated.

“At least” is hard to work with! Lots of ways that can happen.

Try the complement event, which is much simpler: “no repetition”

Let $E^c$ be event that no numbers are repeated. All are distinct. Then $E$ is our desired event.

Count the possibilities:

$$|E^c|=23\cdot 23\cdot 23\cdot 10\cdot 9\cdot 8\cdot 7$$

The total number of plates is still ${23}^3\cdot {10}^4$.

Therefore, license plates with at least one number repeated:

$$\begin{array}{c}|E|=|S|-|E|\\ \\ \gg \gg {23}^3\cdot {10}^4-{23}^3\cdot 10\cdot 9\cdot 8\cdot 7\gg \gg 60348320\end{array}$$

Desired outcomes over total outcomes:

$$\frac{|E|}{|S|}\gg \gg \frac{60348320}{{23}^3\cdot {10}^4}\gg \gg 0.496$$ Link to original

Example - Combinations: Groups with Haley and Hugo

Haley and Hugo from 2 groups of 3

A UVA class has 40 students. Suppose the professor chooses 3 students on Wednesday at random, and again 3 on Friday. What is the probability that Haley is chosen today and Hugo on Friday?

Solution

(1) Count total outcomes:

• We have $\left(\genfrac{}{}{0px}{}{40}{3}\right)$ possible groups chosen Wednesday.
• We have $\left(\genfrac{}{}{0px}{}{40}{3}\right)$ possible groups chosen Friday.

Therefore $\left(\genfrac{}{}{0px}{}{40}{3}\right)\times \left(\genfrac{}{}{0px}{}{40}{3}\right)$ possible groups in total. (Product of possibilities.)

---

(2) Count desired outcomes:

The possible groups of 3 that include Haley can be counted by counting the subgroups of 2 formed of the other students in Haley’s group.

• Therefore we have $\left(\genfrac{}{}{0px}{}{39}{2}\right)$ groups that contain Haley.
• Similarly, we have $\left(\genfrac{}{}{0px}{}{39}{2}\right)$ groups that contain Hugo.

Therefore we count $\left(\genfrac{}{}{0px}{}{39}{2}\right)\times \left(\genfrac{}{}{0px}{}{39}{2}\right)$ total desired outcomes.

---

(3) Compute probability:

Let $E$ label the desired event. By the counting rule:

$$P[E]=\frac{|E|}{|S|}$$

Evaluate using our data:

$$\begin{array}{c}P[E]\gg \gg \frac{\left(\genfrac{}{}{0px}{}{39}{2}\right)\times \left(\genfrac{}{}{0px}{}{39}{2}\right)}{\left(\genfrac{}{}{0px}{}{40}{3}\right)\times \left(\genfrac{}{}{0px}{}{40}{3}\right)}\\ \\ \gg \gg {\left(\frac{\frac{39\cdot 38}{2!}}{\frac{40\cdot 39\cdot 38}{3!}}\right)}^2\gg \gg {\left(\frac{3}{40}\right)}^2\end{array}$$ Link to original

Counting out 4 teams

Counting out 4 teams

A board game requires 4 teams of players. How many configurations of teams are there out of a total of 17 players if the number of players per team is 4, 4, 4, 5, respectively.

Solution

This is just the multinomial coefficient with this data:

$n$	$r_1$	$r_2$	$r_3$	$r_4$
17	4	4	4	5

So we have:

$$\#\text{teams}=\frac{n!}{r_1!r_2!r_3!r_4!}\gg \gg \frac{17!}{4!4!4!5!}\gg \gg 214414200$$

Link to original