\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} % STUDENTS: % You can enter your solutions into this template by just % typing them right after it says "SOLUTION". % Ignore the \ifdefined\sol blocks; you can delete them if you want. % (Note that it won't compile if you try to uncomment the % solution flag :)) % \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} \newcommand{\bE}{\mathbb{E}} \newcommand{\Ex}{\mathbb{E}} \newcommand{\Var}{\mathrm{Var}} \newcommand{\Z}{\mathbb{Z}} \newtheorem{theorem}{Theorem} \newtheorem{assumption}{Assumption} \begin{document} \noindent \textbf{Problem Set 3 \ifdefined\sol Solution \fi} \hfill CS265/CME309, Winter 2026 \ifdefined\sol\else \newline Due: Friday 1/30, 11:59pm on Gradescope \ifdefined\template \newline Group members: INSERT NAMES HERE \fi \vspace{.4cm}\noindent Please follow the homework policies on the course website. \fi \noindent \rule{\linewidth}{0.4pt} \noindent \textbf{Note:} Throughout this problem set (and in general in this class unless otherwise stated), you are allowed to use as a black box anything we have stated in the lecture notes. In particular, there are several statements of Chernoff and Chernoff-like (Hoeffding, Bernstein) bounds in the lecture notes, and a few corollaries. In this problem set you can make your life a lot easier by finding the ``right'' one for the problem! \begin{enumerate} \item \pts{5} \textbf{[The Return of Median-of-means]} Let $X_1,X_2, \ldots, X_n$ be i.i.d. samples of a random variable $X$ with $\bE[X] = \mu$ and $\Var[X] \leq 1$. Suppose that $k$ divides $n$, let $m = n/k$. Consider the following algorithm for estimating $\mu$ from $n$ samples, which we studied in HW2. First, we divide the $n$ samples into $k$ groups of size $m$: \begin{align*} A_1 &= \{X_1, \ldots, X_m\}, A_2 = \{X_{m+1}, \ldots, X_{2m} \}, \cdots, A_k = \{X_{(k-1)m + 1}, \ldots, X_n \}. \end{align*} Then let $Y_i$ be the mean of $A_i$ for each $i = 1, \ldots, k$. Finally, let \[ \hat{\mu} = \mathrm{Median}(Y_1, \ldots, Y_k).\] Let $\epsilon, \delta \in (0,1)$. Our goal in this problem will be to pick $k$ and $m$ (and hence $n = mk$) in terms of $\epsilon$ and $\delta$ so that \begin{equation}\label{eq:want}\Pr[|\hat{\mu} - \mu| > \epsilon] \leq \delta.\end{equation} \begin{enumerate} \item \pts{5} In HW2, you showed that $n = O\left(\frac{1}{\epsilon^2 \delta}\right)$ samples sufficed to achieve the bound \eqref{eq:want} above with the median-of-means scheme. Using a Chernoff bound, show that in fact this scheme (for appropriate values of $k$ and $m$) can achieve \eqref{eq:want} with $n = O\left( \frac{\log(1/\delta)}{\epsilon^2}\right),$ much smaller than the $n$ from HW2. You may use the statement from part (a) of HW2's problem: $\Pr[ |Y_j - \mu| > \epsilon] \leq \frac{1}{m \epsilon^2}$. In your solution, make sure you clearly state how to choose $m$ and $k$, in terms of $\epsilon$ and~$\delta$. \hint{You may want to look back at the structure of the proof from HW2.} \item \pts{0} \textbf{[Optional: this part won't be graded.]}Your friend thinks that all this median-of-means thing is over-rated. They say: \vspace{.2cm} \textcolor{blue!70!black}{ ``Suppose that we define $\hat{\mu} = \frac{1}{n} \sum_{i=1}^n X_i$ instead. Then since the $X_i$ are fully independent, we can apply some Chernoff/Hoeffding/Bernstein bound to conclude that \[ \Pr[ |\hat{\mu} - \mu| \geq \epsilon ] \leq \exp(-\Omega(\epsilon^2 n)).\] In particular, if we choose $n$ on the order of $\log(1/\delta)/\epsilon^2$, then the right-hand side is at most $\delta$, and we achieve \eqref{eq:want}. So we can just use the mean instead of median-of-means and get the same thing.''} \vspace{.2cm} Is this argument correct (in spirit)? If so, make it rigorous. If not, state an additional assumption on the $X_i$'s that would be needed to make it correct, and then make it rigorous. \end{enumerate} \ifdefined\sol \begin{shaded} \textbf{SOLUTION:} \ifdefined\sol \input{solution/medianOfMeans.tex} \fi \end{shaded} \fi %%%%%%%%%%%%%% Graph Coloring %%%%%%%%% \item \pts{11} \textbf{[Graph Coloring]} The vertices of a simple graph (a graph with no self loops or multiple edges) $G = (V,E)$ are each independently assigned one of three colors: red, green, or blue, chosen uniformly at random. \begin{enumerate} \item \pts{3} Let $n = |V|$ be the number of vertices in the graph. Show that the probability that more than half of the vertices are red is $\exp(-\Omega(n))$. \item \pts{4} Let $m=|E|$ be the number of edges in the graph. Show that the probability that more than half of the edges are monochromatic (i.e., both endpoints have the same color) is $O(1/m)$. \item \pts{4} Suppose $G$ is a complete graph (that is, all of the ${n \choose 2}$ possible edges are in the graph). Show that the probability that more than half of the edges are monochromatic is $\exp(-\Omega(\sqrt{m}))$. \hint{Use similar reasoning as you did in part (a) to say something about the vertices.} \item \pts{0} \textbf{[Optional: This won't be graded.]} Improve the bound from part (b). \end{enumerate} \ifdefined\sol \begin{shaded} \textbf{SOLUTION:} \ifdefined\sol \input{solution/graphColoring.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 robust in the following sense: As long as less than half of the failure modes 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$ otheriwse. 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, you are to show that the probability of a crash is exponentially small in $n$. \hint{The inequality $\frac{e^{\delta}}{(1+\delta)^{1+\delta}} \le e^{-\delta^2/3}$ for $\delta \in [0, 1]$, which we used in the lecture notes, might be useful if you use Corollary 6 from the lecture notes.} \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 2$, 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: \begin{enumerate} \item Assumption~\ref{assump:independence} implies Assumption~\ref{assump:group}; and \item 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}. \end{enumerate} \hint{For (ii), 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, as in 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$. \textbf{Note:} \emph{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\sol \begin{shaded} \textbf{SOLUTION:} \ifdefined\sol \input{solution/concentration.tex} \fi \end{shaded} \fi \end{enumerate} \end{document}