CS 203 — Part IV

Independence & Probabilistic

Methods
Pairwise · k-wise · Mutual Independence | Berkson's Paradox | AMS Algorithm
| Ramsey Theory | Sum-Free Subsets

Table of Contents
1. Independence of Events Definition, disjoint vs. independent, correlation Lecture 5

2. Berkson's Paradox Why conditioning creates spurious dependence Lecture 5

Pairwise, k-wise, Mutual Independence Hierarchy of independence Lecture 5

3.
notions

4. Independent Random Variables From events to RVs, k-wise for RVs Lecture 5

Pairwise Independent Bits (Construction) XOR trick: 2n-1 bits Lecture 5

5.
from n

AMS Algorithm — Frequency Moments Estimating F2 with small Lecture 5

6.
space

7. The Probabilistic Method Core idea: existence via non-zero probability Lecture 7

8. Ramsey Numbers Lower bound on R(k,k) via random graphs Lecture 7

9. Linearity of Expectation in Proofs Ramsey via expectation Lecture 7

1 Lecture 7
Sum-Free Subsets n/3 result via probabilistic argument
0.
 ■ LECTURE 5 — Notions of Independence and Applications (Prof. Rajat Mittal, IIT Kanpur)

Lecture 5

Independence of Events
1.1 Motivation and Intuition
Many events in everyday life influence each other. Your chance of arriving late to class might change if
your bus is delayed. The probability of rain today may affect tomorrow's forecast. To handle such
situations formally, we use conditional probability.

P(A | B) := P(A ∩ B) / P(B) (read: probability of A given B)

But sometimes, knowing B tells us nothing new about A. For example, tossing a fair coin twice — the
first toss result gives no information about the second. This is the notion of independence.

1.2 Formal Definition

Definition: Independent Events

Two events A and B are independent if:

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

Equivalently (when P(B) > 0): P(A | B) = P(A)

Independence means: knowing B occurred does not change the probability of A.

We prefer the first form P(A ∩ B) = P(A)P(B) because it also handles the edge case P(B) = 0 where
conditional probability is undefined.

1.3 Classic Examples

Example 1.1 — Unbiased Coin Tossed Twice

Let A = 'first toss is Heads', B = 'second toss is Heads'.

P(A) = 1/2, P(B) = 1/2, P(A ∩ B) = 1/4 = P(A)P(B). So A and B are independent.

This matches intuition: the coin has no memory.

Example 1.2 — Euler Misses School

Euler misses school with probability 1/2 on any day. But if he misses Monday, he likely
misses Tuesday too (he might be ill or travelling).

Let A = 'misses Monday', B = 'misses Tuesday'. P(B|A) > P(B), so they are DEPENDENT.

The physical link (illness/travel) creates statistical dependence.

 Example 1.3 — Balls With and Without Replacement

Urn has 2 Red + 2 Blue balls. Draw two balls. R1 = first is Red, B2 = second is Blue.

WITH replacement: P(R1) = 1/2, P(B2) = 1/2, P(R1 ∩ B2) = 1/4. Independent! ✓

WITHOUT replacement: P(B2 | R1) = 2/3 (two blue remain out of three). P(B2) = 1/2.

Since P(B2|R1) ≠ P(B2), they are DEPENDENT without replacement.

1.4 Independence vs. Disjoint Events — A Common Confusion

Critical Distinction: Independent ≠ Disjoint

DISJOINT (Mutually Exclusive): A ∩ B = empty set, so P(A ∩ B) = 0.

INDEPENDENT: P(A ∩ B) = P(A) · P(B).

If A and B are disjoint with P(A) > 0 and P(B) > 0, then P(A ∩ B) = 0 < P(A)P(B). So disjoint
events are actually NEGATIVELY DEPENDENT — if A happens, B cannot!

Never confuse these two concepts.

1.5 Correlation
Independence is the boundary between positive and negative correlation:

• Independent: P(A ∩ B) = P(A)P(B) — knowing A changes nothing about B

• Positively correlated: P(A ∩ B) > P(A)P(B) — A makes B more likely
• Negatively correlated: P(A ∩ B) < P(A)P(B) — A makes B less likely
 Lecture 5

Berkson's Paradox
2.1 The Paradox
Berkson's Paradox is a striking example of how conditioning can create apparent dependence
between truly independent events. It arises whenever we restrict attention to a biased subset of a
population.

2.2 The Hospital Example

Hospital Survey — How Conditioning Misleads

A hospital contains patients with Asthma and/or Diabetes.

In the general population: Asthma and Diabetes are INDEPENDENT.

Hospital observation: Diabetic patients seem LESS likely to have Asthma.

