Skip to content
nonconvexcard

What correlation does to voting

ProofIntermediate⏱ 30 minAgentscorrelationindependenceeffective sample size

Problem

Model votes as Vi=1[Zi=1]V_i = \mathbb{1}[Z_i = 1] where, with probability ρ\rho, all votes equal a single shared draw, and with probability 1−ρ1-\rho they are independent.

  1. Compute the probability the majority is correct as a function of ρ\rho, pp, kk.
  2. Take k→∞k\to\infty and interpret the limit.
  3. Define an effective number of independent votes and compute it for ρ=0.5\rho = 0.5, k=100k = 100.

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
SolvedProblemFieldTypeDifficultyTime
Pairwise independence does not imply independenceProbabilityProofFoundation15 min
Trajectory success from per-step reliabilityAgentsNumericalFoundation15 min
The reliability wallAgentsNumericalBeginner15 min
Detect-and-retry arithmeticAgentsProofIntermediate30 min
Majority voting via HoeffdingAgentsProofIntermediate30 min