\documentclass[11pt]{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}

\newtheorem{claim}{Claim}

\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{4cm}
\addtolength{\textwidth}{2cm}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\evensidemargin}{-1cm}

\newcommand{\E}{\mathbb{E}}
\renewcommand{\Pr}{\mathbb{P}}

\begin{document}

\noindent 
\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}lr}
{\large \textbf{18.434 Assignment 2}} & Due Friday 25 Feb\\
\end{tabular*}
\vspace{0.2cm}
\hrule
\vspace{0.3cm}

\noindent Name all your collaborators. You must write your own solutions. Assignments must be done in LaTeX. Hand in electronically as a .pdf file to \texttt{olver@math.mit.edu}, using your first name as the filename.

\medskip

\begin{enumerate}
	\item \emph{(Ex. 3.25).} The weak law of large numbers says that if $X_1, X_2, X_3, \ldots$ are iid random variables with mean $\mu$ and standard deviation $\sigma$, then for any $\epsilon > 0$, 
		\[ \lim_{n \rightarrow \infty} \Pr\left(\left|\frac{X_1 + X_2 + \cdots + X_n}{n} - \mu\right| > \epsilon\right) = 0. \]
		Prove this using Chebyshev's inequality.

	\item \emph{(Ex 4.13).} Let $X_1, X_2, \ldots, X_n$ be iid Bernoulli variables: $\Pr(X_i = 1) = p$ and $\Pr(X_i = 0) = 1-p$, for some $0 < p < 1$. 
		Let $X = \sum_{i=1}^n X_i$.

				Let 
				\[ F(t,p) = t\ln(t/p) + (1-t)\ln\left(\frac{1-t}{1-p}\right). \]
		\begin{enumerate}
			\item 
				Show that
				\[ \Pr(X \geq tn) \leq e^{-nF(t,p)}. \]
			\item Show that for $0 < x, p < 1$, we have
				\[ F(t,p) \geq 2(t-p)^2. \]
				\emph{(Probably some calculus - the second derivative is even useful.)}
			\item Hence show
				\[ \Pr(X \geq (p + \epsilon)n ) \leq e^{-2n\epsilon^2}. \]
		\end{enumerate}

	\item Consider the following randomized algorithm for min-cut. Suppose we have a graph $G=(V,E)$ with $n$ vertices.
		We randomly contract edges as usual, but stop before getting down to just $2$ nodes, at some smaller graph $G'$. 
		We then run a deterministic algorithm that always finds a min cut of $G'$.
		Such algorithms exist that take cubic time (cubic in the number of vertices).

		Show that with this approach, we can get an algorithm that runs in time $O(n^{8/3})$, and returns a minimum cut with constant probability.

		\emph{(This is simpler than the tree thing we did in class, where instead of running a deterministic algorithm, we recursively call the contraction algorithm multiple times. But this exercise shows that even this simpler approach yields an improvement over the cubic deterministic runtime.)}

\end{enumerate}
\end{document}