Why the contradiction? The hospital only sees sick people (A ∪ B patients).

Conditioning on 'being in the hospital' = conditioning on A ∪ B.

Even though A and B are independent overall, A|(A∪B) and B|(A∪B) are negatively related!

2.3 Quantitative Illustration

Population of 1000 balls: 100 are Red, 50 are Shiny, 5 are both Red and Shiny.

P(Shiny) = 50/1000 = 1/20. P(Shiny | Red) = 5/100 = 1/20. So Red and Shiny are independent.
Now keep only Red or Shiny balls: 100 + 50 - 5 = 145 balls.

P(Shiny | in filtered set) = 50/145 ≈ 1/3. But P(Shiny | Red and in filtered set) = 5/100 = 1/20.

In the filtered set, Red balls appear mostly NOT Shiny — even though they were independent originally!

Key Result: P(A | A ∪ B) > P(A) whenever P(A), P(B) > 0.

Moral: Never draw causal conclusions from data collected under selection bias. Hospital data, university
admissions data, and online survey data are all prone to Berkson's Paradox.
 Lecture 5

Pairwise, k-wise, and Mutual

Independence
3.1 Why We Need a Hierarchy
When we have a family of events {Ai}i ∈ I, simply saying 'every pair is independent' is not the same as
saying 'all subsets behave independently'. We need a precise hierarchy.

3.2 The Three Notions

Definition 1: Pairwise Independence (2-wise)

Events {A_i} are pairwise independent if for every distinct pair i ≠ j:

P(A_i ∩ A_j) = P(A_i) · P(A_j)

Definition 2: k-wise Independence

Events {A_i} are k-wise independent if for every subset J ⊆ I with |J| = k:

P(∩_{j ∈ J} A_j) = ∏_{j ∈ J} P(A_j)

Note: k-wise independence implies l-wise independence for all l ≤ k.

Definition 3: Mutual Independence

Events {A_i} are mutually independent if for EVERY subset J ⊆ I:

P(∩_{j ∈ J} A_j) = ∏_{j ∈ J} P(A_j)

This is |I|-wise independence — the strongest notion.

3.3 Why These Are All Different

It might seem that pairwise independence automatically implies mutual independence. It does not! Here
is the classic counterexample:
 Counterexample: Pairwise ≠ Mutual Independence

Toss a fair coin twice. Define events:

A = 'both tosses give the same result' (HH or TT)

B = 'first toss is Heads'

C = 'second toss is Heads'

P(A) = P(B) = P(C) = 1/2.

P(A ∩ B) = P(HH) = 1/4 = P(A)P(B). ✓ (A, B independent)

P(A ∩ C) = P(HH) = 1/4 = P(A)P(C). ✓ (A, C independent)

P(B ∩ C) = P(HH) = 1/4 = P(B)P(C). ✓ (B, C independent)

BUT: P(A ∩ B ∩ C) = P(HH) = 1/4 ≠ 1/8 = P(A)P(B)P(C). ✗

So A, B, C are pairwise independent but NOT mutually independent!

3.4 General Construction: k-wise but NOT (k+1)-wise Independent

Pick X1, X2, ..., Xk uniformly and independently from {0, 1}. Define Xk+1 = (X1 + X2 + ... + Xk) mod 2.

Any k of these variables are mutually independent (the XOR constraint only kicks in when all k+1 are
considered). But knowing X1, ..., Xk determines Xk+1 exactly — so they are NOT (k+1)-wise
independent.

3.5 Why Bother with Weaker Notions?

Mutual independence is expensive to construct. Generating n mutually independent bits requires n truly
random bits (one per variable). But many algorithms only need pairwise or k-wise independence. The
next section shows how to generate 2n-1 pairwise independent bits from just n random bits!
 Lecture 5

Independent Random Variables

4.1 From Events to Random Variables
A random variable X : Ω → ■ is a function from the sample space to the reals. Two RVs X and Y are
independent if every event defined by X is independent of every event defined by Y:

X ⊥ Y ⇔ P(X = x ∩ Y = y) = P(X = x) · P(Y = y) for all x, y

Intuitively: knowing the value of X tells you nothing about the value of Y.

4.2 k-wise Independence for Random Variables

Definition: k-wise Independent Random Variables

RVs {X_i}_{i ∈ I} are k-wise independent if for every subset J ⊆ I with |J| = k and for all
values {x_j}:

P(∩_{j ∈ J} {X_j = x_j}) = ∏_{j ∈ J} P(X_j = x_j)

Equivalently, |J| = k is enough to check (not |J| ≤ k).

4.3 Key Implication of Independence

