EE 364 Supplemental – Week 03
Three Types of Proof
1. Direct
\(P \to Q\): assume \(P\), derive \(Q\).
2. Indirect (Proof by Contradiction)
“Reductio ad absurdum” (reduce to absurdity).
Assume \(P \land \sim Q\), derive \(C \land \sim C\) (a contradiction).
\(P \to Q \stackrel{\text{M.I.}}{=} \sim P \lor Q = \sim(P \land \sim Q)\)
\(\therefore \sim(P \to Q) = P \land \sim Q\)
\[ (P \to (Q \mathbin{\&} \sim Q)) \to \sim P \]
Proof. By truth table:
| \(P\) | \(Q\) | \(P \to (Q \land \sim Q)\) | \(\implies\) | \(\sim P\) |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |
\(\therefore\) valid. \(\square\)
Example: Indirect Proof
\(\forall \varepsilon > 0\): \(a \leq b + \varepsilon\) \(\implies\) \(a \leq b\).
Proof. Suppose not, i.e. \(\forall \varepsilon > 0\): \((a \leq b + \varepsilon) \land (a > b)\).
\[ \begin{aligned} a = \frac{a}{2} + \frac{a}{2} &\stackrel{\text{assum.}}{>} \frac{a}{2} + \frac{b}{2} = b - \frac{b}{2} + \frac{a}{2} = b + \frac{a - b}{2} \end{aligned} \]
Since \(a > b\) \(\iff\) \(a - b > 0\) \(\therefore\) \(\frac{a-b}{2} > 0\) \(\therefore\) \(\varepsilon' > 0\).
Let \(\varepsilon' = \frac{a-b}{2} > 0\). Then \(a > b + \varepsilon'\) with \(\varepsilon' > 0\).
Contradiction: since \(a \leq b + \varepsilon\) \(\forall \varepsilon > 0\). \(\square\)
\[ Q \land \sim Q \to P \]
(True AND false implies anything.)
IMAC Example: Finite Sigma-Algebra
Note: HW1/2
Sample space \(X\) contains four elements: \(X = \{a, b, c, d\}\). Its power set \(2^X\) contains \(2^4\) elements. The power set \(2^X\) gives rise to \(2^{16}\) subcollections of sets. Suppose that \(A \subset 2^X\) is one of these \(2^{16}\) set subcollections and that \(A\) contains the following 7 sets:
\[ A = \{\emptyset,\; \{a\},\; \{b\},\; \{a,b\},\; \{a,c,d\},\; \{b,c,d\},\; X\} \]
Can we define a probability space \((X, A, P)\) using the set collection \(A\) if \(P\) is a probability measure?
(Use IMAC format to answer.)
Solution
I: Sigma-algebra (s.a.)
M: \(\mathcal{A} \subset 2^X\) is a sigma-algebra iff \(\mathcal{A}\) is CUT:
- C: \(A \in \mathcal{A} \implies A^c \in \mathcal{A}\)
- U: \(A_1 \in \mathcal{A}, A_2 \in \mathcal{A}, \ldots \implies \bigcup_{k=1}^{\infty} A_k \in \mathcal{A}\)
- T: \(X \in \mathcal{A}\)
A: Check complement:
- \(\{a\}^c = \{b,c,d\} \in \mathcal{A}\)
- \(\{b\}^c = \{a,c,d\} \in \mathcal{A}\)
- \(\{a,b\}^c = \{c,d\} \notin \mathcal{A}\)
- \(\{b,c,d\}^c = \{a\} \in \mathcal{A}\)
- \(\{a,c,d\}^c = \{b\} \in \mathcal{A}\)
- \(\emptyset^c = X \in \mathcal{A}\), \(X^c = \emptyset \in \mathcal{A}\)
\(\therefore\) \(\mathcal{A}\) is not closed under complement because \(\{a,b\}^c \notin \mathcal{A}\).
Check union (exhaustive):
\[ \begin{aligned} \{a\} \cup \{b\} &= \{a,b\} \in \mathcal{A} \\ \{a\} \cup \{a,b\} &= \{a,b\} \in \mathcal{A} \\ \{a\} \cup \{a,c,d\} &= \{a,c,d\} \in \mathcal{A} \\ \{a\} \cup \{b,c,d\} &= X \in \mathcal{A} \\ \{b\} \cup \{a,b\} &= \{a,b\} \in \mathcal{A} \\ \{b\} \cup \{a,c,d\} &= X \in \mathcal{A} \\ \{b\} \cup \{b,c,d\} &= \{b,c,d\} \in \mathcal{A} \\ \emptyset \cup S &= S \in \mathcal{A} \text{ if } S \in \mathcal{A} \\ X \cup S &= X \in \mathcal{A} \text{ if } S \in \mathcal{A} \end{aligned} \]
\(\therefore\) \(\mathcal{A}\) is closed under union.
T: \(X \in \mathcal{A}\).
\(\therefore\) \(\mathcal{A}\) is not CUT \(\therefore\) \(\mathcal{A}\) is not a sigma-algebra.
C: NO. \((X, A, P)\) cannot be a probability space because \(A\) is not a sigma-algebra.
Discrete Sample Spaces
Finite or denumerable outcomes (can put into 1-to-1 correspondence with \(\mathbb{N}\)).
Ex: \(\Omega = \{a_1, a_2, \ldots, a_n\}\) – finite sample space.
Consider “equally likely outcomes”: \[ P[\{a_i\}] = \frac{1}{n} \quad \forall\, i = 1, \ldots, n \]
If event consists of \(k\) distinct outcomes: \[ P[B] = P[\{a_1', a_2', \ldots, a_k'\}] = P[\{a_1'\}] + \cdots + P[\{a_k'\}] = \frac{k}{n} \]
Ex: 3 coin flips \(\therefore\) 8 outcomes.
\(\Omega = \{\text{HHH, HHT, HTH, THH, HTT, THT, TTH, TTT}\}\)
Assume equiprobable: \(P[\text{xxx}] = \frac{1}{8}\).
\(P[\text{2 heads}] = P[\text{HHT or HTH or THH}] = \frac{3}{8}\)
Counting Methods and Combinatorics
In finite sample space with equiprobable outcomes: \[ P[\text{event}] = \frac{\text{distinct \# of outcomes that match event}}{\text{total \# distinct outcomes}} \]
Ex: Multiple choice exam, 10 questions, 4 options each.
# outcomes \(= \underbrace{4 \cdot 4 \cdot \ldots \cdot 4}_{10} = 2^{20} \approx 1\text{ million}\)
Birthday Paradox
Q: How large of group of \(k\) people to have prob. at least 0.5 of having at least two people with same birthday?
(Assume: 365 days/year, independent birthdays, equally likely per day.)
Let \(A_k\) = event at least 2 people in group of \(k\) share a birthday.
Define \(q_k = P[A_k^c]\) (no common birthday in group of \(k\)).
\[ \begin{aligned} q(1) &= 1 \\ q(2) &= q(1) \cdot \frac{364}{365} = \frac{364}{365} \\ q(3) &= q(2) \cdot \frac{363}{365} = \frac{365 \cdot 364 \cdot 363}{365^3} \\ &\;\vdots \\ q(k) &= q(k-1) \cdot \frac{365 - k + 1}{365} = \frac{365 \cdot 364 \cdots (365 - k + 1)}{365^k} = \frac{(365)_k}{365^k} \end{aligned} \]
“365 fall \(k\)”
By computer: \(q(22) = 0.524\), \(q(23) = 0.493\).
\(\therefore k \geq 23\) people.
Random Sampling (Ordered)
With Replacement
- Choose \(k\) from \(n\) distinct elements
- Select 1 at a time and “replace” after each selection
- \(\therefore\) duplicate samples possible
# outcomes: ordered \(k\)-tuple with \(n\) options for each position: \[ = \underbrace{n \cdot n \cdots n}_{k} = n^k \]
Ex: Multiple choice exam with 4 options per question.
Without Replacement
- Choose \(k\) from \(n\) distinct elements
- Select 1 at a time and “remove” after each selection
- \(\therefore\) no duplicate samples possible
\[ n_1 = n, \quad n_2 = n-1, \quad n_3 = n-2, \quad \ldots, \quad n_k = n - k + 1 \]
Note \(k \leq n\).
\(\therefore\) # outcomes \(= n \cdot (n-1)(n-2) \cdots (n-k+1)\)
Ex: Drawing balls #1–60 from urn, don’t replace.
Special Case: Permutation
Sampling w/o replacement, \(k = n\):
\[ \text{\# outcomes} = n \cdot (n-1)(n-2) \cdots (2)(1) = n! \]
Permutations and the Fundamental Rule of Counting
Permutation = self-bijection.
- \(f: S \to S\)
- \(f\): 1-to-1 (injection)
- \(f\): onto (surjection)
Fundamental Rule of Counting
An arrangement consists of positions with \(n_k\) options each:
\[ |\text{arrangements}| = \prod_{k=1}^{n} n_k \]
\(= n^k\) if \(n_k = n\) \(\forall k\).
\(P(n,k)\) = # permutations of length \(k\) on \(n\) elements:
\[ P(n,k) = n \cdot (n-1) \cdots (n - (k-1)) \cdot \frac{(n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} \quad \text{for } k \leq n \]
\[ n! = n \cdot (n-1) \cdots 3 \cdot 2 \cdot 1 \quad \text{for } n \in \{0, 1, 2, \ldots\} \]
(\(0! = 1\).)
Stirling’s Approximation
\[ \ln n! \approx n \ln n - n \approx n \ln n \]
Ex: \(n! < n^n\) for \(n > 2\).
\(\therefore \ln n! < \ln n^n = n \ln n\)
Lower bound: \(e^n = \sum_{k=0}^{\infty} \frac{n^k}{k!} > \frac{n^n}{n!}\) (the \(n\)-th term of the series).
Since \(\sum_{k=0}^{\infty} \frac{n^k}{n!} = \frac{n^0}{0!} + \frac{n^1}{1!} + \frac{n^2}{2!} + \cdots + \frac{n^n}{n!} + \cdots\)
\[ \begin{aligned} \therefore\; n! &> \frac{n^n}{e^n} \\ \therefore\; \ln n! &> n \ln n - n \\ \therefore\; n \ln n - n &< \ln n! < n \ln n \end{aligned} \]
\[ \therefore\; 1 - \frac{1}{\ln n} < \frac{\ln n!}{n \ln n} < 1 \]
\[ \therefore\; \lim_{n \to \infty} \frac{\ln n!}{n \ln n} = 1 \qquad \therefore\; \ln n! \sim n \ln n \]
\[ \ln n! = \ln \prod_{k=1}^{n} k = \sum_{k=1}^{n} \ln k \;\sim\; \int_1^n \ln x\, dx \]
By integration by parts (\(u = \ln x\), \(dv = dx\)):
\[ = x \ln x \Big|_1^n - x \Big|_1^n = n \ln n - n + 1 \sim n \ln n - n \]
Unordered Sampling
Order doesn’t matter, i.e. \((a,b) \sim (b,a)\).
Without Replacement
- Choose \(k\) from \(n\) w/o replacement
- Outcome order does not matter
Ex: “Standard lottery.” Draw 6 balls, “lottery numbers,” any order wins.
\(\therefore\) 60 balls choose 6: \(60 \cdot 59 \cdots 55 = \frac{60!}{54!} = \frac{n!}{(n-k)!}\)
But each outcome has: \(6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6!\) equivalent outcomes (orderings).
\[ \therefore \text{\# outcomes} = \frac{60!}{54!\; 6!} \]
\[ \frac{n!}{(n-k)!\; k!} = \binom{n}{k} \]
With Replacement
- Choose \(k\) from \(n\) with replacement
- Outcome order does not matter
Ex: “Pizza toppings” – \(k = 4\) toppings from \(n = 5\) choices (duplicates OK).
| A | B | C | D | |
|---|---|---|---|---|
| Outcome #1 | XX | X | XX | |
| Outcome #2 | X | XX | X | X |
Shorthand (stars and bars): XX||X|XX (#1), X|XX|X|X (#2) – \(k\) “X”s and \(n-1\) “|”s.
\(\therefore\) every unordered outcome with replacement is equivalent to a unique ordered sample of \(k\) “X”s and \(n-1\) “|”s.
\(\therefore\) # distinct outcomes: sample w/o replacement from urn with \(k\) black balls and \((n-1)\) white balls (\(\therefore\) total \(= n - 1 + k\) balls).
Ex (cont): How many distinct ordered permutations of \(k\) black balls and \(n-1\) white balls?
\[ \frac{(n - 1 + k)!}{k!\;(n-1)!} = \binom{n-1+k}{k} = \binom{n-1+k}{n-1} \]
Choose \(k\) positions for “X” or equivalently choose \(n-1\) positions for “|”.
Counting Method Summary
| With Replacement | Without Replacement | |
|---|---|---|
| Ordered | \(n^k\) | \(n(n-1)\cdots(n-(k-1)) = \frac{n!}{(n-k)!}\) |
| Ex: # ways to answer multiple choice test | Ex: # ways to rank \(k\) students from \(n\) | |
| Unordered | \(\dfrac{(n-1+k)!}{(n-1)!\;k!} = \dbinom{n-1+k}{k}\) | \(\dfrac{n!}{k!\;(n-k)!} = \dbinom{n}{k}\) |
| Ex: # different pizzas with \(k\) toppings (duplicates OK) | Ex: # ways to draw \(k\) “lottery numbers” |
Binomial Coefficients
\(P(n,k)\) = # permutations of length \(k\) on \(n\) elements \(= \dfrac{n!}{(n-k)!}\) for \(k \leq n\).
\(C(n,k)\) = # combinations of length \(k\) on \(n\) elements \(= \dbinom{n}{k} = \dfrac{n!}{(n-k)!\;k!}\) for \(k \leq n\).
Note: \(\binom{n}{0} = 1\) (\(\leftrightarrow \emptyset\)), \(\quad \binom{n}{n} = 1\) (\(\leftrightarrow \Omega\)).
Pascal’s Triangle
\[ \binom{n}{k} = \frac{n!}{k!\;(n-k)!} = \frac{n!}{(n-k)!\;k!} = \binom{n}{n-k} \]
Pascal’s Formula
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
Proof. \[ \begin{aligned} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!\;(n-1-(k-1))!} + \frac{(n-1)!}{k!\;(n-1-k)!} \\[6pt] &= \frac{k}{k} \cdot \frac{(n-1)!}{(k-1)!\;(n-k)!} + \frac{(n-1)!}{k!\;(n-1-k)!} \cdot \frac{n-k}{n-k} \\[6pt] &= \frac{(n-1)!\;k}{k!\;(n-k)!} + \frac{(n-1)!\;(n-k)}{k!\;(n-k)!} \\[6pt] &= \frac{(n-1)!\;(n - k + k)}{k!\;(n-k)!} = \frac{(n-1)!\;n}{k!\;(n-k)!} \\[6pt] &= \frac{n!}{k!\;(n-k)!} = \binom{n}{k} \quad \square \end{aligned} \]
Review: Changing the Index of Summation
Show: \(\displaystyle\sum_{k=1}^{n} a_{k-1} = \sum_{j=0}^{n-1} a_j\)
Technique: Put \(j = k - 1\), \(\therefore k = j + 1\).
\[ \sum_{k=1}^{n} a_{k-1} = \sum_{k=1}^{k=n} a_{k-1} = \sum_{j+1=1}^{j+1=n} a_j = \sum_{j=0}^{n-1} a_j \quad \square \]
Binomial Theorem
\[ (p + q)^n = \sum_{k=0}^{n} \binom{n}{k} p^k\, q^{n-k} \]
Proof. By induction on \(n = 1, 2, 3, \ldots\)
Basis: \(n = 1\). \((p + q)^1 = p + q\).
\[ \sum_{k=0}^{1} \binom{1}{k} p^k q^{1-k} = \binom{1}{0} p^0 q^1 + \binom{1}{1} p^1 q^0 = p + q \quad \square\text{-basis} \]
Induction Step. IH: \((p + q)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} p^k q^{(n-1)-k}\)
\[ \begin{aligned} (p+q)^n &= (p+q)(p+q)^{n-1} \\ &\stackrel{\text{IH}}{=} (p+q) \sum_{k=0}^{n-1} \binom{n-1}{k} p^k q^{(n-1)-k} \\ &= \sum_{k=0}^{n-1} \binom{n-1}{k} p^{k+1} q^{n-k-1} + \sum_{k=0}^{n-1} \binom{n-1}{k} p^k q^{n-k} \end{aligned} \]
Re-index: let \(j = k + 1\) (\(\therefore k = j - 1\)) in the first sum, \(j = k\) in the second:
\[ = \sum_{j=1}^{n} \binom{n-1}{j-1} p^j q^{n-j} + \sum_{j=0}^{n-1} \binom{n-1}{j} p^j q^{n-j} \]
Separate the boundary terms:
\[ = \left[\underbrace{\binom{n-1}{n-1}}_{=1} p^n q^{n-n} + \sum_{j=1}^{n-1} \binom{n-1}{j-1} p^j q^{n-j}\right] + \left[\sum_{j=1}^{n-1} \binom{n-1}{j} p^j q^{n-j} + \underbrace{\binom{n-1}{0}}_{=1} p^0 q^{n-0}\right] \]
\[ = p^n + \sum_{j=1}^{n-1} \left[\binom{n-1}{j-1} + \binom{n-1}{j}\right] p^j q^{n-j} + q^n \]
By Pascal’s formula: \(\binom{n-1}{j-1} + \binom{n-1}{j} = \binom{n}{j}\).
\[ = p^n + \sum_{j=1}^{n-1} \binom{n}{j} p^j q^{n-j} + q^n = \binom{n}{n} p^n q^{n-n} + \sum_{j=1}^{n-1} \binom{n}{j} p^j q^{n-j} + \binom{n}{0} p^0 q^{n-0} \]
\[ = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} \quad \square \]
Corollaries of the Binomial Theorem
1. \(p = q = 1\):
\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n \]
since \(2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k \cdot 1^{n-k}\).
2. \(p + q = 1\) with \(p \geq 0\), \(q \geq 0\) (\(\therefore q = 1 - p\)):
\[ \sum_{k=0}^{n} P(X = k) \stackrel{\text{binomial}}{=} \sum_{k=0}^{n} b(n,k,p) = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} \stackrel{\text{BT}}{=} (p + q)^n = 1^n = 1 \]
where \(b(n,k,p) = \binom{n}{k} p^k q^{n-k}\)
\(\therefore\) Binomial \(b(n,k,p)\) is a probability density.
3. \(p = -1\) and \(q = +1\):
\[ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \]
\[ \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} + \cdots + (-1)^n \binom{n}{n} = 0 \]