\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}}
\newcommand{\Ex}[1]{\operatorname*{\mathbb{E}}\left[#1\right]}
\definecolor{shadecolor}{gray}{0.95}


\begin{document}
\noindent
\textbf{Problem Set 5 \ifdefined\sol Solution \fi} \hfill CS265/CME309, Winter 2025
\ifdefined\sol\else
\newline
Due: Friday 2/28, 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}

%%%%%%%%%%%%%%%%%%%%%% Furthering the second moment method %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item \pts{4} \textbf{[Furthering the second moment method]}

In class, we saw the second moment method to show that a random variable with large expectation and small variance must be non-zero with good probability. Formally, we saw that for a non-negative random variable $X$, 
\begin{align}
\label{eqn1}
\Pr[X = 0] \leq \frac{\textrm{Var}[X]}{(\Ex{X})^2}.
\end{align}
While this is often very useful, it does not let us reason about the probability of $X$ being something small but non-zero. In this question, you will prove a similar inequality that \textbf{does} let us do such a thing. 

\textbf{Prove} that for a non-negative random variable $X$ and any $0 < t < 1$,
\begin{align}
\label{eqn2}
\Pr[X \geq t \cdot \Ex{X}] \geq (1-t)^2\frac{(\Ex{X})^2}{\Ex{X^2}}.
\end{align}

\hint{Write $X$ as $X \cdot \mathrm{1}_{\{X < t \cdot \Ex{X}\}} + X \cdot \mathrm{1}_{\{X \geq t \cdot \Ex{X}\}}$. Use linearity of expectation to compute $\Ex{X}$ and use the Cauchy-Schwarz inequality to bound the term $\Ex{X\cdot \mathrm{1}_{\{X \geq t  \cdot \Ex{X}\}}}$.}

\textbf{Note:} By simple rearrangements of \eqref{eqn2}, one can observe\footnote{There is no question you need to answer about this rearrangement. Simply observe this and try to understand how it compares to the inequality (\ref{eqn1}) from class.} that
\begin{align}
\label{eqn3}
\Pr[X < t \cdot \Ex{X}] \leq \frac{\textrm{Var}[X] + (1-(1-t)^2)(\Ex{X})^2}{\Ex{X^2}} \leq \frac{\textrm{Var}[X]}{(\Ex{X^2})} +  (1-(1-t)^2).
\end{align}

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


%%%%%%%%%%%%%%%%%%%%%% Echoing paths %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item \pts{6} \textbf{[Echoing paths]}

\definecolor{colorC}{HTML}{648FFF}
\definecolor{colorA}{HTML}{DC267F}
\definecolor{colorB}{HTML}{FFB000}

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1]
\draw[line width=0.6mm,color=colorC] (2, 4) -- (3, 2);
\node at (2.7,3.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorC] (2, 0) -- (3, 2);
\node at (2.3,1.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorC] (5, 2) -- (6, 4);
\node at (5.3,3.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorA] (0, 4) -- (1, 2);
\node at (0.7,3.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorA] (4, 4) -- (3, 2);
\node at (3.3,3.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorA] (6, 0) -- (5, 2);
\node at (5.7,1.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorB] (1, 2) -- (2, 4);
\node at (1.3,3.1) {\textcolor{colorB}{$b$}};
\draw[line width=0.6mm,color=colorB] (5, 2) -- (4, 4);
\node at (4.7,3.1) {\textcolor{colorB}{$b$}};
\draw[line width=0.6mm,color=colorB] (7, 2) -- (6, 0);
\node at (6.3,1.1) {\textcolor{colorB}{$b$}};
\draw[fill=black] (2, 0) circle (2pt);
\node at (2,-0.3) {$v_4$};
\draw[fill=black] (6, 0) circle (2pt);
\draw[fill=black] (1, 2) circle (2pt);
\draw[fill=black] (3, 2) circle (2pt);
\node at (3.3,1.7) {$v_5$};
\draw[fill=black] (5, 2) circle (2pt);
\draw[fill=black] (7, 2) circle (2pt);
\node at (7,2.3) {$v_6$};
\draw[fill=black] (0, 4) circle (2pt);
\node at (0,4.3) {$v_1$};
\draw[fill=black] (2, 4) circle (2pt);
\node at (2,4.3) {$v_3$};
\draw[fill=black] (4, 4) circle (2pt);
\draw[fill=black] (6, 4) circle (2pt);
\node at (6,4.3) {$v_2$};
\end{tikzpicture}
\caption{An edge coloring of a graph with some echoing paths.}
\label{fig:graph}
\end{figure}