Theorem: Independent RVs Satisfy the Product Rule

If X and Y are independent random variables, then:

E[XY] = E[X] · E[Y]

Proof: E[XY] = ∑_{x,y} xy · P(X=x, Y=y) = ∑_{x,y} xy · P(X=x)P(Y=y)

= (∑_x x · P(X=x)) · (∑_y y · P(Y=y)) = E[X] · E[Y].

 Lecture 5

Construction of Pairwise
Independent Bits
5.1 The Goal
Given n truly random independent bits X1, X2, ..., Xn, can we generate many more pairwise independent
bits using them? Yes — we can generate 2n - 1 pairwise independent bits using just n random bits!

5.2 The XOR Construction

Construction

For each non-empty subset S ⊆ {1, 2, ..., n}, define:

Y_S = (∑_{i ∈ S} X_i) mod 2 (XOR of the bits in S)

This creates 2^n - 1 new random bits (one for each non-empty subset of {1,...,n}).

5.3 Why Y_S is Uniform

Pick any non-empty S and any index i ∈ S. Fix all bits in S except Xi. Since Xi is 0 or 1 with probability
1/2 independently of the rest, YS flips between 0 and 1 with equal probability. Therefore P(YS = 0) =
P(YS = 1) = 1/2.

5.4 Proof of Pairwise Independence

Take any two distinct non-empty subsets U, V ⊆ {1,...,n}. Without loss of generality, there exists some
index i ∈ U with i ∉ V (otherwise swap U and V).

Fix all variables except Xi such that YV = b. Since i ∉ V, this fixing does not constrain Xi. When Xi
changes, YU flips. So:

P(Y_U = a | Y_V = b) = 1/2 = P(Y_U = a)

This proves YU and YV are independent. Since U, V were arbitrary, all pairs are independent!

Is this construction 3-wise independent?

No! For example, Y_{1}, Y_{2}, Y_{1,2} are pairwise independent but NOT 3-wise.

Y_{1} XOR Y_{2} = Y_{1,2} always — so knowing any two determines the third.

This matches the k-wise counterexample from Chapter 3.

 Lecture 5

AMS Algorithm — Estimating

Frequency Moments
6.1 The Problem
A server receives a stream of requests from n IP addresses with frequencies f1, f2, ..., fn. Define the
frequency moments:

F_1 = ∑ f_i (total requests) F_2 = ∑ f_i² (sum of squared frequencies)

If F2 >> F1, then a few addresses are making most requests — a sign of a potential attack (heavy hitters
problem). Keeping a full frequency table is too expensive in memory. Can we estimate F2 using very
little space?

6.2 The AMS Estimator

AMS Algorithm (Alon, Matias, Szegedy 1999)

For each IP address i, assign a random value a_i ∈ {-1, +1} with equal probability.

Maintain the running sum: Y = ∑_i a_i · f_i (just one counter!)

Output Z = Y² as the estimate of F_2.

6.3 Why Z is a Good Estimator — Expectation

Expand Z = Y²:

E[Z] = E[(∑_i a_i f_i)²] = ∑_i f_i² + ∑_{i≠j} f_i f_j E[a_i a_j]

If ai's are pairwise independent (not even mutual independence needed!): E[ai aj] = E[ai] · E[aj] = 0 · 0
= 0.

E[Z] = ∑_i f_i² = F_2 ✓

6.4 Bounding the Variance — Why 4-wise Independence is Needed

To show Z is close to F2 with high probability, we need Var(Z) to be small. Computing E[Z2] = E[Y4]
expands into many terms. The cross-terms vanish under 4-wise independence of the ai's:

Var(Z) = E[Z²] - (E[Z])² = 2 ∑_{i ≠ j} f_i² f_j² ≤ 2F_2²

6.5 Applying Chebyshev for Error Bound

With E[Z] = F2 and Var(Z) ≤ 2F22:

P(|Z - F_2| ≥ αF_2) ≤ Var(Z) / (αF_2)² ≤ 2F_2² / (α²F_2²) = 2/α²

So Z is within a factor α of F2 with probability at least 1 - 2/α2.

6.6 Boosting Accuracy by Averaging
Take s independent copies Z1, ..., Zs and average them: G = (1/s) ∑ Zi.

E[G] = F_2 Var(G) = Var(Z) / s ≤ 2F_2² / s

Setting s = 16/ε2 gives P(|G - F2| ≥ ε F2) ≤ 1/8. So with just O(1/ε2) counters, we estimate F2 within
factor (1+ε) with probability 7/8!

Summary: Why AMS is Brilliant

Only ONE counter per copy needed (just maintain Y, output Y^2).

