\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,mathtools}
\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 2023
\ifdefined\sol\else
\newline
Due: Friday December 8 at 11:59PM PST
\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{5} \textbf{Sampling \emph{Without} Replacement} 

Suppose there are $n$ total balls, of which $m$ are red. We sample $k$  of the balls uniformly \emph{without replacement}.\footnote{Note that this only makes sense when $k, m \leq n$.} Let $Z$ be the random variable denoting how many of the $k$ balls are red. In this problem, you will show that $Z$ is concentrated around its mean.
\begin{enumerate}
	\item \pts{1} Show that $\bE[Z] = \frac{km}{n}$.
	\item \pts{4} When $k \geq 1$, show that $\Pr[|Z - \bE[Z]| \ge \lambda] \leq 2e^{-\lambda^2/(2k)}$ for any $\lambda > 0$.

	\hint{Try applying the Azuma-Hoeffding tail bound to a Doob martingale. When applying Azuma-Hoeffding to a martingale $\{Z_t\}$, feel free to provide a short/intuitive explanation for why $|Z_i - Z_{i-1}| \leq c_i$ rather than a rigorous proof.}

	\item \textbf{[Optional: this won't be graded.]} When $k$ is close to $n$, a tighter bound than that from part (b) holds.
	\begin{enumerate}
		\item \pts{0} When $k = n$, explain why $\Pr[Z = \bE[Z]] = 1$.
		\item \pts{0} When $1 \leq k \leq n-1$, show that $\Pr[|Z - \bE[Z]| \ge \lambda] \leq 2e^{-\lambda^2/(2v)}$ where $v$ is defined as
		\begin{equation*}
			v \coloneqq \sum_{i = 1}^k \left(1 - \frac{k-i}{n-i}\right)^2.
		\end{equation*}
		%\textbf{Note:} if you do this part correctly, you can write ``follows from (c, ii) and $v \leq k$'' in part (b) get full credit for both parts.
		\item \pts{0} Show that $v \leq O(k(n-k)/n)$. This shows that the bound from part (c), ii is tighter than the bound from part (b) when $k$ is close to $n$.
	\end{enumerate}

	
\end{enumerate}




\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/replacement.tex}
\fi
\end{shaded}
\fi



\item \pts{11} \textbf{Reaching Consensus}


This question considers a simple and fairly natural model of the dynamic of how opinions shift over time in a group.

Suppose 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 ``opinions'' on some topic, and lets suppose that each person has one and only one opinion on the topic at a time.  (For concreteness, think of $S = \{A,B,C,...\}.$  ) We can represent the opinions of the group members by a mapping $\sigma:V\rightarrow S$ where the group member corresponding to vertex $v$ has opinion $\sigma(v)$.

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 determine the likelihood that the group members reach a certain consensus, given their initial opinions.
\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$.

\item \pts{2} Let $X_t$ be the number of group members who have some opinion, say $A \in S$ 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 with opinion A after step $t$. Prove that $(Y_t)_{t\geq 0}$ is a martingale with respect to $(\sigma_t)_{t \geq 0}$. 

\item \pts{2} Assume that $G$ is connected. What is the probability that all members of the group end up with opinion A (ie after some time, everyone has opinion, $A \in S$, for the rest of time)? Express your answer in terms of $G$ and the initial opinion $\sigma_0$ of the group members.

\hint{Try applying the martingale stopping theorem to the martingale $(Y_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}
