[ps4] first problem

1 files changed, 72 insertions, 0 deletions

diff --git a/ps4/main.tex b/ps4/main.tex
new file mode 100644
index 0000000..7799f32
--- /dev/null
+++ b/ps4/main.tex
@@ -0,0 +1,72 @@
+\documentclass[10pt]{article}
+\usepackage{fullpage}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,amsfonts,amsthm}
+\usepackage[english]{babel}
+\usepackage[capitalize, noabbrev]{cleveref}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+
+\newenvironment{enumerate*}%
+  {\vspace{-2ex} \begin{enumerate} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{enumerate}}
+ 
+\newenvironment{itemize*}%
+  {\vspace{-2ex} \begin{itemize} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{itemize}}
+ 
+\newenvironment{description*}%
+  {\vspace{-2ex} \begin{description} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{description}}
+
+
+\DeclareMathOperator{\E}{\mathbb{E}}
+\let\P\relax
+\DeclareMathOperator{\P}{\mathbb{P}}
+\DeclareMathOperator*{\argmin}{\arg\min}
+\newcommand{\ex}[1]{\E\left[#1\right]}
+\newcommand{\prob}[1]{\P\left[#1\right]}
+\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
+\newcommand{\R}{\mathbf{R}}
+\newcommand{\poly}{\text{poly}}
+\newcommand{\N}{\mathbf{N}}
+\newcommand{\C}{\mathcal{C}}
+\newcommand{\eps}{\varepsilon}
+\newcommand{\cl}[1]{\text{\textbf{#1}}}
+\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+\newcommand{\llbracket}{[\![}
+
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{lemma}{Lemma}
+\algrenewcommand\algorithmicensure{\textbf{Output:}}
+\algrenewcommand\algorithmicrequire{\textbf{Input:}}
+
+\author{Thibaut Horel}
+\title{CS 225 Problem Set 4 -- Solutions}
+
+\begin{document}
+\maketitle
+
+\section*{Problem 5.1} I use a simple counting argument. If $\mathcal{C}$ is
+$(\delta, L)$ list-decodable, then for all $r\in \Sigma^{\hat{n}}$ we have
+$|B(r,\delta)\cap \mathcal{C}|\leq L$. Hence:
+\begin{displaymath}
+    \sum_{r\in \Sigma^{\hat{n}}} |B(r,\delta)\cap\mathcal{C}|\leq Lq^{\hat{n}}
+\end{displaymath}
+Furthermore, each code-word $c$ of $\mathcal{C}$ is counted several times in
+the sum: once for each $r\in B(c,\delta)$. But $B(c,\delta)$ is of size
+$q^{\hat{n}H_q(\delta, \hat{n})}$. So each $c\in\mathcal{C}$ appears at most 
+$q^{\hat{n}H_q(\delta, \hat{n})}$ times in the sum:
+\begin{displaymath}
+    |\mathcal{C}|q^{\hat{n}H_q(\delta, \hat{n})}\leq 
+    \sum_{r\in \Sigma^{\hat{n}}} |B(r,\delta)\cap\mathcal{C}|
+\end{displaymath}
+Putting the previous two equations together:
+$ |\mathcal{C}|q^{\hat{n}H_q(\delta, \hat{n})} \leq Lq^{\hat{n}}$. Taking the
+$\log$ both sides and reordering the terms (and using $\rho = \frac{\log
+|\mathcal{C}|}{\hat{n}\log q}$) concludes the proof.
+\end{document}