Pairwise independence of a_i suffices for E[Z] = F2 (no mutual independence needed!).

4-wise independence of a_i suffices for variance bound.

We can generate 4-wise independent a_i's from O(log n) random bits using the XOR
construction.

Total memory: O(log n) bits for the seed + O(log F1) bits for the counter = tiny!
 ■ LECTURE 7 — Probabilistic Methods (Prof. Rajat Mittal, IIT Kanpur)

Lecture 7

The Probabilistic Method

7.1 The Big Idea
The Probabilistic Method is one of the most powerful and elegant techniques in combinatorics and
theoretical computer science. Here is the central idea:

The Probabilistic Method — Core Principle

To prove that an object with a desired property EXISTS:

1. Define a probability distribution over a set of objects.

2. Show that a randomly chosen object has the desired property with POSITIVE probability.

3. Conclude: at least one such object must exist.

The beauty: the problem has no randomness in its statement. We introduce randomness
only as a proof tool.

7.2 Non-Constructive Proofs

These proofs are existential — they guarantee something exists without explicitly constructing it. This
is sometimes frustrating (you want the thing, not just proof it exists!), but it's often the only known way to
prove existence for hard combinatorial problems.
However, the probabilistic method also suggests a randomized algorithm: just sample randomly. If
good objects have non-negligible probability, you'll find one quickly by sampling.
 Lecture 7

Ramsey Numbers
8.1 Graph Theory Background
Two key concepts in graph theory:

• Clique: A set of vertices where every pair is connected by an edge. A k-clique has k vertices all
connected to each other.
• Independent Set: A set of vertices where NO two are connected. A k-independent set has k
vertices with no edges between them.

8.2 Ramsey's Theorem

A fundamental result in combinatorics says: for any k and l, there exists a number n such that every
graph on n vertices contains either a k-clique or an l-independent set. The smallest such n is the
Ramsey number R(k, l).

Example: R(3, 3) = 6

Any graph on 6 vertices contains either a triangle (3-clique) or an independent set of size 3.

A graph on 5 vertices can avoid both (the cycle C5 has no triangle and no 3-independent
set).

So R(3, 3) = 6 exactly.

8.3 The Big Open Problem

Finding exact or tight values of R(k, k) for large k is one of the hardest open problems in combinatorics.
Even R(5, 5) is unknown! We use the probabilistic method to prove a lower bound: R(k, k) > n by
showing there EXISTS a graph on n vertices with no k-clique and no k-independent set.

8.4 Probabilistic Lower Bound on R(k, k)

Define a random graph G(n, 1/2): each edge is present independently with probability 1/2. Call a graph
'good' if it has no k-clique and no k-independent set.

For a particular set S of k vertices, S is a clique if all C(k,2) edges are present (probability
(1/2)^{C(k,2)}), or an independent set if all edges are absent (same probability). So:

P(subgraph S is clique or independent set) = 2 · 2^{-C(k,2)} = 2^{1-C(k,2)}

There are C(n, k) subsets of size k. By the Union Bound:

P(some k-subset is clique/indep. set) ≤ C(n,k) · 2^{1-C(k,2)}

 Theorem: Lower Bound on R(k, k)

If C(n, k) · 2^{1-C(k,2)} < 1, then R(k, k) > n.

That is: there exists a graph on n vertices with no k-clique and no k-independent set.

This holds when n = 2^{k/2} (approximately). So R(k, k) > 2^{k/2}.

The exponential lower bound — proved by Erdos in 1947 using this exact argument!

8.5 The Randomized Algorithm

If we set n = (1/2) · 2k/2, the probability of a bad graph is very small. This means most random graphs
are good! So a simple randomized algorithm works:

Randomized Algorithm for Good Graphs

1. Sample a random graph G(n, 1/2) on n = 2^{k/2}/2 vertices.

2. Check if it has any k-clique or k-independent set (this can be done in polynomial time).

3. If yes, resample. Expected number of trials is O(1).

This is non-constructive: we can't write down an explicit good graph, but we can find one
fast!
 Lecture 7

Linearity of Expectation in
Probabilistic Proofs
9.1 Alternative Proof of Ramsey Bound via Expectation
Instead of the union bound, we can use linearity of expectation to get the same result (and also extract
more information).

Let Ti = 1 if the i-th k-subset is a clique or independent set (else 0). Total 'bad' subgraphs: T = ∑ Ti.
Note: the Ti are DEPENDENT (overlapping subsets), but linearity doesn't care!

E[T] = ∑ E[T_i] = C(n,k) · 2^{1-C(k,2)}

