Majority voting via Hoeffding

ProofIntermediate⏱ 30 minAgentscondorcethoeffdingself-consistency

Problem

Prove that $k$ independent votes each correct with probability $p>1/2$ give majority error at most $\exp(-2k(p-\frac12)^2)$ .
Compute the number of votes needed for 99% majority accuracy at $p = 0.6, 0.75, 0.9$ .
Show the bound is vacuous at $p = 1/2$ and explain what happens for $p<1/2$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Trajectory success from per-step reliability	Agents	Numerical	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
The reliability wall	Agents	Numerical	Beginner	15 min
Derive Hoeffding's inequality from Hoeffding's lemma	High-Dim Probability	Proof	Intermediate	30 min
Detect-and-retry arithmetic	Agents	Proof	Intermediate	30 min