Skip to content
nonconvexcard

The 1/n variance rate requires uncorrelated samples

NumericalIntermediate⏱ 30 minProbabilityvariancecorrelationeffective sample size

Problem

Let X1,…,XnX_1,\dots,X_n have common variance σ2\sigma^2 and equicorrelation Cov⁡(Xi,Xj)=ρσ2\Cov(X_i,X_j) = \rho\sigma^2 for i≠ji\ne j, with ρ∈[0,1]\rho \in [0,1].

  1. Compute Var⁡(Xˉn)\Var(\bar X_n) exactly.
  2. Find the limit as n→∞n\to\infty and interpret it.
  3. Define the effective sample size neff=σ2/Var⁡(Xˉn)n_{\text{eff}} = \sigma^2/\Var(\bar X_n) and compute it for ρ=0.1\rho = 0.1 with n=106n = 10^6.

Compute the requested quantities and say what they mean. A number without an interpretation is not an answer.

Hints

Hints — 0 of 2 revealed

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
The Δ²/12 noise varianceQuantizationProofBeginner15 min
Conditional expectation minimises mean squared errorProbabilityProofIntermediate30 min
Law of total variance and its useProbabilityProofIntermediate30 min
Mini-batching and the compute budgetSGDNumericalIntermediate30 min
Moments from tail bounds via the layer-cake formulaProbabilityProofIntermediate30 min