\documentclass[a4paper,12pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amsfonts,amsthm,amssymb,mathtools}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{enumitem}

\theoremstyle{definition}
\newtheorem{problem}{Problem}

% Some handy macros (similar to your original file)
\def\bZ{\mathbb{Z}}
\def\bE{\mathbb{E}}
\def\bR{\mathbb{R}}
\def\cA{\mathcal{A}}
\def\cB{\mathcal{B}}
\def\cM{\mathcal{M}}
\def\cX{\mathcal{X}}
\def\cY{\mathcal{Y}}
\DeclareMathOperator{\weight}{weight}
\DeclareMathOperator{\enc}{enc}
\DeclareMathOperator{\dec}{dec}
\DeclareMathOperator{\score}{scr}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\hint}[1]{\noindent{\footnotesize{\itshape Hint:} #1}}

\newcommand{\indic}{\mathbbm{1}} % only needed if students want it

% Simple solution environment for students
\newenvironment{solution}{%
  \par\medskip
  \noindent\textbf{Solution.}\ }{\medskip}

\begin{document}

\begin{center}
  {\large \textbf{École polytechnique fédérale de Lausanne (EPFL)}}\\[0.5em]
  {\Large \textbf{COM-404: Information Theory and Coding}}\\[0.75em]
  {\large \textbf{Graded Homework}}\\[0.25em]
  {\normalsize Due: Friday, Dec.~19, 2025, 11:59pm}
\end{center}

\vspace{1.5em}

\noindent\textbf{Student name:} 
Your full name comes here \\[0.6em]
\noindent\textbf{Student ID:} Your ID number comes here\\[0.6em]
\noindent\textbf{Collaborators / sources (if any):} This friend and this textbook, etc.

\vspace{1em}

\begin{quote}
You are allowed (even encouraged) to discuss the problems on the homework with your colleagues. However, your solutions should be in your own words. If you collaborated on your solution, write down the name of your collaborators and your sources; no points will be deducted. But similarities in solutions beyond the listed collaborations will be considered as malpractice. Also, note that $\log$ is in base 2 unless stated otherwise.   
\end{quote}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[A single-server queue as a communication channel]

Consider a single-server queue with the following properties:

\begin{itemize}
  \item Jobs arrive at times $a_1, a_2, \dots$.
  \item Job $i$ requires $S_i$ units of service time. We assume $\{S_i\}_{i\ge 1}$ are i.i.d.
  \item Jobs are processed in first-come-first-served order by a single server.
        If the server is busy when a job arrives, it waits in a queue.
  \item The queue is initially empty.
\end{itemize}

Let $E_i$ and $D_i$ denote the times at which job $i$ enters and departs service, respectively
(with $D_0 := 0$). Then
\[
  E_i = \max\{a_i, D_{i-1}\},\qquad
  D_i = E_i + S_i,\qquad i\ge 1.
\]

We attempt to communicate using this system by sending $n$ jobs to the queue. The sender encodes
its message in the arrival times of the jobs. For example, for $n=3$ and two possible messages
(labelled $1$ and $2$), we might choose
\[
  (a_1,a_2,a_3) =
  \begin{cases}
    (0,   1,   1.5), & \text{if the message is } 1,\\
    (0.5, 0.8, 1.4), & \text{if the message is } 2.
  \end{cases}
\]
The receiver observes the departure times $(D_1,D_2,D_3)$ and decides between messages $1$ and $2$
using some decision rule, for instance, by choosing the more likely of the two messages.

\medskip
\noindent
\textbf{(a)} Suppose $S_i$ are exponential random variables with $\mathbb{E}[S_i]=1$, i.e.
\[
 S_i \text{ has pdf } f_S(s) = e^{-s}\,, \quad s\ge0.
\]
Given the arrival times $a_1,\dots,a_n$,
how can one compute the conditional joint pdf of the departure times $D_1,\dots,D_n$ (which we denote as $f_{D^n|A^n}(d_1,\dots,d_n \mid a_1,\dots,a_n)$)?

\hint{Express your answer in terms of
\[
  s_i := d_i - \max\{a_i, d_{i-1}\},\quad i=1,\dots,n,\quad d_0 := 0.
\]}

\begin{solution}
% Your solution to part (a) here.
\end{solution}

\medskip
\noindent
Now, define the \emph{score} as follows:
\[
  \mathrm{score}(a^n,d^n) := \sum_{i=1}^n s_i,
\]
where $(s_1,\dots,s_n)$ is as in the hint above. Let $a^n(1),\dots,a^n(m)$ denote the arrival-time
sequences chosen by the sender for messages $1,\dots,m$.

\medskip
\noindent
\textbf{(b)} How should the receiver choose the maximally likely message
$\hat w \in \{1,\dots,m\}$ based on an observed departure sequence $d^n$?

\begin{solution}
% Your solution to part (b) here.
\end{solution}

\medskip
Now suppose the arrival times $A_1\le \dots \le A_n$ are chosen randomly according to some
stochastic process. Let $D_1\le \dots \le D_n$ be the corresponding departure times. Recall that
$S_i \sim \text{Exp}(1)$ are i.i.d. and independent of the arrival process.

\medskip
\noindent
\textbf{(c)} Show that
\[
  h(D^n \mid A^n) = n \log e.
\]

\emph{Hint:} Justify the following steps:
\[
  h(D^n \mid A^n)
  = \sum_{i=1}^n h(D_i \mid D^{i-1}, A^n)
  = \sum_{i=1}^n h(S_i)
  = n \log e
\]

\begin{solution}
% Your solution to part (c) here.
\end{solution}

\medskip
\noindent
Define the interdeparture times
\[
  \Delta_i := D_i - D_{i-1},\qquad i=1,\dots,n,
\]
and let
\[
  \delta_i := \mathbb{E}[\Delta_i],\qquad
  \bar\delta := \frac{1}{n}\sum_{i=1}^n \delta_i.
\]

\medskip
\noindent
\textbf{(d)} Show that
\[
  I(A^n;D^n) \le n\log \bar\delta.
\]

\emph{Hint:} First show that $h(D^n) \le \sum_{i=1}^n h(\Delta_i)$.

\begin{solution}
% Your solution to part (d) here.
\end{solution}

\medskip
\noindent
\textbf{(e)} The receiver must wait $D_n$ units of time to observe $D^n$. The mutual information
$I(A^n;D^n)$ is thus developed over an expected time $\mathbb{E}[D_n]$. Show that the
\emph{mutual information per unit time} satisfies:
\[
  \frac{I(A^n;D^n)}{\mathbb{E}[D_n]} \;\le\; \frac{\log e}{e}.
\]

\emph{Hint:} Note that $\mathbb{E}[D_n] = \sum_{i=1}^n \delta_i$.

\begin{solution}
% Your solution to part (e) here.
\end{solution}

\medskip
\noindent
Now suppose the sender can observe the departures from the system. The sender uses the following
strategy:
\begin{enumerate}
  \item For each message $w\in\{1,\dots,m\}$ choose a sequence $x^n(w)$ of nonnegative numbers.
  \item To communicate message $w$, send jobs at times
  \[
    a_1 = x_1(w),\qquad
    a_i = D_{i-1} + x_i(w),\quad i=2,\dots,n.
  \]
\end{enumerate}

\medskip
\noindent
\textbf{(f)} Under this strategy, will any job be queued? What is the relationship between $x^n$,
the interdeparture times $\Delta^n$, and the service times $S^n$?

\begin{solution}
% Your solution to part (f) here.
\end{solution}

\medskip
\noindent
Consider now a memoryless channel with input $X\ge 0$ and output $Y\ge 0$, where
\[
  Y = X + Z,
\]
and $Z\sim\text{Exp}(1)$ is independent of $X$.

\medskip
\noindent
\textbf{(g)} Show that for any input distribution on $X$ with finite mean,
\[
  I(X;Y) \le \log\bigl(1+\mathbb{E}[X]\bigr).
\]

\begin{solution}
% Your solution to part (g) here.
\end{solution}

\medskip
\noindent
\textbf{(h)} Show that equality holds in (g) if $X$ has pdf
\[
  f_X(x) = p\,\delta(x) + (1-p)\,p\,e^{-px}\,\mathbf{1}\{x\ge 0\},
\]
where
\[
  p = \frac{1}{1+\mathbb{E}[X]}.
\]

\begin{solution}
% Your solution to part (h) here.
\end{solution}

\medskip
\noindent
\textbf{(i)} Consider again the memoryless channel with input $X \ge 0$, output $Y = X + Z$,
where $Z \sim \mathrm{Exp}(1)$ is independent of $X$. Let the cost function be
\[
  b(x) = 1 + x,
\]
and for $\beta \ge 0$ define the \emph{cost-constrained capacity}
\[
  C(\beta)
  := \sup\bigl\{ I(X;Y) : X \ge 0,\ \mathbb{E}[b(X)] \le \beta \bigr\}.
\]
Show that
\[
  \max_{\beta} \frac{C(\beta)}{\beta} \;=\; \frac{\log e}{e}.
\]

\begin{solution}
% Your solution to part (i) here.
\end{solution}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}

Let $(U,Y)$ be a pair of random variables with $U \in \{0,1\}$.  
A binary random variable $\hat U \in \{0,1\}$ is called an \emph{estimator of $U$ from $Y$} 
if $U - Y - \hat U$ form a Markov chain.

\medskip
\noindent\textbf{(a)} Show that for any such estimator $\hat U$,
\[
  \Pr(\hat U \neq U) \;\geq\; \sum_y \min_{u \in \{0,1\}} p_{UY}(u,y).
\]
\emph{Hint:} First show that
\[
  \Pr(\hat U \neq U \mid Y=y)
  \;\geq\; \min_{u \in \{0,1\}} p_{U\mid Y}(u\mid y).
\]

\begin{solution}
% Your solution to part (a) here.
\end{solution}

\medskip
\noindent\textbf{(b)} Show that there exists an estimator $\hat U$ such that
\[
  \Pr(\hat U \neq U) \;=\; \sum_y \min_{u \in \{0,1\}} p_{UY}(u,y).
\]
Consequently, the quantity
\[
  P_e(U,Y) \;:=\; \sum_y \min_{u \in \{0,1\}} p_{UY}(u,y)
\]
is the minimal error probability of estimating $U$ from $Y$.

\begin{solution}
% Your solution to part (b) here.
\end{solution}

\medskip
In addition to the quantity $P_e(U,Y)$ above, define also
\[
  B(U,Y) \;:=\; \sum_y 2 \sqrt{\prod_{u \in \{0,1\}} p_{UY}(u,y)}
\]
and
\[
  H(U\mid Y) \;:=\; -\sum_y \sum_{u \in \{0,1\}} p_{UY}(u,y)\,\log_2 p_{U\mid Y}(u\mid y).
\]

Consider the functions $\alpha,\beta,\gamma : [0,1] \to [0,1]$ defined by
\[
  \alpha(t) := 2\min\{t,1-t\}, \qquad
  \beta(t) := 2\sqrt{t(1-t)}, \qquad
  \gamma(t) := -t\log t - (1-t)\log(1-t),
\]
and the three parametric curves in $\mathbb{R}^2$ traced by the points
\[
  (\alpha(t),\beta(t)), \qquad
  (\alpha(t),\gamma(t)), \qquad
  (\beta(t),\gamma(t)),
\]
as $t$ ranges from $0$ to $1$.

 The solid lines in
Figure \ref{figure pp} show these curves. The figure also shows the convex hull of
each curve as the shaded regions. E.g., the shaded region for the first
curve is the set of all points that can be written as $\sum_{i=1}^k
\lambda_i (\alpha(t_i), \beta(t_i))$ for some $t_1,\dots,t_k$ and non-negative
$\lambda_1,\dots,\lambda_k$ with $\sum_i \lambda_i = 1.$

\begin{figure}[h!]
  \centering
  \centerline{\input{pp}}
  \caption{3 parametric curves and their convex hull in respective order.}
  \label{figure pp}
\end{figure}

\medskip
\noindent\textbf{(c)} Show that the point $\bigl(2P_e(U,Y), B(U,Y)\bigr)$ in $\mathbb{R}^2$ belongs to the first shaded region (the convex hull of the curve $(\alpha(t),\beta(t))$).

\emph{Hint:} Find appropriate $\lambda_i$'s and $t_i$'s so that
\[
  2 P_e = \sum_i \lambda_i \alpha(t_i)
  \quad\text{and}\quad
  B = \sum_i \lambda_i \beta(t_i).
\]

\begin{solution}
% Your solution to part (c) here.
\end{solution}

\medskip
\noindent\textbf{(d)} Show that
\[
  2P_e(U,Y) \;\leq\; B(U,Y)
\]
and
\[
  B^2(U,Y) \;\leq\; 4P_e(U,Y) \;-\; \bigl(2P_e(U,Y)\bigr)^2.
\]
\emph{Hint:} Use part (c).

\begin{solution}
% Your solution to part (d) here.
\end{solution}

\medskip
\noindent\textbf{(e)} Let $U \sim \text{Bernoulli}(1/2)$.
Let $Y_1$ be the output of a binary symmetric channel (BSC) with input $U$, 
and $Y_2$ be the output of a binary erasure channel (BEC) with input $U$.
By varying the crossover probability of the BSC and the erasure probability of the BEC, 
show that the inequalities in part (d) between $P_e$ and $B$ are tight (i.e. hold with equality).

\begin{solution}
% Your solution to part (e) here.
\end{solution}

\medskip
\noindent\textbf{(f)} Show that the point $\bigl(2P_e(U,Y), H(U \mid Y)\bigr)$
belongs to the second shaded region (the convex hull of the curve $(\alpha(t),\gamma(t))$).

\begin{solution}
% Your solution to part (f) here.
\end{solution}

\medskip
\noindent\textbf{(g)} Show that the point $\bigl(B(U,Y), H(U \mid Y)\bigr)$
belongs to the third shaded region (the convex hull of the curve $(\beta(t),\gamma(t))$).

\begin{solution}
% Your solution to part (g) here.
\end{solution}

\end{problem}

\end{document}