notes.tex

\documentclass[twoside]{article}
% General document formatting
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{mathrsfs}
\usepackage[nameinlink]{cleveref}
\usepackage{xcolor}
\usepackage[toc,page]{appendix}
\usepackage[]{algorithm2e}

\title{Information Theory and Coding - Prof.~Telatar}
\date{\today}
\author{Jean-Baptiste Cordonnier, Sebastien Speierer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{claim}{Claim}[section]
\newtheorem{fact}{Fact}[section]
\newtheorem{consequence}{Consequence}[section]
\newtheorem{observation}{Observation}[section]
\newtheorem*{wikipedia}{Wikipedia}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}{Definition}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{notation}{Notation}
\theoremstyle{definition} % Attention side effects lololol~
\newtheorem{example}{Example}

\newcommand{\todo}[1]{\textcolor{red}{TODO: #1}}
\renewcommand{\Pr}[1]{Pr\left\{#1\right\}}
\newcommand{\Ex}[1]{\mathbb{E}\left[#1\right]}
\newcommand{\pfrac}[2]{\left( \frac{#1}{#2} \right)}
\newcommand{\overeq}[1]{\stackrel{#1}{=}}

% math bold
\def\*#1{\mathbf{#1}}
% manuscript characters
\def\D{\mathcal{D}}
\def\V{\mathcal{V}}
\def\L{\mathcal{L}}
\def\U{\mathcal{U}}
\def\N{\mathcal{N}}
\def\X{\mathcal{X}}
\def\Y{\mathcal{Y}}
\def\R{\mathbb{R}}
\def\F{\mathbb{F}}
\def\I{\mathbb{I}}


\def\C{\mathcal{C}}
\DeclareMathOperator{\E}{\mathbb{E}}% expected value


\begin{document}

\maketitle
\setcounter{tocdepth}{1}
\tableofcontents

\cleardoublepage

\section{Data compression}

\begin{definition}[Information]
  Abstractly, \textbf{information} can be thought of as the resolution of uncertainty.
\end{definition}

Given an alphabet $\U$ (e.g. $\U = \{a, ..., z, A, ..., Z, ...\}$), we want to assign binary sequences to elements of $\U$, i.e.

\begin{align*}
	\C: \U \rightarrow \{0, 1\}^* = \{\emptyset, 0, 1, 00, 01, ...\}
\end{align*}

For $\X$ a set

\begin{align*}
	\X^n &\equiv \{ (x_0 ... x_n), x_i \in \X\} \\
	\X^* &\equiv \bigcup_{n \geq 0} \X^n
\end{align*}

\begin{definition}
	A code $\C$ is called \textbf{singular} if
	\begin{align*}
		\exists (u, v) \in \U^2, u \neq v \quad s.t. \quad \C(u) = \C(v)
	\end{align*}
	Non singular code is defined as opposite
\end{definition}

\begin{definition}
	A code $\C$ is called \textbf{uniquely decodable} if
	\begin{align*}
		\forall u_1,...,u_n,v_1,...,v_n \in \U^* \quad s.t. \quad u_1,...,u_n \neq v_1,...,v_n
	\end{align*}
	we have
	\begin{align*}
		\C(u_1)...\C(u_n) \neq \C(v_1)...\C(v_n)
	\end{align*}
	i.e, $\C$ is non-singular
\end{definition}

\begin{definition}
	Suppose $\C : \U \rightarrow \{ 0, 1\}^*$ and $\D : \V \rightarrow \{ 0, 1\}^*$ we can define

	\begin{align*}
		\C \times \D : \U \times \V \rightarrow \{0, 1\}^*
		\quad \text{ as } \quad
		(\C \times \D)(u, v) \rightarrow \C(u)\D(v)
	\end{align*}
\end{definition}

\begin{definition}
	Given $\C : \U \rightarrow \{ 0, 1\}^*$, define
	\begin{align*}
		\C^* : \U^* \rightarrow \{0, 1\}^*
		\quad \text{ as } \quad
		\C^*(u_1 ... u_n) = \C(u_1)...\C(u_n)
	\end{align*}
\end{definition}

\begin{definition}
	A code $\U \rightarrow \{0, 1\}^*$ is \textbf{prefix-free} is for no $u \neq v$ $\C(u)$ is a prefix of $\C(v)$.
\end{definition}

\begin{theorem}
	If $\C$ is prefix-free then $\C$ is uniquely decodable.
\end{theorem}

\begin{definition}
  $l(\C(u))$ is the length of the code word $\C(u)$ and $l(\C)$ is the expected length of the code:
  \begin{align*}
    l(\C) = \sum_u l(\C(u)) p(u)
  \end{align*}
\end{definition}

\begin{definition}[Kraft sum]
  Given $\C : \U \rightarrow \{ 0, 1\}^*$
	\begin{align*}
		kraftsum(\C) = \sum_u 2^{-l(\C(u))}
	\end{align*}
\end{definition}

\begin{lemma}
	if $\C : \U \rightarrow \{ 0, 1\}^*$ and $\D : \V \rightarrow \{ 0, 1\}^*$
	then
  $$kraftsum(\C \times \D) = kraftsum(\C) \times kraftsum(\D)$$
	\begin{proof}
    \begin{align*}
      kraftsum(\C \times \D) &= \sum_{u, v} 2^{-(l(\C) * l(\D))} \\
      &= \sum_u 2^{-l(\C)} \sum_v 2^{- l(\D)}
    \end{align*}
	\end{proof}
\end{lemma}

\begin{corollary}
  $kraftsum(\C^n) = (kraftsum(\C))^n$
\end{corollary}

\begin{proposition}
  if $\C$ is non-singular, then
  \begin{align*}
    kraftsum(\C) \leq 1 + \max_u l(\C(u))
  \end{align*}
\end{proposition}

In coding theory, the \textbf{Kraft-McMillan inequality} gives a necessary and sifficient condition for the existence of a uniquely decodable code for a given set of codeword lengths.

\begin{wikipedia}
  Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.
\end{wikipedia}

\begin{theorem}
  if $\C$ is uniquely decodable, then $kraftsum(\C) \leq 1$
\end{theorem}

\begin{proof}
  $\C$ is uniquely decodable $\equiv$ $\C^*$ is non singular
  \begin{align*}
    &\Rightarrow kraftsum(\C^n) \leq 1 + \max _{u_1, ..., u_n} l(\C^n) \\
    &\Rightarrow kraftsum(\C)^n \leq 1 + n L, \quad L = \max l(\C(n))
  \end{align*}
  A growing exp cannot be bounded by a linear function
  \begin{align*}
    \Rightarrow kraftsum(\C) \leq 1
  \end{align*}
\end{proof}

\begin{theorem}
  Suppose $\C : \U \rightarrow \N$ is such that $\sum_u 2^{-l(\C(u))} \leq 1$, then, there exists a prefix-free code $\C': \U \rightarrow \{0, 1\}$ s.t. $\forall u, l(\C'(u)) = l(\C(u))$
\end{theorem}

\begin{proof}
  Let $\U = \{u_1, ..., u_n\}$ and $\C(u_1) \leq \C(u_2) \leq ... \leq \C(u_k) = \C_{max}$.
  Consider the complete binary tree up to depth $\C_{max}$ initially all nodes are available to be used as codewords.
  For $i = 1, 2, ..., n$, place $\C(u_i)$ at an available node at level $\C(u_i)$ remove all descendant of $\C(u_i)$ from the available list.

  \begin{corollary}
    Suppose $\C: \U \rightarrow \{0, 1\}^*$ is uniquely decodable, then there exist an $\C': \U \rightarrow \{0, 1\}^*$ which is prefix-free and $l(\C'(n)) = l(\C(n))$
  \end{corollary}
\end{proof}

\begin{example}
  $\U = \{a, b, c, d\}$, $\C: \{0, 01, 011, 111\}$ and $\C': \{0, 10, 110, 111\}$\\
  In this case, decoding $\C$ may require delay, while decoding $\C'$ is instanteneous.
\end{example}

% -------------------------------------------------------------

\cleardoublepage
\section{Alphabet with statistics}

Suppose we have an alphabet $\U$, and suppose we have a random variable $U$ taking values in $\U$. We denote by $p(u) = Pr(U = u), u \in \U$ with $p(u) \geq 0$ and $\sum_u p(u) = 1$.\\

Suppose we have a code $\C: \U \rightarrow \{0, 1\}^*$. We then have $\C(u)$ a random binary string and $l(\C(u))$ a random integer.

\begin{example}
  $\U = \{a, b, c, d\}$\\
  $p: \{0.5, 0.25, 0.125, 0.125\}$ \\
  $\C: \{0, 01, 110, 111\}$ \\

  then we have
  \begin{align*}
    l(\C(u)) =
    \left\{
      \begin{array}{l}
        1, \quad p = 0.5 \\
        2, \quad p = 0.25 \\
        3, \quad p = 0.125 + 0.125 = 0.25
      \end{array}
    \right.
  \end{align*}
\end{example}

We can measure how efficient $\C$ represents $\U$ by considering
\begin{align*}
  E[l(\C(u))] = \sum_u p(u)l(\C(u)) \quad \text{with} \quad \C(u) = l(\C(u))
\end{align*}

\begin{theorem}
  if $\C$ is uniquely decodable, then
  \begin{align*}
    E[l(\C(u))] \geq \sum_u p(u) \log \frac{1}{p(u)}
  \end{align*}
\end{theorem}

\begin{proof}
  let $\C(u) = l(\C(u))$, we know $\sum_u 2^{-\C(u)} \leq 1$ because $\C$ is uniquely decodable. We write $q(u)~=~2^{-\C(u)}$ and get

  \begin{align*}
    E[l(\C(u))] &= \sum_u p(u) \C(u) = \sum_u p(u) \log_2\frac{1}{q(u)} \\
    &\equiv \sum_u p(u) \log\frac{q(u)}{p(u)} \leq 0 \\
    &\equiv \sum_u p(u) \ln\frac{q(u)}{p(u)} \leq 0 \\
    &\leq \sum_u p(u) \left[\frac{q(u)}{p(u)} - 1\right]
    = \underbrace{\sum_u q(u)}_{\leq 1} - \underbrace{\sum_u p(u)}_{=1} \leq 0
  \end{align*}
\end{proof}

\begin{theorem}
  For any $\U$, there exists a prefix-free code $\C$ s.t.
  \begin{align*}
    E[l(\C(u))] < 1 + \sum_{u \in \U} p(u) \log\frac{1}{p(u)}
  \end{align*}
\end{theorem}
\begin{proof}
  Given $\U$, let
  \begin{align*}
    &\C(u) = \lceil \log\frac{1}{p(u)} \rceil < 1 + \log \frac{1}{p(u)} \\
    &\Rightarrow \sum_u 2^{-\C(u)} \leq \sum_u p(u) = 1 \\
    &\Rightarrow \sum_u p(u) \C(u) < \sum_u p(u) \log \frac{1}{p(u)} + \underbrace{1}_{\sum p(u)}
  \end{align*}
\end{proof}

\begin{definition}[Entropy]
  Entropy quantifies the amount of uncertainty involved in the value of a random variable or the outcome of a random process.
\end{definition}

\begin{theorem}
  The entropy of a random variable $U \in \U$ is
  \begin{align*}
    H(U) = \sum_{u \in \U} p(u) \log \frac{1}{p(u)}
  \end{align*}
  with $p(u) = Pr(U = u)$
\end{theorem}

\begin{wikipedia}
  The entropy is a lower bound on the optimal expected length
  \begin{align*}
    H(U) \leq E[l(\C(u))]
  \end{align*}
  In fact, one can show that there exists a uniquely decodable code such that
  \begin{align*}
     H(U) \leq E[l(\C(u))] < H(U) + 1
   \end{align*}
\end{wikipedia}

Note that $H(U)$ is a fonction of the distribution $\C_u(.)$ of the random variable $U$, it isn't a function of $U$.

\begin{align*}
  H(U) = E[f(U)] \quad \text{where} \quad f(U) = \log \frac{1}{p(u)}
\end{align*}

How to design optimal codes (in the sense of minimizing $E[l(\C(u))]$)? \\
Formally, given a random variable $U$, find $\C(u) \rightarrow \N$ s.t.
\begin{align*}
  \sum_{u \in U} 2^{\C(u)} \leq 1
\quad \text{that minimizes} \quad
  \sum_{u \in U} p(u)l(\C(u))
\end{align*}

Properties of optimal prefix-free codes
\begin{itemize}
  \item if $p(u) < p(v)$ then $l(\C(u)) \geq l(\C(v))$
  \item The two longest codewords have the same length
  \item There is an optimal code such that the two least probable letters are assigned codewords that differ in the last bit.
\end{itemize}

Observe that if $\{\C(u_1), ... , \C(u_{k-1}), \C(u_k)\}$ is a prefix-free collection of the property that
\begin{align*}
\left.
\begin{array}{l l}
  \C(u_{k-1}) &= \alpha 0 \\
  \C(u_k)     &= \alpha 1
\end{array}
\right.
\quad \text{with} \quad \alpha \in \{ 0, 1\}^*
\end{align*}

then $\{\C(u_1), ..., \C(u_{k-2}), \alpha\}$ is also a prefix-free collection.

Also
\begin{align*}
  \sum_{u \in \U} p(u) l(\C(u)) &= p(u_1) l(\C(u_1)) + ... +  p(u_{k-2}) l(\C(u_{k-2}))
  + [p(u_{k-1}) + p(u_k)](l(\alpha) + 1) \\
  &= (p(u_{k-1}) + p(u_k)) + \sum_{v \in \V} p(v) l(\C'(v))
\end{align*}

So we have shown that with
\begin{align*}
  E[l(\C(U)] = p(u_{k-1}) + p(u_k) + E[l(\C'(V))]
\end{align*}
if $\C$ is optimal for $U$, then $\C'$ is optimal for $V$

% -------------------------------------------------------------

\cleardoublepage
\section{Entropy and mutual information}
\label{sec:entropy}

\begin{definition}[Joint entropy]
  Suppose $U, V$ are random variables with $p(u,v) = \Pr{U=u, V=v}$, the joint entropy is
  \[
    H(UV) = \sum_{u,v} p(u,v) \log \frac 1 {p(u,v)}
  \]
\end{definition}

\begin{theorem}
  \[
    H(UV) \leq H(U) + H(V)
  \]
  with equality iff $U$ and $V$ are independants.
\end{theorem}

\begin{proof}
  We want to show that
  \begin{align*}
    \sum_{u,v} p(u,v) \log \frac 1 {p(u,v)} \leq \sum_u p(u) \log \frac 1 {p(u)} + \sum_v p(v) \log \frac 1 {p(v)}
    \iff \sum_{u,v} p(u,v) \log \frac {p(u)p(v)} {p(u,v)} \leq 0
  \end{align*}
  We use $\ln z \leq z - 1$ for all $z$ (with equality iff $z=1$):
  \begin{align*}
    \sum_{u,v} p(u,v) \log \frac {p(u)p(v)} {p(u,v)} \leq \sum_{u,v} p(u,v) \left[ \frac {p(u)p(v)} {p(u, v)} - 1 \right] = \sum_{u,v} p(u)p(v) - \sum_{u,v} p(u,v) = 1 - 1 = 0
  \end{align*}
\end{proof}

Same definitions of entropy holds for $n$ symbols.

\begin{definition}[Joint Entropy]
  Suppose $U_1, U_2, \dots, U_n$ are RVs and we are given $p(u_1 \dots u_n)$, the joint entropy is
  \[
    H(U_1, \dots, U_n) = \sum_{u_1 \dots u_n} p(u_1 \dots u_n) \log \frac 1 {p(u_1 \dots u_n)}
  \]
\end{definition}

\begin{theorem}
  \[
    H(U_1 \dots U_n) \leq \sum_{i=1}^n H(U_i)
  \]
  with equality iff $U$s are independants
\end{theorem}

\begin{corollary}
  if $U_1, \dots, U_n$ are i.i.d. then $H(U_1 \dots U_n) = nH(U_1)$
\end{corollary}

\begin{definition}[Conditional entropy]
  \begin{align*}
    H(U|V) &= \sum_{u,v} p(u,v) \log \frac 1 {p(u|v)}\\
           &= \sum_v H(U | V = v) \Pr{V = v}
  \end{align*}
\end{definition}

\begin{theorem}
  \[
    H(UV) = H(U) + H(V|U) = H(V) + H(U|V)
  \]
\end{theorem}

\begin{theorem}
  \[
    H(U) + H(V) \geq H(UV) = H(V) + H(U|V)
  \]
\end{theorem}

\begin{definition}[Mutual information]
  Mutual information measures the amount of information that can be obtained about one random variable by observing another.
  \begin{align*}
  I(U;V) = I(V;U) &= H(U) - H(U|V)\\
  &= H(V) - H(V|U)\\
  &= H(U) + H(V) - H(UV)
  \end{align*}
\end{definition}

We can apply the chain rule on the entropy as follow

\[
  H(U_1 U_2 \dots U_n) = H(U_1) + H(U_2|U_1) + \dots + H(U_n|U_1 U_2 \dots U_{n-1})
  = \sum_{i = 1}^n H(U_i | U^{i-1})
\]

\begin{definition}[Conditional mutual information]
  \begin{align*}
    I(U;V|W) &= H(U|W) - H(U|VW)\\
    &= H(V|W) - H(V|UW)\\
    &= \E_{u,v,w} \left[ \log \frac {p(uv|w)} {p(u|w)p(v|w)} \right]
  \end{align*}
\end{definition}

\begin{theorem}
  \[
    I(V;U_1\dots U_n) = I(V;U_1) + I(V;U_2 | U_1) + \dots + I(V;U_n|U_1 \dots U_{n-1})
  \]
\end{theorem}

We can apply the chain rule on the mutual information as follows
\[
  I(U_1, U_2, ... ; V) = I(U_1; V) + I(U_2; V | U_1) + ...
\]

\begin{theorem}[Data processing inequality]
  Let $X \rightarrow Y \rightarrow Z$ be a Markov chain, then
  \begin{align*}
    I(X ; Y) \geq I(X ; Z) \quad \text{ and } \quad I(Y ; Z) \geq I(X ; Z)
  \end{align*}
  We have equality iff $I(X ; Y | Z) = 0$ (i.e. $X \rightarrow Z \rightarrow Y$ form a Markov chain)
  This important and useful theorem demonstrates that no processing of $Y$, deterministic or random, can increase the information that $Y$ contains about $X$.
\end{theorem}

\begin{notation}
  \[
    U^n \triangleq (U_1 U_2 \dots U_n)
  \]
\end{notation}

\begin{theorem}
  \[
    I(U;V |W) \geq 0
  \]
  equality iff conditioned on $w$, $u$ and $v$ are independant, that is iff $U-W-V$ is a Markov chain.
\end{theorem}


\begin{proof}
  \begin{align*}
    I(U;V|W) &= \frac 1 {\ln 2} \sum_{u,v,w} p(uvw) \ln \frac {p(u|w)p(v|w)} {p(uv | w)}\\
    &\geq \frac 1 {\ln 2} \sum_{u,v,w} p(uvw) \left[ \frac {p(u|w)p(v|w)} {p(uv | w)} - 1 \right]\\
    &=\frac 1 {\ln 2} \sum_{u,v,w}(p(w)p(u|w)p(v|w) - p(uvw))\\
    &= \frac 1 {\ln 2}(1 - 1) \\
    &=0
  \end{align*}
\end{proof}

% -----------------------------------------------------------------------

\cleardoublepage
\section{Data processing}

\begin{theorem}
  $U-V-W$ is a MC $\iff I(U;W|V) = 0$
\end{theorem}

\begin{corollary}
  $I(U;V) \geq I(U;W)$ and by symetry of MC $I(W;V) \geq I(U;W)$
\end{corollary}

\begin{proof}
  \[
    I(U;VW) = I(U;V) + I(U;W|V) = I(U;V)
  \]
  and
  \[
    I(U;VW) = I(U;W) + I(U;V|W) \geq I(U;W)
  \]
\end{proof}

\begin{theorem}
  Given $U$ a RV taking values in $\U$ then
  \[
    0 \leq H(U) \leq \log | \U |
  \]
  and $H(U)=0$ iff $U$ is constant, $H(U)=\log | \U |$ iff $U$ is $p(u) = 1 / |\U|$ for all $u$.
\end{theorem}

\begin{proof}
For the lower bound,
  \[
    H(U) = \sum_u \underbrace{p(u)}_{\geq 0} \underbrace{\log \frac 1 {p(u)}}_{\geq 0} \geq 0
  \]
For the upper bound,

\begin{align*}
  H(U) - \log | \U |
  &= \sum_u p(u) \log \frac 1 {p(u)} - \sum_u p(u) \log |\U|\\
  &= \frac 1 {\ln 2} \sum_u p(u) \ln \frac 1 {|\U | p(u)}\\
  &\leq \frac 1 {\ln 2} \sum_u p(u) \left(\frac 1 {|\U | p(u)} - 1 \right)\\
  &=\frac 1 {\ln 2} \left[ \sum_u \frac 1 {|\U |} - \sum_u p(u) \right]\\
  &=0
\end{align*}
\end{proof}

\begin{theorem}
  $I(U;V) = 0 \iff U \bot V$
\end{theorem}


\begin{definition}[Entropy rate of a stochastic process]
\[
  r = \lim_{n\to \infty} \frac 1 n H(U^n) \quad \text{ if the limit exists}
\]
\end{definition}

\begin{theorem}
  For stationary stochastic process $U^n$, the sequences
  \[
    a_n = \frac 1 n H(U^n) \text{ and } b_n = H(U_n|U^{n-1})
  \]
  are positive and non increasing. Then $a=\lim_{n\to \infty} a_n$ and $b=\lim_{n\to \infty} b_n$ exists and $a=b$.
\end{theorem}

\begin{proof}
\begin{align*}
  b_{n+1}
  &= H(U_{n+1}|U_1, U_2,\dots,U_n)\\
  &\leq H(U_{n+1}|U_2,\dots,U_n)\\
  &= H(U_n|U_1, U_2,\dots,U_{n-1})\\
  &= b_n \text{ , because $U_1 \dots U_n \sim U_2 \dots U_{n+1}$ (Stationarity).}
\end{align*}


Hence, it is non-increasing.\\\\

For the \{$a_n$\}, observe that

\begin{align*}
a_n = \frac{1}{n} H(U^n)
&= \frac{1}{n} \bigg[ H(U_1)+H(U_2|U_1)+H(U_3|U^2) +\dots+H(U_n|U^{n-1}) \bigg]\\
&= \frac{1}{n} \bigg[ b_1+b_2+\dots+b_n\bigg]
\end{align*}


and by the "Lemma", whenever $b_n \rightarrow b$ , \space $a_n \rightarrow b$
\end{proof}
\begin{lemma}[Cesaro]
	Suppose $b_n \rightarrow b$, \\\\

	then,
	\[
	a_n = \frac{1}{n} \bigg[ b_1+b_2+\dots+b_n\bigg] \text{ also converges and to 1.}
	\]
\end{lemma}
\begin{proof}
	Since $b_n \rightarrow b$ , $\bigg( \equiv \forall \epsilon > 0$ , $\exists$ $n(\epsilon)$ s.t $ \forall n > n(\epsilon)$  $ |b_n-b| < \epsilon\bigg)$\\

	$\exists B $ s.t. $ |b_n| < B$ for all n.\\\\
	Take $n > n_1(\epsilon) \triangleq \dots $ then
	\[
		|a_n-b| \leq \frac{|b_1-b|+|b_2-b|+|b_3-b|+\dots+|b_n-b|}{n}
	\]
	\[
		\text{so  }  |a_n-b| \leq \frac{1}{n}\bigg[ \sum_{i=1}^{n_0(\epsilon)} \underbrace{|b_i-b|}_{2B}  + \sum_{i=n_0(\epsilon)+1}^{n} \underbrace{|b_i-b|}_{\leq \epsilon}\bigg] \leq \frac{n_0(\epsilon) 2B}{n} + \epsilon < 2\epsilon
	\]
	\[
		\text{for } n>n_1(\epsilon) \triangleq \text{max, } \{ n_0(\epsilon) \frac{1}{\epsilon} n_0(\epsilon) 2B \}
	\]
\end{proof}



% -------------------------------------------------------------------------
% class 9.10.2017

\begin{theorem}
  Given a stationary process with entropy rate $r$:
  \begin{align*}
    r = \lim_{n \rightarrow \infty} \frac{1}{n} H(U^n)
  \end{align*}

  then
  \begin{enumerate}
    \item for every source coding scheme
    \begin{align*}
      \C_n: U^n \rightarrow \{0, 1\}^*
    \end{align*}
    the expected number of bits / letter is given by
    \begin{align*}
      \frac{1}{n} E[l(\C(U^n))] \geq r
    \end{align*}
    \item for any $\epsilon > 0$, there exists a source coding scheme $\C_n: U^n \rightarrow \{0, 1\}^*$ s.t.
    \begin{align*}
      \frac{1}{n} E[l(\C_n(U^n))] < r + \epsilon
    \end{align*}
  \end{enumerate}
\end{theorem}

\begin{proof}
  \begin{enumerate}
    \item we already know
    \begin{align*}
      \frac{1}{n} E[l(\C_n(U^n))] \geq \frac{1}{n} H(U^n)
    \end{align*}
    and the right term is decreasing
    \item we also know that for each $n, \exists \C_n$ that is prefix-free s.t.
    \begin{align*}
      E[l(\C_n(U^n))] < \underbrace{\frac{1}{n} H(U^n)}_{r} + \underbrace{\frac{1}{n}}_{0}
    \end{align*}
    we can find $n$ large enough s.t. the right hand side $< r + \epsilon$
  \end{enumerate}
\end{proof}

% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Typicality and typical set}

\begin{definition}[Typicality]
  \label{def:typicality}
Suppose we have a sequence $U_1, U_2, ...$ of i.i.d. random variables taking values in an alphabet $\U$.
Suppose we observe $u_1,u_2..., u_n$. We will call it to be \textit{typical-$(\epsilon, p)$} if
\begin{align*}
  p(u) (1 - \epsilon)
  \leq \frac{\# \text{ of times $u$ appears in $u_1, ..., u_n$}}{n}
  \leq p(u)(1+\epsilon)
\end{align*}
\end{definition}

\begin{theorem}
  $u^n$ is $(\epsilon, p)$-typical then
  \begin{align*}
    2^{-n H(u)(1 + \epsilon)}
    \leq Pr(U^n = u^n)
    \leq 2^{-n H(u)(1 - \epsilon)}
  \end{align*}
\end{theorem}

\begin{proof}
  \begin{align*}
    Pr(U^n = u^n) &= \prod_{i=1}^n Pr(U_i = u_i) = \prod_{i=1}^n p(u_i) = \prod_{u \in \U} p(u)^{\#_u}
  \end{align*}
  with $\#_u$ the number of times $u$ appears in $u_1, ..., u_n$ where
  \begin{align*}
    n (1-\epsilon) p(u) \leq \#_u \leq n(1+\epsilon)p(u)
  \end{align*}
  consequently
  \begin{align*}
    p(u)^{(n p(u)(1-\epsilon))} \geq p(u)^{\#_u} \geq p(u)^{n p(u)(1+\epsilon)}
  \end{align*}
  then
  \begin{align*}
    (\prod_{n} p(u)^{p(u)})^{(1-\epsilon)n}
    \geq Pr(U^n = u^n)
    \geq (\prod_{n} p(u)^{p(u)})^{(1+\epsilon)n}
  \end{align*}
  but
  \begin{align*}
    p(u)^{p(u)} = 2^{-p(u) \log \frac{1}{p(u)}} \Rightarrow \prod p(u)^{p(u)} = 2^{-H(u)}
  \end{align*}
\end{proof}

\begin{definition}[Typical set]
  \begin{align*}
    T(n, \epsilon, p) = \{ u^n \in \U^n : u^n \text{ is } (\epsilon, p)\text{-typical}\}
  \end{align*}
\end{definition}

\begin{wikipedia}
  Typical sets provide a theoretical means for compressing data, allowing us to represent any sequence $X^n$ using $nH(X)$ bits on average, and, hence, justifying the use of entropy as a measure of information from a source.
\end{wikipedia}

\begin{theorem}
  \begin{enumerate}
    \item if $u^n \in T(n, \epsilon, p)$ then
    \begin{align*}
      p(u^n) = Pr(U^n = u^n) = 2^{-n H(u)(1 \pm \epsilon)}
    \end{align*}
    when $U_i$ i.i.d.
    \item
    \begin{align*}
      \lim_{n \rightarrow \infty} Pr(U^n \in T(n, \epsilon, p)) = 1
    \end{align*}
    \item
    \begin{align*}
      |T(n, \epsilon, p)| \leq 2^{n (H(u)(1 + \epsilon))}
    \end{align*}
    \item
    \begin{align*}
      |T(n, \epsilon, p)| \geq (1-\epsilon) 2^{n H(u)(1-\epsilon)}
    \end{align*}
  \end{enumerate}
\end{theorem}

\begin{proof}
  \begin{enumerate}
    \item
    Fix $u \in \U$ let $X_i = 1$ if $ U_i = u$ and $0$ otherwise
    \begin{align*}
      \frac{\text{\# of times } u \text{ appears in } U_1 ... U_n}{n} = \frac{1}{n} \sum_{i = 1}^n X_i
    \end{align*}
    observe that $\{ X_i \}$ are i.i.d.
    \begin{align*}
      &X_i =
      \left\{
        \begin{array}{l l}
          1 & \text{ w.p. } p(u) \\
          0 & \text{ w.p. } 1 - p(u)
        \end{array}
      \right. \\
      &\Rightarrow \Ex{X_i} = p(u) \quad \text{ and } \quad Var[X_i] = p(u) - p(u)^2 \\
    \end{align*}
    \begin{align*}
      \underbrace{
        \Pr{|\frac{1}{n} \sum_{i=1}^n X_i - p(u)|\geq \epsilon p(u)}
      }_{u^n \text{ fails the test for letter } u}
      \leq
      \frac{Var(\frac{1}{n} \sum X_i)}{(\epsilon p(u))^2}
      = \frac{(1 - p(u))}{n\epsilon^2 p(u)}
    \end{align*}

    \item
    \begin{align*}
      \Pr{U^n \not \in T(n, \epsilon, p)} &= \Pr{\bigcup_{u \in U} \{u^n \text{ fails the test for u} \}} \\
      &\leq \sum_{u \in U} \Pr{U^n \text{ fails the test for } u} \\
      &\leq \frac{1}{n} \sum_{u \in U} \frac{(1 - p(u))}{p(u) \epsilon^2} \quad \text{ which goes to 0 as } n \text{ gets large}
    \end{align*}

    \item
    \begin{align*}
      1 \geq \Pr{U^n \in T(n, \epsilon, p)} &= \sum_{u^n \in T(n, \epsilon, p)} \Pr{U^n = u^n} \\
      &\geq \sum_{u^n \in T(n, \epsilon, p)} 2^{-n(1 + \epsilon) H(u)} \\
      &= 2^{-n (1 + \epsilon) H(u)} |T(n, \epsilon, p)|
    \end{align*}

    \item
    \begin{align*}
      1 - \epsilon \leq \Pr{U^n \in T(n, \epsilon, p)} &= \sum_{u^n \in T(n, \epsilon, p)} \Pr{U^n = u^n} \\
       &\leq \sum_{u^n \in T(n, \epsilon, p)} 2^{n H(u)(1-\epsilon)} \\
       &= 2^{-n H(u)(1 - \epsilon)} |T(n, \epsilon, p)|
    \end{align*}

  \end{enumerate}
\end{proof}

\begin{observation}
  $\Pr{U^n \in T(n, \epsilon, p)} \to 1$ as $n\to \infty$
\end{observation}

\begin{definition}[Kullback Leibler divergence]
  \[
    D(p||q) = \sum_u p(u) \log \frac {p(u)} {q(u)} \geq 0 \text{ with equality iff } p = q
  \]
\end{definition}

If we compress data in a manner that assumes $q(u)$ is the distribution underlying some data, when, in reality, $p(u)$ is the correct distribution, the Kullback-Leiber divergence is the average number of additional bits per datum necessary for compression. It is also called \textbf{relative entropy} and is a measure of how one probability distribution diverges from a second probability distribution.

% -----------------------------
% jb - lecture 2017-10-10

\begin{lemma}
  if $U_1 \dots U_n$ are i.i.d. with distribution $q$ and $u_1 \dots u_n$ is $(\epsilon, p)$-tipycal, then
  \[
    2^{-n[H(p) + D(p||q)](1+\epsilon)}
    \leq
    \Pr{U^n = u^n}
  \leq
    2^{-n[H(p) + D(p||q)](1-\epsilon)}
  \]
\end{lemma}

\begin{proof}
  Follows from
\[
  \left[ \prod_u q(u)^{p(u)} \right]^{n(1+\epsilon)} \leq \Pr{U^n = u^n} \leq  \left[ \prod_u q(u)^{p(u)} \right]^{n(1-\epsilon)}
\]
\[
  \prod_u q(u)^{p(u)} = 2^{-\sum p(u) \log \frac 1 {q(u)}}
\]
and

\[
  \sum_u p(u) \log \frac 1 {q(u)} =
  \underbrace{\sum_u p(u) \log \frac 1 {p(u)}}_{H(p)} +
  \underbrace{\sum_u p(u) \log \frac {p(u)} {q(u)}}_{D(p||q)}
\]
\end{proof}


\begin{corollary}
  if $U_1 \dots U_n$ are i.i.d. following distribution $q$, then
  \[
    2^{-n[(1+\epsilon)D(p||q)+2\epsilon H(p)]}
    \leq
    \Pr{U^n \in T(n,\epsilon,p)}
    \leq
    2^{-n[(1-\epsilon)D(p||q) - 2\epsilon H(p)]}
  \]
\end{corollary}

\begin{proof}
  \[
    \Pr{U^n \in T(n,\epsilon,p)} = \sum_{u^n \in T(n, \epsilon, p)} \Pr{U^n = u^n}
  \]
  We have
  \begin{align*}
    2^{-n[H(p) + D(p||q)](1+\epsilon)}
    \leq
    &\Pr{U^n = u^n}
    \leq
    2^{-n[H(p) + D(p||q)](1-\epsilon)}\\
    2^{nH(p)(1-\epsilon)}
    \leq
    &|T(n, \epsilon, p)|
    \leq
    2^{nH(p)(1+\epsilon)}
  \end{align*}
\end{proof}

\begin{example}
  $U \in \{0,1\}$, $p=\frac 1 2, \frac 1 2$, $q=\frac 1 2 - \delta, \frac 1 2 + \delta$
  \[
    D(p||q) = \frac 1 2 \log \frac 1 {1-2\delta} + \frac 1 2 \log \frac 1 {1+2\delta} = \frac 1 2 \log \frac 1 {1-4\delta^2} = - \frac 1 2 \log (1-4\delta^2) \approx \frac 1 2 4\delta^2 + o(\delta^4)
  \]
  So if we want $2^{-n D(p||q)}$ small, we must pick $n=\Omega(1/\delta^2)$
\end{example}

\begin{example}
  Suppose we are told that $U$ is $p$ distributed and $p(u)$ are powers of 2. We design a prefix-free code $\C$ to minimize $\sum_u p(u) l(\C(u))$. We have been misinformed and $U\sim q$, then:

  \begin{align*}
    \Ex{l(\C(u))}
    &= \sum_u q(u) \log \frac 1 {p(u)}\\
    &= \underbrace{H(q)}_{\text{length for optimal code}} + \underbrace{D(q||p)}_{\text{penalty for misbelief}}
  \end{align*}
\end{example}

% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Universal data compression}

Suppose we know that the distribution $p$ of $U$ is either $p_1$, $p_2$ ... $p_k$, can we design a code $\C: U \to \{0,1\}^*$

\[
  \Ex{l(\C(U))} \leq H(U) + \text{small for every } p
\]

\[
  \Ex{\frac 1 n l(\C(U))} \leq o(n) + \Ex{h_2 \pfrac K n}
\]
with $K = \sum_{i=1}^n u_i$

We have $\frac {\Ex{K}} n = \theta_1$ and $\Ex{h_2\pfrac K n} \leq h_2 \left(\Ex{\frac K n} \right) = h_2(\theta)$

\paragraph{Design $\C$}
Because the probability of a bit string is only dependant of the number of
1s (or 0s), it makes sense to encode two strings with the same numbers of 1
with code words of same lengths.
Given $u_1 \dots u_n \in \{0,1\}^n$, first count the number of 1, call it $k$.


\[
  \C(u_1 \dots u_n) =
  \underbrace{\text{describe } k}_{\lceil \log (n+1)\rceil}
  \underbrace{\text{describe } u_1 \dots u_n}_{\lceil \log {n \choose k}\rceil}
\]

We now want to evaluate

\[
  \frac 1 n \Ex{l(\C(U))}
\]

when $U_1 \dots U_n$ are i.i.d with $p_1 = \theta$ and $p_0 = 1 - p_1$

\begin{observation}

for any $0 \leq \alpha \leq 1$

\begin{align*}
  1 = 1^n = (\alpha + (1-\alpha))^n &= \sum_{i=0}^n {n \choose i} \alpha^i (1-\alpha)^{n-i}\\
  & \geq {n \choose k} \alpha^k (1-\alpha)^{n-k}
\end{align*}

Then for all $\alpha$

\[
{n \choose k} \leq \alpha^{-k}(1-\alpha)^{-(n-k)} = 2^{n(\frac k n \log \frac 1 \alpha + (1-\frac k n) \log \frac 1 {1-\alpha})}
\]

We pick $\alpha = \frac k n$, and we get

\[
  {n \choose k} < 2^{n h_2 \pfrac k n}
\]

\end{observation}

Using this bound we have

\[
  \frac 1 n l(\C(u_1 \dots u_n)) \leq \frac 2 n + \frac {\log (n+1)} n + h_2\pfrac k n
\]

\[
  \Ex{\frac 1 n l(\C(U))} \leq o(n) + \Ex{h_2 \pfrac k n}
\]

\begin{claim}
Suppose $U_i$ are i.i.d. with $\Pr{U_1=1}=\theta$. We have $\Ex{ \frac k n} = \theta$ and $\Ex{h_2 \pfrac k n } \leq h_2(\Ex{\frac k n}) = h_2(\theta)$. So
\[
  \lim_{n\to \infty} \frac 1 n \Ex{l(\C(u_1\dots u_n))} \leq h_2(\theta)
\]
consequently this scheme is asymptotically optimal.
\end{claim}

\begin{proof}
  To prove the claim we need to show that if $\beta_1\dots \beta_k$ are in $[0,1]$ and $q_1 \dots q_k$ are non negative numbers that sum to 1 then

  \[
    \sum_{i=1}^k q_i h_2(\beta_i) \leq h_2 \left(\sum_{i=1}^k q_i \beta_i \right)
  \]

  Let $U$ and $V$ be random variables with $U \in \{0,1\}$ and $V \in \{1,\dots,k\}$ with

  \begin{align*}
    \Pr{V=i} &= q_i\\
    \Pr{U=1|V=i} &= \beta_i\\
    \Pr{U=0|V=i} &= 1- \beta_i\\
  \end{align*}
  Then,
  \begin{align*}
    \Pr{U=1} &= \sum_i q_i \beta_i\\
    H(U) &= h_2\left(\sum_i q_i \beta_i \right)\\
    H(U|V) &= \sum_i q_i h_2(\beta_i)
  \end{align*}

  And we already know that $H(U) \geq H(U|V)$
\end{proof}

% -------------------------------------------------------------------------
% lesson - 17.0.2017 - sebastien

Suppose we have an infinite string $u_1 u_2 ..., u_i \in \U$, and
$$u_1 u_2 ... = v_1 v_2 ... \text{ with } v_i \in \U^*, v_i \neq v_j \text{ when } i \neq j$$
for any $k$ we have
\begin{align*}
  \lim_{m \to \infty} \frac{length(v_1...v_m)}{m} \geq k
  \Rightarrow \lim_{m \to \infty} \frac{length(v_1 ... v_m)}{m} =
  \infty
\end{align*}

\begin{definition}
  Given an infinite string $u_1 u_2 ...$ and a machine $M$, let
  \begin{align*}
    \rho_{M}(u_1 u_2 ...) = \overline{\lim_{n \to \infty}} \frac{\text{length of the output } M \text{ after reading } u_1 u_2...}{n}
  \end{align*}
  also given $s > 0$, define
  \begin{itemize}
    \item The compressibility of $\U^*$ be s-state machines
    \begin{align*}
      \rho_s (u_1 u_2 ...) = \min_{M} \rho_{M}(u_1 u_2 ...)
    \end{align*}
    with $M$ an $s'$-state machine with $s' \leq s$
    \item Compressibility of $\U^*$ by finite state machines
    \begin{align*}
      \rho_{FSM} (u_1 u_2 ...) = \lim_{s \to \infty} \rho_s (u_1 u_2 ...)
    \end{align*}
  \end{itemize}
\end{definition}

\begin{definition}
  Suppose $u_1 u_2 ...$ an infinite sequence, define $m(n)$ as the largest $m$ for which $u_1 ... u_n = v_1 ... v_m$ with distinct $v_1 ... v_m$
  \begin{example}
    $$ u = aaaaaaaaa, \quad \underbrace{\emptyset}_{v_1} \underbrace{a}_{v_2} \underbrace{aa}_{v_3} \underbrace{aaa}_{v_4} \underbrace{aaaa}_{v_5} \quad \Rightarrow m(10) = 5 $$
  \end{example}
\end{definition}

So far we know that

\begin{align*}
  \frac{\text{ length of the output of any s-state IL machine when it reads } u_1 u_2 ... }{n} \geq \frac{m(n) \log \frac{m(n)}{8 s^2}}{n}
\end{align*}
with
\begin{align*}
  \frac{m(n) \log \frac{m(n)}{8 s^2}}{n} = \frac{m(n) \log(m(n))}{n} - \frac{m(n) \log(8 s^2)}{length(v_1 ... v_m)}
\end{align*}

hence if $M$ is a s-state machine
\begin{align*}
  \rho_M (u_1 u_2 ...) \geq \overline{\lim_{n \to \infty}} \frac{m(n) \log(m(n))}{n}
  \quad \text{ then } \quad
  \rho_{FSM} (u_1 u_2 ...) \geq \overline{\lim_{n \to \infty}} \frac{m(n) \log m(n)}{n}
\end{align*}


% -------------------------------------------------------------------------
% Lemple-Ziv


\cleardoublepage
\section{Lemple-Ziv data compression method}

Given some alphabet $\U$ to both encoder and decoder, they also agree an order on $\U$:

\begin{enumerate}
  \item Start with a dictionary $\D = \U$
  \item To each word $w \in \D$, assign a $\lceil \log |\D| \rceil $-bit binary description in the dictionary order
  \item Parse the first word $w$ in $u_1 u_2 ...$ in the dictionary, output its binary description
  \item replace $w$ in $\D$ by $\{ wu, \forall u \in \U \}$.
  \item Go to 2.
\end{enumerate}

\begin{example}
  Define an alphabet $\U = \{a, b, c\}$ with $a \leq b \leq c$ and an input message
  $$ u = b b a c a c $$
  \begin{itemize}
    \item Create the dictionary $\D = \{a, b, c\}$ and its corresponding binary description $\D_{bin} = \{00, 01, 10\}$
    \item The first word in the message is $'b'$, output its binary description
    $$ output = 01 $$
    \item Update the dictionary:
    $$ \D = \{a, ba, bb, bc , c\} \quad \D_{bin} = \{000, 001, 010, 011, 100\} $$
    \item Parse the next word $'ba'$ and output its binary description
    $$ output = 01 001 $$
    \item Update the dictionary
    $$ \D = \{a, baa, bab, bac, bb, bc , c\} \quad \D_{bin} = \{000, 001, ...\} $$
    \item Continue until the end of the input data...
  \end{itemize}
  The decoder can proceed in a similar way to iteritavely update the dictionary while decoding the message.
\end{example}

\subsection{Analysis of LZ}

Observe that LZ parses the string $u_1 u_2 ...$ into $v_1 v_2 ...$ with $v_i \in \U^*$ or $v_i \in \D_i$ where $\D_i$ is the dictionary at step $i$.

When going from iteration $i \rightarrow i+1$, $v_i$ is removed from $\D$, consequently $v_1, v_2, v_3$ are distinct.

The length of the output of LZ after reading $u_1 ... u_m$ is given by
\begin{align*}
  \text{LZ output's length} = \lceil \log |\U| \rceil + \lceil \log (2 |\U| - 1) \rceil
  + \lceil \log (3 |\U| - 2) \rceil + ...
  + \lceil \log (m|\U| - m + 1) \rceil
\end{align*}
we observe that
\begin{align*}
  \text{LZ output's length} < m(\log(m |\U|) + 1) = m \log(2 m |\U|)
\end{align*}

Also we have

\begin{align*}
  \text{\# bits / letter} &< \frac{m \log(2m |\U|)}{length(u_1 ... u_m)} \\
  &= \frac{m \log(m)}{ length(u_1 ... u_m)} + \frac{m \log(2 |\U|)}{length(u_1 ... u_m)}
\end{align*}

therefore
\begin{align*}
  \rho_{LZ}(u_1 u_2 ...) = \lim_{m \to \infty} \frac{\text{\# bits}}{\text{letter}} \leq \lim_{m \to \infty} \frac{m \log(m)}{length(u_1 ... u_m)} \leq \lim_{n \to \infty} \frac{m(n) \log(m(n))}{n} \leq \rho_{FSM}(u_1 u_2 ...)
\end{align*}

So we have proved the following theorem:

\begin{theorem}
  for every $u_1 u_2 ...$
  $$ \rho_{LZ}(u_1 u_2 ...) \leq \rho_{FSM}(u_1 u_2 ...) $$
\end{theorem}

\begin{corollary}
  if $u_1 u_2 ...$ is stationary
  $$ \rho_{LZ}(u_1 u_2 ...) = \text{ entropy rate of } u_1 u_2 ...$$
\end{corollary}


% ---------------
% jb 2017-10-23

% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Transmission of data}

Interesting in the case of unreliable transmission media.

\begin{definition}[Communication channel]
  A communication channel $W$ is a device with an input alphabet $\X$ and an output
  alphabet $\Y$. Its behabvior is described by
  \[
    W_i(y_i | x^i, y^{i-1}) = \Pr{Y_i = y_i | X^i = x^i, Y^{i-1} = y^{i-1}}
  \]
\end{definition}

\begin{definition}[Memoryless channel]
  a channel $W$ is said to be memoryless if
  \[
      W_i(y_i | x^i, y^{i-1}) = W(y_i|x_i)
    \]
\end{definition}

\begin{definition}[Stationary channel]
  a channel $W$ is said to be stationary if
  \[
      W_i(y|x) = W(y|x)
    \]
\end{definition}

\begin{example}[Binary erasure channel - BEC]
  $\X = \{0,1\}$ and $\Y = \{0,1,?\}$, then
  \begin{align*}
    W(0|0) &= 1 - p\\
    W(?|0) &= p\\
    W(1|0) &= 0
  \end{align*}
  and same for $x_i=1$.
\end{example}

\begin{example}[Binary symetric channel - BSC]
  \begin{align*}
    W(0|0) &= 1 - p = W(1|1)&\\
    W(1|0) &= p =W(0|1)
  \end{align*}
\end{example}

The input $X_1, X_2 \dots X_n$ to a channel might have memory

\[
  \Pr{X^n = x^n} = p(x_1)p(x_2 | x_1) \dots p(x_i | x^{i-1}) \dots p(x_n|x^{n-1})
\]

\begin{align*}
  \Pr{X^n=x^n, Y^n=y^n} &= p(x_1)W_1(y_1|x_1)p(x_2|x_1,y_1)W(y_2|x_1,x_2,y_1)\dots\\
  &= \prod_i p(x_i|
  \underbrace{x^{i-1}}_{\text{feedback}}
  \underbrace{y^{i-1}}_{\text{memory}}
  )W_i(y_i|x^iy^{i-1})
\end{align*}

\begin{lemma}
  if there is no feedback and the channel is memoryless and stationary, then
  \[
    \Pr{Y^n=y^n | X^n=x^n} = \prod_{i=1}^n W(y_i|x_i)
  \]
\end{lemma}

\begin{proof}
  \begin{align*}
    \Pr{Y^n=y^n, X^n=x^n} &= \prod_{i=1}^n p(x_i|x^{i-1}y^{i-1})W_i(y_i|x^iy^{i-1})\\
    &= \prod_{i=1}^n p(x_i|x^{i-1})W(y_i|x_i)\\
    &= \prod_{i=1}^n W(y_i|x_i) \Pr{X^n=x^n}
  \end{align*}
\end{proof}

\begin{example}
  Suppose $W$ is BSC(1/2) but we have feedback, defined by $X_1=0$ and $X_i=Y_{i-1}$.

  \begin{align*}
    &\Pr{Y^2=00|X^2=01} = 0\\
    &W(0|0)W(0|1) = \frac 1 4
  \end{align*}

\end{example}

\begin{lemma}
  if $W$ is stationary memoryless and there is no feedback, then
  \[
    H(Y^n|X^n) = \sum_{i=1}^n H(Y_i|X_i)
  \]

\end{lemma}

\begin{proof}
  \[
    H(Y^n|X^n) = \Ex{\log \frac 1 {\Pr{Y^n|X^n}}}
    = \Ex{\log \prod_{i=1}^n \frac 1 {\Pr{Y_i|X_i}}}
    = \sum_{i=1}^n \Ex{\log \frac 1 {\Pr{Y_i|X_i}}}
    = \sum_{i=1}^n H(Y_i|X_i)
  \]
\end{proof}

For a memoryless stationary channel $W(Y|X)$ we can compute, for any
distribition $p(x)$, $p(x,y) = p(x)W(y|x)$ and $I(X;Y)$, we can also compute
\[
  C(W) = \max_{p(x)} I(X;Y)
\]

\begin{lemma}
  for a stationary memoryless $W$ without feedback, we have
  \[
    I(X^n;Y^n) \leq n C(W)
  \]
\end{lemma}


\begin{proof}
  \begin{align*}
    I(X^n;Y^n) &= H(Y^n) - H(Y^n|X^n)\\
    &= H(Y^n)- \sum_i H(Y_i|X_i)\\
    &\leq \sum_i H(Y_i) - \sum_i H(Y_i|X_i)\\
    &= \sum_i I(X_i;Y_i)
  \end{align*}

  Note that the joint distribution $\Pr{X_i,Y_i}$ is of the form $p(x)W(y|x)$, then $I(X_i;Y_i) \leq C(W)$
\end{proof}

\begin{notation} for simplicity
  \[
    p\ast q = (1-q)p + q(1-p)
  \]
\end{notation}

\begin{example}
  Let $W$ be a BSC($p$), $\Pr{X=0} = 1 - q$ and $\Pr{X=1} = q$. Then

  \begin{align*}
    \Pr{Y=0} = (1-q)(1-p) + qp\\
    \Pr{Y=1} = (1-q)p + q(1-p)\\
  \end{align*}

  \begin{align*}
    H(Y|X=0) &= p \log \frac 1 p + (1-p) \log \frac 1 {1-p}\\
    H(Y|X=1) &= p \log \frac 1 p + (1-p) \log \frac 1 {1-p}\\
    H(Y|X) &= p \log \frac 1 p + (1-p) \log \frac 1 {1-p}\\
  \end{align*}

  \begin{align*}
    I(X;Y) &= H(Y) - H(Y|X)\\
    &=(p\ast q) \log \frac 1 {p\ast q} + (1-(p\ast q))\log \frac 1 {1-(p\ast q)}
    -
    \left[
    p \log \frac 1 p + (1-p) \log \frac 1 {1-p}
    \right]
  \end{align*}

  We maximize $I(X;Y)$ for $q=1/2$
  \[
    C(W) = \log 2 - h_2(p)
  \]

\end{example}

\begin{example}
  Let $W$ be BEC($p$) and $\Pr{X=1} = q$

  \begin{align*}
    H(X) &= h_2(q)
\\    H(X|Y=0) &= 0\\
    H(X|Y=1) &= 0\\
    H(X|Y=?) &= h_2(q)
  \end{align*}

  \[
    I(X;Y) = h_2(q) - ph_2(q) = (1-p)h_2(q)
  \]
  \[
    C(W) = (1-p)\log 2
  \]
\end{example}

% -----------------------------------
% lesson 10/24/2017 - Sebastien

\subsection{Fano's inequality}
Suppose $U$ and $V$ take values in the same alphabet $\U$, then

\begin{align*}
  H(U | V) \leq p_e \log(|\U| - 1) + h_2(p_e)
\end{align*}
with
\begin{align*}
  p_e = \Pr{U \neq V}
  \quad \text{ and } \quad
  h_2(p) = p \log \frac{1}{p} + (1 - p) \log \frac{1}{(1-p)}
\end{align*}

\begin{proof}
  Define
  \begin{align*}
    Z =
    \left\{
    \begin{array}{ll}
      1 & U \neq V \\
      0 & U = V
    \end{array}
    \right. , \quad
    H(Z) = h_2(p_e)
  \end{align*}

  \begin{align*}
    H(UZ | V) &= H(U|V) + H(Z | UV) \\
    &= H(Z | V) + H(U | VZ) \\
    &\leq H(Z) + H(U | VZ)
  \end{align*}
  but
  \begin{align*}
    H(U | VZ) = \underbrace{H(U | V, Z = 0)}_{0}\Pr{Z = 0} + \underbrace{H(U | V, Z = 1)}_{\leq \log(|\U| - 1)}\underbrace{\Pr{Z = 1}}_{p_e}
  \end{align*}
\end{proof}

So if $H(U|V) > \lambda \Rightarrow \exists f(\lambda) > 0$, $p_e > f(\lambda)$

\begin{corollary}
  Suppose $U^L$, $V^L$ are random sequences with common alphabet $\U$, define :
  \begin{align*}
    p_{e,i} = \Pr{U_i \neq V_i} , \quad
    \bar{p_e} = \frac{1}{L} \sum_{i = 1}^{L} p_{e,i}
  \end{align*}
  then
  \begin{align*}
    \frac{1}{L} H(U^L | V^L) \leq h_2(\bar{p_e}) + \bar{p_e} \log(|\U| - 1)
  \end{align*}
\end{corollary}

\begin{proof}
  \begin{align*}
    \frac{1}{L} H(U^L | V^L) &= \frac{1}{L} \sum_{i = 1}^{L} H(U_i | U^{i-1} V^L) \\
    &\leq \frac{1}{L} \sum_{i = 1}^{L} H(U_i | V_i) \\
    &\leq \frac{1}{L} \sum_{i = 1}^{L}(p_{e,i} \log(|\U| - 1) + h_2(p_{e, i})) \\
    &= \bar{p_e} \log(|\U| - 1) + \frac{1}{L} \sum_{i = 1}^L h_2(p_{e,i}) \\
    &\leq \bar{p_e} \log(|\U| - 1) + h_2(\frac{1}{L} \sum_{i = 1}^L p_{e,i}) \\
    &= \bar{p_e} \log(|\U| - 1) + h_2(\bar{p_e})
  \end{align*}
\end{proof}

\begin{theorem}{"Bad news" theorem, converse to the coding theorem}
  \begin{itemize}
    \item Suppose we have a stationary source $U_1 U_2 ...$ with entropy rate $H$ and produces a letter every $\tau_s$ seconds.
    \item Suppose also that we have a channel $W$ that accepts input $X_1 X_2 ...$ once every $\tau_c$ seconds.
    \item Suppose also
    \begin{align*}
      \frac{H}{\tau_s} > \frac{C(W)}{\tau_c}
    \end{align*}
  \end{itemize}
  then there is a $\lambda > 0$ such that $\bar{p_e} > \lambda$
\end{theorem}

\begin{definition}{stable}
  suppose the encoder works by taking blocks of $L$ letters
  $$(U_1 ... U_L)(U_{L+1} ... U_{2L})...$$
  and outputs
  $$(X_1 ... X_n)(X_{n+1} ... U_{2n})...$$
  then the encoder is stable if
  \begin{align*}
    L \tau_s \geq n \tau_c
  \end{align*}
\end{definition}

\begin{proof}
  Recall that for a stationary source $\frac{H(U_1 ... U_L)}{L}$ tends to $H$ so
  $$ H(U_1 ... U_L) \geq L H$$
  We also have
  \begin{align*}
    I(U^L; V^L) \leq n C(W)
  \end{align*}
  therefore, since $\frac{n}{L} \leq \frac{\tau_s}{\tau_c}$
  \begin{align*}
    H(U^L | V^L) = \frac{1}{L} (H(U^L) - I(U^L; V^L)) &\geq H - \frac{n}{L} C(W) \\
    &\geq H - \frac{\tau_s}{\tau_c} C(W) \\
    &= \tau_s (\frac{H}{\tau_s} - \frac{C(W)}{\tau_c})
  \end{align*}

  The right hand side is
  $$\epsilon(\tau_c, \tau_s, H, C) > 0$$
  so for every stable encoder, decoder, we have
  \begin{align*}
    \bar{p_e} \log(|\U| - 1) + h_2(\bar{p_e}) > \epsilon(\tau_s, \tau_c, H, C)
  \end{align*}
  then
  \begin{align*}
    \bar{p_e} \geq \epsilon(\tau_s, \tau_c, H, C, |\U|)
  \end{align*}
\end{proof}

\begin{example}
  Suppose $\U = \{ 0, 1 \}$ and $U_1 U_2 ...$ is a Markov process with
    \begin{align*}
    U_1 =
    \left\{
    \begin{array}{ll}
      0 & \text{ with } p = 0.5 \\
      1 & \text{ with } p = 0.5
    \end{array}
    \right. , \quad
    p(U_{n+1} | U_n) =
    \left\{
    \begin{array}{ll}
      1 - p & u_{n+1} = u_n \\
      p     & u_{n+1} \neq u_n
    \end{array}
    \right. , \quad
  \end{align*}
\end{example}

\begin{align*}
  H &= \lim_{n \to \infty} H(U_n | U^{n-1})\\
    &= \lim_{n \to \infty} H(U_n | U_{n_1})\\
    &= H(U_2 | U_1) = h_2(p)
\end{align*}

suppose $W = BEC(q), C(W) = (1 - q)\log 2$ and $\tau_s = \tau_c = 1$

\begin{align*}
  h_2(\bar{p_e}) \geq h_2(p) - (1 - q)\log(2) \Rightarrow \bar{p_e} \geq \lambda
\end{align*}

What we want to do next is to show a matching "Good news" theorem:

We could show that if $\frac{H}{\tau_s} \leq \frac{C(W)}{\tau_c}$ then for any $\lambda > 0$, we can find a stable encoder and decoder such that $p_e < \lambda$.
Instead, we will show stronger results:
\begin{enumerate}
  \item \textbf{Separation theorem}
    The encoder can be designed in a modular way:
    \begin{itemize}
      \item A \textbf{source encoder} which encoder message words in bits. The design of this encoder is strongly dependent of the type of the input.
      \item A \textbf{channel encoder} which encoder the bits to maximize the performance with a specific channel.
    \end{itemize}
  \item We will show that
  \begin{align*}
    \Pr{U^L \neq V^L} < \lambda
  \end{align*}
  using the fact that
  \begin{align*}
    (U_i \neq V_i) \Rightarrow (U^L \neq V^L)
    \quad \text{ so } \quad
    p_{e,i} \leq \Pr{U^L \neq V^L} \Rightarrow \bar{p_e} \leq \Pr{U^L \neq V^L}
  \end{align*}
\end{enumerate}

We will now show that good channel encoders and channel decoders exist

\begin{definition}
  Given a channel $W$ with input alphabet $\X$, a block encoder is a function
  \begin{align*}
    Enc: \{1, ..., M\} \rightarrow \X^n
  \end{align*}
  with $n$ the block length.\\
  $Enc(1), ..., Enc(M)$ are each called codewords and $M$ is equal to the number of codewords.\\
  The rate of the code can be defined by
  $$ R = \frac{\log M}{n} $$
\end{definition}
\begin{definition}
  Given a channel $W$ with ouput alphabet $Y$, a block decoder is a function
  \begin{align*}
    Dec: \Y^n \rightarrow \{ ?, 1, ..., M\}
  \end{align*}
\end{definition}

\begin{definition}
  \begin{align*}
    p_{error}(m) = \Pr{\hat{m} \neq m | m}
  \end{align*}
  \begin{align*}
    \bar{p}_{error}(m) = \frac{1}{M} \sum_{m=1}^M p_{error}(m)
  \end{align*}
  \begin{align*}
    \hat{p}_{error}(m) = \max_{m} p_{error}(m)
  \end{align*}
\end{definition}


% -----------------------------------
% lesson 11/1/2017 - Sebastien

\subsection{Computational consideration for $C(W)$}
We have an optimization problem
  \begin{align*}
    \max_{p_X} f(p_X) \quad \text{ where } \quad f(p_X) = I(X ; Y)
  \end{align*}
See \cref{sec:appendix-convex} for further information on convex optimization.
  \begin{claim}
    $f$ is a concave function
  \end{claim}




% -----------------------------------
% lesson 2017-11-06 - JB


We want to compute
\[
  \frac {\partial  I(X;Y)} {\partial p (x)}
\]
We have
\[
  I(X;Y) = \sum_{x,y} p(x) W(y|x) \log \frac {W(y|x)} {p_Y(y)}
\]

\[
  p_Y(y) = \sum_x p(x) W(y|x)
\]

\begin{align*}
  \frac {\partial I} {\partial p(x_0)}
  &= \sum_{x,y} \frac \partial {\partial p(x_0)}
  \left\{ p(x) W(y|x) \log \frac {W(y|x)} {p_Y(y)} \right\}\\
  &= \sum_{x,y} \left\{ I_{x=x_0} W(y|x)  \log \frac {W(y|x)} {P_Y(y)} -
    p(x)W(y|x) \frac {W(y|x_0)}{p_Y(y)} \log e \right\}\\
  &= \sum_y W(y|x_0) \log \frac {W(y|x_0)}{p_Y(y)} - \sum_y p_Y(y) \frac {W(y|x_0)}{p_Y(y)} \log e\\
  &= \sum_y W(y|x_0) \log \frac {W(y|x)} {P_Y(y)} - \log e
\end{align*}

\begin{theorem}
  \label{th:1000}
  $p_X$ maximizes $I(X;Y)$ iff there exists $\lambda$ such that for all $x$
  \[
    \sum_y W(y|x) \log \frac {W(y|x)} {P_Y(y)} \leq \lambda
  \]
  with equality when $p_X(x) \not= 0$. Furthermore $\lambda = C(W)$.
\end{theorem}

\begin{proof}
  We only need to prove the furthermore part. Observe that for all $x$
  \[
    p_X(x) \sum_y W(y|x) \log \frac {W(y|x)} {P_Y(y)} =  p_X(x) \lambda
  \]
  and then
  \[
    \sum_x p_X(x) \sum_y W(y|x) \log \frac {W(y|x)} {P_Y(y)} =  \sum_x p_X(x) \lambda
  \]
\end{proof}

\begin{example}[Z channel]
  $W$ is a normal binary channel that maps a 1 input to a 0 output with probability $\epsilon$. Applying \cref{th:1000} with $x=0$ and $x=1$:

  \begin{align*}
    &W(0|0)\log \frac {W(0|0)} {p_Y(0)} = W(0|1)\log \frac {W(0|1)} {p_Y(1)} + W(1|1)\log \frac {W(1|1)} {p_Y(1)}\\
    \iff& \log \frac 1 {p_Y(y)} = \epsilon \log \frac \epsilon {p_Y(0)} + (1-\epsilon) \log \frac {1-\epsilon} {p_Y(1)} = h_2(\epsilon) + \epsilon \log \frac 1 {p_Y(0)} + (1-\epsilon)\log\frac 1 {p_Y(1)}\\
    \iff&\log \frac {p_Y(1)} {p_Y(0)} = - \frac {h_2(\epsilon)}{1-\epsilon} \triangleq -\alpha\\
    \Longrightarrow~&p_Y(1) = \frac {2^{-\alpha}} { 1+2^{-\alpha}} ~\text{and}~p_Y(0) = \frac 1 {1+2^{-\alpha}}
  \end{align*}

  \[
    C(W) = \log (1+2^{-\alpha})
  \]
\end{example}


\begin{lemma}
  For any circle with red segments of cumulative length strictly less than $1/4$, there exists a square whose all corners are on the circle but not on the red segments.
\end{lemma}

\begin{proof}
  By random construction. Place the first corner of the square uniformly at random on the circle (also makes the 3 other uniform).
  \begin{align*}
    \Pr{\text{1st corner lands on red}} &< \frac 1 4\\
    \Pr{i\text{th corner lands on red}} &< \frac 1 4\\
    \Pr{\bigcup\limits_{i=1} i\text{th corner lands on red}} &< 1\\
    \Pr{\text{none of the corners land on red}} &> 0\\
  \end{align*}
\end{proof}

\begin{theorem}[Channel coding - good news]
  \label{thm:channel-coding}
  Given a channel $W$ (discrete, memoryless, stationary), a rate $R < C(W)$ and $\epsilon > 0$, there exists a $n$ large enough and encoding/decoding functions $Enc:\{1\dots M\} \to \X^n$ with $M \geq 2^{nR}$ and $Dec: \Y^n \to \{1\dots M\}$ such that for all $m\in\{1\dots M\}$
  \[
    \Pr{Dec(Y^n) \not = m | X^n = Enc(m) } < \epsilon
  \]
\end{theorem}

In other words we can communicate reliably at rate greater or equal to $R$ on channel $W$.

\begin{proof}
  Given $W$ and $R<C(W)$, fix a $p_X$ such that $I(X;Y)>R$. Pick $\delta > 0$, $n$
  large enough (to be determined later) and set $M' = \lceil 2 \cdot 2^{nR} \rceil$. Define the
  encoding function
  \begin{align*}
    Enc(1) =~&X(1)_1 \dots  X(1)_n\\
    \dots~=~&\dots\\
    Enc(M') =~&X(M')_1 \dots X(M')_n
  \end{align*}
  choosing $\{X(m)_i : 1 \leq i \leq n, 1 \leq m \leq M' \}$ i.i.d. $\sim p_X$.

  For the decoder fix
  \[
    T(n, \delta, p_{XY})= \left\{(x^n, y^n): (1-\delta)p_{XY}(x,y) \leq \frac {\# \{(x_i, y_i) = (x,y)\}} n \leq (1+\delta)p_{XY}(x,y)\right\}
  \]

  $Dec(y^n)$: check for each $m$ if $(Enc(m), y^n) \in T(n,\delta, p_{XY})$, if there is
  only a single $m$ for which the pair is in the typical set then $Dec(y^n) = m$ otherwise
  (if there is none or more than one) $Dec(y^n) = 0$.

  We now compute the probability of error $p_{e,m} \triangleq \Pr{Dec(Y^n) \not = m | X^n = Enc(m)}$. $p_{e,m}$ depends on the choice of $Enc(1) \dots Enc(M)$ and since $Enc(1) \dots Enc(M)$ are randomly chosen, $p_{e,m}$ is a random variable. Supposing $m$ is sent, an error will happen if and only if $(Enc(m), y^n) \not \in T$ or for some $m' \not = m:~(Enc(m'), y^n)~\in~T$

  \begin{align*}
    \Ex{p_{e,m}} &= E_{Enc}[ E_{y} [ I\left\{\text{error has happened $|~m$ is sent}\right\}]]\\
    &= E_{Enc}[ I\{(Enc(m),y) \not \in T, \exists m' \not=m (Enc(m', Y^n) \in T\} |~m \text{ is sent}]\\
    &\leq E[I\{(Enc(m), Y^n) \not \in T\}] + \sum_{m' \not = m} I\{(Enc(m'), Y^n) \in T\} |~m \text{ is sent}]\\
    &= \Pr{(Enc(m), Y^n) \not \in T | m \text{ is sent}} + \sum_{m'\not = m} \Pr{(Enc(m'), Y^n) \in T| m \text{ is sent}}
  \end{align*}

  We have
  \begin{align*}
    \Pr{Enc(m) = x_1\dots x_n, Y^n=y_1 \dots y_n |~m \text{ is sent}}
    &= p_x(x_1)p_x(x_2)\dots p_x(x_n)W(y_1|x_1)W(y_2|x_2) \dots W(y_n|x_n) \\
    &= p_X(x_1)p_X(x_2)\dots p_X(x_n)p_Y(y_1)p_Y(y_2)\dots p_Y(y_n)
  \end{align*}
  and as $n$ gets large
  \[
    \Pr{(Enc(m), Y^n) \not \in T (p_{XY}, n, \delta)} = \Pr{\text{iid sequence} \sim p_{XY} \not \in T(p_{XY}, n, \delta)} \to 0
  \]
because $(Enc(m), Y^n)$ is iid $\sim p_{XY}$. Recall from typicallity that if $U^n$ is iid $p_U$, then
\begin{align*}
  \lim_{n\to\infty} \Pr{U^n \not \in T(n, p_U, \delta)} = 0
\end{align*}
and if $U^n$ is in reality iid $\sim~q_U$
\[
  \Pr{U^n \in T(n,p,\delta)} \leq 2^{-n[D(p||q) - o(\delta)]}\\
\]

Then,

\begin{align*}
  \Pr{(Enc(m), Enc(m'), Y^n) = (x^n, (x')^n, y^n)} &= p_X(x^n) p_X((x')^n)W(y^n|x^n)\\
  \Pr{(Enc(m), y^n) = (x^n, y^n)} &= p_X(x^n)W(y^n|x^n)\\
  \Pr{(Enc(m'), y^n) = ((x')^n, y^n)} &= p_X((x')^n) \underbrace{\sum_{x^n} p(x^n)W(y^n|x^n)}_{p_Y(y)}\\
  \iff (Enc(m'), y') \text{ is iid } \sim q_{XY} &= p_Xp_Y\\
  \Rightarrow \Pr{(Enc(m'), y^n) \in T(p_{XY}, n, \delta)} &\leq 2^{-n[D(p||q)- o(\delta)]}
\end{align*}

Also
\[
  D(p||q) = \sum_{xy} p_{XY}(x,y) \log \frac {p_{XY}(x,y)} {p_X(x) p_Y(y)} = I(X;Y)
\]


Remember $M' = \lceil2 \cdot 2^{nR} \rceil \leq 2 \cdot 2^{nR} + 1$ then $M'-1 \leq 2 \cdot 2^{nR}$

\[
  \Ex{p_{e,m}} \leq o_n(1) + (M' -1)  2^{-n[I(X;Y)- o(\delta)]}
  \leq o_n(1) + 2 \cdot 2^{-n(I(X;Y) - R - o(\delta))}
\]

We choose $\delta$ small enough to have a negative exponent. Then it will go to 0 as $n$ gets large. So we have shown that for $n $ large enough we can make for every $m$:

\begin{align*}
  &\Ex{p_{e,m}} < \frac \epsilon 2\\
  \Rightarrow& \Ex{\sum_{m=1}^{M'} p_{e,m}} \leq \frac{M'} 2 \epsilon\\
  \Rightarrow& \exists \text{an encoder such that } \sum_{m=1}^{M'} p_{e,m} \leq \frac{M'} 2 \epsilon
\end{align*}

How many terms in the sumation can be greater or equal to $\epsilon$ ? At most $M'/2$, so remaining must be stricly smaller than $\epsilon$ but

\[
  M' - \frac 1 2 M' = \frac 1 2 \lceil 2 \cdot 2^{nR} \rceil \geq \frac 1 2 2 \cdot 2^{nR} = 2^{nR}
\]
We throw away the one smaller than $\epsilon$ and we have a code with rate greater than $R$ for
\[
  \max_m p_{e,m} < \epsilon
\]
\end{proof}

\begin{example}
  Suppose $\X = \{a,b,c\}$, $C(W)=1.3$ and $R=1.25$, then $Enc(1 \dots 32) \to \X^4$ is a valid encoding function for this channel, while $Enc(1 \dots 32) \to \X^5$ would not allow reliable transmission.
\end{example}

\begin{example}
  Suppose we want to design a code with $n=1000$, $R=\frac 1 2$. The encoding table will have $1000 \times 2^{500}$ elements, more than $10^{153}$ elements. "C'est impossible M'sieur !"
\end{example}



% -----------------------------------
% lesson 2017-11-13 - JB

To illustrate the proof technique that we used to prove the coding theorem, we take an example.

\begin{example}
  Assume $W$ is a BEC channel (probability $p$ to have an erasure symbol \texttt{?}).
  \[
    C(W) = 1-p = \max_{p_x} I(X;Y)
  \]
  achieved when $p_X(0)=p_X(1)=\frac 1 2$. Our coding theorem says that when $R<1-p$, $\epsilon > 0$ we can find a code of rate $R$ with error probability $< \epsilon$. In the proof of the \cref{thm:channel-coding}, we generate a $n\times M$ coding matrix with $n$ large and $M=2^{nR}$ according to $p_X$ defining $C(W)$.

  To send a $nR$-bit message $m \in \{1 \dots M\}$, we send the $m$th row of the table over the chanel. When we receive $y~=~(y_1\dots~y_n)$, we compare $y$ to each row of the table and check the tipicality. In our case

  \begin{align*}
    \frac 1 n \{\text{\# of }(0,0)\} \approx \frac {1-p} 2 \hspace{5em}&
    \frac 1 n \{\text{\# of }(0,1)\} = 0 \hspace{5em}&
    \frac 1 n \{\text{\# of }(0,?)\} \approx \frac p 2 \\
    \frac 1 n \{\text{\# of }(1,0)\} = 0 \hspace{5em}&
    \frac 1 n \{\text{\# of }(1,1)\} \approx \frac {1-p} 2 \hspace{5em}&
    \frac 1 n \{\text{\# of }(1,?)\} \approx \frac p 2
  \end{align*}

  If there is exactly one row (i.e. $\hat m$) return $\hat m$, otherwise return $0$.

  \begin{itemize}
    \item The correct codeword will pass the test with high probability, thanks to law of large numbers,
    \item What about an incorrect codeword ?
  \end{itemize}

  Recall the definition of typicality (\cref{def:typicality}) and suppose

  \[
    y = \underbrace{0\dots0}_{n \frac{1-p} 2} \underbrace{1\dots1}_{n \frac{1-p} 2} \underbrace{?\dots?}_{np}
  \]

  $m' = x_1 x_2 \dots x_n$ will be typical only if it is of the type
  \[
    \underbrace{0\dots0}_{n \frac{1-p} 2} \underbrace{1\dots1}_{n \frac{1-p} 2} \underbrace{?\dots?}_{np}
  \]

  \[
    \Pr{
    \begin{pmatrix}
      x_1 & \dots & x_n\\
      y_1 & \dots & y_n
    \end{pmatrix}
    \text{ is typical}
    }
    \leq
    \pfrac 1 2 ^ {n(1-p)} = 2^{-n(1-p)}
  \]
  Then, using that an upperbound to the number of incorrect codewords is $2^{nR}$,
  \[
    \Pr{error} < 2^{-n(1-p)}2^{nR} + \Pr{\text{correct $w$ fails the test}}
  \]
  and because $R < 1-p$
  \[
    \lim_{n\to \infty} \Pr{error} = 0
  \]

\end{example}

% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Differential entropy}

\begin{definition}[Differential entropy]
  Let $X$ be a real valued random variable with probability density function $f(x)$ such that
  \[
    \Pr{x \leq X \leq x + \delta} \approx \delta f(x)
  \]
  The differential entropy of $X$ is
  \[
    h(X) \triangleq \int f(x) \log \frac 1 {f(x)} dx
  \]
\end{definition}

\begin{example}
  Uniform random variable in $[0,a]$ then \[
    h(A) = log a = \begin{cases}
      < 0 & \text{if } a < 1\\
      0 & \text{if } a = 1\\
      > 0 & \text{if } a > 1
    \end{cases}
  \]
\end{example}

\begin{lemma}
  Suppose $Y=X+a$, $a$ is a constante then $h(Y)=h(X)$
\end{lemma}

\begin{proof}
  We have $f_Y(y) = f_X(y-a)$, then
  \[
    h(Y) = \int f_X(y-a) \log \frac 1 {f_X(y-a)}dy = \int f_X(x) \log \frac 1 {f_X(x)}dx = h(X)
  \]
\end{proof}

\begin{lemma}
  Suppose $Y=aX$, then $h(Y) = h(X) + \log |a|$
\end{lemma}

\begin{proof}
  Suppose $a > 0$,

  \[
    f_Y(y) = \Pr{y\leq Y \leq y + \delta} = \Pr{\frac y a \leq X < \frac y a + \frac \delta a} \approx \frac 1 a f_X \pfrac y a
  \]

  \[
    \log \frac 1 {f_Y(y)} = \log a + \log \frac 1 {f_X\pfrac y a}
  \]
  \[
    h(Y) = \int f_Y(y) \log \frac 1 {f_Y(y)} dy = \log a + \int f_X \pfrac y a \left(\log \frac 1 {f_X\pfrac y a} \right) \frac 1 a dy = \log a + \underbrace{\int f_X(x) \log \frac 1 {f_X(x)} dx}_{h(X)}
  \]
\end{proof}

\begin{example}
  Suppose $Y$ is a gaussian with mean $\mu$ and variance $\sigma^2$ then $Y=\sigma X + \mu$ where $X$ is $N(0,1)$

  \[
    h(Y) = h(\sigma X) = \log \sigma + h(X)
  \]

  \[
    h(X) = \int \frac 1 {\sqrt{2\pi}} e^{-\frac {x^2} 2} \left[ \log \sqrt{2\pi} + \frac 1 2 x^2 \log e \right] dx
    \overeq{(a)} \frac 1 2 \log 2\pi + \frac 1 2 \log e = \frac 1 2 \log 2\pi e
  \]
  Where the second term of (a) follows from $\Ex{X^2} = 1$.
\end{example}

\begin{lemma}
  Suppose $X$ is a real value random variable with differentiable entropy $h(X)$. Consider a $\delta > 0$ and $X_\delta$, the quantization of $X$ in interval of width $\delta$
  \[
    X_\delta = \delta \left\lfloor \frac X \delta \right\rfloor = n\delta \text{ if } n\delta \leq X \leq (n+1) \delta
  \]
  then
  \[
    \lim_{\delta \to 0} H(X_\delta) + \log \delta = h(X)
  \]
\end{lemma}

\begin{proof}
\begin{align*}
  H(X_\delta) &= \sum_n \Pr{X_\delta = n\delta} \log \frac 1 {\Pr{X_\delta = n\delta}}\\
  &\approx \sum_n \delta f_X(n\delta) \log \frac 1 {\delta f_X(n\delta)}\\
  &= \log \frac 1 \delta + \sum_n \left(f_X(n\delta) \log \frac 1 {f_X(n\delta)} \right)\delta\\
  &\overeq{(a)} \log \frac 1 \delta + \int f(x) \log \frac 1 {f(x)} dx\\
\end{align*}
We recognize a Riemann sum for equality (a).
\end{proof}


% ------------------------------------
%   Sebastien - 15/11/2017


Suppose $X_1 ... X_n$ are $\R$-valued RV's ($X^n \in \R^n$), we define

\[
  h(X^n) = h(X_1 ... X_n) = \underbrace{\int \int}_{\R^n} f_{X^n} (x_1 ... x_n) \log \frac{1}{f_{X^n}(x_1 ... x_n)} dx_1...dx_n
\]
\[
  h(X|Y) = \int \int f_{XY}(x, y) \log \frac{1}{f_{XY}(X|Y)} dx dy = \Ex{\log \frac{1}{f_XY(X | Y)}}
\]

\begin{theorem}
  \[
    h(X^n) = \sum_{i = 1}^n h(X_i | X^{i - 1})
  \]
  \begin{proof}
    \[
      f_{X^n}(x_1 ... x_n) = f_{x_1}(x_1) f_{x_2 | x_1}(x_2 | x_1) ... f_{x_n | x^{n-1}}(x_n | x^{n-1})
    \]
    take log's, take expectation
  \end{proof}
\end{theorem}

\begin{definition}
  Given two densities $f(x), g(x)$, let
  \[
    D(f || g) = \int f(x) \log \frac{f(x)}{g(x)} dx
  \]
\end{definition}

\begin{lemma}
  \[
    D(f || g) \geq 0
  \]
  with equality iff $f = g$
  \begin{proof}
    use $\ln(z) \leq z - 1$ to show that $-D(f||g) \leq 0$
  \end{proof}
\end{lemma}

\begin{definition}
  For $X, Y$ $\R$-valued RV's, define
  \begin{align*}
    I(x ; Y) &= \int f_{XY}(x,y) \log \frac{f_{XY}(x, y)}{f_X(x) f_Y(y)} dy \\
    &= D(f_{XY} || f_X(x) f_Y(y)) \\
    &= h(X) + h(Y) - h(XY) \\
    &= h(X) - h(X | Y) \\
    &= h(Y) - h(Y | X)
  \end{align*}
\end{definition}

\begin{proposition}
  \[
    I(X ; Y) \geq 0 \quad (=0 \text{ iff } X \bot Y)
  \]
  \begin{proof}
    \[
      I(X ; Y) = D(f_{XY} || f_x f_y)
    \]
  \end{proof}
  \textit{Equivalently}: $h(X | Y) \leq h(x)$, with equallity iff $X$ and $Y$ independent.
\end{proposition}

\begin{lemma}
  Given $X, Y$, $\R$-valued with joint pdf $f_{XY}$, for $\delta > 0$, define $X_{\delta}, Y_{\delta}$ as $X_{\delta} = \delta \lfloor \frac{X}{\delta} \rfloor, Y_{\delta} = \delta \lfloor \frac{Y}{\delta} \rfloor$, then
  \[
    \underbrace{I(X_{\delta}; Y_{\delta})}_{\text{discrete I}} \rightarrow I(X ; Y) \text{ as } \delta \rightarrow 0
  \]

  \begin{proof}
    observe
    \begin{align*}
      \Pr{X_{\delta} = n \delta} &= \Pr{X \in [n \delta, (n+1)\delta]} \equiv \delta f_X(n \delta) \\
      \Pr{Y_{\delta} = m \delta} &= \Pr{Y \in [m \delta, (m+1)\delta]} \equiv \delta f_Y(m \delta) \\
      \Pr{X_{\delta} = n \delta, Y_{\delta} = m \delta}
      &= \Pr{X \in [n \delta, (n+1) \delta], Y \in [m \delta, (m+1)\delta]} \equiv \delta^2 f_{XY}(n \delta, m \delta)
    \end{align*}

    \begin{align*}
      I(X_{\delta} ; Y_{\delta})
      &= \sum_{n, m} \Pr{X_{\delta} = n \delta, Y_{\delta} = m \delta} \log \frac{\Pr{X_{\delta} = n \delta, Y_{\delta} = m \delta}}{\Pr{X_{\delta} = n \delta} \Pr{Y_{\delta} = m \delta}} \\
      &\equiv \sum_{n, m} \delta^2 f_{XY} (n \delta, m \delta) \log \frac{\delta^2 f_{XY}(n \delta, m \delta)}{\delta f_X(n \delta) \delta f_Y(m \delta)} \\
      &\equiv \sum_{n, m} \delta^2 f_{XY} (n \delta, m \delta) \log \frac{f_{XY}(n \delta, m \delta)}{f_X(n \delta) f_Y(m \delta)} \\
      &= \text{Riemann sum for} \quad \int \int f_{XY}(x,y) \log \frac{f_{XY}(x,y)}{f_X(x) f_Y(y)}dx dy = I(X ; Y)
    \end{align*}
  \end{proof}
\end{lemma}

In general, define for $X^n \in \R^n, Y^m \in \R^m, Z^k \in \R^k$

\[
  I(X^n ; Y^m | Z^k) = \underbrace{\int ... \int}_{n + m + k} f_{X^n Y^m Z^k}(x^n, y^m, z^k) \log \frac{f_{XY|Z}(x^n y^m | z^k)}{f_{X|Z}(x^n | z^k) f_{Y|Z}(Y^m | z^k)}
\]

we then have

\begin{theorem}{Chain Rule for $I$}
  \[
    I(X^n ; Y) = \sum_{i = 1}^n I(X_i ; Y | X^{i - 1})
  \]
  \begin{proof}
    Same proof as in the discrete case
  \end{proof}
\end{theorem}

\begin{example}
  $X^n$ is a Gaussian Random Variable with $\E{X^N} = \bar{\mu}$ and variance matrix $K, K_{i,j} = \E{(X_i - \mu _i)(X_j - \mu_j)}$
  \[
    h(X^n) = \underbrace{h(X^n - \bar{\mu})}_{\text{Gaussian with zero-mean with covariance} K}
  \]

  consequently we may assume that $\bar{\mu} = \bar{0}$, recall that the joint pdf of a zero-mean gaussian is given by
  \begin{align*}
    f(\bar{x}) = \underbrace{\frac{1}{det(2 \pi K)^{1/2}}}_{(2 \pi)^{n/2} (det(K)^{1/2})} e^{0.5 (X^T K^{-1} X)}
  \end{align*}

  \[
    \log \frac{1}{f(\bar{x})} = \frac{1}{2} \log(det(2 \pi K)) + \frac{1}{2} x^T K^{-1} x(\log(e))
  \]
  \begin{align*}
    h(X) &= \Ex{\frac{1}{2} \log(det(2 \pi K)) + \frac{\log(e)}{2} x^T K^{-1} x } \\
    &= \frac{1}{2} \log(det(2 \pi K)) + \frac{\log(e)}{2} \underbrace{\underbrace{\Ex{x^T K^{-1} x}}_{tr(K^{-1}K) = tr(I_n) = n}}_{\frac{1}{2} \log(e^n)} \\
    &= \frac{1}{2} \log(det(2 \pi e K))
  \end{align*}

  \textit{Side knowledge}:
  \begin{align*}
    \Ex{X^T A X} = \Ex{\sum_{i,j} X_i A_{ij} X_j} = \sum_{i, j} A_{ij} \Ex{X_i X_j}
    = \sum_{i,j} A_{ij} K_{ij} = \sum_i (\sum_j A_{ij} K_{ij}) = tr(AK)
  \end{align*}
\end{example}

\begin{theorem}
  Suppose $X \in \R^n$ is a random vector with
  \[
    \Ex{X_i X_j} = k_{ij}
  \]
  Then
  \[
    h(X) \leq \frac{1}{2} \log(det(2 \pi e K))
  \]
  (Gaussians have maximum entropy among Random vectors with a given 2nd moment)
\end{theorem}

\begin{proof}
  Let $f$ be the density of $X^n$, let g be the gaussian density
  \[
    g(x) = \frac{1}{det(2 \pi K)^{1/2}} e^{-\frac{1}{2}(x^T K^{-1} x)}
  \]
  observe that $\log \frac{1}{g(x)} = \frac{1}{2} \log(det(2 \pi K) + \frac{1}{2} \log(2) x^T K^{-1} x$
  so
  \begin{align*}
    \int f(\bar{x}) \log \frac{1}{g(x)} d \bar{x} = \frac{1}{2} \log(det(2 \pi K)) + \frac{\log(e)}{2} \underbrace{\Ex{x^T K^{-1} x}}_{n}
    = \int g(x) \log \frac{1}{g(x)} dx
  \end{align*}
  how
  \[
    0 \geq \int f(x) \log \frac{g(x)}{f(x)} dx = - \{\frac{1}{2} \log(det(2 \pi e K))\} + h(x)
  \]
\end{proof}

\textbf{Another example of maximum entropy} \\
Suppose we know that $X \in [a, b]$ with probability 1. then $h(X) \leq \log(b - a)$ equality iff $X$ is uniform on $[a, b]$.
\begin{proof}
  Let
  \[
    g(x) =
    \left\{
    \begin{array}{cc}
      \frac{1}{b - a} , & a \leq x \leq b \\
      0 , & \text{else}
    \end{array}
    \right.
\]
\[
  \int f(x) \log \frac{1}{g(x)} dx = \log(b - a) = \int g(x) \log \frac{1}{g(x)} dx
\]
\[
  0 \geq \int f(x) \log \frac{g(x)}{f(x)} dx = - \log(b - a) + h(X)
\]
\end{proof}


\begin{definition}[Additive Gaussian noise channel]
  An additive Gaussian noise channel is a non-discrete communication channel from $\X$ to $\Y$ such that $Y=X+Z$ where $Z$ is $N(0,\sigma^2)$.
\end{definition}

\begin{example}
  A simple encoder for this channel would be to distribute $m$ points in $\R$ such that $m_{i+1} - m_i = 100\sigma$. The decoder pick the point $m$ closest to $y$. Errrors appear with low probability because the space between point is much larger than the noise. We need a very large range of values (e.g. electrical tension) which is not feasible in practice.
\end{example}

\subsection{Channel with cost constraints}

To avoid physically unrealisable scenarios, we need to impose some kind of cost constraint in our encoder. Suppose now that we are given $b : \X \to \R$ ($b(x) = x^2$ for the previous example) that associates a cost $b(x)$ to each input symbol. When an encoder $Enc: \{ 1 \dots M \} \to \X^n$ is given, in adition to rate $R = \frac 1 n \log M$, we will also define

\[
  b(Enc(m)) = \frac 1 n \sum_{i=1}^n b(Enc(m)_i)
\]
and we let
\[
  cost(Enc) = b(Enc(m))
\]

\begin{definition}[Channel capacity with power]
Given a channel $W(y|x)$ with input $\X$, output $\Y$, $b:\X\to \R$ and $\beta \in \R$ with $\beta > \inf_x b(x)$ we define
\[
  C(W, \beta) = \sup_{x, \Ex{b(x) \leq \beta}} I(X;Y)
\]
\end{definition}

\begin{theorem}[Bad news]
  Suppose a channel $\U^L \to \X^n \xrightarrow{W} \Y^n \to V^L$ with $\frac 1 n \sum_{i=1}^n \Ex{b(X_i)} \leq \beta$ and $\bar p_e = \frac 1 L \sum_{i=1}^L \Pr{U_i \not= V_i}$. Then

  \[
    h(\bar p_e) + \bar p_e \log(|\U| - 1) \geq H - \frac L n C(W, \beta)
  \]
  with $H=\lim_{m \to\infty} \frac {H(U^m)} m$
\end{theorem}

\begin{proof}
  We know that
  \begin{align*}
    h(\bar p_e) - \bar p_e \log(|\U| - 1) &\geq \frac 1 L H(U^L| V^L)\\
    &=\frac 1 L [H(U^L) - I(U^L;V^L)]\\
    &\overset{(a)}\geq \frac 1 L [H(U^L) - I(X^n;Y^n)]\\
    &\overset{(b)}\geq H - \frac 1 L I(X^n;Y^n) \\
    &\overset{(c)}\geq H - \frac n L \frac 1 n \sum_{i=1}^N I(X_i;Y_i) \\
    &\geq H -  \frac n L \frac 1 n \sum_{i=1}^N C(W, \beta_i)\text{ with } \beta_i = \Ex{b(X_i)} \\
    &\overset{(d)}\geq H - \frac n L C\left(W, \frac 1 n \sum_{i=1}^N \beta_i\right) \\
    &\geq H - \frac n L C(W, \beta)
  \end{align*}
  where we use (a) data processing, (b) stationary sources, (c) memoryless and (d) we use the \cref{claim:concavity_inf}.
\end{proof}

\begin{claim}
  \label{claim:concavity_inf}
  $\beta \to C(W, \beta)$ is a non-decreasing concave function.
\end{claim}

\begin{proof}
  Non decreasing is clear because for $\beta_1 < \beta_2$, any $p_X$ admissible for $C(W, \beta_1)$ is also admissible for $C(W, \beta_2)$.

  For concavity, given $\beta_1, \beta_2$ and $\epsilon > 0$, find $p_{X_1}$ and $p_{X_2}$ such that
  \begin{align*}
    \left. I(X;Y) \right|_{p_{X_1}} \geq C(W, \beta_1) - \epsilon \text{ with } \Ex{b(X)}|_{p_{X_1}} \leq \beta_1\\
    \left. I(X;Y) \right|_{p_{X_2}} \geq C(W, \beta_2) - \epsilon \text{ with } \Ex{b(X)}|_{p_{X_2}} \leq \beta_2\\
  \end{align*}

  For $0 \leq \lambda \leq 1$ we define $p_X(x) = \lambda p_{X_1}(x) + (1-\lambda) p_{X_2}(x)$, then
  \[
    \Ex{b(X)}|_{p_X} = \lambda \Ex{b(X)}|_{p_{X_1}} + (1-\lambda) \Ex{b(X)}|_{p_{X_2}} \leq \lambda \beta_1 + (1-\lambda)\beta_2
  \]

  Using that $I(\cdot;\cdot)$ is concave, we get
  \[
    C(W,\lambda \beta_1 + (1-\lambda)\beta_2 ) \geq I(X;Y)|_{p_{X}} \geq \lambda I(X;Y)|_{p_{X_1}} + (1-\lambda) I(X;Y)|_{p_{X_2}} \geq \lambda C(W, \beta_1) + (1-\lambda)C(W,\beta_2) - \epsilon
  \]

  Since $\epsilon > 0$ is arbitrary, we have shown

  \[
    C(W, \lambda \beta_1 + (1-\lambda) \beta_2) \geq \lambda C(W,\beta_1) + (1-\lambda) C(W, \beta_2)
  \]
\end{proof}

\begin{theorem}[Good news]
  Given a channel $W(y|x)$ with $x \in \X$, $y \in \Y$, $b:\X \to \R$, $\beta \geq \max_x b(x)$, $\epsilon \geq 0$ and $R < C(W, \beta)$ then there is a $Enc:\{1 \dots M\} \to \X^n$ and $Dec:\Y^n \to \{0 \dots M \}$ such that
  \begin{align*}
    \frac 1 n \log M \geq R\\
    \forall m~:~p_{e,m} = \Pr{Dec(Y^n) \not = m | m \text{ is sent}} < \epsilon \\
    cost(Enc) = \max_m \frac 1 n \sum_{i=1}^n b(Enc(m)_i) < \beta + \epsilon
  \end{align*}
\end{theorem}

\begin{proof}
  Verbatim as the proof of the coding theorem without costs, namely choose a $p_X$ such that $\Ex{b(X)} \leq \beta$ and $I(X;Y) \geq R$. Construct $Enc(\cdot)$ randomly, use the tipycality decoder. Eliminate half the codewords to end up with $Enc(1) \dots Enc(M)$ with the property that
  \begin{equation}
    \label{eq:pro}
    \forall m~:~\Pr{Dec(Y^n) \not = m | m \text{ is sent}} < \epsilon
  \end{equation}
  Recall that the decoder decodes $m$ only if $(Enc(m), y^n) \in T(p_{X,Y}, n, \delta)$ in particular $Enc(m) \in T(p_X, n, \delta)$. Then \cref{eq:pro} implies that for each $m$, $Enc(m) \in T(p_X, n, \delta)$ and

  \[
    \frac 1 n \sum_{i=1}^n b(Enc(m)_i) = \frac 1 n \sum_{x\in \X} b(x) \{ \# \text{ of } i \text{ such that } Enc(m)_i = x\}
  \]

  \[
    cost(Enc) \leq \underbrace{\Ex{b(x)}}_{\leq \beta} + \delta \underbrace{\Ex{|b(X)|}}_{< \epsilon}
  \]
\end{proof}


\begin{example}
  Assume an additive Gaussian noise channel $W$, $Y=X+Z$ with $Z \sim N(0, \sigma^2)$, and $b(x) = x^2$.

  \begin{align*}
    C(W, \beta) &= \max_{X, \Ex{X^2} \leq \beta} I(X;Y) \\
    &= \max_{p_X, \Ex{X^2} \leq \beta} h(Y) - h(Y|X) \\
    &= \max_{p_X, \Ex{X^2} \leq \beta} h(Y) - h(Y-X|X) \\
    &= \max_{p_X, \Ex{X^2} \leq \beta} h(Y) - h(Z|X) \\
    &= \max_{p_X, \Ex{X^2} \leq \beta} h(Y) - h(Z) \\
    &= \left(\max_{p_X, \Ex{X^2} \leq \beta} h(X+Z)\right) - h(Z) \\
    &= \left(\max_{p_X, \Ex{X^2} \leq \beta} h(X+Z)\right) - \frac 1 2 \log(2\pi e \sigma^2) \\
    &\overset{(a)}\leq \frac 1 2 \log \pfrac{2\pi e (\beta + \sigma^2)}{2\pi e\sigma^2}\\
    &= \frac 1 2 \log \left(1 + \frac \beta {\sigma^2}\right)
  \end{align*}

  For (a), note that
  \[
    \Ex{(X+Z)^2} = \Ex{X^2} + \sigma^2 \leq \beta + \sigma^2 \to h(X+Z) \leq \frac 1 2 \log (2\pi e (\beta + \sigma^2))
  \]
  On the other hand, for $X \sim N(0, \beta)$, we have $\Ex{X^2}\leq \beta$. $X+Z$ is $N(0, \beta+\sigma^2)$ so

  \begin{align*}
    &h(X+Z)~=~\frac 1 2~\log~2\pi~e~(\beta~+~\sigma^2)\\
\Rightarrow&\max_{p_X, \Ex{X^2} \leq \beta} h(X+Z) \geq \frac 1 2 \log \frac {\beta + \sigma^2} {\sigma^2}
  \end{align*}
  Then
  \[
    C(W,\beta)= \frac 1 2 \log\left(1 + \frac \beta {\sigma^2} \right) = \frac 1 2 \log(1 + \text{signal to noise ratio})
  \]
  This formula is well known in industry and abused for other channels. Do not do that!
\end{example}



% ----------------------------
%   Sebastien 11.22.2017

\subsection{$K$ independant gaussian noice channel}

Let's study the channel $W$ such that $\vec{X} \to \vec Y = \vec X + \vec Z$ with

\[
  \vec{Z} \sim N(\vec{0}, diag(\vec{\sigma^2}))
\]

\[
  b(\vec{x}) = \sum_{i = 1}^k X_i^2
\]

\begin{align*}
  &C(X^k \rightarrow Y^k = X^k + Z^k, \beta) = \max_{p_{X^k}, \Ex{||X^k||} \leq \beta} I(X^k, Y^k) \\
  & \text{ with } I(X^k, Y^k) = h(Y^k) - h(Y^k | X^k) \leq \sum_{i = 1}^k \underbrace{(h(Y_i) - h(Z_i))}_{I(X_i, X_i + Z_i)} \\
  & \text{ with } h(Y^k | X^k) = h(Y^k - X^k | X^k) = h(Z^k) = \sum_{i = 1}^k h(Z_i)
\end{align*}

with equality if $X_i$'s are independent

\[
  C(X^k \rightarrow Y^k = X^k + Z^k, \beta) \leq \sum_{i = 1}^k \frac{1}{2} \log \left(1 + \frac{\beta_i}{\sigma^2_i}\right) \quad \text{ with } \beta_i = \Ex{X_i^2}
\]

with equality when $X_i \sim N(0, \beta_i)$

\[
  C(X^k \rightarrow Y^k = X^k + Z^k, \beta) = \max_{\beta_1, ..., \beta_k \geq 0, \sum \beta_i = \beta} \sum_{i = 1}^k \frac{1}{2} \log \left(1 + \frac{\beta_i}{\sigma^2_i} \right)
\]

\[
  C(\beta) = \max_{f_1, ..., f_k \geq 0, \sum f_i = 1} \sum_{i = 1}^k \frac{1}{2} \log \left(1 + \frac{f_i \beta_i}{\sigma^2_i} \right)
\]

thus, we are maximazing a concave function on the simplex, so the optimal $f_i$ satisfies: \textit{for some $\lambda$}

\begin{align*}
  \frac{d}{d f_j} \sum_{i + 1}^k \frac{1}{2} \log(1 + f_i \frac{\beta}{\sigma_i^2}) &\leq \lambda \text{ for all $j$}\\
              &= \lambda \text{ when } f_j > 0
\end{align*}

\[
  \frac{1}{2} \frac{\frac{\beta}{\sigma^2_j}}{1 + f_j \frac{\beta}{\sigma^2_j}} = \frac{\beta}{2} - \frac{1}{\sigma_j^2 + \beta_j}
\]

Using the change of variable $\mu = 1 / \lambda$, the optimal $\{\beta_j\}$ satisfies

\begin{align*}
  \beta_j + \sigma_j^2 &\geq \mu \text{ for all } j \\
                       &= \mu  \text{ for } j \text{ s.t } \beta_j > 0 \\
                       & \equiv \beta_j = \mu - \sigma_j^2
\end{align*}

\begin{notation}
  \begin{align*}
    a^+ \equiv
    \left\{
    \begin{array}{l l}
      a, & \text{ if } a > 0 \\
      0, & \text{else}
    \end{array}
    \right.
  \end{align*}
\end{notation}

So, in terms of $\mu$, we have

\[
  \beta = \sum_i(\mu - \sigma^2_i)^+
\]

\[
  C(\beta) = \sum_i \underbrace{\log(1 + \frac{(\mu - \sigma_i^2)^+}{\sigma_i^2})}_{(\log \frac{\mu}{\sigma^2_i})^+} = \sum_i \left(\log \frac{\mu}{\sigma^2_i}\right)^+
\]

"Water filling" solution pour water of volume $\beta$ to the basin with altitude map given by $\sigma^2_i$'s


% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Elementary Coding Theorem}

\begin{wikipedia}
  The object of coding is to introduce redundancy so that even if some of the information is lost or corrupted, it will still be possible to recover the message at the receiver.
\end{wikipedia}

Restrict ourselves to Binary Symmetric and Binary Erasure Channel. Suppose
\[
  Enc: \{1, ..., M\} \rightarrow \{ 0, 1\}^n, n = 1000, rate = \frac{1}{2}
  \Rightarrow n = 2^{500}
\]

Even the encoding table taken $1000 \cdot 2^{500}$ bits of memory.

We need structure in the $Enc$, let us try linear structures.

\[
  Enc(b_1, ..., b_k) = matrix(n, k) \times \vec{b}
\]

with $k = \log(M)$

\begin{example}
  Consider $\vec{X} = \{ X_1, ..., X_7\}$ s.t.

  \begin{align*}
    &\left[
    \begin{array}{c c c c c c c}
      1 & 0 & 0 & 1 & 1 & 0 & 1 \\
      0 & 1 & 0 & 1 & 0 & 1 & 1 \\
      0 & 0 & 1 & 0 & 1 & 1 & 1
    \end{array}
    \right]
    \left[
    \begin{array}{c}
      X_1 \\
      . \\
      . \\
      . \\
      X_7
    \end{array}
    \right]
    =
    \left[
    \begin{array}{c}
      0 \\
      0 \\
      0
    \end{array}
    \right] \\
    &\equiv
    \begin{array}{l l}
      X_1 = X_4 + X_6 + X_7 \\
      X_2 = X_4 + X_5 + X_7 \\
      X_3 = X_5 + X_6 + X_7
    \end{array}\\
    &\equiv
    \left[
    \begin{array}{c}
      X_1 \\
      . \\
      . \\
      . \\
      X_7
    \end{array}
    \right]
    =
    \left[
    \begin{array}{c c c c}
      1 & 0 & 1 & 1 \\
      1 & 1 & 0 & 1 \\
      0 & 1 & 1 & 1 \\
      1 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 \\
      0 & 0 & 1 & 0 \\
      0 & 0 & 0 & 1 \\
    \end{array}
    \right]
    \left[
    \begin{array}{c}
      X_4 \\
      X_5 \\
      X_6 \\
      X_7
    \end{array}
    \right] \\
    &\equiv Enc(
    \left[
    \begin{array}{c}
      b_1 \\
      b_2 \\
      b_3 \\
      b_4
    \end{array}
    \right]
    )
  \end{align*}
\end{example}

What is the rate of this code?

\[
  \frac{4}{7} = \frac{\# \text{bits of input to Enc}}{\# \text{bits of output to Enc}}
\]

Is there a codeword of $\underbrace{\text{weight}}_{\# \text{of 1's}} = 1$?
No because no column of the matrix is $\{0, 0, 0\}$

Is there a codeword of weight $= 2$? No because no two columns of $H$ are equal.

\begin{definition}
  Given two vectors $X, X' \in \F^n_2$, the Hamming distance is
  \[
    d_H(X, X') = \sum_{i = 1}^n \I\{ x_i \neq x_i'\}
  \]
\end{definition}

\begin{definition}
  Given $x \in \F_2^k$, its Hamming weight is
  \[
    w_H(X) = d_H(X, 0)
  \]
\end{definition}

\textbf{Remarks}: \\
\[
  d_H(X, X') = w_H(X + X')
\]
because $X_i + X_i' = 0 \Leftrightarrow X_i = X_i'$

$d_H$ is a metrix
\begin{enumerate}
  \item $d_H(X, X') \geq 0$ \\
  \item $d_H(X, X') = d_H(X', X)$
  \item $d_H(X, Z) \leq d_H(X, Y) + d_H(Y, Z)$
\end{enumerate}

For the example

\[
  H
  \left[
    \begin{array}{c}
      X_1 \\
      . \\
      . \\
      . \\
      X_7
    \end{array}
  \right]
  =
  \left[
    \begin{array}{c}
      0 \\
      0 \\
      0
    \end{array}
  \right]
\]

suppose $X$ is a codeword $(HX = 0)$ and $X'$ is a codeword $(H X' = 0)$, then $X + X'$ is a codeword $H(X+ X') = HX + HX' = 0$ (codewords from a linear space)

We saw that there are no codewords of weight $1$ or $2$.

So, if $X$ and $X'$ are codewords

\[
  w_H(X+X') = d_H(X, X') \neq 1,2
\]

\[
  \Rightarrow \min_{X, X', X \neq X'} d_H(X, X') \geq 3
\]
and in fact $ = 3$.

For each codeword $X$, consider $\underbrace{B}_{\text{ball}}(\underbrace{X}_{\text{center}}, \underbrace{1}_{\text{radius}}) = \{Y \in \F^7_2 : d_H(X, Y) \leq 1 \}$

\[
  \Rightarrow \text{ if } X \neq X', \text{ then } B(X, 1) \cup B(X', 1) = \emptyset
\]

Also, $|B(X, 1)| = \underbrace{1}_{X} + \underbrace{7}_{\text{ all } Y \text{'s at } d_H = 1}$

There are 16 coderwords:

\[
  | \bigcup_{X \in \text{codewords}} B(X, 1) | = 16 * 8 = 128
\]

So we conclude that

\[
  \bigcup_{X \in \text{codewords}} B(X, 1) = \F_2^7
\]

meaning that we have perfect cover of $\F_2^7$ with disjoint spheres.

For this reason the code described by it is called a perfect code.

The code we are discussing is called

\[
  (\underbrace{7}_{\text{length}}, 4, \underbrace{3}_{\text{minimal distance}})-\text{Hamming code}
\]


% -------------------------
%  JB - 11.27.2017


% \begin{example}
%   $(7, 4, 3)$ Hamming code. All code words $x \in \F_2^7$ satisfy $Hx = 0$ with
%   \[
%     H=\begin{bmatrix}
%       1&0&0&0&1&1&1\\
%       0&1&0&1&0&1&1\\
%       0&0&1&1&1&0&1\\
%     \end{bmatrix}
%   \]
%   We saw there are $2^4$ code words.
% \end{example}

% \begin{observation}
%   In general if $H \in \F_2^{m\times n}$ has rank $r$ then we will have $2^{n-r}$ solutions to $Hx=0$.
% \end{observation}

% \begin{observation}
% Codewords form a linear space (i.e. $x+x'$ is a codeword for all $x,x' \in F_2^n$)
% \end{observation}

Let's extend the Hamming code to more general parameters $(2^{m}-1, 2^m - 1 - m, 3)$. Then H is a matrix $F_2^{m\times2^m-1}$.$\{B(x,1) : x \text{ is a codeword}\}$ form a disjoint collection and

\[
  |B(x,1)| = 1 + (2^m - 1) = 2^m
\]
\[
  | \bigcup B(x,1) | = 2^{2^m - 1 - m} \cdot 2^m = 2^{2^n -1} = | \F_2^{2^m - 1} |
\]

\begin{theorem}[Sphere packing bound]
  Suppose we have a code in $\F_2^n$ with $M$ codewords and the Hamming distance between codewords is
  \[
    d = \min_{x\not=x'} d_H(x,x')
  \]
  then
  \[
    2^m \geq M \sum_{i=0}^{\left\lfloor \frac {d-1} 2 \right \rfloor} {n \choose i}
  \]
\end{theorem}

\begin{proof}
  The balls of radius $\left\lfloor \frac {d-1} 2 \right \rfloor$ around each codeword are distinct (because any two words are more than $d$ appart).
  \[
    2^n
    = |\F_2^n| \geq \left| \bigcup_x B\left(x, \left\lfloor \frac {d-1} 2 \right \rfloor\right) \right|
    = \sum_x \left| \bigcup_x B\left(x, \left\lfloor \frac {d-1} 2 \right \rfloor\right) \right|
    = M \sum_{i=0}^{\left\lfloor \frac {d-1} 2 \right \rfloor} {n \choose i}
  \]
\end{proof}

\begin{theorem}[Gilbert bound]
  Given $n,d$ there is a code in $\F_2^n$ with min distance $\geq 2$ and numbers of codewords $M$ with
  \[
    M\sum_{i=0}^{d-1} {n \choose i} \geq 2^n
  \]
\end{theorem}

\begin{proof}~\\
  \begin{algorithm}[H]
 % \KwData{this text}
 % \KwResult{how to write algorithm with \LaTeX2e }
 $S \leftarrow F_2^n$\;
 \While{$S \not = \emptyset$}{
  pick $x \in S$ as a codeword\;
  $S \leftarrow S \setminus B(x, d-1)$\;
 }
\end{algorithm}
\end{proof}

\begin{observation}
  Suppose we are in $\F_q^n$, we can define the Hamming distance
  \[
    d_H(x, x') = \I_{x_i \not = x_i'}
  \]
  and
  \[
      |B(x,r)| = \sum_{i=0}^r {n \choose i} (q-1)^i
    \]
\end{observation}

\begin{theorem}[Singleton bound]
  Suppose we have a code in $\F_2^n$ with $M > 2^k$ codewords. Then the code has minimum distance $\leq n - k$ (i.e. there are $x\not = x$ codewords with $d_H(x,x' \leq n-k)$).
\end{theorem}

\begin{proof}
  Split words of length $n$ in two parts (of length $n-k$ and $k$). There are $2^k$ possible right halves but $> 2^k$ codewords. By pigeon hole principle, there exists two codewords $x\not = x'$ with the same right half thus $d_H(x,x') \leq n-k$ (left half part is fully changed).
\end{proof}


\subsection{Linear code}

\begin{definition}
  A collection $\C \subseteq \F_2^n$ of code words form a linear code if $\C$ is a vector space over $\F_2$ (i.e. $x,x' \in \C \to x+x' \in \C$).
\end{definition}

\begin{observation}
  The previous definition implies that $0 \in \C$, $-x \in \C$ and $ax +a'x' \in \C \forall a,a' \in \F_2$
\end{observation}

\begin{definition}
  For any collection $\C$, define
  \[
    d_{\min}(\C) = \min_{x,x'\in \C, x\not=x'} d_H(x,x')
  \]
\end{definition}

\begin{lemma}
  if $\C$ is a linear code, then
  \[
    d_{\min}(\C) = w_{\min}(\C) \triangleq \min_{x\in \C, x \not=0} w_H(x)
  \]
\end{lemma}

\begin{proof}
  Let $x, x'\in \C$ have
  \[
    d_H(x,x') = d_{\min} \Rightarrow w_H(x+x') = d_{\min} \Rightarrow w_{\min} \leq d_{\min}
  \]
  Also let $x\in \C$ with $w_H(x) = w_{\min}$ then
  \[
    d_H(0,x) = w_{\min} \Rightarrow d_{\min}(\C) \leq w_{\min}(\C)
  \]
\end{proof}


\begin{fact}
  if $\C$ is a linear code in $\F_2^n$, then there is a matrix $G\in \F_2^{n\times k}$ (called the generator matrix) so that $\C = \{G_u : u \in \F_2^k \}$ in particular $|\C| = 2^k$. One can even pick $G$ to be of the form
  \[
    G=\begin{bmatrix}
      I_k\\
      A_{n-k\times k}
    \end{bmatrix}
  \]
  and its row permutations.
\end{fact}

\begin{consequence}
  if $\C$ is a linear code in $\F_2^n$, then there is a matrix $H \in \F_2^{n\times n}$ such that $\C = \{ x \in \F_2^n : H x = 0 \}$. One can even choose $H$ or some column permutation of
  \[
    H = \begin{bmatrix}
      I_r|A_{r \times n-r}
    \end{bmatrix}
  \]
  so that $|\C| = 2^{n-r} = 2^k$
\end{consequence}


\begin{proof}
  \[
    \text{If } G = \begin{bmatrix}
      I_k\\
      A
    \end{bmatrix} \text{ then } \C = \left\{ \begin{bmatrix}
      u\\ A_u
    \end{bmatrix} : u \in \F_2^k \right\}
    \text{ i.e. } x\in \C \iff \begin{bmatrix}
      1\\ \vdots\\x_k\\x_{k+1}\\ \vdots\\x_n
    \end{bmatrix} \text{ has } \begin{bmatrix}
      x_{k+1}\\ \vdots\\ x_n
    \end{bmatrix} = A \begin{bmatrix}
      x_{1}\\ \vdots\\ x_k
    \end{bmatrix}
  \]
  \[
    \iff I_{k-n} \begin{bmatrix}
      x_{k+1}\\ \vdots\\ x_n
    \end{bmatrix} = A \begin{bmatrix}
      x_{1}\\ \vdots\\ x_k
    \end{bmatrix}
    \iff
    \underbrace{[A~|~-I_{k-n}]}_{H}\begin{bmatrix}
      x_1\\x_k\\x_{k+1}\\x_n
    \end{bmatrix} =
    \begin{bmatrix}
      0\\ \vdots \\ 0
    \end{bmatrix}
  \]
\end{proof}

\begin{theorem}[Gilbert-Varshanov]
  Given $n,d$ there is a linear code in $\F_2^n$ with $\geq 2 ^{n-r}$ codewords, provided that
  \[
    \sum_{i=0}^{d-2} {n-1 \choose i} < 2^n
  \]
\end{theorem}




% -------------------------
%  Sebastien - 11.28.2017

Suppose a code has a minimum distance $d$, and we use this cod over the BSC. At the decoder, given the received $y^n$, decode it to the "nearest" codeword (in $d_H$). Then, if the channel flips $< \frac{d}{2}$ input symbols, we will decode correctly.

\subsubsection*{Relationship between the parity check $H$ and $d_min$, $\#$ of codewords}

Recall $\C = \{ x: Hx = 0\}$, e.g. $(7,4,3)-$Hamming code: 3 equations, also called the parity-check equations. The matrix $H$ is sometime called the parity-check matrix. Recall also that $d_{min} = w_{min}$.

Suppose $H$ has the property that any $k$ columns are linearly independent. Can there be a non-zero codeword with weight $\equiv k$? No

For such an $x$, $Hx $ is a linear combination with weights $x$  of the columns of $H$. Such a combination $\neq 0$

Thus $w_min > k$

Suppose there exists $l$ columns of $H$ which are linearly dependent $\Rightarrow \exists x \neq 0$ with weight $w(x) \leq l$ such that $Hx = 0$. Thus $w_{min} \leq l$

\begin{theorem}
  The code $C = \{ x: Hx = 0 \}$ has minimum distance $d$ if and only if any collection of $d-1$ columns of $H$ are linearly independent, and some $d$ columns are linearly independent.
\end{theorem}

\begin{theorem}
  Suppose the matrix $H \in \F_2^{m \times n}$ has rank $r$. Then $C = \{ x: Hx = 0 \}$ has $2^{n - r}$ codewords.
\end{theorem}

\subsubsection{Revisit the singleton bound for general alphabet}

Recall $d_H(x, x') = \sum_{i = 1}^n \I(x_i \neq x_i')$ with $x, x'\in \X^n$

\textbf{Singleton bound}: Suppose $C \subset \X^n, |C| > |X|^k$ then
\[
  d_{min}(c) \leq n - k
\]

\begin{proof}
  same as in the binary case.
\end{proof}

\begin{definition}{Reed-Solomon Codes}
  are a family of codes for which the Singleton bound is tight. (they will have $|X|^{k+1}$ codewords and $d_{min} = n - k + 1$)
\end{definition}

\textbf{Construction of R-S code}: we are given a set $\F$, a field with $+, \cdot$ operator defined. (typically $\F = \{ 0, 1 \}^l, l = 8, 16$ is usual), let $q = |\F|$.

We will construct a binary code $C \subset \F^n$ with $n \leq q$, with $|C| = q^k, d_{min}(C) = n - k + 1$. To do so, we will pick $\alpha_1, ... , \alpha_n \in \F$ all distinct. The code then will be the following:

for each $(u_0, ..., u_{k-1}) \in \F^k$ we will define $u(D) = u_0 + u_1 D + u_2 D^2 + ... + u_{k-1} D^{k-1}$, and construct $x(u) \in \F^n$ with

\[
  x(u) = (u(\alpha_1), ..., u(\alpha_n))
\]

and $ \C = \{ x(u): u \in \F^k \}$

\textbf{Observation}: Suppose $u \in \F^k, \tilde{u} \in \F^k, u \neq \tilde{u}$
\begin{align*}
  x(u) - x(\tilde{u}) &= u(\alpha_1) - \tilde{u}(\alpha_1), ..., u(\alpha_n) - \tilde{u}(\alpha_n)) \\
  v = u - \tilde{u} \Rightarrow (v(\alpha), ..., v(\alpha_n))
\end{align*}

Where $v(D) = v_0 + v_1 D + ... + v_{k-1} D^{k-1}$ a polynomial of degree $\leq k-1$, with at most $k-1$ roots.

$v$ has atmost $k-1$ entries. Therefor it has at least $n - k + 1$ non-zero entries.

Thus

\[
  x(u) \neq x(\tilde u) \Rightarrow |C| = q^k
\]
and $d_{min} \geq n - k + 1$ (actually equal because singleton bound says $d_{min} \leq n - k + 1$)

Furthermore, if $x \in C, \tilde{x} \in C$, if $a, \tilde{a} \in \F$, then $ax + \tilde{a} \tilde{x} \in C$, because $x = x(u), \tilde{x} = x(\tilde{u})$ then $ax + \tilde{a} \tilde{x} = x(a u +  \tilde{a} \tilde{x})$, so $C$ is a linear code.

\begin{example}
  $\F = \{ 0, 1, 2 \}, n = 3, \alpha_1 = 0, \alpha_2 = 1, \alpha_3 = 2$ with $mod 3$ addition and multiplication

  \begin{align*}
    \begin{array}{c c | c || c c c }
      u_0 & u_1 & u(D) & & x(u) \\
      \hline
     0 & 0 & 0      & 0 & 0 & 0  \\
     0 & 1 & D      & 0 & 1 & 2  \\
     0 & 2 & 2D     & 0 & 2 & 1  \\
     1 & 0 & 1      & 1 & 1 & 1  \\
     1 & 1 & 1 + D  & 1 & 2 & 0  \\
     1 & 2 & 1 + 2D & 1 & 0 & 2  \\
     2 & 0 & 2      & 2 & 2 & 2  \\
     2 & 1 & 2 + D  & 2 & 0 & 1  \\
     2 & 2 & 2 + 2D & 2 & 1 & 0  \\
    \end{array}
  \end{align*}
\end{example}

In general, if we are given an $X$ with $|X| = p^l$ with $p$ prime, we identify $X$ with $\F_p^l$

$\rightarrow$ polynomials over $\F_q$ of degree $< l - 1$ with addition modulo $p$ and multiplication modulo a suitably chosen polynomial of degree $l$.


\subsubsection{Polar codes}

Channel 1:

\[
  y_0 \cap y_1 = \emptyset~~~C(W)=1
\]
Easy to achieve capacity: send unencoded binary data

Polar cosing is a technique to convert $n$ copies of a "mediocre" channel $W$ to $n$ extremal channels, while preserving the total capacity

$2\times 2$ building blocks:

\begin{align*}
  \begin{bmatrix}
    X_1\\X_2
  \end{bmatrix}
  &=
  \begin{bmatrix}
    1 & 1 \\ 0 & 1
  \end{bmatrix}
  \begin{bmatrix}
    U_1 \\ U_2
  \end{bmatrix}\\
  \begin{bmatrix}
    U_1\\U_2
  \end{bmatrix}
  &=
  \begin{bmatrix}
    1 & 1 \\ 0 & 1
  \end{bmatrix}
  \begin{bmatrix}
    X_1 \\ X_2
  \end{bmatrix}\\
  \begin{matrix}
  X_1 = U_1 \oplus U_2\\
  X_2 = U_2
  \end{matrix} &\iff
  \begin{matrix}
  U_1 = X_1 \oplus X_2\\
  U_2 = X_2
  \end{matrix}\\
  \Rightarrow I(U_1U_2;Y_1Y_2) = I(X_1 X_2 ; Y_1Y_2)
\end{align*}

\[
  U_1U_2 \text{ i.i.d. } \sim B\pfrac 1 2 \Rightarrow
  \begin{array}{cc|c}
    U_1 & U_2 & p\\
    \hline
    0 & 0 & 1/4\\
    0 & 1 & 1/4\\
    1 & 0 & 1/4\\
    1 & 1 & 1/4
  \end{array}
  \Rightarrow
  \begin{array}{cc|c}
    X_1 & X_2 & p\\
    \hline
    0 & 0 & 1/4\\
    0 & 1 & 1/4\\
    1 & 0 & 1/4\\
    1 & 1 & 1/4
  \end{array}
  \Rightarrow
  X_1, X_2 \text{ i.i.d.} \sim B\pfrac 1 2
\]

\begin{align*}
  I(X_1X_2; Y_1Y_2) &\overset{(\ast)}= I(X_1; Y_1 ) + I(X_2;Y_2) = 2I(W)\\
  I(U_1U_2; Y_1Y_2) &= I(U_1; Y_1Y_2) + I(U_2; Y_1Y_2|U_1)\\
  &\triangleq I(W^-) + I(W^+)
\end{align*}
where $(\ast)$ is because $X$'s are i.i.d.

\begin{align*}
  W^- : U_1 \rightarrow Y_1Y_2,~ W^-(y_1y_2| u_1) &= \frac 1 2 \Pr{Y_1Y_2 = y_1y_2 | X_1X_2 = U_10} +
  \frac 1 2 \Pr{Y_1Y_2 = y_1y_2 | X_1X_2 = \bar U_1 1}\\
  &= \frac 1 2 W(y_1|u_1) W(y_2|0) + \frac 1 2 W(y_1|\bar u_1)W(y_2|1)\\
\end{align*}

\begin{align*}
  W^+ : U_2 \rightarrow Y_1Y_2U_1,~ W^+(y_1y_2| u_2) &= \frac 1 2 \Pr{Y_1Y_2 = y_1y_2 | X_1 = u_1 + u_2, X_2 = u_2} \\
  &= \frac 1 2 W(y_1|u_1 + u_2) W(y_2|u_2)
\end{align*}

\textbf{Question: } Are $W^-$ and $W^+$ real ?

In the general case, say $U_1U_2\dots U_n$\\
\emph{Oracle aided decoder}
\begin{align*}
  \hat U_1 &= \Phi_1(Z)\\
  \hat U_2 &= \Phi_2(ZU_1)\\
  \hat U_3 &= \Phi_3(ZU_1 U_2)\\
  &~~\vdots\\
  \hat U_n &= \Phi_n(ZU_1U_2\dots U_{n-1})\\
\end{align*}
\emph{Unaided decoder} (with same $\Phi_i$'s as the oracle aided decoder)
\begin{align*}
  \tilde U_1 &= \Phi_1(Z)\\
  \tilde U_2 &= \Phi_2(Z\tilde U_1)\\
  \tilde U_3 &= \Phi_3(Z\tilde U_1 \tilde U_2)\\
  &~~\vdots\\
  \tilde U_n &= \Phi_n(Z\tilde U_1\tilde U_2\dots \tilde U_{n-1})\\
\end{align*}

Suppose that
\begin{align*}
  \hat U ^ n = U^n &\Rightarrow \tilde U_1 = \hat U_1 = U_1\\
  &\Rightarrow \tilde U_2 = \Phi_2(Z\tilde U_1 = U_1) = \hat U_2 = U_2\\
  &\Rightarrow \tilde U _3 = \Phi_3(Z,\tilde U_1 \tilde U_2 = U_1 U_2) = \tilde U_3 =U_3\\
  &\Rightarrow \dots
\end{align*}

Check that $\hat U^n \not = U^n \Rightarrow \tilde U^n \not = U^n$

\[
  \Rightarrow \Pr{\hat U ^n = U^n} = \Pr{\tilde U^n = U^n}
\]

If we decide $U_1$ first ($\equiv$ decode $W^-$ first) and use the decision $\tilde U_1$ as if it were true (as if it was the oracle's answer) when decoding $W^+$. So $W^+$ is a "real" channel.

So far $2I(W) = I(W^-) + I(W^+)$

\begin{example}
  $W=\text{BEC}(p)$
  \[
    Y_1 = \begin{cases}
      X_1 & \text{ with probability } 1 - p\\
      ? & \text{ with probability } p
    \end{cases}
  \]

  \[
    W^-:U_1 \rightarrow Y_1 Y_2 =
    \begin{cases}
      X_1X_2 & \text{ with probability } wp(1-p)^2\\
      X_1 ? & \text{ with probability } p(1-p)\\
      ?X_2 & \text{ with probability } p(1-p)\\
      ? ? & \text{ with probability } p^2
    \end{cases}
  \]

  \[
    X_1 = U_1 \oplus U_2~~X_2=U_2
  \]

  \[
    U_1 \text{ independent of } U_2 \equiv \begin{cases}
      U_1&wp(1-p)^2\\
      ?&wp(2p-p^2)\\
      ?&wp(2p-p^2)\\
      ?&wp(2p-p^2)\\
    \end{cases} \equiv \text{BEC}(2p - p^2)
  \]

  \[
    W^+:U_2 \rightarrow Y_1Y_2U_1 = \begin{cases}
      X_1X_2U_1\\
      X+1 ? U_1\\
      ?X_2 U_1\\
      ??U_1
    \end{cases}
    \equiv
    \begin{cases}
      U_2& \text{with probability } (1-p^2)\\
      U_2& \text{with probability } (1-p^2)\\
      U_2& \text{with probability } (1-p^2)\\
      ?& \text{with probability } p^2
    \end{cases}
    \equiv
    \text{BEC}(p^2)
  \]

  $W^+$ is a much better channel than $W$. In general
  \[
    I(W^+) = I(U_2;Y_1Y_2U_1) \geq O(X_2,Y_2) = I(W) \Rightarrow I(W^-) \leq I(W) \leq I(W^+)
  \]
\end{example}

% ------------------------
% Sebastien 12.7.2017

How to decoder the output $\Y$ of a binary input channel $W$? Given $y$ (the output of $W$)

Compute $W(y|0), W(y|1)$, max likelihood decoding rule

\[
\varphi(y) =
\left\{
\begin{array}{c c}
  0 & \text{if } W(y|0) > W(y|1) \\
  1 & \text{if } W(y|1) < W(y|1) \\
\end{array}
\right.
\]


\subsubsection*{Encoding / decoding complexity}

\textbf{Encoding} complexity:
\[
  \frac{nk}{2} XOR - \frac{1}{2} n \log n
\]

\textbf{Decoding} complexity
\[
  \frac{nk}{2} proc^{-/+}
\]

We are now left with the question: does this $W$ result in extremal channel?

Restrict $W = BEC(p)$:
\begin{align*}
  & W^+ = BEC(p^2) = BEC(p(+)) \\
  & W^- = BEC(p(2-p)) = BEC(p(-)) \\
  & p(++) = (p^2)^2 \\
  & p(+-) = p^2 (2 - p^2) \\
  & p(-+) = (p(2-p))^2 \\
  & etc...
\end{align*}

Define a $BEC(p)$ to be $\epsilon$-mediocre if $p \ni (\epsilon, 1-\epsilon)$ define for a $BEC(p)$ its ugliness to be $\sqrt{4 p(1-p)}$ \\
If $W$ is $\epsilon$-mediocre then $ugl(W) \geq \sqrt{4 \epsilon ( 1 - \epsilon)}$

Suppose $W = BEC(p)$
\begin{align*}
  ugl(W^+) &= \sqrt{4 p^2 (1-p^2)}    = ugl(W) \sqrt{p (1+p)} \\
  ugl(W^-) &= \sqrt{4 p (2-p)(1-p)^2} = ugl(W) \sqrt{(2-p)(1+p)} = f(1-p)
\end{align*}

\begin{align*}
  \frac{1}{2} [ugl(W^+) + ugl(W^-)] &= ugl(W) \frac{1}{2} [f(p) + f(1-p)] \quad \text{ with } f(p) = \sqrt{p(1-p)} \\
    &\leq ugl(W) \frac{1}{2} 2 f(\frac{1}{2}) = ugl(W) \sqrt{\frac{3}{4}}
\end{align*}

\begin{align*}
  \Rightarrow \frac{1}{2^k} \sum_{s^k \in \{+, -\}^k} ugl(W^{(s^k)}) &\leq (\frac{3}{4})^{k/2} \quad \text{tends to 0 as } k \text{ gets large} \\
  &= \frac{1}{2^k} \sum_{s^k \in \{+, -\}^k} \I\{W^k \text{ is } \epsilon \text{-mediocre}\} \sqrt{4 \epsilon(1 - \epsilon)} \\
  & \Rightarrow \text{fraction of } \epsilon \text{-mediocre channel s.t. stage } k \\
  & \leq \frac{(3/4)^{k/2}}{\sqrt{4 \epsilon (1 - \epsilon)}}  \quad \text{tends to 0 as } k \text{ gets large}
\end{align*}

So we have shown the following: let $\mu_k(\epsilon)$ be the function of $\epsilon$-mediocre channels s.t. stage $k$, then
\[
  \lim_{k \to \infty} \mu_k(\epsilon) = 0
\]
$\Rightarrow$ the fraction of $\epsilon$-good channels $\rightarrow (1-p)$\\
$\Rightarrow$ the fraction of $\epsilon$-bad channels $\rightarrow p$ \\

This suggest the following coding methods: Given $R < 1 - p = C(BEC(p))$, pick $\epsilon > 0$ and $k$ large enough so that fraction of $\epsilon$-good channels is $>R$. Then


\[
  \Pr{\hat{U}^n \neq U^n} \leq \sum_{i: \epsilon\text{-good}} \Pr{\hat{U}_i \neq U_i} \leq nR \epsilon
\]

we need to show that the good channels are in fact very good.\\

For this we need

\begin{definition}
  A channel $W^k$ is called $\epsilon$-pure if for all $\sqrt{k} \leq i \leq k$, $W^{si}$ is not $\epsilon$-mediocre.

  \textit{Observation:} $\mu_i(\epsilon) \leq \frac{1}{\sqrt{4(\epsilon(k \epsilon))}}(\frac{3}{4})^{1/2}$ fraction of $\epsilon$-mediocre channels at gen $u$.

  $\Rightarrow$ fraction of $\epsilon$-inpure channels at gen $k$ is
  \[
    \leq \sum_{i = \sqrt{k}}^k \mu_i(\epsilon) \leq \sum_{i = \sqrt{2}}^{\infty} (\frac{3}{4})^i \frac{1}{\sqrt{\epsilon(1 - \epsilon)}} \leq const (\epsilon)(\frac{3}{4}^{\sqrt{k}/2}) \rightarrow 0
  \]
  $\Rightarrow$ fraction of $\epsilon$-pure channels $\rightarrow 1$ as $k$ gets large.\\

  \textit{Observation:} $p$ cannot convert good to bad, bad to good $\Rightarrow$ an $\epsilon$-pure channel comes from a set of $\epsilon$-good ancestor and $\epsilon$-good$_-$
\end{definition}


% --------------------------------
%   Sebastien 12/12/2017

% -------------------------------------------------------------------------
% -------------------------------------------------------------------------

\cleardoublepage
\section{Quantization / Rate-Distortion Theory}

We have seen (lossless) source coding

\[
  U^n \rightarrow \text{bits} \rightarrow \hat{U}^n = U^n
\]

Lossless is not possible if $U$ takes on values in $\R$. Then the question is: What is the trade-off between fidelity (how close $\hat{U}^n$ is to $U^n$) and "rate" ($\#$ of bits / source-letter)?

Consider $U_1, U_2, ...$ iid $\sim P_u$ on an alphabet $\U$. We also have a reproduction alphabet $\V$ and a function
\[
  d: \U \times \V \rightarrow \R \quad (\text{measures the penalty for reprenting } u \text{ as } v)
\]

\begin{example}
  \[
    \U = \V = \{ 0, 1 \}, \quad d(u,v) = \I\{u \neq v\}
  \]
\end{example}

\begin{example}
  \[
    \U = \V = \R, \quad d(u,v) = |u - v|^2
  \]
\end{example}

\begin{example}
  \begin{align*}
    \U = \{0, 1\}, \V = \{ 0, 1, ? \} \quad & d(0,0) = d(1,1) = 0 \\
                                            & d(0,1) = d(1,0) = 10 \\
                                            & d(0,?) = d(?,1) = 1 \\
  \end{align*}
\end{example}

\begin{definition}
  Given $\U$ and $\V$, a quantizer consists of two maps: $f$ and $\phi$
  \begin{align*}
    f: & \quad \U^n \rightarrow \{ 1, ..., n \} (\log_2 M \text{ bits description of } (U_1, ..., U_n)) \\
    \phi: & \quad \{1, ..., n \} \rightarrow \V^n
  \end{align*}
  We will assess the quality of the quantizer by
  \begin{align*}
    rate &= \frac{\log M}{n} \\
    distortion &= \E[d(U^n, \phi(f(u^n)))] \quad \text{ where } \quad d(u^n, v^n) = \sum_{i = 1}^n d(u_i, v_i)
  \end{align*}
\end{definition}

\begin{theorem}
  Suppose that for a source iid $U$ with statistics $P_u$ and distortion measure $d$, we have designed a quantizer with rate $R$, and distortion $\Lambda$. Then there is a joint distribution $P_{uv}$ such that
  \[
    \Lambda = \E[d(U, V)] \quad \text{ and } \quad R \geq I(U;V)
  \]
\end{theorem}

\begin{corollary}
  For any quantizer with distortion $\Lambda$, we will have rate
  \[
    R \geq \min_{\E[d(u,v)] = \Lambda} I(U;V)
  \]
\end{corollary}

\begin{example}
  $U$ is Gaussian $0$-mean, variance $\sigma^2$, $\V = \R$ and $d(u,v) = (u-v)^2$.\\
  Suppose $(u,v)$ is such that $\E[(u-v)^2] = \Lambda$, then
  \begin{align*}
    I(U;V) &= h(U) - h(U|V) \\
           &= h(U) - h(U-V|V) \\
           &\geq h(U) - h(U-V) \\
           &\geq h(U) - \frac{1}{2} \log(2 \pi e \Lambda) \\
           &= \frac{1}{2} \log \frac{\sigma^2}{\Lambda}
  \end{align*}
  \[
    \Rightarrow I(U;V) \geq (\frac{1}{2} \log \frac{\sigma^2}{\Lambda})^+
  \]
  Indeed
  \[
     \min_{\E[(u,v)^2] = \Lambda} I(U;V) = \frac{1}{2} \log \frac{\sigma^2}{\Lambda} \quad \text{when} \quad \Lambda \leq \sigma^2
  \]

  Recall: $I(U;V)$ as a function of $(P_u, P_{v|u})$ is concave in $P_u$ and convex in $P_{v|u}$
\end{example}

\begin{theorem}
  Given an iid source $U_1, U_2, ...$, given $d: \U \times \V \rightarrow \R$, given a $P_{uv}$ with $\E[d(U,V)] = \Lambda$ and $I(U;V) = R$, given an $\epsilon > 0$, there exists a quantizer $(f, \phi)$ with
  \[
    rate \leq R + \epsilon \quad \text{ and } \quad |distortion - \Lambda| < \epsilon
  \]
\end{theorem}

\begin{proof}
  See \textbf{chapter 10 section 4} in \textit{"Elements of information theory, second edition"}
\end{proof}


% --------------------------------
%   JB 18/12/2017

Given i.i.d. source $U_1U_2 \dots$ and a distorsion measure $d:\U \times \V \to \R$ the possible ($R$ rate, $D$ distorition) pairs are

\[
  R\geq \min_{p_{V|U} : \Ex{d(U,V)} = D} I(U;V)
\]

\begin{definition}[Rate distorsion]
  \[
    R\geq \min_{p_{V|U} : \Ex{d(U,V)} \leq D} I(U;V)
  \]
\end{definition}

\begin{example}
  When $U\sim N(0, \sigma^2)$ and $d(u,v) = (u-v)^2$
  \[
    R(D) = \left(\frac 1 2 \log \frac { \sigma^2} D \right)^+
  \]
  \[
    D(R) = \sigma^2 2^{-2R}, R \geq 0
  \]
\end{example}

\subsection{Multi party communications}

Encode two message $m_1 \in \{1, \dots, M_1\}$ and $m_2 \in \{1, \dots, M_2\}$ with two encoders $Enc_i$. Transmit with one channel and decode with onde decoder $Dec$ that gives $(\hat m_1, \hat m_2)$.

\[
  R_i = \frac 1 n \log M_i
\]
\[
  p_e = \frac 1 {M_1 M_2} \sum_{m_1, m_2} \Pr{(\hat m_1, \hat m_2) \not= (m_1, m_2) | m_1,m_2 \text{ is sent}}
\]

\begin{definition}
  Given a channel $W(y|x_1,x_2)$ (memoryless), a rate pair $(R_1, R_2)$ is said to be achievable if $\forall \epsilon > 0$ there is $(Enc_1, Enc_2, Dec)$ such that the rate of $Enc_1$ is greater that $R_1 - \epsilon$, the rate of $Enc_2$ is greater that $R_2 - \epsilon$ and $p_e \leq \epsilon$. The set of all achievable rate-pairs (for the given $W$) is denoted $C(W)$ and called the capacity region.
\end{definition}


\begin{theorem}
  Given $W(y|x_1,x_2)$ for any $p_{X_1}, p_{X_2}$ then the achievable pair rates are
  \[
    \{
      (R_1, R_2) : R_1 \leq I(X_1;YX_2), R_2 \leq I(X_2;YX_1), R_1+R_2 \leq I(X_1X_2;Y)
    \}
  \]
\end{theorem}

\begin{proof}
  Suppose we are given $W$, $p_{X_1}$ and $p_{X_2}$, $R_1 \leq I(X_1;YX_2)$, $R_2 \leq I(X_2;YX_1)$, $R_1 + R_2 \leq I(X_1X_2;Y)$. Fix $\epsilon$

  Let $M_1 = 2^{n(R_1 - \epsilon})$, $M_2 = 2^{n(R_2 - \epsilon})$, set $p_{X_1X_2Y} = p_{X_1}(x_1)p_{X_2}(x_2)W(y|x_1x_2)$. Create the random encoder with
  \[
    \{ X_{ij}(m) : i \in \{1,2\}, 0 \leq j < n, m \in M_i\} \sim p_{X_i}
  \]
\end{proof}

We use the typicality decoder: given $Y^n$ search for $\hat m_1, \hat m_2$ such that
\[
  (Enc_1^n(\hat m_1), Enc_2^n(\hat m_2), Y^n) \in T(n, \delta, p)
\]
If only one pair $(\hat m_1, \hat m_2)$ is found declare it, otherwise declare 0. We are fine concerning the rates. For the probability of error assume (w.l.o.g.) that $m_1 = 1, m_2 = 1$ is sent.

\[
  \{
    \text{error}
  \}
  =
  \{(X_1^n(1), X_2^n(1), Y^n) \not \in T\} \cup \bigcup_{(m_1',m_2') \not=(1,1)} \{(X_1^n(m_1'), X_2^n(m_2'), Y^n) \in T\}
\]

\[
  p_e = \Pr{(X_1^n(1), X_2^n(1), Y^n) \not \in T} + \sum_{(m_1',m_2') \not=(1,1)} \Pr{(X_1^n(m_1'), X_2^n(m_2'), Y^n) \in T}
\]

\[
  (m_1', m_2') \not = (1,1) \Rightarrow \begin{cases}
    m_1' = 1, m_2' \not=1, \text{genericity } (1,2), (M_2 - 1) \text{ such terms}\\
    m_1' \not= 1, m_2' =1, \text{genericity } (2,1), (M_1 - 1) \text{ such terms}\\
    m_1' \not= 1, m_2' \not=1, \text{genericity } (2,2), (M_1 - 1)(M_2 - 1) \text{ such terms}\\
  \end{cases}
\]

Then
\begin{align*}
  p_e \leq \Pr{(X_1^n(1), X_2^n(1), Y^n) \not \in T}
  & + (M_2 - 1) \Pr{(X_1^n(1), X_2^n(2), Y^n) \in T}\\
  & + (M_1 - 1) \Pr{(X_1^n(2), X_2^n(1), Y^n) \in T}\\
  & + (M_1 - 1)(M_2 - 1) \Pr{(X_1^n(2), X_2^n(2), Y^n) \in T}
\end{align*}

Given that $(X_1^n(1), X_2^n(1), Y^n)$ i.i.d. $\sim p_{X_1,X_2,Y}$ then
\[
  \lim_{n \to \infty} \Pr{(X_1^n(1), X_2^n(1), Y^n) \not \in T} = 0
\]

$(X_1^n(1), X_2^n(2), Y^n)$ i.i.d. $\sim p_{X_1,Y}p_{X_2} \triangleq q_1$ then
\[
  \Pr{(X_1^n(1), X_2^n(2), Y^n) \in T(p)} = 2^{-n(D(p||q_1) + o(\delta))}
\]

\[
  D(p||q_1) = \sum_{x_1,x_2,y} p(x_1,x_2,y) \log \frac {p(x_1,x_2,y)}{p(x1,y)p(x_2)} = I(X_2; YX_1)
\]
Similarly

\begin{align*}
    \Pr{(X_1^n(2), X_2^n(1), Y^n) \in T(p)} = 2^{-n(I(X_1;YX_2) + o(\delta))}\\
    \Pr{(X_1^n(2), X_2^n(2), Y^n) \in T(p)} = 2^{-n(I(X_1X_2;Y) + o(\delta))}
\end{align*}

so

\begin{align*}
  p_e \leq 2^{-n(I(X_2;YX_1) + o(\delta))} + 2^{-n(I(X_1;YX_2) + o(\delta))} + 2^{-n(I(X_1X_2;Y) + o(\delta))} \to 0
\end{align*}
as $R_2\leq I(X_2;YX_1)$, $R_1\leq I(X_1;YX_2)$ and $R_1 + R_2\leq I(X_1X_2;Y)$


% --------------------------------
%   Sebastien 19/12/2017

Suppose we are given a "working system", normally

with $\frac{1}{M_1 M_2} \Pr{\hat{m_1}\hat{m_2} \neq m_1 m_2 | m_1 m_2 \text{ is sent }} < \epsilon$

We want to show that $(R_1, R_2)$ belongs to convex hull $(\bigcup_{P_{x_1} P_{x_2}} \{...\})$
To that end, let $U_1$ be uniformly distributed on ${1 ... M_1}$ with $R_1 = \frac{1}{n} H(U_1)$ and let $U_2$ be uniformly distributed on ${1 ... M_2}$ with $R_2 = \frac{1}{n} H(U_2)$
also with
\[
  \Rightarrow \Pr{V_1 V_2 \neq U_1 U_2} < \epsilon \Rightarrow
  \left\{
  \begin{array}{c}
    \Pr{V_1 \neq U_1} < \epsilon \\
    \Pr{V_2 \neq U_2} < \epsilon \\
  \end{array}
  \right.
\]


\begin{align*}
  H(U_1 | V_1) &\leq h_2(\epsilon) + \epsilon \log(M_1 - 1) \leq h_2(\epsilon) + \epsilon_n R_1 \\
  H(U_2 | V_2) &\leq h_2(\epsilon) + \epsilon \log(M_2 - 1) \leq h_2(\epsilon) + \epsilon_n R_2 \\
  H(U_1 U_2 | V_1 V_2) &\leq h_2(\epsilon) + \epsilon \log(M_1 M_2 - 1) \leq h_2(\epsilon) + \epsilon_n (R_1 + R_2)
\end{align*}

\begin{align*}
  \rightarrow \frac{1}{n} I(U_1; V_1) = \frac{1}{n} H(U_1) - \frac{1}{n} H(U_1 | V_1) &\geq (1 - \epsilon) R_1 - \frac{1}{n} h_2(\epsilon)\\
  \frac{1}{n} I(U_2; V_2) = \frac{1}{n} H(U_2) - \frac{1}{n} H(U_2 | V_2) &\geq (1 - \epsilon) R_2 - \frac{1}{n} h_2(\epsilon) \\
  \frac{1}{n} I(U_1 U_2; V_1 V_2) &\geq (1 - \epsilon) (R_1 + R_2) - \frac{1}{n} h_2(\epsilon) \leftarrow \mathbf{(\Omega)}
\end{align*}

Observe
\[
  U_1 \rightarrow X_1^n \rightarrow Y^n \rightarrow V_1 \text{ so } I(U_1 ; V_1) \leq I(X_1^n; Y^n)
\]
and
\[
  U_2 \rightarrow X_2^n \rightarrow Y^n \rightarrow V_2 \text{ so } I(U_2 ; V_2) \leq I(X_2^n; Y^n)
\]
so
\[
  (U_1 U_2) \rightarrow (X_1^n X_2^n) \rightarrow Y^n \rightarrow (V_1 V_2) \text{ so } I(U_1 U_2 ; V_1 V_2) \leq I(X_1^n X_2^n; Y^n)
\]

and also $X_1^n$ is indep. of $X_2^n$

\begin{align*}
  I(X_1^n ; Y^n) &\leq I(X_1^n ; Y^n X_2^n) \\
                 &= I(X_1^n ; Y^n | X_2^n) + \underbrace{I(X_i^n ; X_2^n)}_{\to 0} \\
                 &= H(Y^n | X_2^n) - H(Y^n | X_1^n X_2^n) \\
                 &\leq \sum_{i = 1}^n H(Y_i | X_{2i}) - \sum_{i = 1}^n H(Y_i | X_{1i} X_{2i}) \\
                 &= \sum_{i = 1}^n I(X_{1i} ; Y_i | X_{2i}) \\
                 &= \sum_{i = 1}^n \underbrace{I(X_{1i} ; Y_i X_{2i})}_{a_i} - \underbrace{I(X_{1i} ; X_{2i})}_{\to 0}
\end{align*}

Similarly
\[
  I(X_2^n ; Y^n) \leq \sum_{i = 1}^n \underbrace{I(X_{2i} ; Y_i X_{1i})}_{b_i}
\]
and
\begin{align*}
  I(X_1^n X_2^n ; Y^n) &= H(Y^n) - H(Y^n) - H(Y^n | X_1^n X_2^n ) \\
                       &\leq \sum_i H(Y_i) - H(Y_i | X_{1i} X_{2i}) \\
                       &= \sum_i \underbrace{I(X_{1i} X_{2i} ; Y_i)}_{c_i}
\end{align*}

Therefore we have
\begin{align*}
  \mathbf{(\Omega)} \leq \frac{1}{n} \sum_{i=1}^n a_i \\
  (1 - \epsilon) R_2 - \frac{1}{n} h_2(\epsilon) \leq \frac{1}{n} \sum_{i=1}^n b_i \\
  (1 - \epsilon) (R_1 + R_2) - \frac{1}{n} h_2(\epsilon) \leq \frac{1}{n} \sum_{i=1}^n c_i \\
\end{align*}

\[
  \Rightarrow (R_1, R_2) - O(\epsilon) \in Pent' = Pent = \frac{1}{n} \sum_{i=1}^n Pent_i
\]
\[
  \subseteq ConvexHull(\bigcup_i Pent_i) \subseteq ConvexHull(\bigcup_{P_{X_1} P_{X_2}} \{ R_1 \leq I(X_1 ; Y X_2),  R_2 \leq I(X_2 ; Y X_1),  R_1 + R_2 \leq I(X_1 X_2 ; Y)\})
\]

So we have proved that

\begin{theorem}
  \[
    C(W) \subseteq ConvexHull(\bigcup_{P_{X_1} P_{X_2}} \{...\})
  \]
  So, using what we have shown before, we get the equality
  \[
    C(W) = ConvexHull(\bigcup_{P_{X_1} P_{X_2}} \{...\})
  \]
\end{theorem}

\begin{example}
  \[
    X_1 \in \{0, 1\}, X_2 \in \{0, 1\}, Y = X_1 + X_2 = \{0, 1, 2\}
  \]
  so
  \[
    R_1 \leq 1, R_2 \leq 1, R_1 + R_2 \leq \frac{3}{2}
  \]
\end{example}







% -------------------------------------------------------------------------
% -------------------------------------------------------------------------
% -------------------------------------------------------------------------
% appendices


\cleardoublepage
\begin{appendices}
\section{Markov chains}
\label{appendix:markov-chains}

$U_1 - U_2 - \dots - U_n$ forms a Markov chain if the joint probability
distribution of the RVs is
\[
  p(a,b,c,d) = p(a)p(b|a)p(c|b)p(d|c)
\]
which is equivalent to $(U_1, \dots, U_{k-1})$ are independant of $(U_{k+1}, \dots, U_n)$ when conditionned on $U_k$ for any $k$.


\begin{theorem}
  The reverse of a MC is a MC
\end{theorem}


\section{Stochastic processes}
\label{appendix:stoch-proc}

A stochastic process is a collection $U_1, U_2 \dots U_n$ of RVs each taking values in $\U$. It is described by its joint probability
\[
  p(u^n) = P(U_1 \dots U_n = u_1 \dots u_n) = P(U^n = u^n)
\]

\begin{definition}[Stationary stochastic process]
  A process $U_1, U_2, \dots$ is called stationary if for every $n$ and $k$ and $u_1 \dots u_n$, we have
  \[
    p(u^n) = p(U_1 \dots U_n = u_1 \dots u_n) = p(U_{1+k} \dots U_{n+k} = u_1 \dots u_n)
  \]
  In other words, the process is time shift invariant.
\end{definition}


\section{Concave/convex functions}
\label{sec:appendix-convex}

A function $f : S \rightarrow \R $ is called convex if
\[ \forall x,y \in S, 0 \leq \lambda \leq 1,  f(\lambda x - (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \]
where $S$ is a convex set.

\begin{definition}
  A set $S \subseteq \R^k$ is called to be convex if
  \[ \forall x,y \in S, 0 \leq \lambda \leq 1,  \lambda x + (1 - \lambda) y \in S\]
\end{definition}

\begin{definition}
  $f$ is called concave if $-f$ is convex.
\end{definition}

\begin{definition}{k-simplex}
\[ S_k = \{(p_1, ..., p_k) \in \R^k , p \geq 0, \sum_i p_i = 1 \} \]
as the k-simplex ( a $(k-1)$-dimentional subset of $\R^k$)
\end{definition}

Remark:
Given $S_k$ a convex set and $p,q \in S_k$, let
\begin{align*}
  r   &= \lambda p + (1 - \lambda)q \\
  r_i &= \lambda p_i + (1 - \lambda) q_i \geq 0
\end{align*}

\[ \sum r_i = \lambda + (1 - \lambda) = 1 \]

\begin{example}
  Let $f : S_k \rightarrow \R $, with
  \[ f(p_1, ..., p_k) = \sum^k p_i \log_{\frac{1}{p_i}} \]
  claim: f is concave

  \begin{proof}
    Given $p, q \in S_k, 0 \leq \lambda \leq 1$, define $(U, V)$ with $U \in \{0, 1\}$ and $V \in \{1, ..., k\}$

    \begin{align*}
      P_{UV}(u, v) =
      \left\{
      \begin{array}{l l}
        \lambda p_i, & u=0, v=i \\
        (1 - \lambda)q_i, & u=1, v=i
      \end{array}
      \right.
    \end{align*}
    therefore we have
    \begin{align*}
      \Pr{V = i} &= \lambda p_i + (1 - \lambda) q_i \\
      H(V) &= f(\lambda p + (1 - \lambda) q) \\
      H(V | U) &= \lambda f(p) + (1 - \lambda) f(q) \\
    \end{align*}
  \end{proof}
\end{example}


\begin{example}
  For $W(Y | X)$ let $f(p_X) = I(X ; Y)$ when $p(x, y) = p_X(x) W(Y | X) $
  \textbf{Claim:} $f$ is concave,
  \[ I(X ; Y) = H(Y) - H(X | Y) \]
  and
  \[ H(Y|X) = \sum_x p_X(x) \sum_y W(Y|X) \log \frac{1}{W(Y | X)} \]
  We see that $H(Y|X)$ is a linear function of $p_X(x)$.\\
  $H(Y)$ is a concave function of $p_Y(y)$ with
  \[ p_Y(y) - \sum_x p_X(x) W(Y|X) \]

  \begin{align*}
    p_X \underbrace{\longrightarrow}_{\text{linear}} p_Y \underbrace{\longrightarrow}_{\text{concave}} H(Y)
    \Longrightarrow p_X \underbrace{\longrightarrow}_{\text{concave}} H(Y)
  \end{align*}
\end{example}

How to maximize a function on the simplex?

\begin{theorem}{Karush-Kuhn-Tucker conditions - (KKT)} \\
  Suppose $f: S_k \rightarrow \R$, smooth ($\frac{df}{dp_i dp_j}$ exists), then if $p = \{ p_1, ..., p_k\}$ maximizes $f$, then $\exists \lambda$ s.t.
  \[ \forall i, \frac{df}{d p_i} \leq \lambda \]
  with equality $\forall i$ for which $p_i > 0$

\begin{proof}
  Suppose $(p_1, ..., p_k)$ maximizes $f$, then suppose that $p_i > 0$. Then we can consider a $p' \in S_k$ as follow:\\
  Pick $j \neq i$ and a small $\epsilon, 0 < \epsilon < p_i$
  \begin{align*}
    p_k' =
    \left\{
    \begin{array}{ll}
      p_i - \epsilon, &k = i \\
      p_j + \epsilon, & k = j \\
      p_k, &\text{else}
    \end{array}
    \right.
  \end{align*}

  \begin{align*}
    f(p') &= f(p) + \frac{d f(p)}{d p_i}(- \epsilon) + \frac{d f(p)}{d p_j} (\epsilon) + O(\epsilon^2) \\
    &= f(p) + \epsilon \left[ \frac{df}{dp_j} - \frac{df}{dp_i} \right] + O(\epsilon^2)
  \end{align*}

  So for every $i, j$ with $p_i > 0$ we have
  \[ \frac{df}{dp_j} \frac{df}{dp_i} \]
  $\Rightarrow$ equality if $i$ and $j$ are such that $p_i > 0, p_j > 0$

  $\Rightarrow$ for $i$'s such that $p_i > 0, \frac{df}{dp_i} = \lambda$ and all the indices $j$ have $\frac{df}{dp_j} \leq \lambda$
\end{proof}

\end{theorem}

\begin{theorem}
  Suppose $f: S_k \rightarrow \R$, suppose $f$ is concave and suppose for $p \in S_k$, the KKT condition hold. Then $\forall q \in S_k, f(q) \leq f(p) $

  \begin{proof}
    \begin{align*}
      f(\epsilon q + (1 - \epsilon)p) \geq (1 - \epsilon) f(p) + \epsilon f(q) \\
      \frac{f(\epsilon q + (1 - \epsilon)p) - f(p)}{\lambda} \geq f(q) - f(p), \quad \forall 0 < \epsilon \leq 1
    \end{align*}
    \begin{align*}
      \Rightarrow f(q) - f(p) \leq \lim_{\epsilon \to 0} \frac{f(p + \epsilon(q - p)) - f(p)}{\epsilon}
    \end{align*}
    \begin{align*}
      f(p + \epsilon (q - p)) = f(p) + \sum \epsilon(q_i - p_i) \frac{df(p)}{dp_i} + O(\epsilon^2) \\
      \frac{f(p + \epsilon(q - p)) - f(p)}{\epsilon} = \sum_{i} (q_i - p_i) \frac{d f(p)}{d p_i} + O(\epsilon)
    \end{align*}
    So
    \begin{align*}
      \lim_{\epsilon \to 0} \frac{f(p + \epsilon(q - p)) - f(p)}{\epsilon} = \sum_i (q_i - p_i) \frac{d f(p)}{d p_i}
    \end{align*}
    with
    \begin{align*}
      (q_i - p_i) \frac{df}{dp_i} =
      \left\{
      \begin{array}{ll}
        \lambda (q_i - p_i), & p_i > 0 \\
        \underbrace{(q_i - p_i)}_{\geq 0} \underbrace{\frac{df}{dp_i}}_{\leq \lambda}, & p_i = 0
      \end{array}
      \right.
      \leq \lambda (q_i - p_i)
    \end{align*}
    \begin{align*}
      \Rightarrow f(q) - f(p) \leq \lim_{\epsilon \to 0} [...] \leq 0
    \end{align*}
  \end{proof}
\end{theorem}

\begin{example}
  Supppose $f(p_1, p_2, p_3) = p_1 p_2^2 p_3^3$.
  We want to maximize it. If it isn't concave, we know that $\log(f(..))$ is concave. A try with KKT:
  \begin{align*}
    \frac{df}{dp_1} = \frac{1}{p_1}, \frac{df}{dp_2} = \frac{2}{p_2}, \frac{df}{dp_3} = \frac{3}{p_3}
  \end{align*}
  setting then all $\lambda$ yeild
  \[ (p_1, p_2, p_3) = \lambda (1, 2, 3) = ( \frac{1}{6}, \frac{2}{6}, \frac{3}{6}) \]
\end{example}

\begin{example}
  \[f(p_1, p_2, p_3) = (1 + p_1) p_2 p_3 \]
  maximize $f$ on the simplex by considering
  \[ \log(f) = \log(1 + p_1) + \log(p_2) + \log(p_3) \]
  therefore:
  \[
    \frac{df}{dp_1} = \frac{1}{1 + p_1}, \frac{df}{dp_2} = \frac{1}{p_2}, \frac{df}{dp_3} = \frac{1}{p_3}
  \]
  suggest $p = (0, 0.5, 0.5)$ the $\frac{df}{dp} = (1, 2, 2)$
  $\rightarrow$ satisfy KKT with $\lambda = 2$
\end{example}


\section{A story of two pentagons}
Consider two pentagons:

\[
  Pent_1 = \{(R_1, R_2): 0 \leq R_1 \leq a_1, 0 \leq R_2 \leq b_1, 0 \leq R_1 + R_2 \leq c_1  \}
\]

\[
  Pent_2 = \{(R_1, R_2): 0 \leq R_1 \leq a_2, 0 \leq R_2 \leq b_2, 0 \leq R_1 + R_2 \leq c_2  \}
\]

Set
\[
  Pent = \frac{1}{2} Pent_1 + \frac{1}{2} Pent_2 = \{(R_1, R_2): (R_1, R_2) =  \frac{1}{2} (R'_1, R'_2) + \frac{1}{2} (R''_1, R''_2)  \}
\]
such that $ (R'_1, R'_2) \in Pent_1 $ and $ (R''_1, R''_2) \in Pent_2 $

And
\[
  Pent' = \{(R_1, R_2): R_1 \leq \frac{a_1 + a_2}{2}, 0 \leq R_2 \leq \frac{b_1 + b_2}{2}, 0 \leq R_1 + R_2 \leq \frac{c_1 + c_2}{2} \}
\]

Suppose $(R_1, R_2) \in Pent$, then
\[
  \{ 0 \leq R_1 \leq \frac{a_1 + a_2}{2}, 0 \leq R_2 \leq \frac{b_1 + b_2}{2}, 0 \leq R_1 + R_2 \leq \frac{c_1 + c_2}{2} \} \Rightarrow (R_1, R_2) \in Pent'
\]

So we have shown that $Pent \subseteq Pent'$

However, if we assume further
\[
  \{ \max(a_1, b_1) \leq c_1 \leq a_1 + b_1, \max(a_2, b_2) \leq c_2 \leq a_2 + b_2\}
\]

then $Pent' = Pent$

\begin{theorem}
  Suppose $(a_i, b_i, c_i) \geq 0, i = 1 , ..., n$ with $max(a_i, b_i) \leq c_i \leq a_i + b_i$ and
  \[
    Pent_i = \{(R_1, R_2): R_1 \leq a_i, R_2 \leq b_i, R_1 + R_2 \leq c_i \}
  \]
  \[
    Pent' = \{(R_1, R_2): R_1 \leq \frac{1}{n} \sum q_i , R_2 \leq \frac{1}{n} \sum b_i, R_1 + R_2 \leq \frac{1}{n} \sum c_i \}
  \]
  \[
    Pent = \frac{1}{n} \sum Pent_i = \{\frac{1}{n} \sum (R_{1i}, R_{2i}) : (R_{1i}, R_{2i}) \in Pent_i \}
  \]
  then $Pent = Pent'$
\end{theorem}

\end{appendices}

\end{document}