# Probability

• Counting

## Counting

### Trees

• How many 3-bit strings? $2^3 = 8$
1. How would you make one sequence?
2. How many different sequences of 3 bits from {0, 1}?
         0                 1
/       \         /       \
00       01       10       11
/  \     /  \     /  \     /  \
000  001 010  011 100  101 110  111


### First Rule of Counting: Product Rule

Objects made by chosing from $n_1$, then $n_2$, …, then $n_k$. Then number of objects if $n_1 \times n_2 \times ... \times n_k$

#### First Rule Example

• How many outcomes possible for $k$ coin tosses? –> $2^k$
• How many 10 digit numbers? –> $10^{10}$
• How many $n$ digit base $m$ numbers? –> $m^n$, actually $(m - 1)m^{n - 1}$

### Functions, Polynomials

How many functions $f$ mapping $S$ to $T$?

$\|T\|$ ways to choose for $f(s_1)$, $\|T\|$ ways to choose for $f(s_2)$

So, $\| T \| ^{ \| S \|}$ such functions

How many polynomials of degree $d$ modulo $p$?

• $p$ ways to choose $d + 1$ coefficients, so $p^{d + 1}$

## Permutations

How many 10 digits numbers without repeating a digit? Answer: $10!$

The number of possible choices for the second number is dependent on the first.

How many different samples of size $k$ from $n$ numbers without displacement? $n \cdot (n - 1) \cdot ... \cdot (n - k + 1) = \dfrac{n!}{(n-k)!}$

Permutation of $n$ objects = $n!$

### One-to-one Functions

How many one-to-one functions from $|S|$ to $|S|$?

## Counting Without Order

How many poker hands? $52 \times 51 \times 50 \times 49 \times 48 \times 47$?? Not really, because A, K, Q, 10, J of spades are the “same” as 10, J, Q, K, A of spades.

### Second Rule of Counting

Second Rule of Counting: If order doesn’t matter, count ordered objects and then divide by number of orderings.

Number of ordering for a poker hand = $5!$

So, correct answer is $\frac{52!}{5!\times47!}$

To choose $k$ out of $n$: $\dfrac{n!}{(n - k)! \times k!}$

Notation: $\displaystyle {n \choose k}$

### Examples

How many orderings of “ANAGRAM”?

• Ordered set: $7!$, except for “A”
• A’s are the same. There’re 3 “A”s, so number of such repeated ones = $3!$
• Answer = $\dfrac{7!}{3!}$

How many orderings of “MISSISSIPPI”?

• Ordered set: $11!$
• 4 S’s, 4 I’s, 2 P’s, so $4! \times 4! \times 2!$ ordered objects per unordered object

## Sampling

Sample $k$ items out of $n$.

Without replacement:

• If order matters, $\dfrac{n!}{(n - k)!}$
• If order doesn’t matter, $\dfrac{n!}{(n - k)!\times k!} =$ $\displaystyle {n \choose k}$

With replacement:

• If order matters, $n^k$
• If order doesn’t matter: not so easy … depends on how many of each item we choose.
• Different number of unordered elts map to each unordered elt.

### Example: Splitting up some money …

How many ways can Bob and Alice split 5 dollars?

Attempt #1:

For each of the 5 dollars pick Bob or Alice, so $2^5$ and divide out order. Does this work??

• Nope, doesn’t work. Second rule of counting isn’t the best here.

Let’s make the question harder… How many ways can Bob, Alice, and Eve split 5 dollars?

Attempt #2:

* * * * * –––– 5 stars are the 5 dollars

| | * * * * *
| * | * * * *
| * * | * * *
...


How many different 5 star and 2 bar diagrams? 7 positions in which to place the 2 bars. Answer: ${7 \choose 2} = {7 \choose 5}$

### Stars and Bars

Ways to add up $n$ numbers to sum to $k$, or “$k$ from $n$ with replacement where order doesn’t matter”.

In general, if we have $k$ stars and $n$ bars, there are $n+k$ positions from which to choose $n$ bar positions. i.e. $\displaystyle {n+k-1 \choose n-1}$

