From the free course Statistics and Probability on Lykke

Probability and Combinatorics

Key concepts: Theoretical vs. Experimental Probability · Addition and Multiplication Rules · Conditional Probability · Permutations and Combinations · Independent Events

The mathematical foundations of chance, including counting rules and probability laws.

Probability and Combinatorics

Probability is the mathematical framework for quantifying uncertainty, providing the rigorous foundation upon which all of modern statistics, machine learning, and risk management are built. While descriptive statistics allow us to summarize the past, probability allows us to model the future. Combinatorics, the "art of counting," serves as the essential toolkit for determining the size of sample spaces that are often too vast to enumerate by hand.

Foundations of Probability

At its core, probability is the study of Random Phenomena—processes where the individual outcome is uncertain, but there is nonetheless a regular distribution of outcomes over a large number of repetitions. We define the Sample Space (S) as the set of all possible outcomes. An Event (E) is a subset of the sample space.

Kolmogorov’s Axioms:

  1. For any event $A$, $P(A) \geq 0$.
  2. The probability of the entire sample space is $P(S) = 1$.
  3. For any sequence of mutually exclusive events, the probability of their union is the sum of their individual probabilities.

Theoretical vs. Experimental Probability

The distinction between theoretical and experimental probability lies in the source of the data. Theoretical Probability is based on physical properties or logical reasoning (e.g., the symmetry of a fair die), while Experimental Probability (or Empirical Probability) is derived from observed data.

Feature Theoretical Probability Experimental Probability
Basis Logical reasoning, symmetry, and mathematical models. Observed frequency from trials or historical data.
Calculation $P(E) = \frac{\text{favorable outcomes}}{\text{total possible outcomes}}$ $P(E) \approx \frac{\text{number of times } E \text{ occurred}}{\text{total trials}}$
Context Games of chance, idealized physics, pure math. Quality control, insurance, clinical trials, ML.
Accuracy Exact within the model's assumptions. Subject to sampling error; improves with $n$.

The bridge between these two is the Law of Large Numbers (LLN). The LLN states that as the number of trials $n$ increases, the experimental probability converges to the theoretical probability.

The Rules of Probability

To navigate complex systems, we rely on a set of foundational rules that govern how probabilities interact. These rules allow us to decompose complex "compound events" into simpler components.

The Addition Rule (The "OR" Logic)

The Addition Rule is used when we want to find the probability that either Event A or Event B (or both) occurs. The primary challenge here is avoiding "double-counting" the intersection where both events happen simultaneously.

General Addition Rule: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$

If events are Mutually Exclusive (disjoint), meaning they cannot happen at the same time ($P(A \cap B) = 0$), the formula simplifies to $P(A) + P(B)$.

The Multiplication Rule (The "AND" Logic)

The Multiplication Rule determines the probability of two events occurring in sequence or simultaneously. It is intrinsically linked to the concept of Conditional Probability.

General Multiplication Rule: $P(A \cap B) = P(A) \cdot P(B|A)$

If the events are Independent, the occurrence of $A$ does not change the probability of $B$. In this specific case, $P(B|A) = P(B)$, and the rule simplifies to $P(A) \cdot P(B)$.

Conditional Probability and Independence

Conditional Probability is the probability of an event occurring given that another event has already occurred. This is the cornerstone of Bayesian statistics and modern predictive modeling. It effectively "shrinks" the sample space to only those outcomes where the given condition is met.

Formal Definition and Bayes' Theorem

The notation $P(A|B)$ is read as "the probability of A given B." It is calculated as: $$P(A|B) = \frac{P(A \cap B)}{P(B)}$$

This leads directly to Bayes' Theorem, which allows us to reverse the condition—finding $P(A|B)$ if we know $P(B|A)$. This is vital in medical testing, where we want to know the probability of having a disease given a positive test result.

