Information theory MOC
$\require{mathtools}
%
%%% GENERIC MATH %%%
%
% Delimiters
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\inner}{\langle}{\rangle}
\DeclarePairedDelimiter{\set}{\{}{\}}
\newcommand{\SET}[1]{\!\set*{#1}}
\DeclarePairedDelimiter{\p}{(}{)}
\newcommand{\P}[1]{\!\p*{#1}}
\DeclarePairedDelimiter{\sqb}{[}{]} % deprecated
\let\b\undefined
\DeclarePairedDelimiter{\b}{[}{]}
\newcommand{\B}[1]{\!\b*{#1}}
\DeclarePairedDelimiter{\abs}{|}{|}
\DeclarePairedDelimiter{\norm}{\|}{\|}
\newcommand{\frob}[1]{\norm{#1}_\mathrm{F}}
\newcommand{\frobs}[1]{\norm*{#1}_\mathrm{F}}
%% .. two-part
\newcommand{\cond}[2]{#1\,|\,#2}
\newcommand{\INTERNALCOND}[2]{#1\,\middle|\,#2}
\newcommand{\COND}[2]{\left.\INTERNALCOND{#1}{#2}\right.}
\newcommand{\at}[2]{#1|_{#2}}
\newcommand{\AT}[2]{\left.#1\right|_{#2}}
\newcommand{\para}[2]{#1\,\|\,#2}
\newcommand{\PARA}[2]{#1\,\middle\|\,#2}
\newcommand{\setco}[2]{\set{\cond{#1}{#2}}}
\renewcommand{\setcos}[2]{\set*{\INTERNALCOND{#1}{#2}}}
\newcommand{\SETCO}[2]{\!\SET{\INTERNALCOND{#1}{#2}}}
\newcommand{\bco}[2]{\b{\cond{#1}{#2}}}
\newcommand{\bcos}[2]{\b*{\INTERNALCOND{#1}{#2}}}
\newcommand{\BCO}[2]{\B{\INTERNALCOND{#1}{#2}}}
\newcommand{\ppa}[2]{\p{\para{#1}{#2}}}
\newcommand{\ppas}[2]{\p*{\PARA{#1}{#2}}}
\newcommand{\PPA}[2]{\P{\PARA{#1}{#2}}}
% compatibility
\newcommand{\ps}[1]{\p*{#1}}
%
% Shortcuts
\newcommand{\al}[1]{\begin{align}#1\end{align}}
\newcommand{\ob}{\overbrace}
\newcommand{\ub}{\underbrace}
\newcommand{\ol}{\overline}
\newcommand{\tld}{\widetilde}
\newcommand{\ht}{\widehat}
\newcommand{\f}{\frac}
\newcommand{\sse}{\subseteq}
\newcommand{\ce}{\coloneqq}
\newcommand{\ec}{\eqqcolon}
\newcommand{\la}{\lessapprox}
\newcommand{\ga}{\greaterapprox}
\newcommand{\q}{\quad}
\newcommand{\qq}{\qquad}
\newcommand{\heart}{\heartsuit}
\newcommand{\eps}{\epsilon}
\let\fi\phi % because it looks like an f
\let\phi\varphi % because it looks like a p
%
% Miscellaneous
\newcommand{\LHS}{\mathrm{LHS}}
\newcommand{\RHS}{\mathrm{RHS}}
% .. operators
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\quasipoly}{\mathrm{quasipoly}}
\newcommand{\negl}{\mathrm{negl}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
% .. functions
\newcommand{\sign}{\mathrm{sign}}
\newcommand{\d}{\mathrm{d}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\ReLU}{\mathrm{ReLU}}
% .. sets
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
%
%%% SPECIALIZED MATH %%%
%
% Logic
\newcommand{\and}{\wedge}
\newcommand{\AND}{\bigwedge}
\newcommand{\or}{\vee}
\newcommand{\OR}{\bigvee}
\newcommand{\xor}{\oplus}
\newcommand{\XOR}{\bigoplus}
\newcommand{\union}{\cup}
\newcommand{\inter}{\cap}
\newcommand{\UNION}{\bigcup}
\newcommand{\INTER}{\bigcap}
\newcommand{\comp}{\overline}
%
% Linear algebra
\newcommand{\span}{\mathrm{span}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\proj}{\mathrm{proj}}
\DeclareMathOperator{\Ima}{Im}
\newcommand{\transp}{\mathsf{T}}
\newcommand{\t}{^\transp}
% ... named tensors
\newcommand{\namedtensorstrut}{\vphantom{fg}} % milder than \mathstrut
\newcommand{\name}[1]{\mathsf{\namedtensorstrut #1}}
\newcommand{\nbin}[2]{\mathbin{\underset{\substack{#1}}{\namedtensorstrut #2}}}
\newcommand{\ndot}[1]{\nbin{#1}{\odot}}
\newcommand{\ncat}[1]{\nbin{#1}{\oplus}}
\newcommand{\nsum}[1]{\sum\limits_{\substack{#1}}}
\newcommand{\nfun}[2]{\mathop{\underset{\substack{#1}}{\namedtensorstrut\mathrm{#2}}}}
\newcommand{\ndef}[2]{\newcommand{#1}{\name{#2}}}
\newcommand{\nt}[1]{^{\transp(#1)}}
%
% Probability
\newcommand{\Normal}{\mathcal{N}}
\let\Pr\undefined
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}
\DeclareMathOperator*{\Odd}{\mathbf{O}}
\DeclareMathOperator*{\E}{\mathbf{E}}
\DeclareMathOperator*{\Var}{\mathbf{Var}}
\newcommand{\Cov}{\mathbf{Cov}}
\DeclareMathOperator{\median}{median}
\DeclareMathOperator{\One}{\mathbf{1}}
\DeclareMathOperator{\1}{\mathbf{1}}
\newcommand{\dTV}{d_{\mathrm{TV}}}
\newcommand{\corr}{\mathrm{corr}}
% ... information theory
\let\H\undefined
\DeclareMathOperator{\H}{\mathbf{H}}
\DeclareMathOperator{\I}{\mathbf{I}}
\DeclareMathOperator{\KL}{\mathbf{KL}}
\newcommand{\KLb}{\mathrm{KL}}
%
%%% SPECIALIZED TCS %%%
%
% Complexity classes
% .. classical
\newcommand{\Poly}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\PH}{\mathsf{PH}}
\newcommand{\PSPACE}{\mathsf{PSPACE}}
\newcommand{\L}{\mathsf{L}}
% .. probabilistic
\newcommand{\formost}{\mathsf{Я}}
\newcommand{\RP}{\mathsf{RP}}
\newcommand{\BPP}{\mathsf{BPP}}
\newcommand{\MA}{\mathsf{MA}}
\newcommand{\AM}{\mathsf{AM}}
\newcommand{\IP}{\mathsf{IP}}
\newcommand{\RL}{\mathsf{RL}}
% .. circuits
\newcommand{\NC}{\mathsf{NC}}
\newcommand{\AC}{\mathsf{AC}}
\newcommand{\ACC}{\mathsf{ACC}}
\newcommand{\TC}{\mathsf{TC}}
\newcommand{\Ppoly}{\mathsf{P}/\poly}
\newcommand{\Lpoly}{\mathsf{L}/\poly}
% .. resources
\newcommand{\TIME}{\mathsf{TIME}}
\newcommand{\SPACE}{\mathsf{SPACE}}
\newcommand{\TISP}{\mathsf{TISP}}
\newcommand{\SIZE}{\mathsf{SIZE}}
% .. keywords
\newcommand{\co}{\mathsf{co}}
\newcommand{\Prom}{\mathsf{Promise}}
%
% Boolean analysis
\newcommand{\zo}{\set{0,1}}
\newcommand{\pmo}{\set{\pm 1}}
\newcommand{\harpoon}{\!\upharpoonright\!}
\newcommand{\restrict}[2]{#1\harpoon_{#2}} % deprecated
\newcommand{\rr}[2]{#1\harpoon_{#2}}
\newcommand{\Fou}[1]{\widehat{#1}}
\DeclareMathOperator{\Ind}{\mathrm{Ind}}
\DeclareMathOperator{\Inf}{\mathrm{Inf}}
\DeclareMathOperator{\D}{\mathrm{D}}
\DeclareMathOperator{\Stab}{\mathrm{Stab}}
\DeclareMathOperator{\T}{T}
\DeclareMathOperator{\sens}{\mathrm{s}}
\DeclareMathOperator{\bsens}{\mathrm{bs}}
\DeclareMathOperator{\fbsens}{\mathrm{fbs}}
\DeclareMathOperator{\Cert}{\mathrm{C}}
\DeclareMathOperator{\DT}{\mathrm{DT}}
\DeclareMathOperator{\CDT}{\mathrm{CDT}} % canonical
\DeclareMathOperator{\ECDT}{\mathrm{ECDT}}
\DeclareMathOperator{\CDTv}{\mathrm{CDT_{vars}}}
\DeclareMathOperator{\ECDTv}{\mathrm{ECDT_{vars}}}
\DeclareMathOperator{\CDTt}{\mathrm{CDT_{terms}}}
\DeclareMathOperator{\ECDTt}{\mathrm{ECDT_{terms}}}
\DeclareMathOperator{\CDTw}{\mathrm{CDT_{weighted}}}
\DeclareMathOperator{\ECDTw}{\mathrm{ECDT_{weighted}}}
\DeclareMathOperator{\AvgDT}{\mathrm{AvgDT}}
\DeclareMathOperator{\PDT}{\mathrm{PDT}} % partial decision tree
\DeclareMathOperator{\DTsize}{\mathrm{DT_{size}}}
\DeclareMathOperator{\W}{\mathbf{W}}
% .. functions (small caps sadly doesn't work)
\DeclareMathOperator{\Par}{\mathrm{Par}}
\DeclareMathOperator{\Maj}{\mathrm{Maj}}
\DeclareMathOperator{\HW}{\mathrm{HW}}
\DeclareMathOperator{\Th}{\mathrm{Th}}
\DeclareMathOperator{\Tribes}{\mathrm{Tribes}}
\DeclareMathOperator{\RotTribes}{\mathrm{RotTribes}}
\DeclareMathOperator{\CycleRun}{\mathrm{CycleRun}}
\DeclareMathOperator{\SAT}{\mathrm{SAT}}
\DeclareMathOperator{\UniqueSAT}{\mathrm{UniqueSAT}}
%
% Alignment
\DeclareMathOperator{\Amp}{\mathrm{Amp}}
%
%%% TYPESETTING %%%
%
% In text
\renewcommand{\th}{^{\mathrm{th}}}
\renewcommand{\degree}{^\circ}
%
% Fonts
% .. calligraphic
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calW}{\mathcal{W}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}
% .. bold
\newcommand{\bA}{\boldsymbol{A}}
\newcommand{\bB}{\boldsymbol{B}}
\newcommand{\bC}{\boldsymbol{C}}
\newcommand{\bD}{\boldsymbol{D}}
\newcommand{\bE}{\boldsymbol{E}}
\newcommand{\bF}{\boldsymbol{F}}
\newcommand{\bG}{\boldsymbol{G}}
\newcommand{\bH}{\boldsymbol{H}}
\newcommand{\bI}{\boldsymbol{I}}
\newcommand{\bJ}{\boldsymbol{J}}
\newcommand{\bK}{\boldsymbol{K}}
\newcommand{\bL}{\boldsymbol{L}}
\newcommand{\bM}{\boldsymbol{M}}
\newcommand{\bN}{\boldsymbol{N}}
\newcommand{\bO}{\boldsymbol{O}}
\newcommand{\bP}{\boldsymbol{P}}
\newcommand{\bQ}{\boldsymbol{Q}}
\newcommand{\bR}{\boldsymbol{R}}
\newcommand{\bS}{\boldsymbol{S}}
\newcommand{\bT}{\boldsymbol{T}}
\newcommand{\bU}{\boldsymbol{U}}
\newcommand{\bV}{\boldsymbol{V}}
\newcommand{\bW}{\boldsymbol{W}}
\newcommand{\bX}{\boldsymbol{X}}
\newcommand{\bY}{\boldsymbol{Y}}
\newcommand{\bZ}{\boldsymbol{Z}}
\newcommand{\ba}{\boldsymbol{a}}
\newcommand{\bb}{\boldsymbol{b}}
\newcommand{\bc}{\boldsymbol{c}}
\newcommand{\bd}{\boldsymbol{d}}
\newcommand{\be}{\boldsymbol{e}}
\renewcommand{\bf}{\boldsymbol{f}}
\newcommand{\bg}{\boldsymbol{g}}
\newcommand{\bh}{\boldsymbol{h}}
\newcommand{\bi}{\boldsymbol{i}}
\newcommand{\bj}{\boldsymbol{j}}
\newcommand{\bk}{\boldsymbol{k}}
\newcommand{\bp}{\boldsymbol{p}}
\newcommand{\bq}{\boldsymbol{q}}
\newcommand{\br}{\boldsymbol{r}}
\newcommand{\bs}{\boldsymbol{s}}
\newcommand{\bt}{\boldsymbol{t}}
\newcommand{\bu}{\boldsymbol{u}}
\newcommand{\bv}{\boldsymbol{v}}
\newcommand{\bw}{\boldsymbol{w}}
\newcommand{\bx}{\boldsymbol{x}}
\newcommand{\by}{\boldsymbol{y}}
\newcommand{\bz}{\boldsymbol{z}}
\newcommand{\bpi}{\boldsymbol{\pi}}
\newcommand{\btau}{\boldsymbol{\tau}}$
Distributions
- Density function
- Repairing distributions
Entropies
- Entropy
- KL divergence
- Sanov’s theorem
- Entropy deficit
- Cross-entropy
- Mutual information
- Power entropies