\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{float}
\usepackage{tikz}
\usetikzlibrary{fit,positioning}
\usetikzlibrary{bayesnet}
\usepackage{mathtools}
\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {\bf MATH888: High-dimensional probability and statistics } \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}
\newcommand{\ind}{\perp\!\!\!\!\perp} 

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribe: #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem*{remark}{Remark}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{33 --- Nov 22, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Liancheng Fang}

\section{Overview}
In today's lecture we continue our quick tour of information theory, which prepare us for the proof of Fano's method. More material can be found in \cite{CovThm}.


\section{Quick tour of information theory}
We assume RVs are discrete, we use $X$ to denote RV, $x$ for a specific value, $\mathcal{X}$ for the set of all possible value, $p(x)$ for probability mass function at $x$.
Convention: $0\log 0 = 0, 0\log {0\over 0} = 0$

\begin{definition}
$H(X) = -\sum_{x\in\mathcal{X}}p(x)\log p(x)$
\end{definition}
\begin{remark} Under the assumption that $\mathcal{X}$ is finite, it holds that $H(x)\le \log |\mathcal{X}|$, and the equality is achieved for uniform distribution only.
\end{remark}

\begin{definition}
$H(X|Y) = -\sum_{x,y}p(x,y)\log p(x|y)$
\end{definition}
\begin{remark}
Since $H(X|Y) = -\sum_y p(y) \sum_x p(x|y)\log p(x|y)$, conditional entropy can be understand as the expectation of entropy of conditional distribution of $X$ given $Y$.
\end{remark}

\begin{lemma}
$H(X,Y) = H(X) + H(Y|X)$
\end{lemma}
\begin{proof}
$H(X,Y) = -\sum_{x,y} p(x,y)\log p(x,y) = -\sum_{x,y} p(x,y)\log p(x) - \sum_{x,y} p(x,y) \log p(y|x)$= $H(X)+H(Y|X) $.
\end{proof}

\begin{lemma}(\textbf{Chain rule}) 
$H(X_1,...,X_n) = \sum_{i=1}^n H(X_i|X_{i-1},...,X_1)$ 
\end{lemma}
\begin{proof}
By induction.
\end{proof}

\begin{definition}
$I(X;Y) = KL(P_{XY}\| P_X P_Y)$
\end{definition}
\begin{remark}
$I(X;Y)$ is always non-negative, and equal to zero iff $X\ind Y$.
\end{remark}

\begin{lemma}
$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)$
\end{lemma}
\begin{proof}
$I(X;Y) = \sum_{x,y} p(x,y)\log \frac{p(x,y)}{p(x)p(y)} = \sum_{x,y}p(x,y)\log p(x|y) - \sum_{x,y} p(x,y)\log p(x) = -H(X|Y) + H(X)$. 
\end{proof}

\begin{lemma}
$H(X|Y) \le H(X)$
\end{lemma}
\begin{proof}
This follows from $I(X;Y) = H(X) - H(X|Y) \ge 0$.
\end{proof}

\begin{definition}(\textbf{conditional mutual information})
\begin{equation}\nonumber
\begin{aligned}
I(X;Y|Z) &:= H(X|Z) - H(X|Y,Z)
\\& = \sum_{x,y,z} p(x,y,z)\log \frac{p(x,y|z)}{p(x|z)p(y|z)}

\end{aligned}
\end{equation}

\end{definition}

\begin{lemma}
$I(X;Y|Z) = 0\Longleftrightarrow X\ind Y|Z$
\end{lemma}
\begin{proof}
$X\ind Y|Z\Longleftrightarrow p(x,y|z) = p(x|z)p(y|z), \forall x,y,z\Longleftrightarrow I(X;Y|Z) = 0$
\end{proof}
\begin{remark}
The conditional independence is equivalent to the following two factorization of joint density function:
\begin{equation}
    p(x,y,z) = p(z)p(x|z)p(y|z), \forall x,y,z
\end{equation}
which means we first generate $z$ from $p(z)$, then generate $x,z$ from $p(x|z), p(y|z)$ respectively. In graphical model this is: 
\begin{figure}[H]
  \centering
  \tikz{ %
    \node[latent] (z) {$Z$} ; %
    \node[latent, above=of z, xshift=-1cm] (x) {$X$} ; %
    \node[latent, above=of z, xshift=1cm] (y) {$Y$} ; %
  
    \edge {z} {x} ; %
    \edge {z} {y} ; %
  
  }
\end{figure}
\newline If we apply Bayesian rule on $p(x|z)$, we get
\begin{equation}
    p(x,y,z) = p(x)p(z|x)p(y|z), \forall x,y,z