An \emph{edge coloring} of an (undirected) graph $G=(V,E)$ assigns exactly one color to each edge of the graph.  We say that a colored path in the graph is \emph{echoing} if the path has an even number of edges, and the second half of the path is colored identically to the first half of the path (i.e. the sequence of colors in the second half of the path is the same sequence as in the first half). For example, in Figure~\ref{fig:graph}, the paths from $v_1$ and $v_2$, from $v_3$ to $v_4$, and from $v_5$ to $v_6$ are all echoing paths. Edges are colored and labeled $a, b,$ or $c$ corresponding to their color.

Throughout this problem, by ``path'' we refer only to simple paths---i.e. paths that do not re-use any edges.


\begin{enumerate}
\item \pts{4} Prove that for any graph whose maximum degree is $d$, there exists a coloring using $10 \cdot d^2$ colors such that there are no echoing paths of length $4$ (i.e. no echoing paths consisting of 4 distinct edges, like the path from $v_5$ to $v_6$ in Figure~\ref{fig:graph}). 

\hint{Use the Lovasz Local Lemma.}

 \item \pts{2} Given the setup in the previous part, give an algorithm that will find such a coloring in expected time polynomial in the size of the graph, and justify the runtime.  
\item \pts{0} \textbf{[This problem is optional.]}  Prove that there is some constant $C$ such that for any graph whose maximum degree is $d$, there exists a coloring using $C \cdot d^2$ colors such that there are no echoing paths (of any length).
\end{enumerate}


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


%%%%%%%%%%%%%%%%%%%%%% Near-Markov random walks
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item \pts{6} \textbf{[Near-Markov random walks]}

Let $G$ be a $d$-regular graph with $n$ vertices. Suppose each vertex $v$ has an assigned label $\ell(v)$ of either 0 or 1. Beginning at a fixed vertex $v_0$, perform a random walk $v_0, v_1, v_2, \ldots$, where $v_{t+1}$ is chosen uniformly at random from the $d$ neighbors of $v_t$. We say a random walk $v_0, v_1, v_2, \ldots$ is $\epsilon$-\textbf{Markov} if for all $t \geq 0$, \[\left|\Ex{\ell(v_t) \mid \ell(v_{t-1}), \ell(v_{t-2}), \ldots, \ell(v_0)} - \frac{1}{2}\right| \leq \epsilon.\] 

\begin{enumerate}
\item \pts{4} Let $\epsilon >0$ be fixed. Show that there is some lower bound $d_\epsilon$ such that if $d \geq d_\epsilon$, there exists a labeling for the $n$ vertices such that a random walk beginning at any vertex satisfies the $\epsilon$-Markov property. You do not need to calculate the value of $d_\epsilon$ explicitly, but rather simply show that such a $d_\epsilon$ exists.

\hint{Use the Lovasz Local Lemma. For every vertex $v$, consider the event $A_v$ given by $|P_v - \frac{1}{2}| > \epsilon$, where $P_v$ is the probability that after taking one step starting from $v$ during the walk, we visit a vertex with the label $1$.}

 \item \pts{2} Give an algorithm that will construct such a labeling in time polynomial in $n$ and $d$.
\end{enumerate}


\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/near-Markov-random-walks}
\fi
\end{shaded}
\fi


\end{enumerate}
\end{document}