Shannon vs Universal Compression
February 16, 2023
$$
\newcommand{\mb}{\mathbb}
\newcommand{\mc}{\mathcal}
\newcommand{\B}{\mb{B}}
\newcommand{\Z}{\mb{Z}}
\newcommand{\N}{\mb{N}}
\newcommand{\R}{\mb{R}}
\newcommand{\D}{\Delta}
\newcommand{\X}{\mc{X}}
\newcommand{\T}{\Theta}
\newcommand{\O}{\Omega}
\newcommand{\o}{\omega}
\newcommand{\l}{\lambda}
\newcommand{\z}{\zeta}
\newcommand{\g}{\gamma}
\newcommand{\e}{\varepsilon}
\newcommand{\E}{\mb{E}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\par}[1]{\left(#1\right)}
\newcommand{\brac}[1]{\left[#1\right]}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\real}[1]{#1^{(\R)}}
\newcommand{\bin}[1]{#1^{\par{\B^\infty}}}
\newcommand{\binn}[1]{#1^{\par{\B^n}}}
\newcommand{\cyl}[1]{{\overbracket[0.5pt]{\underbracket[0.5pt]{#1}}}}
\newcommand{\int}[2]{\left[#1,\,\,#2\right)}
\newcommand{\len}[1]{\abs{#1}}
\newcommand{\Mid}{\,\middle\vert\,}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\up}[1]{^{\par{#1}}}
\newcommand{\Km}{Km}
$$
References
An Introduction to Kolmogorov Complexity and Its Applications - Li & Vitanyi 2008 (L&V) Elements of Information Theory - Cover & Thomas 2nd ed. 2006 (C&T) A Mathematical Theory of Communication - Claude Shannon 1948 (Shannon) AIT = Algorithmic Information Theory…