09 Discrete Probability Space, Properties of Probability, Union of Events, Laplace Space, Composite Probability, Combinatorics

Lecture from: 18.03.2025 | Video: Homelab

Introduction

In our previous discussions, we’ve seen glimpses of how randomness can be a powerful tool in algorithm design (e.g., QuickSort, primality testing, cryptography, distributed computing). To rigorously analyze and understand such algorithms, we need a solid foundation in probability theory. This lecture introduces the basic building blocks: probability spaces, events, and fundamental rules for calculating probabilities.

Probability Space (Wahrscheinlichkeitsraum)

The mathematical framework for dealing with randomness is the probability space.

Definition 2.1: Discrete Probability Space

A discrete probability space is defined by:

Sample Space (Ergebnismenge) $Ω$ : This is the set of all possible outcomes of a random experiment. We denote these outcomes as elementary events (Elementarereignisse). For a discrete space, $Ω$ is countable: $Ω = {ω_{1}, ω_{2}, ω_{3}, ...}$
Probability Assignment (Wahrscheinlichkeit): Each elementary event $ω_{i} \in Ω$ is assigned a probability $Pr [ω_{i}]$ . This assignment must satisfy two conditions:
- Non-negativity: $0 \leq Pr [ω_{i}] \leq 1$ for all $ω_{i} \in Ω$ . (Probabilities are between 0 and 1, inclusive).
- Normalization: The sum of probabilities of all elementary events must equal 1: $\sum_{ω \in Ω} Pr [ω] = 1$

Events (Ereignisse)

An event (Ereignis) $E$ is any subset of the sample space $Ω$ , i.e., $E \subseteq Ω$ . An event represents a collection of possible outcomes.

The probability of an event $E$ , denoted $Pr [E]$ , is the sum of the probabilities of all elementary events contained within $E$ :

$Pr [E] := \sum_{ω \in E} Pr [ω]$

Complementary Event (Komplementärereignis)

If $E$ is an event, its complementary event, denoted $\overset{ˉ}{E}$ , consists of all elementary events in $Ω$ that are not in $E$ . Formally:

$\overset{ˉ}{E} := Ω ∖ E$

Example: Rolling a Die (Betrachte Würfel)

Consider the simple experiment of rolling a standard six-sided die.

Sample Space: The possible outcomes are the numbers 1 through 6. $Ω = {1, 2, 3, 4, 5, 6}$
Probability Assignment: Assuming a fair die, each outcome is equally likely. $Pr [1] = Pr [2] = Pr [3] = Pr [4] = Pr [5] = Pr [6] = \frac{1}{6}$ Note: $0 \leq 1/6 \leq 1$ and $\sum_{i = 1}^{6} Pr [i] = 6 \times \frac{1}{6} = 1$ .
Events: Let’s define some events:
- $A$ : “The result is even” (Augenzahl ist gerade). $A = {2, 4, 6}$ $Pr [A] = Pr [2] + Pr [4] + Pr [6] = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{3}{6} = \frac{1}{2}$
- $B$ : “The result is a prime number” (Augenzahl ist Primzahl). $B = {2, 3, 5}$ $Pr [B] = Pr [2] + Pr [3] + Pr [5] = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{3}{6} = \frac{1}{2}$
- $C$ : “The result is divisible by 6” (Augenzahl ist durch 6 teilbar). $C = {6}$ $Pr [C] = Pr [6] = \frac{1}{6}$

Basic Properties of Probability

From the definition of a probability space, several fundamental properties follow.

Lemma 2.2: Properties of Events

For any events $A, B, A_{1}, A_{2}, ...$ in a probability space $Ω$ :

Empty Set and Sample Space:
- $Pr [\emptyset] = 0$ (The probability of the impossible event is 0).
- $Pr [Ω] = 1$ (The probability of the certain event is 1).
Bounds: $0 \leq Pr [A] \leq 1$ .
Complement Rule: $Pr [\overset{ˉ}{A}] = 1 - Pr [A]$ . (The probability of an event not happening is 1 minus the probability that it does happen).
Monotonicity: If $A \subseteq B$ , then $Pr [A] \leq Pr [B]$ . (If event A implies event B, then the probability of A cannot exceed the probability of B).
Addition Rule for Disjoint Events (Additionssatz): If events $A_{1}, ..., A_{n}$ are pairwise disjoint (meaning $A_{i} \cap A_{j} = \emptyset$ for all $i \neq = j$ ), then the probability of their union is the sum of their individual probabilities: $Pr [⋃_{i = 1}^{n} A_{i}] = \sum_{i = 1}^{n} Pr [A_{i}]$ This rule also extends to a countably infinite collection of pairwise disjoint events: $Pr [⋃_{i = 1}^{\infty} A_{i}] = \sum_{i = 1}^{\infty} Pr [A_{i}]$