\begin{aligned}
&\text{Bayes' Theorem Derivation:} \\
&1. P(A \cap B) = P(A|B)P(B) \\
&2. P(B \cap A) = P(B|A)P(A) \\
&\text{Since } P(A \cap B) = P(B \cap A): \\
&P(A|B)P(B) = P(B|A)P(A) \\
&\implies P(A|B) = \frac{P(B|A)P(A)}{P(B)}
\end{aligned}

Testing for Independence

Two events are Independent if and only if the knowledge that one has occurred does not affect the probability of the other. Mathematically, $A$ and $B$ are independent if any of the following hold:

  1. $P(A|B) = P(A)$
  2. $P(B|A) = P(B)$
  3. $P(A \cap B) = P(A) \cdot P(B)$
Concept Definition Mathematical Condition
Independent One event's outcome provides no info about the other. $P(A \cap B) = P(A)P(B)$
Dependent The outcome of one event changes the likelihood of the other. $P(A \cap B) \neq P(A)P(B)$
Mutually Exclusive The events cannot happen at the same time. $P(A \cap B) = 0$

Common Pitfall: Many students confuse "Independent" with "Mutually Exclusive." In fact, if two events with non-zero probabilities are mutually exclusive, they cannot be independent. If you know $A$ happened, the probability of $B$ happening becomes zero—a massive change in information.

Combinatorics: The Mathematics of Counting

In many probability problems, the sample space is too large to list. Combinatorics provides the formulas to calculate the number of outcomes in the sample space ($|S|$) and the number of favorable outcomes ($|E|$).

The Fundamental Counting Principle

If one task can be performed in $n$ ways and a second task in $m$ ways, then the sequence of two tasks can be performed in $n \times m$ ways. This generalizes to any number of tasks.

Permutations: Order Matters

A Permutation is an arrangement of items where the order is significant. For example, the sequence (A, B, C) is different from (C, B, A).

  • Permutations of $n$ items: $n!$ (n factorial)
  • Permutations of $n$ items taken $r$ at a time: $$P(n, r) = \frac{n!}{(n-r)!}$$

Combinations: Order Does Not Matter

A Combination is a selection of items where the order is irrelevant. For example, a committee of (Alice, Bob) is the same as (Bob, Alice).

  • Combinations of $n$ items taken $r$ at a time: $$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$
Scenario Order Matters? Formula Example
Permutation Yes $\frac{n!}{(n-r)!}$ Race finishes (1st, 2nd, 3rd)
Combination No $\frac{n!}{r!(n-r)!}$ Choosing a pizza topping combo
Permutation (with repetition) Yes $n^r$ Combination lock digits
Combination (with repetition) No $\frac{(n+r-1)!}{r!(n-1)!}$ Buying 5 sodas from 3 brands

Advanced Combinatorial Applications

Combinatorics extends beyond simple dice and cards into the realm of Binomial Distributions and Stochastic Processes.

The Binomial Coefficient in Probability

The formula for combinations, $\binom{n}{k}$, is also known as the Binomial Coefficient. It appears in the expansion of $(x+y)^n$ and is used to calculate the probability of exactly $k$ successes in $n$ independent Bernoulli trials (trials with only two outcomes: success or failure).

The probability of $k$ successes is given by: $$P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}$$ where $p$ is the probability of success on a single trial.

Combinatorial Explosion

In systems design, we must be wary of Combinatorial Explosion. As the number of variables $n$ increases, the number of possible states or paths often grows factorially ($n!$) or exponentially ($2^n$). This is why brute-force testing is impossible for complex software; we must use probabilistic sampling instead.

Common Pitfalls and Paradoxes

Probability is notoriously counter-intuitive. Even experts frequently fall into these traps:

  1. The Gambler's Fallacy: The belief that if an event happened more frequently than normal in the past, it is less likely to happen in the future (or vice versa). If a coin lands heads 10 times in a row, the probability of tails on the 11th flip is still exactly 0.5 (assuming the coin is fair).
  2. The Prosecutor's Fallacy: Confusing $P(Evidence|Innocent)$ with $P(Innocent|Evidence)$. Just because a DNA match is rare ($1$ in $1,000,000$) doesn't mean there is only a $1$ in $1,000,000$ chance the defendant is innocent.
  3. Ignoring the Base Rate: When calculating conditional probability, people often focus on the "hit rate" of a test and ignore how rare the condition is in the general population.
  4. Overestimating Small Sample Strengths: Humans tend to believe that small samples should be highly representative of the population, leading to the "Law of Small Numbers" bias.

Summary of Key Formulas

To master this section, one must be fluent in the following relationships:

Name Formula
Complement Rule $P(A^c) = 1 - P(A)$
General Addition $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
Conditional Prob $P(A|B) = \frac{P(A \cap B)}{P(B)}$
Independence Test $P(A \cap B) = P(A) \cdot P(B)$
Permutation $P(n, r) = \frac{n!}{(n-r)!}$
Combination $C(n, r) = \frac{n!}{r!(n-r)!}$
Probability and Combinatorics - Statistics and Probability - image 1
Probability and Combinatorics - Statistics and Probability - image 1
Probability and Combinatorics - Statistics and Probability - diagram 1
Probability and Combinatorics - Statistics and Probability - diagram 1
Probability and Combinatorics - Statistics and Probability - diagram 2
Probability and Combinatorics - Statistics and Probability - diagram 2
Probability and Combinatorics - Statistics and Probability - diagram 3
Probability and Combinatorics - Statistics and Probability - diagram 3

Source Materials

Study Statistics and Probability on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Statistics and Probability · Browse more course pages