\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}

\title{CSCI 145 Problem 1: The Correlation Floor}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}

\maketitle

\subsection*{Submission Instructions}

Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive --- so bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 1: The Correlation Floor}

A poll asks $n = 10{,}000$ randomly selected people a yes/no question.
The textbook margin of error for a poll this size is about one point,
and it shrinks like $1/\sqrt{n}$: pay for more respondents, get a better answer.
Yet real polls of this size routinely miss the true answer by three points or more.
In this problem, we will find out why, and discover that no number of respondents can fix it.

Model person $i$'s answer as a random variable $X_i$ with $\Var(X_i) = \sigma^2$
(for example, $X_i = 1$ if person $i$ says yes and $X_i = 0$ otherwise).
The poll reports the sample mean
\begin{align*}
    \bar{X} = \frac{1}{n} \sum_{i=1}^n X_i.
\end{align*}

\subsection*{Part A: Variance of a Sum}

In class, we proved that $\Var(X + Y) = \Var(X) + \Var(Y) + 2\Cov(X, Y)$.
Generalize this identity to $n$ random variables:
\begin{align*}
    \Var\left( \sum_{i=1}^n X_i \right)
    = \sum_{i=1}^n \Var(X_i) + \sum_{i \neq j} \Cov(X_i, X_j),
\end{align*}
where the second sum ranges over all ordered pairs $i \neq j$.
(Both tools are in the reading: $\Var(Z) = \Cov(Z, Z)$, and covariance is \textit{bilinear}, so it distributes over sums in each of its two arguments just like foiling a product.)

\subsection*{Part B: Correlated Voices}

Independence between respondents is a fiction:
they share news sources, the poll reaches some groups more easily than others,
and people are more willing to admit some opinions to a stranger than others.
Model this shared error by making the answers \textit{equicorrelated}:
$\Cov(X_i, X_j) = \rho \sigma^2$ for all $i \neq j$.
Since all the $X_i$ share the standard deviation $\sigma$, this $\rho$ is exactly the correlation from lecture; take $0 \leq \rho < 1$.
Show that
\begin{align*}
    \Var(\bar{X}) = \frac{(1 - \rho)\sigma^2}{n} + \rho \sigma^2.
\end{align*}
(Lecture's $\Var(aZ) = a^2 \Var(Z)$ handles the $\frac1n$ out front.)
Check your formula on the independent case:
$\rho = 0$ should give $\Var(\bar{X}) = \sigma^2/n$, which for a yes/no question ($\sigma \leq \frac12$) and $n = 10{,}000$ is a standard deviation of at most half a point, the textbook margin.
What happens to each of the two terms as $n \to \infty$?

\subsection*{Part C: The Floor}

Take $\sigma = \frac12$ and $n = 10{,}000$.
How large must $\rho$ be for the standard deviation of $\bar{X}$ to reach three points, i.e., $0.03$?
(Part B tells you which term you may ignore.)
Your $\rho$ should be far too small to notice between two individual respondents.
Conclude in one sentence why the pollster cannot fix the miss by polling more people, and say what \textit{would} have to change instead.

\vspace{0.5em}
\noindent
\textbf{Where this goes next.}
This calculation seeds the course's variance-reduction thread.
Next lecture uses correlation the other way: a quantity \textit{correlated} with the one we care about becomes a tool for driving variance down, by an amount set by exactly the $\rho$ from this problem.
The floor returns when we study stochastic gradient descent, where near-duplicate examples in a batch are correlated voices.

%\input{solutions/solution01}

\end{document}