Union of Events (Vereinigung von Ereignissen)

What happens when events are not disjoint? The simple addition rule no longer applies directly.

Example: Dice (Continued)

Consider events $B = {2, 3, 5}$ and $C = {6}$ from the dice example. These are disjoint ( $B \cap C = \emptyset$ ). Their union is $B \cup C = {2, 3, 5, 6}$ . $Pr [B \cup C] = Pr [2] + Pr [3] + Pr [5] + Pr [6] = \frac{4}{6}$ Using the addition rule for disjoint events: $Pr [B] + Pr [C] = \frac{3}{6} + \frac{1}{6} = \frac{4}{6}$ . This works.

Now consider events $A = {2, 4, 6}$ and $B = {2, 3, 5}$ . These are not disjoint, as $A \cap B = {2}$ . Their union is $A \cup B = {2, 3, 4, 5, 6}$ . $Pr [A \cup B] = Pr [2] + Pr [3] + Pr [4] + Pr [5] + Pr [6] = \frac{5}{6}$ If we incorrectly use the simple addition rule: $Pr [A] + Pr [B] = \frac{3}{6} + \frac{3}{6} = \frac{6}{6} = 1$ . This is incorrect because we double-counted the outcome $ω = 2$ , which is in both $A$ and $B$ .

Boole’s Inequality (Union Bound)

For any (not necessarily disjoint) events $A_{1}, ..., A_{n}$ , the probability of their union is less than or equal to the sum of their individual probabilities.

Satz 2.4 (Boolesche Ungleichung): $Pr [⋃_{i = 1}^{n} A_{i}] \leq \sum_{i = 1}^{n} Pr [A_{i}]$

This is also known as the union bound. It provides a simple upper bound for the probability of a union, which is often useful even if it’s not exact.

Principle of Inclusion-Exclusion (Siebformel)

To calculate the exact probability of the union of non-disjoint events, we use the Principle of Inclusion-Exclusion (PIE), also known as the Sieve Formula (Siebformel).

Satz 2.3 (Siebformel, Prinzip der Inklusion/Exklusion): For any events $A_{1}, ..., A_{n}$ (where $n \geq 2$ ):

$Pr [i = 1 ⋃ n A_{i}] = i = 1 \sum n Pr [A_{i}] - 1 \leq i_{1} < i_{2} \leq n \sum Pr [A_{i_{1}} \cap A_{i_{2}}] + 1 \leq i_{1} < i_{2} < i_{3} \leq n \sum Pr [A_{i_{1}} \cap A_{i_{2}} \cap A_{i_{3}}] - \dots + (- 1)^{l + 1} 1 \leq i_{1} < \dots < i_{l} \leq n \sum Pr [A_{i_{1}} \cap \dots \cap A_{i_{l}}] + \dots + (- 1)^{n + 1} Pr [A_{1} \cap \dots \cap A_{n}]$

Explanation: The formula starts by summing all individual probabilities. Then, it subtracts the probabilities of all pairwise intersections (to correct for double-counting). Then, it adds back the probabilities of all three-way intersections (because they were subtracted too many times), and so on, alternating signs until the intersection of all $n$ events is considered.

Case n=3: For three events $A, B, C$ : $Pr [A \cup B \cup C] = Pr [A] + Pr [B] + Pr [C] - Pr [A \cap B] - Pr [A \cap C] - Pr [B \cap C] + Pr [A \cap B \cap C]$ This can be visualized using a Venn diagram.

Example: Dice (n=3): Let’s calculate $Pr [A \cup B \cup C]$ for the dice example using PIE. $A = {2, 4, 6}$ , $B = {2, 3, 5}$ , $C = {6}$ . $Pr [A] = 3/6$ , $Pr [B] = 3/6$ , $Pr [C] = 1/6$ . $A \cap B = {2}$ , $Pr [A \cap B] = 1/6$ . $A \cap C = {6}$ , $Pr [A \cap C] = 1/6$ . $B \cap C = \emptyset$ , $Pr [B \cap C] = 0$ . $A \cap B \cap C = \emptyset$ , $Pr [A \cap B \cap C] = 0$ .

