\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}
\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{\clarification}[1]{\noindent{[\textbf{Clarification:} \em #1 \em]}}
\newcommand{\bE}{\ensuremath{\mathbb{E}}}
\begin{document}
\noindent
\textbf{Problem Set 8 \ifdefined\sol Solution \fi} \hfill CS265, Fall 2020
\ifdefined\sol\else
\newline
Due: November 20 (Friday) at 23:59 (Pacific Time)
\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}
\begin{enumerate}
\item \pts{4} \textbf{Random Walk on Hypercubes}
Consider a random walk on the $n$-dimensional hypercube (i.e.,\ the graph where the vertices are $\{0,1\}^n$, and $v,w \in \{0,1\}^n$ are connected by an edge if they differ in at most one place).
At each step of the random walk,
with probability $1/2$ the walk stays at the current vertex $v$, and with probability $1/2$, it chooses
a random index $i \in \{1,\ldots,n\}$ and flips the $i$-th coordinate of $v$. Prove that the mixing time of this random walk is $O(n \log n)$.
\hint{Use a coupling. When defining the coupling, it might be helpful to view the above random
walk as follows: pick a random index $i \in \{1,\ldots,n\}$, and a value $b\in \{0, 1\}$, and update the $i$-th coordinate to have value $b$.}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/walk.tex}
\fi
\end{shaded}
\fi
\item \pts{5} \textbf{Number of Empty Bins}
Suppose that we are in the standard setting of the balls-in-bins problem: we have $n$ balls and $m$ bins, and we independently allocate each ball to a bin chosen uniformly at random.
We assume $m$ and $n$ are positive integers, and we use random variable $Z$ to denote the number of empty bins after we allocate all the $n$ balls.
\begin{enumerate}
\item \pts{1} What is $\mathbb E[Z]$?
\item \pts{4} Show that $\Pr[|Z - \bE[Z]| \ge \varepsilon n] \leq 2e^{-\varepsilon^2 n/2}$ for any positive real number $\varepsilon$.
\hint{Try applying the Azuma-Hoeffding tail bound to a Doob martingale.}
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/empty.tex}
\fi
\end{shaded}
\fi
\item \pts{9} \textbf{Homework Solution Consensus}
Suppose that your homework group\footnote{For the purposes of making this question more interesting, pretend that your homework group has more than three people in it...} is working on a very difficult multiple choice question, where only one of the answers is correct.
It turns out that your opinion on which choice is correct differs from the opinions of many other members of the group. Fortunately, you have many friends in this group who are willing to listen to your opinion, and you are willing to listen to theirs as well. You want to talk with your friends hoping that all the group members will eventually agree on the same choice.
Formally, there is an undirected graph $G = (V,E)$ whose vertices represent the group members and a pair of members are friends if and only if they are connected by an edge. For simplicity, we assume that $G$ contains none of the following: 1) self-loops, 2) multiple edges connecting the same pair of vertices, or 3) isolated vertices, i.e., vertices with no edge on them. Let $S$ be the set of possible answers to the homework question (for example, $S = \{\mathrm{A,B,C,D}\}$). We can represent the opinions of the group members by a mapping $\sigma:V\rightarrow S$ where the group member corresponding to vertex $v$ thinks that $\sigma(v)$ is the correct answer.
The opinions $\sigma$ of the group members evolve due to discussions between friends.
We model the evolution of $\sigma$ by the following time-homogeneous Markov chain:
starting from the initial opinion $\sigma_0$, $\sigma$ changes from $\sigma_{t-1}$ to $\sigma_t$ at step $t$ as follows. Independently for every vertex $v$, we flip a fair coin. If the outcome is ``heads'', $\sigma_t(v)$ remains the same as $\sigma_{t-1}(v)$; otherwise, $\sigma_t(v)$ becomes $\sigma_{t-1}(v')$ for a uniformly random neighbor $v'$ of $v$.
In short, every group member keeps their own opinion with probability $1/2$, and takes one of their friends' opinion with the remaining $1/2$ probability.
In this problem, we will prove that the group members will eventually reach consensus almost surely assuming that $G$ is connected.
\begin{enumerate}
\item \pts{1} If $G$ is disconnected and $|S| > 1$, show that there exist initial opinions $\sigma_0$ of the members for which consensus is never reached.
\item \pts{3} If $G$ is connected, show that consensus is eventually reached almost surely. That is, show that as the number of steps goes to infinity, the probability that consensus has been reached approaches $1$.
\hint{Mimic the proof for the fact that random walks in one dimension eventually return to the starting point almost surely. (We saw this in Lecture 14.)
That is, bound the probability that consensus is not achieved within $\_\_\_\_$ steps from any state of the Markov chain $(\sigma_t)_{t\geq 0}$, where you have to fill in the blank.}
\item \pts{2} Let $X_t$ be the number of group members who think that choice A is the correct answer after step $t$. Give an example where $(X_t)_{t\geq 0}$ is \emph{not} a martingale with respect to $(\sigma_t)_{t \geq 0}$.
The example should be one specific tuple $(G, S, \sigma_0)$.
\item \pts{3} Let $Y_t$ be the sum of the degrees of the vertices $v$ corresponding to the group members who think that choice A is the correct answer after step $t$. Prove that $(Y_t)_{t\geq 0}$ is a martingale with respect to $(\sigma_t)_{t \geq 0}$.
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/consensus.tex}
\fi
\end{shaded}
\fi
\end{enumerate}
\end{document}