%% -*- mode: latex; mode: reftex; mode: flyspell; coding: utf-8; tex-command: "pdflatex.sh" -*-

%% Any copyright is dedicated to the Public Domain.
%% https://creativecommons.org/publicdomain/zero/1.0/
%% Written by Francois Fleuret <francois@fleuret.org>

\documentclass[10pt,a4paper,twoside]{article}
\usepackage[paperheight=18cm,paperwidth=10cm,top=5mm,bottom=20mm,right=5mm,left=5mm]{geometry}
%\usepackage[a4paper,top=2.5cm,bottom=2cm,left=2.5cm,right=2.5cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,dsfont}
\usepackage[pdftex]{graphicx}
\usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue,citecolor=blue]{hyperref}
\usepackage{tikz}
\usetikzlibrary{arrows,arrows.meta,calc}
\usetikzlibrary{patterns,backgrounds}
\usetikzlibrary{positioning,fit}
\usetikzlibrary{shapes.geometric,shapes.multipart}
\usetikzlibrary{patterns.meta,decorations.pathreplacing,calligraphy}
\usetikzlibrary{tikzmark}
\usetikzlibrary{decorations.pathmorphing}
\usepackage[round]{natbib}

\usepackage{mleftright}

\newcommand{\setmuskip}[2]{#1=#2\relax}
\setmuskip{\thinmuskip}{1.5mu} % by default it is equal to 3 mu
\setmuskip{\medmuskip}{2mu} % by default it is equal to 4 mu
\setmuskip{\thickmuskip}{3.5mu} % by default it is equal to 5 mu

\setlength{\parindent}{0cm}
\setlength{\parskip}{12pt}
%\renewcommand{\baselinestretch}{1.3}
%\setlength{\tabcolsep}{0pt}
%\renewcommand{\arraystretch}{1.0}

\def\argmax{\operatornamewithlimits{argmax}}
\def\argmin{\operatornamewithlimits{argmin}}
\def\expect{\mathds{E}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

Information Theory is awesome so here is a TL;DR about Shannon's entropy.

The field is originally about quantifying the amount of
``information'' contained in a signal and how much can be transmitted
under certain conditions.

What makes it awesome IMO is that it is very intuitive, and like
thermodynamics in Physics it give exact bounds about what is possible
or not.

\section{Shannon's Entropy}

Shannon's entropy is the key concept from which everything is defined.

Imagine that you have a distribution of probabilities $p$ on a finite
set of symbols, and that you generate a stream of symbols by sampling
them one after another independently with that distribution.

To transmit that stream, for instance with bits over a communication
line, you can design a coding that takes into account that the symbols
are not all as probable, and decode on the other side.

For instance if $P('\!\!A')=1/2$, $P('\!\!B')=1/4$, and
$P('\!\!C')=1/4$ you would transmit ``0'' for a ``A'' and ``10'' for a
``B'' and ``11'' for a ``C'', 1.5 bits on average.

If the symbol is always the same, you transmit nothing, if they are
equiprobable you need $\log_2$(nb symbols) etc.

Shannon's Entropy (in base 2) is the minimum number of bits you have
to emit on average per symbol to transmit that stream.

It has a simple analytical form:
%
\[
 H(p) = - \sum_k p(k) \log_2 p(k)
\]
%
where by convention $0 \log_2 0 = 0$.

It is often seen as a measure of randomness since the more
deterministic the distribution is, the less you have to emit.

The examples above correspond to "Huffman coding", which reaches the
Entropy bound only for some distributions. A more sophisticated scheme
called "Arithmetic coding" does it always.

From this perspective, many quantities have an intuitive
value. Consider for instance sending pairs of symbols (X, Y).

If these two symbols are independent, you cannot do better than
sending one and the other separately, hence
%
\[
H(X, H) = H(X) + H(Y).
\]

However, imagine that the second symbol is a function of the first
Y=f(X). You just have to send X since Y can be computed from it on the
other side.

Hence in that case
%
\[
H(X, Y) = H(X).
\]

An associated quantity is the mutual information between two random
variables, defined with
%
\[
I(X;Y) = H(X) + H(Y) - H(X,Y),
\]
%
that quantifies the amount of information shared by the two variables.

\section{Conditional Entropy}

Conditional entropy is the average of the entropy of the conditional distribution:
%
\begin{align*}
&H(X \mid Y)\\
 &= \sum_y p(Y=y) H(X \mid Y=y)\\
       &= \sum_y P(Y=y) \sum_x P(X=x \mid Y=y) \log P(X=x \mid Y=y)
\end{align*}

Intuitively it is the [minimum average] number of bits required to describe X given that Y is known.

So in particular, if X and Y are independent, getting the value of $Y$
does not help at all, so you still have to send all the bits for $X$,
hence
%
\[
  H(X \mid Y)=H(X)
\]

if X is a deterministic function of Y then
%
\[
  H(X \mid Y)=0.
\]

And if you send the bits for Y and then the bits to describe X given
that Y, you have sent (X, Y). Hence we have the chain rule:
%
\[
H(X, Y) = H(Y) + H(X \mid Y).
\]

And then we get
%
\begin{align*}
I(X;Y) &= H(X) + H(Y) - H(X,Y)\\
       &= H(X) + H(Y) - (H(Y) + H(X \mid Y))\\
       &= H(X) - H(X \mid Y).
\end{align*}

\section{Kullback-Leibler divergence}

Imagine that you encode your stream thinking it comes from
distribution $q$ while it comes from $p$. You would emit more bits than
the optimal $H(p)$, and that supplement is $D_{KL}(p||q)$ the
Kullback-Leibler divergence between $p$ and $q$.

In particular if $p=q$
%
\[
 D_{KL}(p\|q)=0,
\]
%
and if there is a symbol $x$ with $q(x)=0$ and $p(x)>0$, you cannot encode it and
%
\[
 D_{KL}(p\|q)=+\infty.
\]

Its formal expression is
%
\[
D_{KL}(p\|q) = \sum_x p(x) \log\left(\frac{p(x)}{q(x)}\right)
\]
%
that can be understood as a value called the cross-entropy between $p$ and $q$
%
\[
H(p,q) = -\sum_x p(x) \log q(x)
\]
%
minus the entropy of p
\[
H(p) = -\sum_x p(x) \log p(x).
\]

Notation horror: if $X$ and $Y$ are random variables $H(X, Y)$ is the
entropy of their joint law, and if $p$ and $q$ are distributions,
$H(p,q)$ is the cross-entropy between them.

\end{document}
