\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}

In lecture we halved a Monte Carlo estimator's error without rolling a single extra die: we subtracted off a surrogate whose average we already knew, scaled by a coefficient guessed out of the air ($c = \tfrac{1}{2}$).
Was the guess lucky, and how much can the trick ever buy us?
In Problem 1 correlation was the villain that put a floor under a poll; here it answers both questions.

We want $\mu = \mathbb{E}[f(X)]$, and alongside the target $f(X)$ we have a \textit{surrogate} $g(X)$ whose expectation $\mathbb{E}[g(X)]$ we know exactly.
In class we built the adjusted Monte Carlo estimator
\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*}
where $X^{(1)}, \ldots, X^{(n)}$ are independent samples distributed like $X$, and we proved it unbiased for \textit{every} constant $c$.
So all choices of $c$ are correct on average; they differ only in variance.

\subsection*{Part A: The Variance Is a Parabola}

Show that
\begin{align*}
    \Var(\hat{\mu}_c)
    = \frac{1}{n} \Big( \Var(f(X)) - 2c \Cov(f(X), g(X)) + c^2 \Var(g(X)) \Big).
\end{align*}
(Hint: the samples are independent, so the variance of the average is the variance of one adjusted sample divided by $n$, the $\rho = 0$ case of Problem 1.
Then expand the variance of $f(X) - c\,g(X)$ with the variance-of-a-sum identity from class; constants shift nothing.)
As a function of $c$, is this parabola smiling or frowning, and why does that matter for what comes next?

\subsection*{Part B: The Bottom of the Parabola}

Find the coefficient $c^\star$ minimizing $\Var(\hat{\mu}_c)$ by setting the derivative in $c$ to zero.
Your answer should be
\begin{align*}
    c^\star = \frac{\Cov(f(X), g(X))}{\Var(g(X))}.
\end{align*}
Sanity-check it: what does the formula say when $f$ and $g$ are independent, and does that match what the adjustment \textit{should} do?

\subsection*{Part C: How Much It Saves}

Substitute $c^\star$ back into Part A and show that
\begin{align*}
    \Var(\hat{\mu}_{c^\star}) = \frac{\Var(f(X))}{n} \left( 1 - \rho^2 \right),
    \qquad \text{where} \quad
    \rho = \frac{\Cov(f(X), g(X))}{\sqrt{\Var(f(X)) \Var(g(X))}}
\end{align*}
is the correlation between target and surrogate.
Now apply it to the class example, with $f$ the larger of two dice and $g$ their sum, using the exact moments from enumerating the $36$ outcomes:
\begin{align*}
    \Var(f(X)) = \tfrac{2555}{1296}, \qquad
    \Cov(f(X), g(X)) = \tfrac{35}{12}, \qquad
    \Var(g(X)) = \tfrac{35}{6}.
\end{align*}
Compute $c^\star$ and the reduction factor $1 - \rho^2$, compare $c^\star$ against the value lecture guessed, and say how many games the adjustment saves.
Conclude in one sentence: what two properties make a surrogate $g$ worth having, and which of them decides \emph{how much} it is worth?

\medskip
\noindent
\textbf{Where this goes next.}
Stochastic gradient descent estimates the gradient by Monte Carlo, so everything you proved here applies to it verbatim, and in the final week the variance-minimizing \textit{baseline} an agent subtracts from its returns turns out to be exactly your $c^\star$.

%\input{solutions/solution02}

\end{document}
