\documentclass[10pt, a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{float}
\usepackage{graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%							PROBLEM SET		
%
\newif\ifsol		% switch between solution and problem set
\soltrue 			% pick this one for solution set	
%\solfalse			% pick this one for problem set
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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{December 5, 2023}{{\Large Problem Set 7 {\bf (Graded)}
---{\em Due Tuesday, December 19, before class starts}} \\ For the Exercise Sessions on Dec 5 and Dec 12}

\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 \\ 
  &   &  & \\ 
  &   &   & \\ \hline
\end{tabular}
\end{center}
\vspace{.5cm}

\begin{problem}[Exponential Families and Maximum Entropy 1]
Let $Y = X_1+X_2$. Find the maximum entropy of $Y$ under the constraint $\E[X^2_1]=P_1$, $\E[X_2^2] = P_2:$ 

{\em (a)} If $X_1$ and $X_2$ are independent.

{\em (b)} If $X_1$ and $X_2$ are allowed to be dependent. 
\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Exponential Families and Maximum Entropy 2]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PROBLEM
Find the maximum entropy density $f$, defined for $x\ge 0$, satisfying $\E[X]=\alpha_1$, $\E[\ln X] = \alpha_2$. That is, maximize $-\int f\ln f$ subject to $\int x f(x)dx = \alpha_1$, $\int(\ln x)f(x) dx = \alpha_2$, where the integral is over $0\le x< \infty$. What family of densities is this?
\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Exponential Families and Maximum Entropy 3]
% Final Exam Fall 2020
For $t > 0$, consider a family of distributions supported on
$[t,+\infty]$ such that $\mathbb E[\ln X] = \frac{1}{\alpha}+\ln
t$, $\alpha>0$.

\begin{enumerate}
\item
What is the parametric form of a maximum entropy distribution
satisfying the constraint on the support and the mean?

\item Find the exact form of the distribution.
\end{enumerate}

\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Exponential Families and Maximum Entropy 4: $I$-projections]
Let $P$ denote the zero-mean and unit-variance Gaussian distribution.
Assume that you are given $N$ iid samples distributed according to
$P$ and let $\hat{P}_N$ be the empirical distribution.

Let $\Pi$ denote the set of distributions with second moment
$\E[X^2] = 2$.  We are interested in
\begin{align*}
\lim_{N \rightarrow \infty} \frac1{N} \log \text{Pr}\{\hat{P_N} \in \Pi\} = - \inf_{Q \in \Pi} D(Q \| P).
\end{align*}

(a) Determine $- \text{arginf}_{Q \in \Pi} D(Q \| P)$, i.e., determine the element $Q$ for which the infinum is taken on. 

(b) Determine $- \inf_{Q \in \Pi} D(Q \| P)$. 
\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Choose the Shortest Description]
	
Suppose $\mathcal{C}_0:\mathcal{U}\to\{0,1\}^*$ and $\mathcal{C}_1:\mathcal{U}\to\{0,1\}^*$ are
two prefix-free codes for the alphabet $\mathcal{U}$.  Consider the code
$\mathcal{C}:\mathcal{U}\to\{0,1\}^*$ defined by
$$
\mathcal{C}(u)=\begin{cases}[0, \mathcal{C}_0(u)]
& \text{if $\text{length}\mathcal{C}_0(u)\leq \text{length}\mathcal{C}_1(u)$}\\
[1, \mathcal{C}_1(u)]
& \text{else.}
\end{cases}
$$
Observe that $\text{length}(\mathcal{C}(u))=1+\min\{\text{length}(\mathcal{C}_0(u)),\text{length}(\mathcal{C}_1(u))\}$.
\begin{itemize}
	\item[(a)] 
	Is $\mathcal{C}$ a prefix-free code?  Explain.
	\item[(b)]
	Suppose $\mathcal{C}_0,\dots,\mathcal{C}_{K-1}$ are $K$ prefix-free codes for the
	alphabet $\mathcal{U}$.  Show that there is a prefix-free code $\mathcal{C}$ with
	$$
	\text{length}(\mathcal{C}(u))=\lceil\log_2K\rceil + \min_{0\leq k<K-1} \text{length}(\mathcal{C}_k(u)).
	$$
	\item[(c)] 
	Suppose we are told that $U$ is a random variable taking values in $\mathcal{U}$,
	and we are also told that the distribution $p$ of $U$ is one of
	$K$ distributions $p_0,\dots,p_{K-1}$, but we do not know which.  Using (b)
	describe how to construct a prefix-free code $\mathcal{C}$ such that
	$$
	\E[\text{length}(\mathcal{C}(U))]\leq \lceil\log_2K\rceil+1+H(U).
	$$
	[Hint: From class we know that for each $k$ there is a prefix-free code
	$\mathcal{C}_k$ that descibes each letter $u$ with at most $\lceil-\log_2 p_k(u)\rceil$
	bits.]
\end{itemize}

\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Universal codes]
Suppose we have an alphabet $\cU$, and let $\Pi$ denote the set of
distributions on $\cU$.  Suppose we are given a family of $S$ of
distributions on $\cU$, i.e., $S\subset \Pi$.  For now,
assume that $S$ is finite.

Define the distribution $Q_S\in\Pi$
$$
Q_S(u)=Z^{-1}\max_{P\in S}P(u)
$$
where the normalizing constant $Z=Z(S)=\sum_u \max_{P\in S}P(u)$
ensures that $Q_S$ is a distribution.