\end{equation}
which means we first generate $x$ from $p(x)$, then generate $z$ from $p(z|x)$, finally generate $y$ from $p(y|z)$. In graphical model this is:
\begin{figure}[H]
  \centering
  \tikz{ %
    \node[latent] (x) {$X$} ; %
    \node[latent, right=of x] (z) {$Z$} ; %
    \node[latent, right=of z] (y) {$Y$} ; %
  
    \edge {x} {z} ; %
    \edge {z} {y} ; %
  
  }
\end{figure}
\end{remark}

\begin{lemma} (\textbf{Chain rule for MI})
$$I(X_1,...,X_n;Y) = \sum_{i=1}^n I(X_i;Y|X_{i-1},...,X_1)$$

\end{lemma}

\begin{lemma}(\textbf{Data processing inequality})
If $X\rightarrow Y\rightarrow Z$, then $I(X;Y)\ge I(X;Z)$. Equivalently, $H(X|Y)\le H(X|Z)$

\end{lemma}
\begin{remark}
Interpretation: Consider $Z$ as some function of $Y$, data processsing inequality tells that any function of $Y$ does not contain more information about $X$ than $Y$ itself.
\end{remark}
\begin{proof}
Apply chain rule with $(X_1,X_2) = (Z,Y), (Y,Z)$ respectively, we get the following two inequalities:

\begin{equation}\nonumber
    \begin{aligned}
    I(X;Y,Z) = I(X;Z) + I(X;Y|Z) = I(X;Y) + I(X;Z|Y)
    \end{aligned}
\end{equation}
Since $I(X;Y|Z)\ge 0$ and $I(X;Z|Y) =0$ by assumption, the proof completes.
\end{proof}

\begin{theorem}(Fano's Inequality)
Suppose $X\rightarrow Y\rightarrow \hat{X}$, and $P_e = \mathbb{P}(\hat{X}\neq X)$, then 
$$
H(P_e) + P_e\log|\mathcal{X}| \ge H(X|Y)
$$
\end{theorem}
where $H(P_e)$ is defined as the entropy of an indication RV, formally we define $H(P_e):=-P_e\log P_e - (1-P_e)\log (1-P_e)$. 
\begin{proof}

\[ E = \begin{cases*}
                    1 & if  $\hat{X}\neq X$  \\
                     0 & otherwise 
                 \end{cases*} \]%
Apply chain rule with different order of $E,X$, we get                 
\begin{equation}\label{eq:1}
    \begin{aligned}
    H(E,X|\hat{X}) & = H(X|\hat{X}) + H(E|X, \hat{X})
    \\& = H(E|\hat{X}) + H(X|\hat{X},E)
    \end{aligned}
\end{equation}
Note that $H(E|\hat{X})\le H(E) = H(P_e)$, $H(X|\hat{X},E) = \mathbb{P}(E=0)H(X|\hat{X},E=0) + \mathbb{P}(E=1)H(X|\hat{X},E=1)\le P_e\log(|\mathcal{X}|-1)$, $H(E|X,\hat{X})=0$, plug these inequality into \eqref{eq:1}, we get 
\begin{equation}\label{eq:2}
H(X|\hat{X}) \le H(P_e) + P_e \log(|\mathcal{X}|)
\end{equation}
Finally, by data process inequality, we have $$H(X|\hat{X})\ge H(X|Y)$$ Plug this into \eqref{eq:2} complete the proof.
\end{proof}
\paragraph{Application to Fano's method}
\begin{itemize}
  \item $|\mathcal{X}|=M$  
    \item $J$ uniform at random in $[M]$
    \item $Z\sim P_{\theta_j}$ given $J = j$
    \item test $\psi(Z) $
\end{itemize}
Apply Fano's inequality with $J = X$, $Z = Y$, $\psi(X) = \hat{X}$.
\newline Note that $H(Z,J) = H(J|Z) = H(J) - I(Z;J) = \log M - I(Z;J)$, and $H(P_e)$ term in Fano's inequality $\le 1$ since the indicator function can only take 2 value. From Fano we have
$$
1 + Q[\psi(Z)\neq J]\log M\ge \log M - I(Z;J)
$$
Rearrange terms we get
$$
Q[\psi(Z)\neq J] \ge 1- \frac{I(Z;J)+1}{\log M}
$$


%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{CovThm}
Cover, Thomas M.,
\emph{Elements of information theory},
John Wiley $\&$ Sons, 1999. 

\bibitem{Wainwright}
Wainwright, Martin J.,
\emph{High-Dimensional Statistics: A Non-Asymptotic Viewpoint},
Cambridge Series in Statistical and Probabilistic Mathematics, 2019.


\end{thebibliography}

\end{document}
