\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
% \def\sol{1}
 \def\template{1}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1 \em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}

\newtheorem{assumption}{Assumption}

\newcommand{\eps}{\epsilon}
\newcommand{\Ex}[1]{\operatorname*{\mathbb{E}}\left[#1\right]}
\newcommand{\N}{\mathbb{N}}
\newcommand{\note}[1]{\noindent{[\textbf{NOTE:} \em #1 \em]}}
\newcommand{\pr}[1]{\Pr\left[#1\right]}
\newcommand{\R}{\mathbb{R}}

\begin{document}
\noindent
\textbf{Problem Set 3 \ifdefined\sol Solution \fi} \hfill CS265, Autumn 2023
\ifdefined\sol\else
\newline
Due: October 20 (Friday) 
\ifdefined\template
\newline 
Group members: INSERT NAMES HERE
\fi

%\today
\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi

\noindent
\rule{\linewidth}{0.4pt}

\begin{enumerate}


%%%%%%%%%%%%%%%%%%%%%% AGGREGATING GUESSES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
\item \pts{11} \textbf{Aggregating Guesses}

In this problem, we'll consider several different settings where we are aggregating a large number of noisy, unbiased estimates. Suppose a class has $n$ students. Each student is asked to estimate the current temperature.  Assume that they each provide independent, unbiased estimates, with $X_i$ denoting the $i$th student's guess.   Let $v_i$ denote $\mathrm{Var}[X_i]$.

\begin{enumerate}
	\item \pts{4} Suppose we know each of the $v_i$'s and decide to compute  a weighted combination $Z= \sum_i w_i X_i$, where the weights $w_i \geq 0$ are chosen so as to minimize the variance of $Z$, subject to $\sum_i w_i = 1$.  What are those optimal weights as a function of the $v_i$'s, and roughly how accurate will $Z$ be?  Please give an answer of the form: ``with probability at least $0.9$, $Z$ will be within $blah$ of the true temperature, where $blah$ is a function of the $v_i$'s.
	
	\item \pts{5} For this part, assume each $X_i$ is drawn from a normal (Gaussian) distribution, whose mean is the true temperature, and whose variance is 1.  Roughly how accurate should we expect the \emph{median} of the $n$ guesses to be?  As above, please give an answer of the form: ``with probability at least $0.9$, the median of the $X_i$'s will be within $blah$ of the true temperature,'' where $blah$ is a function of $n$.  Your value of $blah$ should be accurate up to a constant factor and use big-Oh notation, for example $O(1/n^{3/4})$ or something like that.
	
\hint{The following basic fact about a Gaussian should be helpful, and is the only property of a Gaussian that you will need: if $Y$ is a Gaussian with mean $\mu$ and variance 1, for any $\epsilon \in (0,1/2)$ $\Pr[Y<\mu-\epsilon]=\Pr[Y>\mu+\epsilon] < 1/2 - 0.3 \epsilon.$}
	 
	\item \pts{2} Answer the same question as above for the \emph{mean} of the $n$ values $X_i$.  How do your answers compare?
	
	\item \pts{0} \textbf{[Optional: This is a research-level problem.]} As above, suppose each $X_i$ is independently drawn from a normal distribution whose  mean is the true temperature, and variance $v_i$.  Assume you know the (multi)set of the $v_i$'s, but you don't know which variance corresponds to which guess.  How well should you expect to do, and is there an efficient algorithm that achieves this?
	
	\item \pts{0} \textbf{[Optional: This is a research-level problem.]} Suppose we are in the setting above, but don't know anything about the variances.  What is a near-optimal algorithm, and how well will it do, as a function of the (unknown) list of variances $v_1,\ldots.$?  

	\hint{ Note that if two $X_i$'s are identical (or super, super close) then we know that two of the variances are 0 (or really, really small), and hence either of those $X_i$'s would give an extremely accurate guess, no matter what the other $n-2$ guesses are...}
\end{enumerate}

\ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/aggregate.tex}
	\fi
\end{shaded}
\fi

%%%%%%%%%%%%%% CONCENTRATION WITHOUT INDEPENDENCE %%%%%%%%%%%%%%%%%%%%%%

\item \pts{11} \textbf{Concentration without Independence}

A computer system has $n$ different failure modes, each of which happens with a small probability. Fortunately, the system is designed to be sufficiently robust in the following sense: as long as less than half of the failures occur, things are fine; otherwise, a large-scale crash will happen. We want to make sure that the probability of crashing is small enough.

To model the above scenario, we define $n$ Bernoulli random variables $X_1, \ldots, X_n$. Each $X_i$ is the indicator of the $i$-th failure mode, i.e., $X_i = 1$ if failure $i$ occurs and $X_i = 0$ otherwise. Our goal is to upper bound the probability $\Pr\left[\sum_{i=1}^{n}X_i \ge n/2\right]$.

\begin{enumerate}
\item \pts{2} Let's first assume that the $n$ failure events are independent and the probability of each failure is at most $1/3$. Formally, we have:
\begin{assumption}\label{assump:independence}
    $\Pr[X_i = 1] \le 1/3$ for every $i \in [n]$ and $X_1, \ldots, X_n$ are independent.
\end{assumption}
Prove that under Assumption~\ref{assump:independence}, for some constant $C > 0$ that does not depend on $n$,
\begin{equation}\label{eq:p2-concentration}
    \Pr\left[\sum_{i=1}^{n}X_i \ge n/2\right] \le e^{-Cn}.
\end{equation}
Thus, the probability of a crash is exponentially small in $n$.

\hint{Feel free to use (without proof) any of the Chernoff bounds in lecture note \#5 (including Theorem 2 and Corollaries 5 and 6) and also the inequality $\frac{e^{\delta}}{(1+\delta)^{1+\delta}} \le e^{-\delta^2/3}$ for $\delta \in [0, 1]$.}

\item \label{part:counterexample} \pts{1} Now we decide that Assumption~\ref{assump:independence} is too unrealistic, since many of the failure modes are known to be strongly correlated. Show that only assuming $\Pr[X_i = 1] \le 1/3$ (and not the independence), the probability of crashing can be as large as $\Omega(1)$. In particular, prove that for any $n \ge 1$, there exist random variables $X_1, \ldots, X_n$ that satisfy: (1) $\Pr[X_i = 1] \le 1/3$ for every $i \in [n]$; (2) $\Pr\left[\sum_{i=1}^{n}X_i \ge n/2\right] \ge 1/3$.

\item \pts{2} Let's try the following relaxation of Assumption~\ref{assump:independence}, which states that the probability for $k$ different failures to occur simultaneously is exponentially small in $k$:
\begin{assumption}\label{assump:group}
    For any $S \subseteq [n]$, $\Pr\left[X_i = 1\text{ for all } i \in S\right] \le (1/3)^{|S|}$.
\end{assumption}

Show that Assumption~\ref{assump:group} is strictly weaker than Assumption~\ref{assump:independence} by proving: (1) Assumption~\ref{assump:independence} implies Assumption~\ref{assump:group}; (2) the implication on the other direction does not hold, i.e., there exist some $n$ and $X_1, \ldots, X_n$ that satisfy Assumption~\ref{assump:group} but not Assumption~\ref{assump:independence}.

\hint{For (2), there exists a counterexample for $n=2$.} 

\item \pts{6} Prove that under Assumption~\ref{assump:group}, inequality~\eqref{eq:p2-concentration} holds for some constant $C > 0$. In your proof, you can appeal to the proof of the Chernoff bounds from lecture videos/notes if you need to write it out verbatim at some point. For example, if you manage to upper bound $\Pr\left[\sum_{i=1}^{n}X_i \ge n/2\right]$ by an expression involving the moment-generating function of some random variable $Y$ that is the sum of $n$ independent Bernoulli random variables, you can simply say that ``the rest of the proof is exactly the proof of Theorem 2 from Lecture \#5''.

\hint{Consider independent Bernoulli random variables $Y_1, \ldots, Y_n$ with $Pr[Y_i = 1] = 1/3$ for each $i \in [n]$. For distinct indices $i, j, \ell \in [n]$, does $\Ex{X_iX_jX_\ell} \le \Ex{Y_iY_jY_\ell}$ hold? Can you extend your proof of the inequality to the case with repeating indices?}


\hint{Let $X = \sum_{i=1}^{n}X_i$ and $Y = \sum_{i=1}^{n}Y_i$. What can we say about $\Ex{X^k}$ and $\Ex{Y^k}$ for integer $k \ge 0$? Considering the identity $e^z = \sum_{k=0}^{+\infty}\frac{z^k}{k!}$, what can we say about $\Ex{e^{tX}}$ and $\Ex{e^{tY}}$ for any $t > 0$?}

\item \pts{0} \textbf{[Optional: this won't be graded.]} Can you construct counterexamples for Part~\ref{part:counterexample} that satisfy \emph{pairwise independence} but have a crashing probability of $\Omega(1/n)$? Formally, prove that there exists $C > 0$ such that for any $n \ge 2$, there exist $X_1, \ldots, X_n$ that satisfy: (1) $\Pr[X_i = 1] \le 1/3$; (2) $X_i$ and $X_j$ are independent for distinct $i, j \in [n]$; (3) $\Pr\left[\sum_{i=1}^{n}X_i \ge n/2\right] \ge C/n$.

\note{This shows that unlike Chebyshev's inequality, Chernoff bounds do not hold if we only assume pairwise independence.}

\hint{Recall pairwise independent hash functions if you have seen them before. You can use the Bertrand-Chebyshev theorem, which states that for any integer $n \ge 1$, there exists a prime number $p$ with $n < p < 2n$.}


\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/concentration.tex}
\fi
\end{shaded}
\fi


%%%%%%%%%%%%%%%%%%%%% PROCESSES AND CPUs %%%%%%%%%%%%%%%%%%


\item \pts{8} \textbf{Processes and CPUs}

Suppose that in a distributed system, we have $N$ CPUs and $P$ processes. 
Each process is independently and uniformly allocated to a CPU. However, if multiple processes are allocated to the same CPU, the CPU will choose one of them at random to complete; the remaining processes allocated to that CPU will not be completed.

\begin{enumerate}
    \item \pts{2} 
What is expected number of processes that will be completed?
    \item \pts{6} Suppose that $P \geq N$, and denote the total number of completed processes by $C$. \textbf{Use Poissonization} to prove that $\Pr\left[C \leq \frac{N}{2}\right] \leq e^{-\Omega(N)}.$

[\textbf{Note:} There may be ways to do this problem that don't involve Poissonization, but we want you to use it to get practice with it.  That is, you should prove the statement by analyzing the case when the number of processes is an appropriate Poisson random variable.  Don't forget the de-Poissonization step!]

   \item \pts{0} \textbf{[Optional: this won't be graded.]} Let $\mu$ be your answer from part (a).  Under what conditions on $P$ and $N$ can you use Poissonization to show that $\Pr[ C \leq (1 -\delta)\mu ] \leq e^{-\Omega_\delta(N)}$ for any $\delta > 0$, where the $\Omega_\delta$ notation means that you are allowed to have constants that depend on $\delta$ hidden inside the big-Omega.

    \ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/poissonization}
	\fi
\end{shaded}
\fi
\end{enumerate}



\end{enumerate}

\end{document}