\begin{itemize}
\item[(a)]
Show that $D(P\|Q)\leq \log Z\leq\log|S|$ for every $P\in S$.
% Since Q(u)>= P(u)/Z we have $P(u)/Q(u)\leq Z$, so the first bound is
% proved.  For the second max_{P\in S} P(u) <= sum_{P\in S} P(u), so
%Z(S) \leq sum_u\sum_{P in S} P(u) = sum_{P in S} sum_u P(u)=|S|.
\item[(b)]
For any $S$, show that there is a prefix-free code $\cC:\cU\to\{0,1\}^*$
such that for any random variable $U$ with distribution $P\in S$,
$$
E[\length\cC(U)] \leq H(U) + \log Z + 1.
$$
(Note that $\cC$ is designed on the knowledge of $S$ alone, it cannot
change on the basis of the choice of $P$.)  [Hint: consider
$L(u)=-\log_2 Q_S(u)$ as an `almost' length function.]
% let L(u) be the ceiling of the function in the hint.
\item[(c)]
Now suppose that $S$ is not necessarily finite, but there is a finite
$S_0\subset\Pi$ such that for each $u\in\cU$,
$\sup_{P\in S}P(u)\leq\max_{P\in S_0}P(u)$.  Show that $Z(S)\leq |S_0|$.
% just use (a).
\end{itemize}
Now suppose $\cU=\{0,1\}^m$.  For $\theta\in[0,1]$ and
$(x_1,\dots,x_m)\in\cU$, let 
$$
P_\theta(x_1,\dots,x_n)=\prod_i \theta^{x_i}(1-\theta)^{1-x_i}.
$$
(This is a fancy way to say that the random variable $U=(X_1,\dots,X_n)$
has i.i.d.\ Bernoulli $\theta$ components).  Let $S=\{P_\theta:\theta\in[0,1]\}$.
\begin{itemize}
\item[(d)]
Show that for $u=(x_1,\dots,x_m)\in\{0,1\}^m$
$$
\max_\theta P_\theta(x_1,\dots,x_m) = P_{k/m}(x_1,\dots,x_m)
$$
where $k=\sum_i x_i$.
% easy calculation, e.g., by differention wrt theta, or the positivity of
% divergence.
\item[(e)]
Show that there is a prefix-free code $\cC:\{0,1\}^m\to\{0,1\}^*$ such that
whenever $X_1,\dots,X_n$ are i.i.d.\ Bernoulli,
$$
\frac1m\E[\length\cC(X_1,\dots,X_m)]\leq H(X_1)+\frac{1+\log_2(1+m)}m.
$$
% by (c) and (b) and (d), with S_0 having cardinality m+1.
\end{itemize}
\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[Elias coding]
Let $0^n$ denote a sequence of $n$ zeros.  Consider the code (the subscript
$U$ a mnemonic for `Unary'), $\cC_U:\{1,2,\dots\}\to\{0,1\}^*$ for the
positive integers defined as $\cC_U(n)=0^{n-1}$.

\begin{itemize}
\item[(a)]
Is $\cC_U$ injective?  Is it prefix-free?
\end{itemize}

Consider the code (the subscript $B$ a mnenonic for `Binary'),
$\cC_B:\{1,2,\dots\}\to\{0,1\}^*$ where
$\cC_B(n)$ is the binary expansion of $n$.  I.e., $\cC_B(1)=1$, $\cC_B(2)=10$, 
$\cC_B(3)=11$, $\cC_B(4)=100$, \dots.  Note that
$$
\length\cC_B(n)=\lceil\log_2 (n+1)\rceil= 1+\lfloor\log_2 n\rfloor.
$$

\begin{itemize}
\item[(b)]
Is $\cC_B$ injective?  Is it prefix-free?
\end{itemize}
With $k(n)=\length\cC_B(n)$, define $\cC_0(n)=\cC_U(k(n))\cC_B(n)$.
\begin{itemize}
\item[(c)]
Show that $\cC_0$ is a prefix-free code for the positive
integers.  To do so, you may find it easier to describe how you would
recover $n_1,n_2,\dots$ from the concatenation of their codewords
$\cC_0(n_1)\cC_0(n_2)\dots$.
\item[(d)]
What is $\length(\cC_0(n))$?
% ans: 1+2floor(log(n))
\end{itemize}

Now consider $\cC_1(n)=\cC_0(k(n))\cC_B(n)$.
\begin{itemize}
\item[(e)]
Show that $\cC_1$ is a prefix-free code for the positive integers,
and show that $\length(\cC_1(n))=
2+2\lfloor\log(1+\lfloor\log n\rfloor)\rfloor+\lfloor \log n\rfloor
\leq 2+2\log (1+\log n) +\log n$.
% ans: 1 + 2floor(log k(n))+1+floor(log(n))
% = 2 + 2floor(log (1+floor(log(n))))+floor(log(n))
\end{itemize}
%We can now iterate, and define $\cC_k(n)=\cC_{k-1}(n)\cC_B(n)$,
%$k=2,3,\dots$.
%\begin{itemize}
%\item[(g)]
%Show that for each $k$, $\cC_k$ is prefix-free.
%\end{itemize}
Suppose $U$ is a random variable taking values in the positive integers
with $\Pr(U=1)\geq\Pr(U=2)\geq\dots$.
\begin{itemize}
\item[(f)]
Show that $\E[\log U]\leq H(U)$, [Hint: first show $i\Pr(U=i)\leq 1$], and
conclude that
$$
E[\length\cC_1(U)]\leq H(U)+2\log(1+H(U))+2.
$$
% 1\geq sum_{j=1}^i P(U=j) \geq i P(U=i), so log u <= log 1/p(u).  The rest
% follows easily
\end{itemize}
\end{problem}
\begin{solution}
% Write your solution here.
\end{solution}
\end{document}
