\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 2: The Optimal Control Variate}
\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 2: The Optimal Control Variate \hfill \textnormal{2 points}}

We want $\mu=\mathbb{E}[f(X)]$ and know the exact mean of a surrogate
$g(X)$, where $\Var(f(X))>0$ and $\Var(g(X))>0$.  From independent samples $X^{(1)},\ldots,X^{(n)}$, lecture
constructed the unbiased family
\begin{align*}
    \hat{\mu}_c=\frac{1}{n}\sum_{i=1}^n
    \Big[f(X^{(i)})-c\big(g(X^{(i)})-\mathbb{E}[g(X)]\big)\Big].
\end{align*}
Determine the best member of this family.  A complete analysis should find
the coefficient $c^\star$ that minimizes its variance, express the minimum
variance as a multiple of $\Var(f(X))/n$ using the correlation $\rho$ between
$f(X)$ and $g(X)$, and explain what your formulas predict when the surrogate
is uncorrelated with the target.

Test the result on the lecture's dice example, where $f$ is the larger of two
dice and $g$ is their sum.  Enumeration of the $36$ outcomes gives
\begin{align*}
    \Var(f(X))=\frac{2555}{1296},\qquad
    \Cov(f(X),g(X))=\frac{35}{12},\qquad
    \Var(g(X))=\frac{35}{6}.
\end{align*}
Compute $c^\star$, compare it with lecture's choice $c=\frac12$, and determine
how many independent games the unadjusted estimator would need to match the
variance of the optimally adjusted estimator using $n$ games.

\paragraph{Results you may use.}
The estimator above is unbiased for every constant $c$; the variance of an
average of $n$ independent, identically distributed random variables is the
variance of one divided by $n$; and
$\Var(U+aV)=\Var(U)+2a\Cov(U,V)+a^2\Var(V)$.
A quadratic $ac^2+bc+d$ with $a>0$ is minimized at $c=-b/(2a)$.

%\input{solutions/solution02}

\end{document}
