Home / Courses / Discrete Mathematics / Unit 5

Discrete Mathematics Unit 5: Discrete probability

Discrete probability counts favorable outcomes over total outcomes, using the counting tools from the previous unit.

Covers: Sample spaces, conditional probability, expected value

Study guide

Discrete probability works with finite or countable sample spaces. The sample space S is the set of all possible outcomes, and an event E is a subset. When outcomes are equally likely, P(E) = |E|/|S|, so counting techniques (permutations and combinations) do most of the work. Probabilities are between 0 and 1, P(Eᶜ) = 1 − P(E), and P(E ∪ F) = P(E) + P(F) − P(E ∩ F).

Conditional probability is P(A | B) = P(A ∩ B)/P(B): the probability of A once you know B happened. Events are independent if P(A ∩ B) = P(A)P(B). Bayes' theorem reverses conditioning: P(A | B) = P(B | A)P(A)/P(B), where P(B) often comes from the law of total probability, summing over cases. It explains results like why a positive test for a rare disease can still be likely to be a false positive.

A random variable assigns a number to each outcome. Its expected value is E(X) = Σ x·P(X = x), the long-run average; a fair die has E(X) = 3.5. Linearity of expectation says E(X + Y) = E(X) + E(Y) even when X and Y are dependent, which makes many problems easy by splitting a count into indicator variables. Variance measures spread: V(X) = E(X²) − E(X)².

Bernoulli trials (independent success/failure trials) lead to the binomial distribution: P(k successes in n trials) = C(n, k)pᵏ(1 − p)ⁿ⁻ᵏ.

For a nonnegative random variable X and any a > 0, P(X ≥ a) ≤ E(X)/a. It needs only the mean. Shifting X by a known lower bound first often gives a sharper result. For any random variable with mean μ and variance σ², P(|X − μ| ≥ c) ≤ σ²/c². This bounds the chance of being far from the mean using only the variance.

Var(aX + b) = a²·Var(X), and Var(X + Y) = Var(X) + Var(Y) when X and Y are independent. So the average of n independent copies of X has variance Var(X)/n, and the standard deviation is the square root of the variance. If independent trials each succeed with probability p, the number of trials until the first success has a geometric distribution with expected value 1/p.

Key ideas

• With equally likely outcomes, P(E) = |E|/|S|.
• Complement: P(not E) = 1 − P(E).
• Conditional probability: P(A | B) = P(A ∩ B)/P(B).
• Bayes' theorem reverses a conditional probability.
• Expected value is the weighted average of outcomes; it's linear.

Formulas and rules

Common mistakes

• Assuming outcomes are equally likely when they aren't.
• Confusing P(A | B) with P(B | A).

Words to know

Probability with equally likely outcomes

P(E) = |E|/|S|

Bayes' theorem

P(A | B) = P(B | A)P(A)/P(B)

Linearity of expectation

E(X + Y) = E(X) + E(Y), even if X and Y are dependent.

"At least one" probability

1 − P(none)

Expected value

E(X) = Σ x·P(x); a fair die averages 3.5.

Sample space

The set of all possible outcomes.

Event

A subset of the sample space.

Conditional probability

P(A | B) = P(A ∩ B)/P(B)

Independent events

P(A ∩ B) = P(A)P(B)

Law of total probability

P(B) = Σ P(B | Aᵢ)P(Aᵢ)

Variance

V(X) = E(X²) − E(X)²

Bernoulli trial

An independent trial with two outcomes.

Indicator variable

1 if an event happens, 0 if not; its expected value is the probability.

Sample practice questions

27 more questions like these, from level 1 to 5, are in the practice set.