$Pr [A \cup B \cup C] = Pr [A] + Pr [B] + Pr [C] - Pr [A \cap B] - Pr [A \cap C] - Pr [B \cap C] + Pr [A \cap B \cap C]$ $Pr [A \cup B \cup C] = \frac{3}{6} + \frac{3}{6} + \frac{1}{6} - \frac{1}{6} - \frac{1}{6} - 0 + 0 = \frac{7 - 2}{6} = \frac{5}{6}$ This matches our previous calculation by listing the elements in $A \cup B \cup C = {2, 3, 4, 5, 6}$ .

Proof of the Principle of Inclusion-Exclusion (Beweis der Siebformel)

Consider an arbitrary elementary event $ω \in ⋃_{i = 1}^{n} A_{i}$ . We need to show that $Pr [ω]$ is counted exactly once on both sides of the PIE formula.

Left-Hand Side (LHS): $Pr [⋃_{i = 1}^{n} A_{i}] = \sum_{ω^{'} \in ⋃ A_{i}} Pr [ω^{'}]$ . By definition, $Pr [ω]$ is included exactly once in this sum because $ω$ is in the union.
Right-Hand Side (RHS): Suppose $ω$ belongs to exactly $k$ of the sets $A_{1}, ..., A_{n}$ (where $1 \leq k \leq n$ ). How many times is $Pr [ω]$ counted on the RHS?
- It’s counted $(1 k) = k$ times in the first sum $\sum Pr [A_{i}]$ .
- It’s counted $(2 k)$ times in the second sum $\sum Pr [A_{i_{1}} \cap A_{i_{2}}]$ (since $ω$ is in an intersection $A_{i_{1}} \cap A_{i_{2}}$ if and only if it belongs to both $A_{i_{1}}$ and $A_{i_{2}}$ ).
- It’s counted $(l k)$ times in the sum corresponding to $l$ -way intersections $\sum Pr [A_{i_{1}} \cap \dots \cap A_{i_{l}}]$ .
- It’s counted $(k k) = 1$ time in the $k$ -way intersection sum.
- It’s counted $(l k) = 0$ times in sums for $l > k$ .
The total number of times $Pr [ω]$ is counted on the RHS is: $N_{k} = (1 k) - (2 k) + (3 k) - \dots + (- 1)^{k + 1} (k k)$

Recall the binomial theorem: $(x - y)^{k} = \sum_{j = 0}^{k} (j k) x^{k - j} (- y)^{j}$ . Let $x = 1$ and $y = 1$ . Then for $k \geq 1$ : $(1 - 1)^{k} = 0 = \sum_{j = 0}^{k} (j k) (1)^{k - j} (- 1)^{j} = (0 k) - (1 k) + (2 k) - \dots + (- 1)^{k} (k k)$ $0 = 1 - ((1 k) - (2 k) + (3 k) - \dots + (- 1)^{k + 1} (k k))$ $0 = 1 - N_{k}$ Therefore, $N_{k} = 1$ .

Since $Pr [ω]$ is counted exactly once on both the LHS and RHS for any $ω$ in the union, the Principle of Inclusion-Exclusion holds.

Laplace Space (Laplace-Raum)

A particularly important type of discrete probability space is the Laplace space.

Definition: A Laplace space is a finite probability space where all elementary events are equally likely.

If $Ω$ is the sample space of a Laplace space, then $∣Ω∣$ is finite, and for every $ω \in Ω$ :

$Pr [ω] = \frac{1}{∣Ω∣}$

Calculating Probabilities in a Laplace Space:

For any event $E \subseteq Ω$ in a Laplace space, the probability of $E$ is simply the ratio of the number of outcomes in $E$ to the total number of possible outcomes:

$Pr [E] = \sum_{ω \in E} Pr [ω] = \sum_{ω \in E} \frac{1}{∣Ω∣} = \frac{∣ E ∣}{∣Ω∣}$

(Probability = Number of favorable outcomes / Total number of outcomes)

Example: Drawing a Card

