\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{\fact}[1]{\noindent{\textbf{FACT:} \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]}}
\usepackage{mathtools}
\newcommand{\bE}{\ensuremath{\mathbb{E}}}
\newcommand{\bR}{\ensuremath{\mathbb{R}}}
\newcommand{\cE}{\ensuremath{\mathcal{E}}}
\newcommand{\eps}{\ensuremath{\epsilon}}
\newcommand{\rank}{\ensuremath{\mathrm{rank}}}
\newtheorem{theorem}{Theorem}
\begin{document}
\noindent
\textbf{Problem Set 6 \ifdefined\sol Solution \fi} \hfill CS265, Fall 2020
\ifdefined\sol\else
\newline
Due: October 30 (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{[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]}{(\textrm{E}[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 \textrm{E}[X]] \geq (1-t)^2\frac{(\textrm{E}[X])^2}{\textrm{E}[X^2]}.
\end{align}
\hint{Write $X$ as $X \cdot \mathrm{1}_{\{X < t \cdot \textrm{E}[X]\}} + X \cdot \mathrm{1}_{\{X \geq t \cdot \textrm{E}[X]\}}$. Use linearity of expectation to compute $\textrm{E}[X]$ and use the Cauchy-Schwarz inequality to bound the term $\textrm{E}[X\cdot \mathrm{1}_{\{X \geq t \cdot \textrm{E}[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 \textrm{E}[X]] \leq \frac{\textrm{Var}[X] + (1-(1-t)^2)(\textrm{E}[X])^2}{\textrm{E}[X^2]} \leq \frac{\textrm{Var}[X]}{(\textrm{E}[X^2])} + (1-(1-t)^2).
\end{align}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/Paley-Zygmund.tex}
\fi
\end{shaded}
\fi
\item \pts{5} \textbf{[How far do we get in life by walking aimlessly?]}
Consider an $n$-step random walk on the integers. That is, let $S_n = X_1 + X_2 + ... + X_n$, where each $X_i$ is a uniformly random $\{+1,-1\}-$valued random variable and represents a random step either to the right or the left on the number line. Think of the walker as having started at the origin of the number line (i.e. $0$).
%
Thus, $S_n$ tracks the location of the walker after $n$ steps. We want to understand the typical behaviour of such a random walk: how far does this walk typically get from it's starting spot at $0$?
\begin{enumerate}
\item \pts{1} Show that there exist two constants $0 < c_u$ and $0 < p_u < 1$ such that \[\Pr[|S_n-0| \geq c_u\sqrt{n}] \leq p_u.\] That is, the probability that ``the distance of the random walk's location from its starting spot after $n$ steps grows faster than $\Theta(\sqrt{n})$'' is bounded away from 1.
\item \pts{4} Show that there exist two constants $0 < c_\ell$ and $0 < p_\ell < 1$ such that \[\Pr[|S_n-0| < c_\ell \sqrt{n}] \leq p_\ell.\] That is, the probability that ``the distance of the random walk's location from its starting spot after $n$ steps grows slower than $\Theta(\sqrt{n})$'' is bounded away from 1.
\hint{$|S_n-0| < c_\ell \sqrt{n}$ is equivalent to $S_n^2 < c_\ell^2 n$. We have learnt how to show the probability of non-negative random variables being too small is small in Question 1. You can use results from Question 1 even if you couldn't get it.}
\hint{Even though this question looks like it should be a Markov chain problem, remember that this week's HW is on Classes 11 and 12. (Next week's HW will cover Markov chains!)}
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/Random-walk.tex}
\fi
\end{shaded}
\fi
\item \pts{7} \textbf{[On the existence of good error correcting codes]}
Let $H(p) := p \log_2(\frac{1}{p}) + (1-p)\log_2(\frac{1}{1-p})$ for $0 \leq p \leq 1$ denote the binary entropy function\footnote{Let $0 \log_2 0 = 0$.}. Further define the Hamming distance between two binary strings $x,y \in \{0,1\}^n$ as the number of coordinates at which they differ $d(x,y) := \sum\limits_{i=1}^n \mathrm{1}_{x(i) \neq y(i)}$.
\fact{For $\delta \in (0,\frac{1}{2})$, the volume of a Hamming ball of radius $\delta n$ around any point $x \in \{0,1\}^n$ is $2^{nH(\delta) \pm o(n)}$. That is, \[|y \in \{0,1\}^n : d(x,y) \leq \delta n| = 2^{nH(\delta) \pm o(n)}.\]}
It is a major open question in the theory of \em error correcting codes \em whether, for all large enough $n$, there exists some constant $0 < \delta < 1/2$ and set $S \subseteq \{0,1\}^n$ so that
\begin{itemize}
\item $|S| \geq 2^{(1-H(\delta)+0.001)n}$ and
\item $\forall x,y \in S$, we have $d(x,y) > \delta n$.
\end{itemize}
(But you don't need to know anything about error correcting codes to do this problem).
\begin{enumerate}
\item \pts{2} Your friend has just learnt the LLL and they think they can show the existence of such a set. Their strategy is the following:
\begin{enumerate}
\item
Let $S \subseteq \{0,1\}^n$ be a random set where each $x \in \{0,1\}^n$ is included independently with probability $2^{-n(H(\delta)-0.001) + 1}$ (we choose $\delta$ with $H(\delta) > 0.001$ and assume that $n$ is sufficiently large so that the probability is less than 1). Then $\mathbb{E}|S| = 2^{(1-H(\delta)+0.001)n + 1}$, and by a Chernoff bound $|S|$ is at least $\mathbb{E}|S|/2 = 2^{(1-H(\delta)+0.001)n}$ with overwhelming probability.
\item
For any $x,y \in \{0,1\}^n$ such that $d(x,y) \leq \delta n$, let $A_{xy}$ denote the bad event that both $x$ and $y$ are contained in $S$. Clearly, $\Pr[A_{xy}] = 2^{-2n(H(\delta)-0.001) + 2}$. Then we can use the LLL to show that no bad events happen.
\item
$A_{xy}$ is only dependent with
\begin{itemize}
\item $A_{xz}$ for $z$ such that $d(x,z) \leq \delta n$.
\item $A_{zy}$ for $z$ such that $d(z,y) \leq \delta n$.
\end{itemize}
By the FACT, there are $2 \cdot 2^{n(H(\delta)\pm o(1))} = 2^{n(H(\delta)\pm o(1))}$ of these dependent events.
\item
Hence when we use the LLL, we can set ``$d$'' (the number of dependent events) to be $2^{n(H(\delta)\pm o(1))}$.
\item
We can apply the LLL whenever $4pd < 1$ which is equivalent to $4 \cdot 2^{-2n(H(\delta)-0.001) + 2} \cdot 2^{n(H(\delta)\pm o(1))} < 1$. This holds for many positive constants $\delta$, such as $\delta = 0.25$.
\end{enumerate}
Hence by the LLL your friend concludes that such a set $S$ exists.
As awesome as it would be if your friend had solved this problem, unfortunately there's a problem with the proof strategy above.
\textbf{What is the flaw in this reasoning?}
\item \pts{5} Use the LLL to show that for any constant $\delta \in (0,1/2)$ and for large enough $n$, there exists a set $S$ of size $|S| \geq 2^{n(1-H(\delta)-0.001)}$ so that $\forall x,y \in S$, we have $d(x,y) > \delta n$.
\hint{Choose a random multi-set $S \in \{0,1\}^n$ by choosing $2^{n(1-H(\delta)-0.001)}$ randomly, independently with replacement.}
\\ \hint{Try and justify that any set $S$ constructed via the previous hint that has the desired distance properties must also have the desired size property.}
\item \pts{0} [\textbf{Optional: This part will not be graded.}]
For any constant $\delta \in (0,1/2)$, let $S$ be a random subspace of $\{0,1\}^n$ of dimension $n(1-H(\delta)-0.001)$. Note that $|S| = 2^{n(1-H(\delta)-0.001)}$. Show that with probability at least $0.99$, the Hamming distance between any two distinct strings in $S$ is greater than $\delta n$.
Note that sampling a random subspace can be done computationally efficiently, which is why this is a more interesting result than the one from part (b).
\item \pts{0} [\textbf{Optional: This part will not be graded.}]
Your friend is pretty excited about part (b), since they claim that it means that the constructive LLL gives an efficient Las Vegas algorithm to find a set as in part (b). Your friend heard that it is also a major open problem to find such a set with a Las Vegas algorithm in expected time $\mathrm{poly}(n)$, and they are looking forward to winning the Shannon award for this. What is your friend missing? (They are correct that this is a major open problem).
\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/LLL.tex}
\fi
\end{shaded}
\fi
\end{enumerate}
\end{document}