What correlation does to voting
ProofIntermediate⏱ 30 minAgentscorrelationindependenceeffective sample size
Problem
Model votes as where, with probability , all votes equal a single shared draw, and with probability they are independent.
- Compute the probability the majority is correct as a function of , , .
- Take and interpret the limit.
- Define an effective number of independent votes and compute it for , .
Write a complete argument. Every inequality you use should be one you could state precisely.
Solution
Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.
Related problems
All problems| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Pairwise independence does not imply independence | Probability | Proof | 15 min | ||
| Trajectory success from per-step reliability | Agents | Numerical | 15 min | ||
| The reliability wall | Agents | Numerical | 15 min | ||
| Detect-and-retry arithmetic | Agents | Proof | 30 min | ||
| Majority voting via Hoeffding | Agents | Proof | 30 min |