\documentclass[12pt]{article}
%AMS-TeX packages
\usepackage{amssymb,amsmath,amsthm}
%geometry (sets margin) and other useful packages
\usepackage[margin=1.25in]{geometry}
\usepackage{graphicx,ctable,booktabs}
%
%Redefining sections as problems
%
\makeatletter
\newenvironment{problem}{\@startsection
{section}
{1}
{-.2em}
{-3.5ex plus -1ex minus -.2ex}
{2.3ex plus .2ex}
{\pagebreak[3]%forces pagebreak when space is small; use \eject for better results
\large\bf\noindent{Problem }
}
}
\makeatother
%
%Fancy-header package to modify header/page numbering
%
\usepackage{fancyhdr}
\pagestyle{fancy}
%\addtolength{\headwidth}{\marginparsep} %these change header-rule width
%\addtolength{\headwidth}{\marginparwidth}
\lhead{ }
\chead{}
\rhead{\thepage}
\lfoot{\small\scshape Randomized Algorithms}
\cfoot{}
\rfoot{\footnotesize CS 574}
\renewcommand{\headrulewidth}{.3pt}
\renewcommand{\footrulewidth}{.3pt}
\setlength\voffset{-0.25in}
\setlength\textheight{648pt}
\newtheorem{lemma}{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Contents of problem set
%
\begin{document}
\title{CS 574. Randomized Algorithms\\ Problem Set 2}
\author{Alexandra Kolla}
\date{due October 20, 2015}
\maketitle
\thispagestyle{empty}
%Example problems
\noindent {\bf Collaboration Policy:} The homework can be worked in
groups of up to 3 students each (2 would be optimal, but 1 and 3 are both accepted).%
\vspace{0.3cm}%
\noindent {\bf One} submission per team is sufficient. Please write the solution for each of the
problems on a separate sheet of paper. Write your team names and netids on
each submission and please \textbf{staple} all the sheets together.
\vspace{0.3cm}%
\noindent {\bf Extra} 5\% for typed homeworks (preferably pdf).
\vspace{0.3cm}%
\noindent {\bf Homework is due} on or before the end of class, October 20. Only one late homework per person will be allowed. If you submit more than one homework late, you will get no grade for the excess late homeworks.
\vspace{0.5cm}%
\begin{problem}{\it{Independence Matters}} (5 pts.)
Consider a function $f(x_1, ...,x_n)$ which is 1-Lipschitz. Let $X_1, ..., X_n$ be random variables, all falling in the range $[0, 1]$. By definition, we know that for
$Y_i = E[f(X_1,...,X_n)|X_1,...,X_i]$ the sequence $\{Y_i\}$ is a martingale.
Show that if $X_1,...,X_n$ are not independent then it is no longer (always) true that the $Y_n - Y_0$ is concentrated. That is, you need to give a specific example where Azuma's inequality would break in such a case. Recall that in class we showed that if they are independent then $|Y_{i+1}-Y_i|<1$, thus Azuma's inequality applies.
\end{problem}
\begin{problem}{\it{Is Markov's and Chenrnoff's Inequality Tight?}} (10 pts.)
\begin{enumerate}
\item For an integer $k$, define a non-negative random variable $X_k$, such that $E[X_k] = 1$, and $Pr[X_k \geq k] = 1/k$. Namely, Markov's inequality can be tight for any k.
\item Consider a positive integral random variable $X$ with $ \Delta = E[X]<\infty$. Furthermore, for any number $x$, there exists an integer $ y (x)> x$, such that we have $Pr[X\geq x\Delta] \geq Pr[X \geq y\Delta] \geq c/y$, where $c>0$ is some arbitrary constant. Prove, that no such random variable X exists.
\item Let $X_1,...,X_n$ be independent random variables taking values from $\{-1,1\}$ with equal probability. Let $X=\sum X_i$. Let $P(n,\Delta)=Pr[X> \Delta]$. Prove that for $\Delta\leq n/C$ we have $P(n,\Delta)\geq \frac{1}{C}e^{-\frac{\Delta^2}{Cn}}$, where $C$ is a suitable constant. Namely, Chernoff's bound $P(n,\Delta)\leq e^{-\frac{\Delta^2}{2n}}$ is almost tight. [Hint: Use Stirling's Formula]
\end{enumerate}
\end{problem}
\begin{problem}{\it{Disjoint Cycles}}(5 pts)
Let G be an arbitrary $k$-regular directed graph (i.e., every vertex has in and out degree k). In this problem, we will show, using the Lov'asz Local Lemma (LLL), that G contains at least $\lfloor\frac{k}{3\ln k}\rfloor$ vertex-disjoint cycles.
\begin{enumerate}
\item Suppose the vertices of G are partitioned into $c=\lfloor\frac{k}{3\ln k}\rfloor$ components by assigning each vertex to a
component chosen independently and u.a.r. For each vertex $v$, let $A_v$ be the event that $v$ has no edge
to another vertex in its component. Show that $Pr[A_v] \leq k^{-3}$.
\item Let $D_v$ denote the ``dependency set'' of event $A_v$ (i.e., $A_v$ is independent of all events $A_u$ except for
those in $D_v$). Show that $|D_v| \leq (k + 1)^2$.
\item Deduce from parts (1) and (2) and the LLL that G contains at least c vertex-disjoint cycles.
\end{enumerate}
\end{problem}
\end{document}