AI summary by TwinMind
Linearity of Expectations
MIT OpenCourseWare
12m 55s
Linearity of Expectations Definition
- Basic yet important concept in probability theory
- For random variables X1 through XM and constants C1 through CM
- Linear combination: C1X1 + C2X2 + ... + CM*XM
- Expectation distributes across sum: E[C1X1 + C2X2 + ... + CMXM] = C1E[X1] + C2E[X2] + ... + CME[XM]
- Note: Similar property does NOT hold for products
- E[XY] ≠ E[X]E[Y] in general
- Exception: when X and Y are independent or uncorrelated
Application 1: Fixed Points in Random Permutations
- Question: Average number of fixed points in random permutation of 1 through n
- Fixed point: element that maps to itself in permutation
- Example: permutation with n=4 showing 2 fixed points
- Solution approach using linearity of expectations:
- Define indicator random variable XI = 1 if I is fixed point, 0 otherwise
- E[XI] = probability I is fixed point = 1/n (uniform distribution)
- Total fixed points = X1 + X2 + ... + Xn
- E[total fixed points] = E[X1] + E[X2] + ... + E[Xn] = n * (1/n) = 1
- Answer: Average number of fixed points = 1
Application 2: Tournament Theory and Hamilton Paths
- Tournament definition:
- n vertices (players)
- Directed edge between every pair of vertices
- Each edge points in one of two directions
- Hamilton path definition:
- Directed path following edge directions
- Passes through each vertex exactly once
- Example shown with 4-vertex tournament containing Hamilton path
Theorem: Existence of Tournaments with Many Hamilton Paths
- Statement: For every n, there exists tournament on n vertices with at least n!*2^(-(n-1)) Hamilton paths
- Proof method: Probabilistic method using linearity of expectations
- Random tournament construction:
- Take complete graph on n vertices
- For each edge, flip fair coin to decide direction
- Analysis:
- Each of n! permutations of vertices forms potential directed path
- Probability any specific permutation becomes Hamilton path = 2^(-(n-1))
- Need n-1 coin flips to align correctly
- Expected number of Hamilton paths = n! * 2^(-(n-1))
- By probabilistic method: some tournament must achieve at least this expected value
- Conclusion: Proves existence without explicit construction
