\documentclass[11pt]{article}
	\usepackage[margin=1in]{geometry}
	\usepackage{amsfonts, amsmath, amssymb, amsthm}
	\usepackage{microtype}
	\usepackage{nicefrac}
	\usepackage[small]{complexity}

	\usepackage[colorlinks=true]{hyperref}
	\hypersetup{
		linkcolor=[rgb]{0.5, 0.2, 0.2},
		citecolor=[rgb]{0.2, 0.5, 0.2},
		urlcolor =[rgb]{0.2, 0.2, 0.5}
	}

	% complexity, needs to be after hyperref to work
		\renewcommand{\S}{\defaultS}
		\renewcommand{\L}{\ComplexityFont{L}}
		\newcommand{\ETIME}{\ComplexityFont{E}}

	\newcommand{\thecourse}{\errmessage{Course is undefined}}
	\newcommand{\handout}[5]{
		%\renewcommand{\thepage}{#1-\arabic{page}}
		\noindent%
		\begin{center}%
			\framebox{%
				\vbox{%
					\vspace{1mm}%
					\hbox to 5.78in {
						{\bf \thecourse}%
						\hfill%
						\smash{\parbox[t]{3in}{\raggedleft #2}}%
					}%
					\vspace{\baselineskip}%
					\hbox to 5.78in { {\Large \hfill #5  \hfill} }%
					\vspace{\baselineskip}%
					\hbox to 5.78in {%
						\smash{\parbox[b]{2.5in}{\raggedright #3}}%
						\hfill
						\smash{\parbox[b]{3in}{\raggedleft #4}}%
						}%
				}%
			}%
		\end{center}%
		\vspace*{4mm}%
	}%

	% \setlength\parindent{0pt}

	% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
	\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
	\newif\ifstaritem
	\newcommand{\setupstarnumerate}{%
		\global\staritemfalse
		\let\origmakelabel\makelabel
		\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
		\def\makelabel##1{%
		\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
		\global\staritemfalse}%
	}

	% math
	\newcommand{\N}{\mathbb{N}}
	\newcommand{\F}{\mathbb{F}}
	\newcommand{\bits}{\ensuremath{\{0,1\}}}
	\newcommand{\la}{\langle}
	\newcommand{\ra}{\rangle}
	\newcommand{\rX}{\mathsf{X}}
	\newcommand{\rY}{\mathsf{Y}}
	\newcommand{\rZ}{\mathsf{Z}}
	\newcommand{\e}{\mathrm{e}}
	\renewcommand{\vec}[1]{\overline{#1}}
	\newcommand{\floor}[1]{\lfloor #1 \rfloor}
	\newcommand{\ceil}[1]{\lceil #1 \rceil}
	\newcommand{\eps}{\epsilon}
	\DeclareMathOperator{\Var}{Var}

	\renewcommand{\E}{\mathbb{E}}

	%	open/closed intervals
	%       [
	\newcommand{\ocint}[2]{\ensuremath{(#1,#2]}}%)
	\newcommand{\icint}[1]{\ocint{\infty}{#1}}
	%       (
	\newcommand{\coint}[2]{\ensuremath{[#1,#2)}}%]
	\newcommand{\ciint}[1]{\coint{#1}{\infty}}
	\newcommand{\ccint}[2]{\ensuremath{[#1,#2]}}%)
	\newcommand{\ooint}[2]{\ensuremath{(#1,#2)}}%)

	% copied from 2018-01_cs473-algorithms.lectures.zip/prefix.tex
	\newcommand{\fcode}[1]
		{
			\smallskip
			\centerline{
				\fbox{
					\begin{minipage}{0.95\linewidth}
						\code{#1}
					\end{minipage}
				}
			}
			\smallskip
		}
	\newcommand{\innercode}[1]
		{
			\begin{tabbing}
				----\=----\=----\=----\=----\=----\=----\kill
				#1
			\end{tabbing}
		}
	\newcommand{\code}[1]
		{
			\footnotesize
			\tt
			\begin{center}
				\innercode{#1}
			\end{center}
		}

	\newcommand{\cH}{\mathcal{H}}
	\newcommand{\Z}{\mathbb{Z}}

\begin{document}

\renewcommand{\thecourse}{cs473 Algorithms}
\handout{0}%
	{}%
	{Prof.\ Michael A. Forbes}%
	{Due: \textit{Fri., 2026-04-10 17:00}}%
	{Problem Set \#7}

All problems are of equal value.

\begin{enumerate}

	\item (Multiplicative Chernoff Bound).  Let $\rX_1,\ldots,\rX_n$ be independent random variables taking values over the continuous real interval $[0,1]$, where we do not assume they are identically distributed.  Let $\rX = \sum_i \rX_i$.  Show the following.

		\begin{enumerate}
			\item For %[ 
				$r\in(-\infty,\ln 2]$%)
				, prove that $\E[\e^{r\rX}]\le \e^{r\E[\rX]+r^2\E[\rX]}$, where you may use (without proof) that $1+z\le \e^z$ for all $z\in \mathbb{R}$, and $\e^z\le 1+z+z^2$ for $z\le \ln 2$.
			\item Explain how the above used the independence of the $\rX_i$.
			\item Apply Markov's inequality ($\Pr[\rY\ge a]\le\nicefrac{\E[\rY]}{a}$) to $\e^{r\rX}$, and optimize over $r$, to conclude that:
				\begin{enumerate}
					\item For $0\le \epsilon\le \ln4$, $\Pr[\rX\ge (1+\epsilon)\E[\rX]]\le \e^{-\epsilon^2\E[\rX]/4}$.
					\item For $\epsilon\ge\ln4$, $\Pr[\rX\ge (1+\epsilon)\E[\rX]]\le 2^{-\epsilon\E[\rX]/2}$.
					\item For $0\le\epsilon\le 1$, $\Pr[\rX\le (1-\epsilon)\E[\rX]]\le \e^{-\epsilon^2\E[\rX]/4}$.
					\item (Additive Chernoff Bound) For $\epsilon\ge 0$, $\Pr[|\rX-\E[\rX]|\ge \epsilon \cdot n]\le 2\e^{-\epsilon^2 n/4}$.
				\end{enumerate}
			\item Suppose now you have $m$ independent identically random variables $\rY_1,\ldots,\rY_m$ over $\{0,1\}$, where each for each $\rY_i$, $\Pr[\rY_i=1]=\frac{\lg m}{m}$.  Define $\rY=\sum_i \rY_i$.  Bound the tail probability $\Pr[\rY\ge 2\E[\rY]]$, using both (i) and (iv) above, and compare these bounds.
		\end{enumerate}
		\emph{Note:} The above omits one range of parameters, where one can show that $\Pr[\rX\ge (1+\epsilon)\E[\rX]]\le \e^{-(1+\epsilon)\ln(1+\epsilon)\E[\rX]/4}$ if $\epsilon\ge 1$.

	\item  Balls and Bins.  Kleinberg-Tardos Chapter 13, Problem \#13.

	\item In lecture we saw the random contraction algorithm for computing a global min-cut for undirected (and unweighted) graphs.  In particular, we saw that if $C$ is a minimum cut then the probability one round of random contraction will output $C$ is $\ge \nicefrac{1}{\binom{n}{2}}$.  This problem will explore the ability of the algorithm to output \emph{almost} minimum cuts.

		Let $k\ge 1$ be an integer, and suppose $\hat{C}$ is a $k$-min-cut, in that $\hat{C}$ has value $|\hat{C}|\le k\min_C |C|$.  

		\begin{enumerate}
			\item Prove that after $n-2k$ randomly contracted edges, the probability the cut $\hat{C}$ has survived (that is, none of its edges have been contracted) is at least $\frac{1}{\binom{n}{2k}}$.

			\item Suppose we modify the algorithm, so that after the first $n-2k$ contractions, we output a random cut from the contracted graph.  Prove that $\hat{C}$ is output with probability $\ge \frac{1}{2^{2k}\binom{n}{2k}}$.

				\emph{Hint:} what is an upper bound for the number of cuts in the contracted graph?
			
			\item Conclude that there are at most $O(n^{2k})$ $k$-minimum cuts.
		\end{enumerate}

\end{enumerate}

\end{document}
