\documentclass[a4paper]{slides}
\usepackage{amsmath,amsthm}

\advance\textheight \headheight
\advance\textheight \headsep
\topmargin=-10mm
\headheight=0pt
\headsep=0pt
\advance\textheight -\topmargin

\hyphenpenalty=10000
\parindent=0pt

\begin{document}
\begin{titlepage}
\begin{center}
\large\bf
A comparison of growths of simple and prefix entropies
\end{center}
\vspace{7ex}
\centerline{Alexei Semenov\hfil Andrej Muchnik}
\vspace{3ex}
\centerline{\it Institute of New Technologies}
\centerline{\it Moscow}
\end{titlepage}
\begin{slide}
Plain (simple) entropy $KS(x)$ of a binary word $x$ is
the length of the shortest code of $x$
in a certain optimal  encoding system.

Prefix entropy $KP(x)$ of a binary word $x$ is
the length of the shortest code of $x$
in a certain optimal encoding system such that
any code does not extend any other code.

Clearly, prefix encoding is
\mbox{\emph{uniquely decodable:}}\\[1.4ex]
\centerline{
\parbox{0.9\textwidth}{
no binary word can be divided\\
into codes in two different ways}
}

A uniquely decodable but not prefix code:
$$
\{0,010\}
$$

{\bf McMillan--Kraft Theorem}\\
For any uniquely decodable encoding system
there exists a prefix encoding
with the same code-word lengths.
\end{slide}

\begin{slide}
$w_1,\ldots, w_k$ are code words,
$L=\max\limits_i \ell(w_i)$

$$
(w_1+\cdots+w_k)^n \le
\sum_{l\le nL}\; \sum_{\ell(v)=l} v
$$

$$
\left(2^{-\ell(w_1)}+\cdots+2^{-\ell(w_k)}
\right)^n \le
nL\cdot 1
$$

Consequently,
$$
2^{-\ell(w_1)}+\cdots+2^{-\ell(w_k)} \le 1
$$

\bigskip
\bigskip

Passage to the limit proves the theorem
for the countable number of code words.

Given the code-word lengths,
a prefix encoding is constructed easily
step by step beginning with the smallest length.
\end{slide}

\begin{slide}

Obviously, for any $x$
\begin{gather*}
KS(x) \le KP(x) + O(1)\\[1ex]
KS(x) \le \ell(x) + O(1)
\end{gather*}

\begin{gather*}
\sum_x 2^{-KS(x)}\ge
 \sum_x 2^{-\ell(x)-O(1)} = \infty\\[2ex]
\sum_x 2^{-KP(x)}\le 1
\end{gather*}

Therefore, $KP(x)-KS(x)$ is unbounded.

Does $KP(x)-KS(x)$ tend to infinity?
\end{slide}

\begin{slide}
{\bf Theorem (R.\:Solovay, unpublished)}
\begin{multline*}
KP(x)-KS(x)\;\ge\\[.5ex]
KP(KP(x))- 2 KP(KP(KP(x))) - O(1)
\end{multline*}

{\bf Proof}

{$\strut$}
\centerline{
$S_{n,i}\subseteq \{0,1\}^n$
}\\[1ex]
\centerline{
$i\ne k \Rightarrow S_{n,i}\cap S_{n,k}=\emptyset$
}\\[1ex]
\centerline{$\bigl|S_{n,i}\bigr| =
\left\lfloor 2^{n-KP(i)}\right\rfloor$ }

Define an auxiliary coding function~$f$:\\
enumerating from above the function $KP$,
for $y\in S_{n,i}$ and $x$ such that $KP(x) < n+i$,\\
put $f(y)=x$
(if $f(y)$ was not defined before).

\bigskip

Let $KP(x)=m$, $KP(m)=j$.\\
Let $n=m-j+2KP(j)$, $i=j-2KP(j)+1$.

It is sufficient to prove that
$\forall^{{}^\infty} i\;\forall n$
$$
\bigl|S_{n,i}\bigr|\ge \bigl|\{z\mid KP(z) < n+i\}\bigr|
$$
\end{slide}

\begin{slide}
$KP(x)=m$, $KP(m)=j$,\\
$n=m-j+2KP(j)$, $i=j-2KP(j)+1$.\\
\smallskip
\hrule height 1pt
\vspace{5ex}

\begin{gather*}
\alpha(q)= \sum_{KP(z) < q} 2^{-q}\\[1.5ex]
\alpha(q)\;\text{is enumerable from below
semimeasure}\\[1ex]
\sum_q \alpha(q) = \sum_z 2^{-KP(z)} \le 1
\end{gather*}

\centerline{Hence,\hfill
$\alpha(q) \le 2^{-KP(q)+O(1)},\hfill$}
$\bigl|\{z\mid KP(z) < m + 1\}\bigr| \le 2^{m-KP(m)+O(1)} =$\\[1ex]
$2^{n - 2 KP(j)+O(1)} =
\bigl| S_{n,i}\bigr|\cdot 2^{KP(i) - 2KP(j) +O(1)}$

$KP(i)\le KP(j) + KP(KP(j)) + O(1)$

\qed
\end{slide}

\begin{slide}

\begin{multline*}
KP(x)\;\ge\\[.5ex]
KS(x) + KP(KP(x))- O(\log\log\ell(x))
\end{multline*}

This bound is sharp:

\begin{multline*}
KP(x) \le KS(x) + KP(KS(x)) + O(1)\le\\[1ex]
\hfill KS(x) + KP(KP(x)) + \hfill\hfill\hfill\hfill\\
    KP(KP(x)-KS(x)) + O(1)\le\\[1ex]
 KS(x) + KP(KP(x)) + O(\log\log\ell(x))
\end{multline*}

\end{slide}

\begin{slide}

 The graphs of  $KS$ and $KP$ are close:
 $$
  KS(y) \gg KS(x) \quad\Leftrightarrow\quad
   KP(y) \gg KP(x)
 $$

\centerline{({\small $K(y)\gg K(x)\text{ means }
 K(y) - K(x) \ge \Omega(\log\max\{\ell(x),\ell(y)\})$})}



{\bf Theorem}\\
({\it\small Theor. Comp. Sci., 2002, 271, pp.15--35})\\[1ex]
\hspace*{1em} $\forall C\;\exists x,y$
\begin{align*}
 KS(y) &> KS(x) + C\\
\intertext{and}
 KP(y) &< KP(x) - C
\end{align*}


\end{slide}

\end{document}