Consider drawing a single card from a standard 52-card deck. Let $C$ be the set of all 52 cards. $C = {♣, ♠, ♡, ♢} \times {2, 3, ..., 9, 10, J, Q, K, A}$ . The sample space is $Ω = C$ , and $∣Ω∣ = 52$ . Assuming the deck is well-shuffled, each card is equally likely to be drawn. This is a Laplace space. $Pr [ω] = \frac{1}{52}$ for any card $ω \in Ω$ .

Let $E$ be the event “drawing a King”. $E = {♣ K, ♠ K, ♡ K, ♢ K}$ . $∣ E ∣ = 4$ . $Pr [E] = \frac{∣ E ∣}{∣Ω∣} = \frac{4}{52} = \frac{1}{13}$ .

Composite Probability Spaces (zusammengesetzte W’räume)

Often, the most “natural” sample space for a problem might not be a Laplace space. It’s crucial to define the underlying probability space carefully, often by choosing a more detailed sample space that is a Laplace space, to correctly calculate probabilities.

Scenario 1: Drawing Two Cards

Experiment: Shuffle a deck and draw two cards.

Incorrect/Difficult $Ω$ ?: If we define $Ω = {X ∣ X \subseteq C, ∣ X ∣ = 2}$ , the set of all possible 2-card hands. $∣Ω∣ = (2 52) = \frac{52 \times 51}{2} = 1326$ . This is a Laplace space if we consider drawing the set of two cards. Each 2-card hand is equally likely. $Pr [X] = 1/ (2 52)$ .
Alternative (Often Easier) $Ω^{'}$ : Define $Ω^{'} = {(x_{1}, x_{2}) ∣ x_{1} \in C, x_{2} \in C, x_{1} \neq = x_{2}}$ , the set of ordered pairs of distinct cards.
- $∣ Ω^{'} ∣ = 52 \times 51 = 2652$ .
- This is also a Laplace space. The first card $x_{1}$ can be any of the 52 (equally likely). Given $x_{1}$ , the second card $x_{2}$ can be any of the remaining 51 (equally likely).
- $Pr [(x_{1}, x_{2})] = \frac{1}{52 \times 51}$ .
- Any specific 2-card hand $X = {a, b}$ corresponds to two outcomes in $Ω^{'}$ : $(a, b)$ and $(b, a)$ .
- Therefore, $Pr [X] = Pr [(a, b)] + Pr [(b, a)] = \frac{1}{52 \times 51} + \frac{1}{52 \times 51} = \frac{2}{52 \times 51} = \frac{1}{26 \times 51} = \frac{1}{1326}$ , matching the probability calculated using $Ω$ .

Scenario 2: Rolling Two Dice and Summing

Experiment: Roll two fair dice and observe the sum of the numbers shown.

Incorrect $Ω$ : If we define $Ω = {2, 3, 4, ..., 12}$ (the possible sums). $∣Ω∣ = 11$ .
- This is NOT a Laplace space. The outcome “sum = 2” can only happen in one way (1, 1), while “sum = 7” can happen in six ways (1,6), (2,5), (3,4), (4,3), (5,2), (6,1). Therefore, $Pr [2] \neq = Pr [7]$ .
Correct $Ω^{'}$ : Define $Ω^{'} = {(x_{1}, x_{2}) ∣ x_{1}, x_{2} \in {1, 2, 3, 4, 5, 6}}$ , the set of ordered pairs representing the outcomes of the two dice.
- $∣ Ω^{'} ∣ = 6 \times 6 = 36$ .
- This is a Laplace space. Each pair $(x_{1}, x_{2})$ is equally likely, with $Pr [(x_{1}, x_{2})] = \frac{1}{36}$ .
- We can calculate probabilities of sums using $Ω^{'}$ :
  - Event “Sum = 2”: $E_{2} = {(1, 1)}$ . $∣ E_{2} ∣ = 1$ . $Pr [Sum = 2] = 1/36$ .
  - Event “Sum = 7”: $E_{7} = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)}$ . $∣ E_{7} ∣ = 6$ . $Pr [Sum = 7] = 6/36 = 1/6$ .
  - Event “Sum = 10”: $E_{10} = {(4, 6), (5, 5), (6, 4)}$ . $∣ E_{10} ∣ = 3$ . $Pr [Sum = 10] = 3/36 = 1/12$ .

Key Takeaway: When calculating probabilities, especially involving multiple steps or components, it is often best to define the sample space $Ω$ such that it represents the most elementary, equally likely outcomes (a Laplace space), even if it’s more detailed than the final event you’re interested in.

Combinatorics Review: Counting the Ways to Choose

To correctly calculate probabilities, especially in Laplace spaces, we often need to count the number of possible outcomes ( $∣Ω∣$ ) and the number of outcomes corresponding to a specific event ( $∣ E ∣$ ). Combinatorics provides the tools for this counting.

A fundamental problem in combinatorics is determining the number of ways to choose $k$ items from a set containing $n$ distinct items. The method for counting depends on two crucial questions:

Does the order of selection matter? (Is the selection ordered or unordered?)
Can items be selected more than once? (Is the selection with replacement or without replacement?)

Let’s explore the four resulting scenarios.

1. Ordered Selection with Replacement (Tuples)

Scenario: We select $k$ items from a set of $n$ distinct items. The order in which we select the items matters, and we are allowed to select the same item multiple times.
Intuition: Think of filling $k$ ordered slots. For the first slot, we have $n$ choices. Since we are replacing the item (or can choose the same type again), we still have $n$ choices for the second slot, $n$ choices for the third, and so on, up to the $k$ -th slot.
Derivation: This uses the basic multiplication principle of counting. We have $k$ independent choices to make, and each choice has $n$ possibilities. Total ways = (Choices for slot 1) $\times$ (Choices for slot 2) $\times \dots \times$ (Choices for slot k) Total ways = $n \times n \times \dots \times n$ ( $k$ times)
Formula: The number of ways is $n^{k}$ .
Result Type: An ordered list of length $k$ , often called a tuple.
Examples:
- Possible 4-digit PIN codes using digits 0-9 ( $n = 10, k = 4$ ): $1 0^{4} = 10000$ .
- Possible outcomes when rolling a die 3 times ( $n = 6, k = 3$ ): $6^{3} = 216$ . (e.g., (1, 6, 1) is different from (6, 1, 1)).

2. Ordered Selection without Replacement (k-Permutations)

Scenario: We select $k$ items from a set of $n$ distinct items. The order of selection matters, but we cannot select the same item more than once. (Note: This requires $k \leq n$ ).
Intuition: Again, think of filling $k$ ordered slots. For the first slot, we have $n$ choices. Since we cannot replace the chosen item, we only have $n - 1$ choices remaining for the second slot. For the third slot, we have $n - 2$ choices, and so on, until the $k$ -th slot, for which we have $n - (k - 1) = n - k + 1$ choices.
Derivation: Using the multiplication principle with decreasing choices: Total ways = (Choices for slot 1) $\times$ (Choices for slot 2) $\times \dots \times$ (Choices for slot k) Total ways = $n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)$
Formula: This quantity is often denoted as $n^{\underline{k}}$ (falling factorial) or $P (n, k)$ . It can also be expressed using factorials: $n^{\underline{k}} = \frac{n !}{( n - k )!}$ Recall that $n! = n \times (n - 1) \times \dots \times 2 \times 1$ .
Result Type: An ordered list of $k$ distinct items, often called a k-permutation of $n$ .
Examples:
- Ways to award Gold, Silver, Bronze medals in a race with 8 competitors ( $n = 8, k = 3$ ): $8^{\underline{3}} = 8 \times 7 \times 6 = 336$ .
- Ways to arrange 3 distinct books from a collection of 5 on a shelf ( $n = 5, k = 3$ ): $5^{\underline{3}} = 5 \times 4 \times 3 = 60$ .

3. Unordered Selection without Replacement (Combinations / Sets)

Scenario: We select $k$ items from a set of $n$ distinct items. The order of selection does not matter, and we cannot select the same item more than once. (Requires $k \leq n$ ). This is equivalent to choosing a subset of size $k$ .
Intuition: How is this related to the ordered case without replacement (Case 2)? In Case 2, we counted sequences like (A, B, C) and (C, B, A) as distinct outcomes. However, if the order doesn’t matter, these sequences correspond to the same selection: the set ${A, B, C}$ . We need to figure out how many ordered sequences correspond to each unordered set.
Derivation:
1. Start with the ordered count: From Case 2, we know there are $n^{\underline{k}} = \frac{n !}{( n - k )!}$ ordered ways to select $k$ distinct items.
2. Identify overcounting: Consider any specific set of $k$ items. How many different ways could we have ordered these $k$ items when we were counting in Case 2? There are $k!$ ways to order $k$ distinct items (k choices for the first position, k-1 for the second, etc.).
3. Correct for overcounting: Since each unordered set of size $k$ corresponds to exactly $k!$ ordered sequences, the count from Case 2 ( $n^{\underline{k}}$ ) overcounts each unordered set by a factor of $k!$ . To get the number of unordered sets, we divide the ordered count by the overcounting factor $k!$ . Number of unordered sets = $\frac{Number of ordered sequences}{Number of ways to order each set} = \frac{n ^{\underline{k}}}{k !}$
Formula: This is the binomial coefficient, read as “n choose k”: $(k n) = \frac{n ^{\underline{k}}}{k !} = \frac{n !}{k ! ( n - k )!}$ Note that $(k n) = (n - k n)$ . Choosing $k$ items to include is the same as choosing $n - k$ items to exclude.
Result Type: An unordered set of $k$ distinct items, often called a combination.
Examples:
- Ways to choose 3 winners from 10 lottery tickets (order doesn’t matter) ( $n = 10, k = 3$ ): $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ .
- Ways to form a 5-card poker hand from a 52-card deck ( $n = 52, k = 5$ ): $(5 52) = \frac{52 !}{5 ! 47 !} = 2, 598, 960$ .

4. Unordered Selection with Replacement (Multisets / Stars and Bars)

Scenario: We select $k$ items from a set of $n$ distinct types of items. The order of selection does not matter, and we can select the same type of item multiple times.
Intuition: This is often the trickiest case to grasp. Imagine we have $n$ bins, representing the $n$ distinct types of items we can choose from. We want to choose a total of $k$ items. Since order doesn’t matter and we can repeat types, this is like deciding how many times we choose type 1, how many times type 2, …, up to type $n$ , such that the total number of choices is $k$ .
Derivation (Stars and Bars technique):
1. Represent Choices: Let $k$ “stars” $(*)$ represent the $k$ items we need to choose. Our goal is to divide these stars into $n$ groups, where each group corresponds to one of the $n$ types of items.
2. Represent Dividers: To divide the stars into $n$ groups, we need $n - 1$ “bars” (|). For example, if we have $n = 4$ types and want to choose $k = 5$ items, the sequence **|*||** could represent choosing 2 items of type 1, 1 item of type 2, 0 items of type 3, and 2 items of type 4.
3. Combine Stars and Bars: Every possible selection corresponds uniquely to an arrangement of $k$ stars and $n - 1$ bars in a sequence.
4. Counting Arrangements: We have a total of $k + (n - 1)$ positions in the sequence. We need to determine where the $k$ stars (or equivalently, the $n - 1$ bars) go.
5. Apply Combination Formula: This is now a combination problem (Case 3)! We need to choose $k$ positions for the stars out of the $k + n - 1$ total positions. The number of ways to do this is $(k k + n - 1)$ . Alternatively, we could choose $n - 1$ positions for the bars out of the $k + n - 1$ total positions, which gives $(n - 1 k + n - 1)$ . These two binomial coefficients are equal.
Formula: $(k n + k - 1) = (n - 1 n + k - 1)$
Result Type: An unordered collection where repetitions are allowed, often called a multiset.
Examples:
- Ways to choose 3 scoops of ice cream from 5 available flavors ( $n = 5, k = 3$ ): $(3 5 + 3 - 1) = (3 7) = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ .
- Number of non-negative integer solutions to $x_{1} + x_{2} + x_{3} = 10$ ( $n = 3$ types/variables, $k = 10$ total value/items): $(10 3 + 10 - 1) = (10 12) = (2 12) = \frac{12 \times 11}{2} = 66$ .

Summary Table

Selection Type	Replacement?	Order Matters?	Formula
Tuple	Yes	Yes	$n^{k}$
k-Permutation	No	Yes	$n^{\underline{k}} = \frac{n !}{( n - k )!}$
Combination / Set	No	No	$(k n) = \frac{n !}{k ! ( n - k )!}$
Multiset / Stars and Bars	Yes	No	$(k n + k - 1) = (n - 1 n + k - 1)$

Examples

Example: Card Game - Dealing Hands

Scenario: Shuffle a 52-card deck ( $∣ C ∣ = 52$ ). Deal 5 cards to Player A and 5 cards to Player B.

Sample Space $Ω$ : An outcome is a pair of hands $(X, Y)$ , where $X$ is Player A’s 5-card hand, $Y$ is Player B’s 5-card hand, $X, Y \subseteq C$ , $∣ X ∣ = ∣ Y ∣ = 5$ , and the hands are disjoint ( $X \cap Y = \emptyset$ ).

Calculating $∣Ω∣$ : This is a counting problem without replacement, and the order within a hand doesn’t matter, but the assignment to Player A vs Player B does. We can think sequentially:

Choose 5 cards for Player A: There are $(5 52)$ ways.
Choose 5 cards for Player B from the remaining 47 cards: There are $(5 47)$ ways.

Since these choices are made sequentially to define one outcome, we multiply the number of ways:

$∣Ω∣ = (5 52) \times (5 47) = \frac{52 !}{5 ! 47 !} \times \frac{47 !}{5 ! 42 !} = \frac{52 !}{5 ! 5 ! 42 !}$

This represents the total number of ways to deal two distinct 5-card hands to two players. This forms a Laplace space, where each deal $(X, Y)$ is equally likely.

(Note: The slide shows $5 2^{5} \cdot 5 2^{5}$ which is incorrect as it implies ordered selection with replacement. It also shows $(10 52) (5 10)$ which is an alternative correct way: first choose 10 cards to be dealt, then assign 5 of those 10 to player A (the rest go to B).)

Example: Permutations and Derangements

Scenario: Shuffle a deck of $n$ cards (initially ordered 1 to $n$ ). What is the probability that at least one card ends up in its original position?

Sample Space $Ω$ : The set of all possible permutations of $[n] = {1, 2, ..., n}$ . $∣Ω∣ = n!$ . This is a Laplace space, assuming a perfect shuffle.
Event $A$ : “At least one card is in its original position.” (A fixed point exists). $A = {π \in Ω ∣ \exists i \in [n] : π (i) = i}$
Calculating $Pr [A]$ using PIE: It’s easier to calculate $Pr [A]$ by defining events $A_{i}$ for each card $i$ . Let $A_{i}$ be the event “Card $i$ is in position $i$ “. Then $A = ⋃_{i = 1}^{n} A_{i}$ . We use the Principle of Inclusion-Exclusion: $Pr [A] = \sum_{i} Pr [A_{i}] - \sum_{i < j} Pr [A_{i} \cap A_{j}] + \sum_{i < j < k} Pr [A_{i} \cap A_{j} \cap A_{k}] - \dots$

Consider the intersection of $l$ such events, $A_{i_{1}} \cap \dots \cap A_{i_{l}}$ . This is the event that cards $i_{1}, ..., i_{l}$ are all in their original positions. The remaining $n - l$ cards can be permuted in $(n - l)!$ ways. So, $∣ A_{i_{1}} \cap \dots \cap A_{i_{l}} ∣ = (n - l)!$ . $Pr [A_{i_{1}} \cap \dots \cap A_{i_{l}}] = \frac{( n - l )!}{n !}$ .

There are $(l n)$ ways to choose the indices $i_{1}, ..., i_{l}$ . The $l$ -th term in the PIE sum is: $(- 1)^{l + 1} \sum_{1 \leq i_{1} < \dots < i_{l} \leq n} Pr [A_{i_{1}} \cap \dots \cap A_{i_{l}}] = (- 1)^{l + 1} (l n) \frac{( n - l )!}{n !}$ $= (- 1)^{l + 1} \frac{n !}{l ! ( n - l )!} \frac{( n - l )!}{n !} = (- 1)^{l + 1} \frac{1}{l !}$

So, the PIE formula becomes: $Pr [A] = \sum_{l = 1}^{n} (- 1)^{l + 1} \frac{1}{l !} = \frac{1}{1 !} - \frac{1}{2 !} + \frac{1}{3 !} - \dots + (- 1)^{n + 1} \frac{1}{n !}$

Recall the Taylor series expansion for $e^{x} = \sum_{k = 0}^{\infty} \frac{x ^{k}}{k !}$ . For $x = - 1$ , $e^{- 1} = \frac{1}{0 !} - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots = 1 - Pr [A]$ (for large $n$ ). Therefore, $Pr [A] = 1 - e^{- 1} \approx 1 - 0.367879... \approx 0.632$ .

The probability that at least one card remains in its original position converges to $1 - 1/ e \approx 63.2%$ as $n$ becomes large. The probability that no card is in its original position (a derangement) converges to $1/ e \approx 36.8%$ .

Continue here: 10 Conditional Probability, Independence, and Bayes’ Theorem

CS Notes

Explorer