Complement 2: Combinatorics and Probability Distributions

Note

This content was crafted by Ms. Colleen Pfaff.

Combinations

$C^n_r = \frac{n!}{(n-r)!r!}$

Helpful Tip: If you’re having trouble visualizing a probability problem, draw it as a tree diagram, with each combination forming a different branch.

Example Combinations

Red cards numbered 2–10 and black cards 2–10 are placed in a bag. If 4 cards are selected at random, what is the probability that 2 are red and 2 are black?

Solution

There are $C^9_2$ ways to choose 2 red cards. There are $C^9_2$ ways to choose 2 black cards.

To calculate the probability, we need the total number of ways to choose 4 cards:

Number of ways to choose 4 cards: $C^{18}_4$

Probability = $\frac{C^9_2 C^9_2}{C^{18}_4} = \frac{1296}{3060}$

Discrete Probability

$\langle x \rangle = \sum_i x_i P_i$

$\langle x^2 \rangle = \sum_i x_i^2 P_i$

Example Discrete Probability

Calculate $\langle x \rangle$ , $\langle x^2 \rangle$ , and $\sigma^2$ for a coin flip.

Solution

$\langle x \rangle = (1)(0.5) + (-1)(0.5) = 0$

$\langle x^2 \rangle = (1)^2(0.5) + (-1)^2(0.5) = 1$

$\sigma^2 = \langle x^2 \rangle - \langle x \rangle^2 = 1 - 0 = 1$

Continuous Probability

$\langle x \rangle = \int x P(x)\,dx$

and

$\int P(x)\,dx = 1$

Independent Variables

$\langle uv \rangle = \langle u \rangle \langle v \rangle$

Example Independent Variables

Are temperature and the size of a system independent?

Solution

Yes, temperature and system size are independent!

Binomial Distribution

A success has probability $p$ , and a failure has probability $1 - p$ . Success typically has a value of 1 and failure a value of –1. This makes sense since $p + (1 - p) = 1$ .

Probability of $k$ successes and $n-k$ failures in $n$ trials:

$p^k(1-p)^{n-k}$

If we have $k$ successes in $n$ trials, then there must be $n-k$ failures because there are only two possible outcomes. The average number of successful trials is the probability of success times the number of trials:

$\langle k \rangle = np$

$\sigma^2 = np(1-p)$

Drunkard’s Walk

A man leaves the bar and he is just as likely to step to the left as to the right. What is his average distance after $N$ steps, and what is the variance?

Solution

Let’s examine the possible outcomes after 2 steps: LL, RR, LR, RL — and the probability of each of these outcomes is:

$\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}$

This means that after 2 steps, the average distance is 0. We can extrapolate this behavior to $N$ steps — therefore, after $N$ steps the average distance is still 0.

$\langle d^2 \rangle = (\langle s_1 \rangle + \langle s_2 \rangle + \ldots + \langle s_N \rangle)^2 = \langle s_1^2 \rangle + \langle s_2^2 \rangle + \ldots + \langle s_N^2 \rangle + \langle s_1s_2 \rangle + \langle s_2s_1 \rangle + \ldots$

We know that:

$\langle s_1^2 \rangle = 1$

Whereas each term like $\langle s_1 s_2 \rangle$ is equally likely to be 1 or –1, and thus averages to 0.

Therefore, for every $N$ steps:

$\langle d^2 \rangle = (1 + 1 + 1 + \ldots + 1) = N$

$\sigma_d = \sqrt{N}$