\documentclass[10pt, a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{epsfig,amsmath,amssymb,amsthm}
\newcommand{\reals}{\mathbb{R}}

% A bunch of settings
\setlength{\topmargin}{0pt}
\addtolength{\topmargin}{-\headheight}
\addtolength{\topmargin}{-\headsep}
\setlength{\textheight}{8.9in}
\setlength{\textwidth}{6.3in}
\setlength{\oddsidemargin}{0.1in}
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\parskip}{8pt}
\setlength{\parindent}{0pt}
\raggedbottom

%\settowidth{\leftmargini}{10pt}
\theoremstyle{definition}
\newtheorem{solution}{Solution}

\newtheoremstyle{problem_test}
  {\topsep}
  {\topsep}
  {\normalfont}
  {0pt}
  {\bfseries}
  {}
  {\newline}
  {\thmname{#1}~\thmnumber{#2:}\thmnote{ #3}
  {\newline}}
\theoremstyle{problem_test}
\newtheorem{problem}{Problem}


% Standard handout
\newcommand{\handout}[2]{{\parindent 0pt
Foundations of Data Science \hfill Ecole Polytechnique F\'ed\'erale, Lausanne: Fall 2023\\
Gastpar \& Urbanke \hfill #1}\\[.2cm]
\begin{center}
\hrule\vspace*{5pt}
{#2}
\vspace*{15pt}\hrule
\end{center}
\vspace*{1cm}}


\newcommand{\sect}[1]{
\vspace*{12pt}
\noindent \mbox{\large #1}}

%\pagestyle{empty}
\parskip 6pt
\parindent 0pt

\DeclareMathOperator{\Var}{Var}
\def\cU{\mathcal U}
\def\cV{\mathcal V}
\def\cS{\mathcal S}
\def\R{\mathbb R}
\def\cC{\mathcal C}
\DeclareMathOperator{\length}{length}
\newcommand{\E}{{\mathbb E}}

\begin{document}

\mathsurround 1.5pt
\def\s{\sigma}
\def\lbar{\overline\ell}

\handout{September 26, 2023}{{\Large Problem Set 2 {\bf (Graded)}  
---{\em Due Tuesday, October 10, before class starts}} \\ For the Exercise Sessions on September 26 and Oct 3}

\newcommand{\cX}{{\cal X}}
\newcommand{\cY}{{\cal Y}}
\def\bra{\langle}
\def\ket{\rangle}
%\newcommand{\vec}{{\overline}}}

\vspace{-1cm}

\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Last name \hspace{2.5cm} &  First name \hspace{2.5cm} &  SCIPER Nr \hspace{2.5cm}  & Points \\ 
  &   &  & \\ 
%Type your last name here
  & 
%Type your first name here
  &  
% Type your SCIPER number here
  & \\ \hline
\end{tabular}
\end{center}
\vspace{.5cm}

%%%%%
\begin{problem}[Axiomatic definition of entropy]
Let $(p_1,p_2,\dots,p_m)$ be such that $p_i \geq 0$ for $i=1,\dots,m$ and $\sum_i p_i = 1$. Let
\begin{equation}
\label{entropy}
H(p_1, \dots, p_m) = -\sum_i p_i \log p_i
\end{equation}
be the entropy of $(p_1,p_2,\dots, p_m)$.
\begin{itemize}
\item[(a)] \emph{(Grouping property)} Prove that 
$$ H(p_1, p_2, p_3, \dots, p_m) = H(p_1+p_2, p_3, \dots, p_m) + (p_1+p_2) H\left(\frac{p_1}{p_1+p_2},\frac{p_2}{p_1+p_2}\right). $$

The above property models the fact that the uncertainty in choosing among $m$ objects should be equal to the uncertainty in first choosing a subgroup of the objects, and then choosing an object in the selected subgroup.

\textbf{Solution}: %Type your solution here.

\item[(b)] Prove that if a function $F$ of probability vectors $(p_1,p_2,\dots,p_m)$, $m\geq2$, is such that
\begin{enumerate}
\item $F(p_1,p_2,\dots,p_m)$ is continuous in the $p_i$'s,
\item $F(p_1,p_2,\dots,p_m)$ satisfies the grouping property (a),
\item $F(\frac{1}{m},\dots,\frac{1}{m}) = \log m$,
\end{enumerate}
then $F$ must be equal to the entropy \eqref{entropy}.

\emph{Hint: Suppose that the $p_i's$ are rational, i.e., $p_i = \frac{m_i}{m}$ for some positive integers $\{m_i\}_{i=1,\dots,k}$. Show using (a) recursively that 
$$ F\left(\frac{1}{m},\dots, \frac{1}{m}\right) = F\left(\frac{m_1}{m},\dots,\frac{m_k}{m}\right) + \sum_i \frac{m_i}{m} F\left(\frac{1}{m_i},\dots,\frac{1}{m_i}\right).$$}

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
%%%%%
\begin{problem}[Entropy and geometry]
Suppose $X$, $Y$ and $Z$ are random variables.
\begin{itemize}
\item[(a)]
Show that $H(X)+ H(Y)+ H(Z)\geq \frac12\bigl[H(X,Y)+H(Y,Z)+H(Z,X)\bigr]$.

\textbf{Solution}: %Type your solution here.

\item[(b)]
Show that $H(X,Y)+H(Y,Z)\geq H(X,Y,Z)+H(Y)$.

\textbf{Solution}: %Type your solution here.

\item[(c)]
Show that
$$
2\bigl[H(X,Y)+H(Y,Z)+H(Z,X)\bigr]\geq 3H(X,Y,Z)+H(X)+H(Y)+H(Z).
$$

\textbf{Solution}: %Type your solution here.

\item[(d)]
Show that $H(X,Y)+H(Y,Z)+H(Z,X)\geq 2H(X,Y,Z)$.

\textbf{Solution}: %Type your solution here.

\item[(e)]
Suppose $n$ points in three dimensions are arranged so that their projections to the $xy$, $yz$ and $zx$ planes give $n_{xy}$, $n_{yz}$
and $n_{zx}$ points.  Clearly $n_{xy}\leq n$, $n_{yz}\leq n$,
$n_{zx}\leq n$.
Use part (d) to show that
$$
n_{xy} n_{yz} n_{zx}\geq n^2.
$$

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
%%%%%
\begin{problem}[Conditional KL divergence]
We saw in class that a \emph{probability kernel} $P_{Y|X}: \cX \to \cY$ is a matrix $P_{Y|X}=P_{Y|X}(y|x): x\in\mathcal{X},y\in\mathcal{Y}$ such that $P_{Y|X}(y|x)\geq 0$, and for each $x\in\mathcal{X}, \sum_y P_{Y|X}(y|x)=1$. Let $P_X \in \Pi(\mathcal{X})$ be a probability distribution on $\mathcal{X}$. We define the \emph{conditional KL divergence} between two probability kernels $P_{Y|X}: \cX \to \cY$ and $Q_{Y|X}: \cX \to \cY$ given $P_X$ to be
$$ D(P_{Y|X} \| Q_{Y|X} | P_X) \triangleq \sum_{x\in\cX} P_X(x) D( P_{Y|X}(\cdot | x) \| Q_{Y|X}(\cdot | x)) $$
where for every $x$, $D( P_{Y|X}(\cdot | x) \| Q_{Y|X}(\cdot | x))$ is the standard KL divergence between the two distributions $P_{Y|X}(\cdot | x)$ and $Q_{Y|X}(\cdot | x)$ over $\cY$.
\begin{itemize}
\item[(a)] \emph{(Chain rule of the KL divergence)} Show that
$$ D(P_{X,Y} \| Q_{X,Y}) = D(P_X \| Q_X) + D(P_{Y|X}\| Q_{Y|X} | P_X) $$
where $P_{X,Y}$ and $Q_{X,Y}$ are two joint distributions on $\cX \times \cY$ such that $P_{X,Y} (x,y) = P_X(x) P_{Y|X}(y|x)$ and $Q_{X,Y} (x,y) = Q_X(x) Q_{Y|X}(y|x)$.

\textbf{Solution}: %Type your solution here.

\item[(b)] Using (a), show that
$$ D(P_{Y|X}\| Q_{Y|X} | P_X) = D(P_{X,Y} \| Q_{X,Y}) $$
where $P_{X,Y} (x,y) = P_X(x) P_{Y|X}(y|x)$ and $Q_{X,Y} (x,y) = P_X(x) Q_{Y|X}(y|x)$.

\textbf{Solution}: %Type your solution here.

\item[(c)] \emph{(Conditioning increases divergence)} Using (b) and the Data Processing Inequality seen in class, show that
$$ D(P_Y \| Q_Y) \leq D(P_{Y|X}\| Q_{Y|X} | P_X)$$
where $P_{Y}(y) = \sum_{x\in\mathcal{X}} P_{X}(x)P_{Y|X}(y|x)$ and $Q_{Y}(y) = \sum_{x\in\mathcal{X}} P_{X}(x)Q_{Y|X}(y|x)$.

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
%%%%%
\begin{problem}[Variational characterization of mutual information]
Let $X$ and $Y$ be two random variables over finite alphabets $\cX$ and $\cY$ with joint probability distribution $P_{XY}$, and let $I(X;Y)$ be their mutual information.
\begin{itemize}
\item[(a)] Show that for every function $f(X,Y)$ such that $E_{P_XP_Y} [ e^{f(X,Y)} ]$ is finite,
\begin{equation*}
I(X;Y) \geq \E_{P_{XY}} [f(X,Y)] - \E_{P_Y} [\log \E_{P_X}[e^{f(X,Y)}]].
\end{equation*}

\textbf{Solution}: %Type your solution here.

\item[(b)] Show that there is a function $\tilde{f}(X,Y)$ such that $E_{P_XP_Y} [ e^{f(X,Y)} ]$ is finite and
\begin{equation*}
I(X;Y) = \E_{P_{XY}} [\tilde{f}(X,Y)] - \E_{P_Y} [\log \E_{P_X}[e^{\tilde{f}(X,Y)}]].
\end{equation*}

\textbf{Solution}: %Type your solution here.

\item[(c)] Conclude that 
\begin{equation*}
I(X;Y) = \sup_f \E_{P_{XY}} [f(X,Y)] - \E_{P_Y} [\log \E_{P_X}[e^{f(X,Y)}]]
\end{equation*}
where the $\sup$ is over all functions $f$ such that $E_{P_XP_Y} [ e^{f(X,Y)} ]$ is finite.

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
%%%%%
\begin{problem}[$f$-divergences]
Suppose $f$ is a convex function defined on $(0,\infty)$ with $f(1)=0$.
Define the $f$-divergence of a distribution $P$ from a distribution $Q$ as
$$
D_f(P\|Q) \triangleq \sum_x Q(x)f(P(x)/Q(x)).
$$
In the sum above we take $f(0):= \lim_{t\to 0}f(t)$, $0f(0/0):= 0$, and $0f(a/0):=\lim_{t\to 0} tf(a/t) = a \lim_{t\to 0} t f(1/t)$.
\begin{itemize}
\item[(a)] Show that the following basic properties hold:
\begin{enumerate}
\item $D_{f_1+f_2}(P\|Q) = D_{f_1}(P\|Q) + D_{f_2}(P\|Q)$
\item $D_f(P\|P) = 0$
\item $D_f(P\|Q) \geq 0$
\item $D_f(P\|Q) = 0$ for every $P\neq Q$ if and only if $f(x) = c (x-1)$ for some constant $c$.
\end{enumerate}

\textbf{Solution}: %Type your solution here.

\item[(b)] \emph{(Monotonicity)} Show that $D_f(P_{XY}\|Q_{XY}) \geq D_f(P_X\|Q_X)$.

\textbf{Solution}: %Type your solution here.

\item[(c)] \emph{(Data processing inequality)} Show that for any probability kernel $W(y|x)$ from $\cX$ to $\cY$, and any two distributions $P_X$ and $Q_X$ on $\cX$
$$
D_f(P_X\|Q_X) \geq D_f(P_Y\| Q_Y)
$$
where $P_Y$ and $Q_Y$ are probability distributions on $\cY$ given by $P_Y(y) = \sum_x P_X(x)W(y|x)$ and $Q_Y(y) = \sum_x Q_X(x)W(y|x)$.

\textbf{Solution}: %Type your solution here.

\item[(d)] Show that if $f$ is strictly convex in 1, then $D_f(P\|Q)=0$ if and only if $P=Q$.

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
%%%%%
\begin{problem}[Entropy and combinatorics]
Let $n\geq 1$ and fix some $0\leq k\leq n$. Let $p = \frac{k}{n}$ and let $T_p^n \subset \{0,1\}^n$ be the set of all binary sequences with exactly $np$ ones.
\begin{itemize}
\item[(a)] Show that
\begin{equation*}
\log |T_p^n| = nh(p) + O(\log n)
\end{equation*}
where $h(p) = -p\log p -(1-p)\log(1-p)$ is the binary entropy function.
Hint: Stirling’s approximation states that for every $n\geq 1$,
\begin{equation*}
e^{\frac{1}{12n + 1}} \sqrt{2\pi n} \left(\frac{n}{e}\right)^n \leq n! \leq e^{\frac{1}{12n}} \sqrt{2\pi n} \left(\frac{n}{e}\right)^n.
\end{equation*}

\textbf{Solution}: %Type your solution here.

\item[(b)] Let $Q^n = \mathrm{Bernoulli}(q)^n$ be the i.i.d. Bernoulli distribution on $\{0, 1\}^n$. Show that 
\begin{equation*}
\log Q^n[T_p^n] = -n d(p\|q) + O(\log n)
\end{equation*}
where $d(p\|q) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}$ is the binary KL divergence.

\textbf{Solution}: %Type your solution here.

\end{itemize}
\end{problem}
\end{document}