## Summary

First rule: $k$ sampls with replacement from $n$ items: $n^k$ Samples without replacement: $\dfrac{n!}{(n-k)!}$

Second rule: when order doesn’t matter

### Balls in bins

$k$ balls in $n$ bins” $\equiv$$k$ samples from $n$ possibilities”. “indistinguishable balls” $\equiv$ “order doesn’t matter” “only one ball in each bin” $\equiv$ “without replacement”

### Sum Rule

Sum rule: Can sum over disjoint sets

Example 1: Two indistinguishable jokers in 54-card deck. How many 5 card poker hands? No jokers: $52 \choose 5$ One joker: $52 \choose 4$ Two jokers: $52 \choose 3$ So, answer: $52 \choose 5$ + $52 \choose 4$ + $52 \choose 3$

Example 2: Two distingiushable jokers in 54-card deck. No jokers: $52 \choose 5$. One black/white joker: $2 \times {52 \choose 4}$ Both jokers: $52 \choose 3$ Answer is actually same as $54 \choose 5$

### Combinatorial Proofs

#### Theorem 1

Theorem: $\displaystyle {n \choose k} = {n \choose n - k}$

Proof: Choosing what we choose is the same as choosing what we leave out.

#### Theorem 2 – Pascal’s Triangle

Pascal’s rule: ${n + 1 \choose k} = {n \choose k} + { n \choose k-1}$

Proof: How many size $k$ subsets of $n+1$? $n+1 \choose k$ Disjoint sets:

• Contains first element: then $n \choose k - 1$
• Doesn’t contain first element: then $n \choose k$
    0
1 1
1 2 1
1 3 3 1
1 4 6 4 1


Row $n$: coefficients of $(1 + x)^n$

Foil (4 terms) on steroids: $2^n$ terms: choose $1$ or $x$ from each factor of $(1+x)$

Simplify: collect all terms corresponding to $x^k$. Coefficient of $x^k$ is $n \choose k$: choose $k$ factors where $x$ is in product.

#### Theorem 3

Theorem: $\displaystyle { {n \choose k} = {n-1 \choose k-1} + ... + {k-1 \choose k-1} }$

Proof: Consider size $k$ subset where $i$ is the first element chosen:

• Must choose $k-1$ elements from the remaining $n-i$ elements. => $n-i \choose k-1$ such subsets.
• Add the up to get the total number of subsets

#### Theorem 4 – Binomial Theorem: x = 1

Theorem: $\displaystyle { 2^n = {n \choose n} + {n \choose n - 1} + {n \choose 0} }$

Proof: How many subsets of {1, …, $n$}? Construct a subset with sequence of $n$ choices.

First rule of counting: $2^n$ subsets.

Sum over $i$ to get

### Simple Inclusion/Exclusion

Sum Rule: For disjoint sets $S$ and $T$, $\| S \cup T \| = \|S\| + \|T\|$

Inclusion/Exclusion Rule: For any $S$ and $T$, $\|S \cup T \| = \|S\| + \|T\| - \|S \cap T\|$

Example: How many 10-digit phone numbers have 7 as their first or second digit?

$S$ = phone numbers with 7 as first digit. $\|S\| = 10^9$

$T$ = phone numbers with 7 as first digit. $\|S\| = 10^9$

### Key Points

• Uncertainty doesn’t mean “nothing is known”

## Conditional Probability

Definition:

For events $A$ , $B$ in the same probability space, such that ${\mathbb{P}}[B]>0$ , the conditional probability of $A$ given $B$ is:

${\mathbb{P}}[A\mid B] = \dfrac{\mathbb{P}[A\cap B]}{\mathbb{P}[B]}$.

### Total Probability Rule

For disjoint sets $A_1, A_2, …, A_N$, $Pr(B) = Pr(A_1 \cap B) + Pr(A_2 \cap B) + … + Pr(A_N \cap B)$

Hey, kudos for making it this far! Wanted to let you know that if you liked this, you might also like tmux Cheatsheet and Shortcuts.