If E[T] < 1, then there must exist a graph with T = 0 (no bad subgraph), since T is a non-negative integer
and its expectation is less than 1. Same conclusion as union bound!

Bonus: Expectation gives more. If E[T] = c for small c, we can remove at most one vertex from each
bad subgraph, deleting at most c · k vertices to make the graph completely good. This gives a better
constructive approach.

9.2 Independent Set in Any Graph

Linearity of expectation can also prove the existence of large independent sets in any graph.

Theorem: Every Graph Has a Large Independent Set

For any graph G = (V, E), there exists an independent set of size at least:

∑_{v ∈ V} 1 / (deg(v) + 1)

Proof idea: Consider a random permutation of vertices. Include vertex v in the independent
set if v comes before all its neighbors in the permutation.

P(v is chosen) = 1/(deg(v)+1) by symmetry. Sum by linearity.

 Lecture 7

Sum-Free Subsets
10.1 Definitions
Given a set of integers S, define S + S = {s1 + s2 : s1, s2 ∈ S}.

A set S is sum-free if S ∩ (S + S) = ∅. That is, no element of S equals the sum of two elements in S.

Examples of Sum-Free Sets

The set of odd numbers in {1, ..., 2n} is sum-free: odd + odd = even, so no sum stays odd.

{3, 4, 5} is sum-free: 3+3=6, 3+4=7, 3+5=8, 4+4=8, 4+5=9, 5+5=10. None in the set.

The set {k+1, k+2, ..., 2k+1} in Z_{3k+2} is sum-free (we will use this below).

10.2 The Main Theorem

Theorem (Probabilistic Method)

For any set S of n non-zero integers, there exists a sum-free subset of S of size > n/3.

Note: This is a purely combinatorial statement with no randomness — yet we prove it with
probability!

10.3 The Proof Strategy

The key idea: multiply S by a random integer r (modulo a carefully chosen prime p) and intersect with a
sum-free set T. On average, the intersection is large.

Step 1: Pick a prime p = 3k + 2 with p > 3 · max|s_i|.

(There are infinitely many primes of the form 3k + 2, so we can always find one.)

Step 2: The set T = {k+1, k+2, ..., 2k+1} is sum-free modulo p.

The size of T is k+1 > p/3 (since p = 3k+2). Note that (p-1)/3 < |T|/p < 1/3 + 1/p, so T covers just over 1/3
of {1,...,p-1}.

Step 3: Pick r uniformly at random from {1, 2, ..., p-1}.

Form rS mod p = {r · s1 mod p, ..., r · sn mod p}. Since p is prime, multiplication by r is a permutation of
{1,...,p-1}, so each r · si mod p is uniformly distributed.

Step 4: Count the expected size of rS mod p ∩ T.

E[|rS mod p ∩ T|] = ∑_i P(r·s_i mod p ∈ T) = n · |T|/(p-1) > n/3

Step 5: Since the expected size exceeds n/3, there must exist some r0 for which |r0S mod p ∩ T| > n/3.

Call this intersection T'. Since T is sum-free mod p and T' ⊆ T, T' is also sum-free mod p.

The pre-image r0-1T' in S (multiply back by r0-1) is sum-free over the integers (not just mod p, because p
was chosen larger than all sums).
 Conclusion: S contains a sum-free subset of size > n/3. ■

10.4 Why This Is Remarkable

The Power of the Argument

The theorem says nothing about randomness — it's a statement about integers.

But the proof is cleaner and shorter than any known deterministic proof.

The random r acts as a 'lens' that maps S into a well-understood structure (T).

This is typical of probabilistic arguments: introduce randomness to exploit symmetry, then

extract a deterministic conclusion via expectation or counting.

Quick Reference: Probabilistic Method Toolkit

Tool When to Use Key Formula Example Application

Union Bound P(any bad event) small P(∪ E_i) ≤ ∑ P(E_i) Ramsey lower bound

Linearity of Count expected

E[∑ X_i] = ∑ E[X_i] Empty bins, fixed points, sum-free
Expectation good/bad structures

First Moment Show E[X] < 1 implies

E[X] < 1 ⇒ ∃outcome: X=0 Ramsey via expectation
Method X=0 possible

Probabilistic + Remove small fraction of Delete ≤ c items to fix c bad

Larger independent sets
Alteration bad elements structures

When mutual
Pairwise
independence is too E[a_i a_j] = 0 for i ≠ j AMS frequency estimation
Independence
costly

Random Symmetric arguments on P(v before nbrs) =

Independent set size bound
Permutation orderings 1/(deg(v)+1)

End of CS 203 Part IV • Lecture 5 (Independence) + Lecture 7 (Probabilistic Methods) • Good luck on
your exams!