\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 3}
\author{Alexandra Kolla}
\date{due November 24, 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 November 24th} - you can e-mail it by the due date or hand it in physically before the break. 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{Rumor Spreading}} (5 pts.)
Let $G = (V,E)$ be an arbitrary connected undirected graph with n vertices and m edges. Consider the following random process on $G$, which is a very simple model for the spread of rumors or infections. Initially, each vertex of G is colored either black or white (with no constraints). Then, at each step, all vertices simultaneously update their colors, independently of all other vertices, as follows:
\begin{itemize}
\item with probability $1/2$ do nothing.
\item else pick a neighboring vertex u.a.r. and adopt the color of that vertex
\end{itemize}
(Note that all vertices make these decisions before any vertex changes color.) It should be clear that this process will eventually terminate with all vertices black or all white, after which no further change is possible.
\begin{enumerate}
\item Let the random variable $X_t$ denote the sum of the degrees of all the white vertices at time $t$. Show that $X_t$ is a martingale with respect to the obvious sequence of random variables.
\item Use the optional stopping theorem to compute the probability that the process terminates in the all- white configuration, as a function of the initial configuration.
%\item Use the optional stopping theorem again to show that the expected duration of the process is at most $O(m^2)$ steps. [NOTE: Justify carefully any claims you make about the conditional variance of $X_t$.]
\end{enumerate}
\end{problem}
\begin{problem}{\it{Cover Times of Regular Graphs}} (5 pts.)
For this problem, you should use the connection between random walks and electrical networks established in the relevant lecture. You may also need to employ the Rayleigh monotonicity principle we discussed: When resistances increase, the effective resistance cannot go down, and conversely when they decrease, the effective resistances cannot go up. Note that contracting an edge corresponds to decreasing its resistance to zero and deleting an edge corresponds to increasing its resistance to infinity.
\begin{enumerate}
\item Let G be a regular graph on $n$ vertices (i.e. all the degrees are the same). Show that the cover time of G is at most $O(n^2 \log n)$.
\textbf{Bonus:} Show that the cover time of G is at most $O(n^2)$.
\item Now suppose that G is such that every vertex has degree strictly larger than $n/2$. Prove that the cover time is $O(n \log n)$. [Hint: Show that between every pair of vertices u, v, you can find $\Omega(n)$ short, edge-disjoint paths.]
\item Given an example of a regular graph with all vertex degrees at least $n/2 - O(1)$ whose cover time is $\Omega(n^2)$ (and prove it).
\end{enumerate}
\end{problem}
\begin{problem}{\it{Coupling}} (10 pts.)
\begin{enumerate}
\item Let $\mu$ and $\nu$ be two probability measures on a finite set $\Omega$. The total variation distance
between $\mu$ and $\nu$ is given by
$$d_{TV}(\mu,\nu)=\frac{1}{2}\sum_{\omega \in\Omega}|\mu(\omega)-\nu(\omega)|$$
A coupling of $\mu$ and $\nu$ is a pair of random variables $(X, Y)$ such that $X$ has law $\mu$ and Y has the law $\nu$. Prove that for any coupling $(X, Y)$ of $\mu$ and $\nu$, we have
$Pr[X\neq Y]\geq d_{TV}(\mu,\nu)$. Then prove that there exists a coupling $(X, Y)$ achieving this bound, i.e. such that $Pr[X\neq Y]=d_{TV}(\mu,\nu)$.
\item Suppose that we have a graph $G=(V, E)$ so that the corresponding Markov chain is
aperiodic and irreducible (for undirected graphs, this is equivalent to G being connected
and non-bipartite). Let $\pi(v)=\frac{deg(v)}{2|E|}$ denote the stationary distribution.
Let $p(x)$ be the distribution of the random walk started at $x$ after t steps, and define $$\Delta(t)=\max_{x\in V} d_{TV}(p_t^{x},\pi)$$
Also set $$D(t)=\max_{x,y\in V} d_{TV}(p_t^{x},p_t^{y})$$
Show that for every $t$, we have $\Delta(t)\leq D(t) \leq 2\Delta(t)$.
\item Now consider a pair of random processes $(\{X_t\}, \{Y_t\})$ that are coupled random walks on G in the following sense: $\{X_t\}$ and $\{Y_t\}$ both evolve marginally according to the distribution of the random walk. And if $X_t=Y_t$ then $X_{t+1}=Y_{t+1}$. Define the random variable $T_{xy}=\min\{t: X_t=Y_t |X_0= x,Y_0=y\}$. Show that $$\Delta(t)\leq \max_{x,y \in V}Pr[T_{xy}>t]$$
\item Recall the mixing time of the random walk is $\tau_{mix} =\min \{t:\Delta(t)\leq 1/2e\}$. Consider the random walk on the hypercube graph $\{0,1\}^n$ where every vertex has a self loop of weight $1/2$ (so with probability $1/2$ the walk stays in place and with probability $1/2$ goes to a random neighbor). This random walk in equivalent to the following: Suppose we are at vertex $x\in \{0,1\}^n$. At every step, choose a coordinate $i\in \{1,\cdots{},n\}$ uniformly at random and also choose a $b\in \{0,1\}$ uniformly and independently at random and set $x_i=b$. We can define a coupling $(\{X_t\},\{Y_t\})$ as in the previous part, by having $X_t$ and $Y_t$ make the same choice for $i$ and $b$ at every step. Use part (3) above to show that $\tau_{mix}=O(n\log n)$.
\end{enumerate}
\end{problem}
\end{document}