ps4/main.tex


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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}