\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} % STUDENTS: % You can enter your solutions into this template by just % typing them right after it says "SOLUTION". % Ignore the \ifdefined\sol blocks; you can delete them if you want. % (Note that it won't compile if you try to uncomment the % solution flag :)) % \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{\eps}{\ensuremath{\epsilon}} \newcommand{\bE}{\ensuremath{\mathbb{E}}} \begin{document} \noindent \textbf{Problem Set 7 \ifdefined\sol Solution \fi} \hfill CS265/CME309, Winter 2025 \ifdefined\sol\else \newline Due: Friday 3/14, 11:59pm on Gradescope \ifdefined\template \newline Group members: INSERT NAMES HERE \fi %\today \vspace{.4cm}\noindent Please follow the homework policies on the course website. \fi \noindent \rule{\linewidth}{0.4pt} \begin{enumerate} % ---------- Empty bins ---------- \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 % ---------- Homework consensus ---------- \item \pts{11} \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 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 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}$. \item \pts{2} Assume that $G$ is connected. What is the probability that every member of the group eventually thinks that choice A is the correct answer? 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 \item \pts{0} \textbf{[This question is optional, in case you want more practice with the martingale stopping theorem.]} Recall that the Martingale Stopping Theorem states that for a martingale $\{Z_i\}$ with respect to $\{X_i\}$, if $T$ is a stopping time for $\{X_i\}$, then $\bE[Z_T]=\bE[Z_0]$ provided at least one of the following conditions hold: \begin{itemize} \item There exists a constant $c$ s.t. $|Z_i| \le c$ for all $i$. \item There exists a constant $c$ s.t. $T