% created 18.11.04
% edited 20.11.04
% edited 21.11.04
% edited 04.12.04
% edited 05.12.04
% edited 23.12.04
% ����������� �� ������ ������ � �������� ������� ��� ������������ �.�.
% � ���������� � �������������� ���� 24.05.2007 - ����
% ������ ������� (�����-�� ������������� � ��������)


\documentclass[12pt,a4paper%,draft
]{article}

\usepackage{amsmath,amssymb,russcorr}
\usepackage{amsthm}
\usepackage{russadd}
\usepackage{fullpage}
\usepackage{soul}

\newcommand{\F}{\mathcal{F}}
\newcommand{\E}{\mathbf{E}}

\newtheorem{theorem}{�������}
\newtheorem{lemma}{�����}
\renewcommand{\proofname}{\so{��������������}}

%\usepackage{Defs}

%\hfuzz=0.5pt
%\tolerance=500
\sloppy

\author{������� ������� �������\thanks{
        e-mail: alsemenov@mtu-net.ru,
        fax: +(095)9156963.}
        \and
        ������ ����������� ������\thanks{
        e-mail: muchnik@lpcs.math.msu.su,
        fax: +(095)9156963.}
       }

\title{����������� ��������� �������������
��������� ���� ���������\footnote{
������ ��������� ��� ��������� ���������
����������� ����� ��������������� ������������,
������� \�����~04-01-00427, \�����~02-01-10904, �
������ ��������� ������� ���� ��� ���������� ��.}
}

\date{}

\begin{document}

\maketitle

\begin{center}
\textit{�������������� ����� ���, ��������� �����������,}\\
\textit{119991, ������, ���-1}
\end{center}



\begin{abstract}
��������������� ��������������� �~������ ����������
������������������� � �������� �������� $A$ (inductive inference).
���������� ���������� ���������� ������������� ������������
��~$A$. ������������� $p$ ���������������� ��� ������� ��� $n$\�
�� ����� ������������������ $y_1,y_2,\ldots$, ���� �~����� ������
������ �������� ��� ��������� ��������� $y_{n-1},y_{n-2},\ldots$
�������� ����������� ������� $y_n=a$ ����� $p(a)$.

�����������, ���� ������� � ���������� ��������� ���������. ���
�������� �� ���� ��������� ������������������� ��������� ���
������ $n$ ������ ��������� ������������������ $y$, �~�����
�������� ������ $n-1$ ������ $y$. �� ����� ������ �ݣ ���� �������
��� $n$\� �� ����� $y$. �����������, ��� ��� ������� ����� $y$
������� �� $j$\� �� ������������������ ������� �� $j$\� �� ��������.
�����\- �� ���������, ����� ������������������ ��������� �� ������
��������� ��������� ���������� ������ (� ������������� ������)
�~����� ������ ������� ��������. ��� ��������� ��������
��������������� ������������ ���������� ����������.

��� ��������, ����� ��������� ����, ������� �����������
(������������ ��������������� ���� ��������) ���������
���������������. �������� ��������������� ���� ������������
��������: \�� ���������� �������\��\ � \�� ������������
�������������\��.
\end{abstract}

\section[��������� ���� � ������ ������� ����������]
{��������� ���� � ������ ������� ����������}

���� �� �������� ��� �ޣ���� ��������� ������ ��� �������������
������������ $p$ � $q$, �� ���������� ����� ���� �� ����� ��������
�� ����������: $\rho(p,q)=\sum_{i}(\sqrt{p(i)}-\sqrt{q(i)})^2$.
���� � ������ ������� ��������� ����������. ����ף� ���������
�������, �� ������� �� ����� ������������ ������ ����������
����������.

��-������, � 1986 �. ���� ������� ���������  (��.~\cite{Vovk}).

����� �� ������������ ����������� ������������������� � ��������
�������� $A=\{a_0, a_1,\dots\}$ (�� ���� �� ������ ���������
$|A|$) ���� ��� ���������� ���� $P$ � $Q$, ������������� �� ����
�������. ���� $P$ ������ ��� �������� $x$ ����� ������������
$P(x)$. ��� $a\in A$ ��������� $P(xa|x)$ ����� ����������
$P(xa)/P(x)$. ���� $x$ ������������, �� $P(xa|x)$ ������
������������� ������������ ��~$A$. ������ ����� $n$ �����������
������������������ $y$ ��������� ����� $y_{1:n}$.

����������� ������������������ $y$, ��������� �� ������-���
������������ $P$, ����� � ������ ����� �������� �� ������-���
������������ $Q$, �����
        $$
\sum_{n}\rho(\lambda
a.P(y_{1:n}a|y_{1:n}), \lambda a.Q(y_{1:n}a|y_{1:n}))<\infty
        $$
(� ���������� ������ $\lambda a.$ ����� ����������).

�������� ����������� �������� � �������� ������ ���������� ��
�������.

��-������, ������� $\rho$ ����������� � ���������� (� �������,
��������, �� ����� ������������ � �������������� ����������
���������� �������� � ���������� $\chi^2$). ��������, ������
$0\leqslant\rho\leqslant2$ � $\rho(p,q)=0\Leftrightarrow p=q$.
������� ������ ����������� �������~$\rho$. ���� $\forall i\
(p(i)=0\rightarrow q(i)=0) \land \forall i (p(i)\neq 0\rightarrow
|p(i)-q(i)|\leqslant\varepsilon\ll p(i))$, ��
$\rho(p,q)=O(\varepsilon^2)$. ���� �� $\exists i\ (p(i)=0\ \land\
q(i)=\varepsilon>0)$, �� $\rho(p,q)>\varepsilon$. ��� �������� ���
����, ��� ������ ������ ������� ����������� �� ��������� ������
������� ������, ��� ������ ���������� ��������� �������������
�����������. ��������, ������ ������� �������� ������������
���������� $$L_1(p,q)=\sum_i |p(i)-q(i)|;$$
$$L_2(p,q)=\sqrt{\sum_i (p(i)-q(i))^2};$$ $$L_{\infty}(p,q)=\max_i
|p(i)-q(i)|.$$ �~������ �������, � ������� �� $L_1$, $L_2$,
$L_\infty$, ������� $\rho$ �� �������� ������: $\rho(p,q)$ ������
������ ������ $\rho(p,r)+\rho(q,r)$ \smash[b]{\Big(}��������, ���
$p=(1,0)$, $q=(0,1)$, $r=\left(\frac12,\frac12\right)$\Big).
�����������, ������� � ����������� ������������, ��� $\rho$
�ӣ-���� ����: $\rho(p,q)\leqslant2(\rho(p,r)+\rho(q,r))$.

\section{�������� �����������}

����� �������� $A$ ����� ���������������� ��� ��������� �������,
$n$\� �~����� ������������������ � �������� $A$ ����������������
��� �������, ������������ � ������ �������~$n$. \emph{���������}
����ף� �������, ������� ������ �������� ������������������ $x$
���� �� $A$ ������������ ������������� ��~$A$, ������������
$P(xa|x)$ (��� �������, ���
� ���������� ������� ������� ��������� ������� �� $x$, �����������
����, ��� � ��������� ������ �������ģ� ������� $a$, �~�����
������ �������� ����� $P(xa|x)$). ���� ����~--- �� ������
$P_1,\dots,P_J$ ���������
��������� �ݣ ������ �������� $Q$, ������������
�������� ���� �� ���������� ����� �~����� ������ ������� ��
��������� ���������. \emph{��������� ������} �������� $Q$ �~�����
������ �������� $P$ �� ������������������ $\langle
y_1,\dots,y_N\rangle$ ��������� ��� $\sum_{n=0}^N
\rho(P(y_{1:n}a|y_{1:n}), Q(y_{1:n}a|y_{1:n}))$. ��� ��� ������
��� ������ ������������, �� �� ��������� ��������� �������
��������� ������, �� �������, ����� ����������� ������ ���������
�~����� ������ $P$ ���� ����. �� ���� ��� ����� ������������
�������� �������� ������� $\F_{P,Q}(s)$, ������ ���� $P$ ���������
$\{y\,|\,\sum_{n=0}^\infty \rho(P(y_{1:n}a|y_{1:n}),
Q(y_{1:n}a|y_{1:n}))>s\}$. (����� ����� ��������� ��������
$P(xa|x)$, ��� ������� ��� ��� ���������� ����������, ��
���������� �� ���������� �����������, �� ��������� ��������
��������, ��������� �~�������� �� ����.)

����ף� \emph{��������������} ��������, �������, �������
������������������ $\langle y_1,\dots,y_{N}\rangle$ � ��������
$P_j(y_{1:n}a|y_{1:n})$ ��� ���� $j\in\{1,\dots,J\}$,
$n\in\{0,\dots,N\}$, $a\in A$, ������ ������������� ������������
�� $A$, ��������������� $Q(y_{1:N}a|y_{1:N})$. (��� $N=0$
������������� �������� �� ���� ������ ������������������.) ��
����� �������� ������������� \emph{�������} �������������, ���
������� $\forall N\ \exists j\ \forall a\
Q(y_{1:N}a|y_{1:N})=P_j(y_{1:N}a|y_{1:N})$ � ������� ��� ������
������ �� $j$ �� ���� $N$ �� ��������� ��������
$P_j(y_{1:N}a|y_{1:N})$. ������� �������� ������������� ��������
����� ��� ��� ����������, ����� ������ �������� ���������� ������
�������� � �������� �������.

�����������, ��� � ���������������� ������������������ $y$
����������� � ������������ �~�������������� $R$. �����
������������ $Q$ �������� ���������� ������� ������������ $R$,
���� \emph{���� �� ����} �� ��������� $P_j$ ���������� �����
������������ $R$. (��� ��������� ���������� �������� ��������
$\F_{R,Q}(s)$ � $\F_{R,P_j}(s)$.) ��� ��� ���� ���������� �����
�������� ������ ������� $\F_{P_j,Q}(s)$, �� ������� �������������
� �������������� ������������� $R$ (� ���� � ��� �������) �
������������� ������ ��� �� �����������.

�~������ 1950-� ����� ��������� ���������� ������� �������������
(inductive inference) � ��������� ����� ��������������, ����������
\emph{���������� �������}. �������� ������� �������� $P_j$ ���
$w_j>0$ ���, ��� ���� �������� ������������� ������������ ��
������� ���������. �����������, ��� ����� ��������� ���� �����,
������� ������������� \�� ���������\��, �� ���� ��� ������������
��������� �~������������ ������������� $R$. ����� ��� $w_j$
�������� ������� ����� ��������� ����������� � ���, ��� ���������
��������� �������� $P_j$. ����� ��������� ���������� � ������ $n$
�������� ($\langle y_1,\dots,y_n\rangle=z$) ���� ������� � $j$\� ��
��������, �����������, ����� ��������. ��� ����������� ��
������������ ������� $w_jP_j(z)/\sum_i w_iP_i(z)=W_j(z)$.
������������� $Q$ (\�� ���������� �������\��) ������������ ���:
$Q(za|z)=\sum_j W_j(z)P_j(za|z)$. ������ �����������, ���
$Q(za|z)=\sum_j w_jP_j(za)/\sum_j w_jP_j(z)$ � ���
$W_j(za)=W_j(z)P_j(za|z)/\sum_i W_i(z)P_i(za|z)$. ����� �������,
������������� $Q$ ��� ������ ���������� ������� ������������� ����
$W_j(z)$ � �������� ��������� ������������ ������� ��������.
�������, ��� ������������� $P_j=R$ ���� ����� ������ ���
�����������. ���������, � ����������� ��� ����� �� ������������.

�~������� ������� ������������� \�� ���������� �������\��\ �������
����� ������������. ������ ���������� �������� ��������� ���������
� ��������� ��������� �������������. ����� �������� ������������ �~������� ������� ������� ������������� \emph{������������
�������������}. ��� ����� ������������� $\forall a\
Q(y_{1:n}a|y_{1:n})=P_j(y_{1:n}a|y_{1:n})$ ��� ���� (������ ��
���)~$j$, ��� �������� $P_j(y_{1:n})$ ��������� ����������
��������. ��� ������ ��� ���������� ������� �����
$P_j(y_{1:n})/\sum_i P_i(y_{1:n})$ � �������� ���������
������������ ������� ��������.

\section{����� �����������}

��� ����, ��� ��� ������������� \�� ���������� �������\��\
�������� �������� ������������ $Q(y_{1:n+1}|y_{1:n})$ �
$P_j(y_{1:n+1}|y_{1:n})$ ���������� ��� ����� $n$ ��� ����� ����
$y$ � ������ $P_j$, ��� �������� ���������� �~������ ������. ��
������� ���� ��� ����� ��� $P$ � $Q$, �������� �� ������,
��������� $Q(y_{1:n})/P(y_{1:n})$ ����� �������� ������ ���
$n\to\infty$ ��� ����� ���� � ������ ���� $P$
�������������������~$y$. ��������� ��� \�� �����������
��������\��\ ����� ��������� $Q(x)/P_j(x)\geqslant w_j$, �� �����
����� $\lim\limits_{n\to\infty}Q(y_{1:n})/P_j(y_{1:n})>0$, �
�������������, ����������� ��������� $\lim\limits_{n\to\infty}
Q(y_{1:n+1}|y_{1:n})/P_j(y_{1:n+1}|y_{1:n})=1$. ���� ��������
����������� $P(xa|x)$ ����� ������ �����-������ �������������
���������, �� ������� ���� ����� ��������: ��� ������ ��������
������������������ $z$ ��� ����� ���� ������������ $P$ �����������
������������������� $y$ ������ ��� $n\to\infty$ ���������
$Q(y_{1:n}z)/P(y_{1:n}z)$ �����
$\lim\limits_{n\to\infty}Q(y_{1:n})/P(y_{1:n})$. �������������,
��� ������� $\exists\delta>0$ $\forall x,a$ $P_j(xa|x)>\delta$ ���
����� ���� ������������ �������� $P_j$ �����������
������������������� $y$ ��������� $\forall
z,a$~$\lim\limits_{n\to\infty}
Q(y_{1:n}za|y_{1:n}z)/P_j(y_{1:n}za|y_{1:n}z)=1$, ��� $Q$~---
���������� ������� ��������� $P_i$. (������� ����̣������ �� ����
�������� ������������ �������� ����������� � ������� 5.2.2 ��
\cite[�. 332]{Li}. �������������� ����� ������� ����������
��������� ������. ����� $P_1$, $P_2$~--- ���� �� �������� ������,
� $\forall n$ $P_1(0^n1|0^n)=(n+2)^{-3}$,
$P_2(0^n1|0^n)=(n+2)^{-2}$. ��� ���� ������������ ��
������������������ $0^\omega$. �������������, ������������� ����
$W_1(0^n)$, $W_2(0^n)$ ����� ������������� ������� ���
$n\to\infty$. ����� $Q(0^n1|0^n)=\Omega((n+2)^{-2})$ �
$\lim\limits_{n\to\infty} Q(0^n1|0^n)/P_1(0^n1|0^n)=\infty$.)

���� ���� $Q$ ��������� �������������� \�� ������������
�������������\��, �� ��� ������� $j$ ����� ����� �� ��
�����������: ��� ����� ���� ������������ $P_j$
������������������� $y$
         $$
\lim\limits_{n\to\infty}
    {Q(y_{1:n+1}|y_{1:n})}/{P_j(y_{1:n+1}|y_{1:n})}=1;
         $$
���� $\exists\delta>0$ $\forall x,a$ $P_j(xa|x)>\delta$, �� ���
����� ���� ������������ $P_j$ ������������������� $y$
        $$
\forall
z,a\ \lim\limits_{n\to\infty}
Q(y_{1:n}za|y_{1:n}z)/P_j(y_{1:n}za|y_{1:n}z)=1.
        $$

�������������,
� ������ ������� $x$ �������� ����������� $Q(xa|x)$ ����� ����� ��
�������� ������������ $P_i(xa|x)$. ������� ������\break
$Q(y_{1:n+1}|y_{1:n})/P_j(y_{1:n+1}|y_{1:n})$ ����� ����� 1, ����
����� 1 �������\break $P_i(y_{1:n+1}|y_{1:n})/P_j(y_{1:n+1}|y_{1:n})$
��� ��� $i$, ��� ������� � ���������� ������ �������� $y_{1:n}$
$i$\� � ������� �������� �������������. ��� ����� $i$
$\exists^\infty n\ P_i(y_{1:n})/P_j(y_{1:n})\geqslant1$, �
�������������, ������ $P_i(y_{1:n})/P_j(y_{1:n})$ ����� ����
������ �������������.

������� ���� � ���������� �� ��� ����������� �� ���� �������
������ �� �������� ��������� $Q(y_{1:n+1}|y_{1:n})$ �
$P_j(y_{1:n+1}|y_{1:n})$. �~1978~�. ��������� \cite{Solomonov}
������� ����� ������ ��� ������������� \�� ���������� �������\��.
�� �������, ��� ��� ������� $j$
\[
\E_{P_j}\sum_{n=0}^\infty
\rho\,'(P_j(y_{1:n}a|y_{1:n}), Q(y_{1:n}a|y_{1:n}))\leqslant -\ln
w_j,
\]
��� $\rho\,'$~--- ���������� �������� ($\rho\,'(p, q)=\sum_a
p(a)\ln (p(a)/q(a))$). �� ����� �������, ��� ���� $P_j$ ���������
$\{y\,|\,\sum_{n=0}^\infty \rho\,'(P(y_{1:n}a|y_{1:n}),
Q(y_{1:n}a|y_{1:n}))>s\}$ ������ $(-\ln w_j)/s$. ������� $(-\ln
w_j)/s$ ������� ������� ��������. �~������ \cite{Vovk} ����
�������� �����������, �� ������� �����, ��� ��� ����������
���������� $\rho$
\begin{equation}
\label{Vovkformula01} \E_{P_j}e^{\frac12\sum_{n=0}^\infty
\rho(P_j(y_{1:n}a|y_{1:n}), Q(y_{1:n}a|y_{1:n}))}\leqslant
w_j^{-1/2}.
\end{equation}

��� ��� ������� $e^x$ ������� ����, ��
\begin{multline*}
e^{\E_{P_j}\frac12\sum_{n=0}^\infty \rho(P_j(y_{1:n}a|y_{1:n}),
Q(y_{1:n}a|y_{1:n}))}\leqslant\\
\leqslant\E_{P_j}e^{\frac12\sum_{n=0}^\infty
\rho(P_j(y_{1:n}a|y_{1:n}), Q(y_{1:n}a|y_{1:n}))}\leqslant
w_j^{-1/2}.
\end{multline*}
����� ���������������� � ��������� �� 2 ���������� ����� ��
���������, ��� � ����������, ������ ��� ���������� $\rho$, �~��
$\rho\,'$. �~������ �������, �� �����, ��� ���� $P_j$ ���������\\
$\{y\,|\,\sum_{n=0}^\infty \rho(P_j(y_{1:n}a|y_{1:n}),
Q(y_{1:n}a|y_{1:n}))>s\}$ (������� �� ���������� �����
$\F_{P_j,Q}(s)$) ������ $w_j^{-1/2}e^{-s/2}$.

��� �������������� \eqref{Vovkformula01} ���� �������������
��������������� ���� $R(x)$ �� ������, ������������ �� �����������
��� �������� ������������ $R(x_{1:n}a|x_{1:n})=
\frac{\sqrt{P_j(x_{1:n}a|x_{1:n})Q(x_{1:n}a|x_{1:n})}} {\sum_b
\sqrt{P_j(x_{1:n}b|x_{1:n})Q(x_{1:n}b|x_{1:n})}}$. ���������
�������� $\rho(p,q)=2-2\sum_{i}\sqrt{p(i)q(i)}$ ��� ����������
����������, ����������� �����������:
\[
\sum_b
\sqrt{P_j(x_{1:n}b|x_{1:n})Q(x_{1:n}b|x_{1:n})}=
1-\frac12\rho(P_j(x_{1:n}b|x_{1:n}), Q(x_{1:n}b|x_{1:n})).
\]
�����
\begin{multline*}
R(x_{1:n})=\prod_{m=0}^{n-1}
\frac{\sqrt{P_j(x_{1:m+1}|x_{1:m})Q(x_{1:m+1}|x_{1:m})}} {\sum_b
\sqrt{P_j(x_{1:m}b|x_{1:m})Q(x_{1:m}b|x_{1:m})}}=\\
=\frac{\sqrt{P_j(x_{1:n})Q(x_{1:n})}}{\prod_{m=0}^{n-1}
(1-\frac12\rho(P_j(x_{1:m}b|x_{1:m}),Q(x_{1:m}b|x_{1:m})))}.
\end{multline*}
��������� $e^{-z}\geqslant1-z$, �� ����� ������
\begin{multline*}
R(x_{1:n})\geqslant \frac{\sqrt{P_j(x_{1:n})Q(x_{1:n})}}
{\prod_{m=0}^{n-1} e^{-\frac12\rho(P_j(x_{1:m}b|x_{1:m}),
Q(x_{1:m}b|x_{1:m}))}}=\\ =\sqrt{P_j(x_{1:n})Q(x_{1:n})}
e^{\frac12\sum_{m=0}^{n-1}\rho(P_j(x_{1:m}b|x_{1:m}),
Q(x_{1:m}b|x_{1:m}))}=\\ =\sqrt{\frac{Q(x_{1:n})}{P_j(x_{1:n})}}
P_j(x_{1:n}) e^{\frac12\sum_{m=0}^{n-1}\rho(P_j(x_{1:m}b|x_{1:m}),
Q(x_{1:m}b|x_{1:m}))}\geqslant\\ \geqslant\sqrt{w_j}P_j(x_{1:n})
e^{\frac12\sum_{m=0}^{n-1}\rho(P_j(x_{1:m}b|x_{1:m}),
Q(x_{1:m}b|x_{1:m}))}.
\end{multline*}
����� �������, $w_j^{-1/2}R(x_{1:n})\geqslant P_j(x_{1:n})
e^{\frac12\sum_{m=0}^{n-1}\rho(P_j(x_{1:m}b|x_{1:m}),
Q(x_{1:m}b|x_{1:m}))}$, �~����� ������������ �� ���� $x$ ����� $n$
��������~\eqref{Vovkformula01}.

\emph{��������������� �������������} ����ף� ������ ������� ����� ���
$\alpha$, ��� ������� �� ����� ��������� $P_j$ �������������
������ ������ �������� $Q$, ��� $\forall j\
\F_{P_j,Q}(s)=O(e^{-\alpha s})$. ������������� ��� �����������,
��� ������ ��� ��������������. ��� ��������, ����� ��������� ����,
���� �������� ��������� ����������. ������� 5 ����������, ���
�������������� \�� ����������� ��������\��\ �����
$\frac{1}{2}$, �~�������������� \�� �������������
�������������\��\ �� ��������� $\frac{1}{2}$. �~�� �� �����, �
������� 6 �������� ������� ������������� �~��������������� 1. ��
������� 4 �������, ��� ��� �������������� ���������� ���������
���� � ������ ���� ��������������.

����� �������, ������������� \�� ���������� �������\��\ � \��
������������ �������������\��\ ������ �� ���������� � ������ ����
�������������� � � ������ ���� ������� ��������������,
��������������. \emph{��������������� ���������} $\kappa$,
���������� �� ��������������, ����ף� ������ ������� �����
����� $\alpha$, ��� ��� ���������� $\beta$ � ��� ����
$s>0$ ���������� ������������� ��
$\kappa$, ������� �� ����� ��������� $P_j$ ������ �������� $Q$ ��
��������� $\forall j\ \F_{P_j,Q}(s)<e^{\beta-\alpha s}$.
�������������� ������������� �������� ��������� �~���������������
��������������� ���������, ����������� ���� �������������. ��
�������� 6 � 3 �������������� ������ ���� ������� ��������������
�����~1. �~��� �������������� ������ ���� ��������������
����������� ������ 2, � ������������ �~��������� 1 � 2.

\section{������ ������ ���������� �������������}

\begin{lemma}
����� �� �������� �������� ��������� $A$ ��� ��������
�������� ����� ������������� ������������ $\{p_j\}$. ����������
������������ ������������� ������������ $q$ �� $A$, ��� ��������
��������� �������� ����� ���������� ���������� �� $p_j$ �� $q$.
\end{lemma}
\begin{proof}
��� ��� ������������ ������������� ������������ �� $A$ ��������� �
������� �������, �~���������� ���������� ���������� � �������
�������, �� ������� $\sum_j \rho(p_j,q)$ ����������� ��� ������-��
$q$. �������, ��� ���� $q(a)=0$, �� $\forall j\ p_j(a)=0$.
���������� �� $b$, ��� �������� $q(b)>0$, � ���������� �����
������������� ����� $\varepsilon$. ��������� �������������
������������ $r$ �� $A$: $r(a)=\varepsilon$,
$r(b)=q(b)-\varepsilon$, �� ��������� ��������� $A$ �������������
$r$ ��������� �~$q$. �������� ����� $\sum_j \rho(p_j,r)$ � $\sum_j
\rho(p_j,q)$ ����� $2(\sqrt{q(b)}-\sqrt{q(b)-\varepsilon}\,)
\sum_j\sqrt{p_j(b)}-2\sqrt{\varepsilon} \sum_j\sqrt{p_j(a)}$.
��������� $\sqrt{q(b)}-\sqrt{q(b)-\varepsilon}=O(\varepsilon)$, ��
� ������ $\exists j\ p_j(a)>0$ ���� �� $\sum_j \rho(p_j,r)<\sum_j
\rho(p_j,q)$.

���� ��� ���������� $b$ �������� $q(b)=1$, �� $\forall a\neq b\
q(a)=0$, $\forall j\forall a\neq b\ p_{j}(a)=0$ � $\forall j\
p_{j}(b)=1$. ����� $\sum_{j}\rho(p_j,q)=0$ � $\forall r\neq q\
\sum_{j}\rho(p_j,r)>0$.

����� $B$~--- ��������� ��� ��������� $A$, �� ������� $q$
������������ � $|B|\geqslant 2$. ����� $\sum_{b\in B} q(b)=1$ �
$\forall j\ \sum_{b\in B} p_j(b)=1$. ������������� �������
$\sum_j(2-2\sum_{b\in B}\sqrt{p_j(b)}\sqrt{x_b}\,)$ �� �������
$x_b$, ������� ������ ������� �����������, ����������������
������� (1,\dots,1), ����� $\forall b\ x_b=q(b)$. �����������
��������� ������� �� $x_b$  � ����� $q$ �����
\hbox{($-\sum_j\sqrt{p_j(b)}/\sqrt{q(b)}$\,)}. �� ���� $q(b)$
��������������� $(\sum_j\sqrt{p_j(b)}\,)^2$ � ����������
$q(b)=\frac{(\sum_j\sqrt{p_j(b)})^2}
{\sum_a(\sum_j\sqrt{p_j(a)})^2}$. ��������� ������� ��������
��������� �� ���� ����������� �������.
\end{proof}

������� ���������� ����������, ���
        $$
\min_q\sum_j\rho(p_j,q)=2J-
2\sqrt{\sum_a \left({\displaystyle\sum_j\sqrt{p_j(a)}}\right)^2},
        $$
��� $J$~--- ���������� �������������~$p_j$. �������, ��� ���
������ $J=2$ ���������� $\rho(p_1,q)$ � $\rho(p_2,q)$ ���������
� ����� $2-\sqrt{4-\rho(p_1,p_2)}$.

\begin{theorem}
        %
��� ������� $s>0$ ���������� �������������, ������� ��
��������� $P_1$, $P_2$ ������ �������� $Q$ � $\forall j\
\F_{P_j,Q}(s)<e^{2}e^{-2s}$.
        %
\end{theorem}
        %
\begin{proof}
        %
����������� ��������� $s>0$. ����� $x$~---\break
������������������ �������. ������� ����� $x$, �������������
��\break ���������� ���� $m$ ������ �������������
$Q(x_{1:m}a|x_{1:m})$ �� $A$, ��-\break ������������ �����
���������� ���������� �� �������������\break
$P_1(x_{1:m}a|x_{1:m})$ �~$P_2(x_{1:m}a|x_{1:m})$. ��� ���� ��
���������� ��������\linebreak $c(x_{1:m})=
\sum_{i=0}^m\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))$.
������� � ��������� ������� $P_1$ ��� $P_2$~--- �� �����,
��������� �� ����� �� ��������. ��� �������� �������
$c(x_{1:-1})=0$. ���� ����� ���� $n$ ������ ��� �����
$c(x_{1:n})>s-(2-\sqrt2)$ (����ף� $x_{1:n+1}$ \emph{������
������������}), �� ������������� �������� $j$, ��� ��������
$P_j(x_{1:n+1})$ ������, � ������ ����� ��� $m>n$ ������
$Q(x_{1:m}a|x_{1:m})=P_j(x_{1:m}a|x_{1:m})$.

���ģ� ������ ��� $\F_{P_1,Q}(s)$ (� ���� ���������, �� �� ������
����� ����� � ��� $P_2$). �������, ��� ����
$\sum_{i=0}^m\rho(P_1(x_{1:i}a|x_{1:i}), Q(x_{1:i}a|x_{1:i}))>s$,
�� $m>n$, ��� ��� $\sum_{i=0}^{n-1}\rho(P_1(x_{1:i}a|x_{1:i}),
Q(x_{1:i}a|x_{1:i}))\leqslant s-(2-\sqrt2)$ �
$\rho(P_1(x_{1:n}a|x_{1:n}),Q(x_{1:n}a|x_{1:n}))=
2-\sqrt{4-\rho(P_1(x_{1:n}a|x_{1:n}),P_2(x_{1:n}a|x_{1:n}))}
\leqslant2-\sqrt2$. ���ޣ� ������������� � ����� $x_{1:n+1}$
������������ �� $P_2$, �~�� �� $P_1$, ����� ��� $m>n$ �����
$\rho(P_1(x_{1:m}a|x_{1:m}),Q(x_{1:m}a|x_{1:m}))=0$~�
$\sum_{i=0}^m\rho(P_1(x_{1:i}a|x_{1:i}),
Q(x_{1:i}a|x_{1:i}))=\sum_{i=0}^n\rho(P_1(x_{1:i}a|x_{1:i}),
Q(x_{1:i}a|x_{1:i}))\,{\le}\,s$. ����� �������, ����
$P_{1}$ ��������� $\{x\,|\sum_{i=0}^\infty
\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))\!>s\}$ ��
��������� ���� $P_{1}$ ��������� $M$ ��� ����� ������������
$x_{1:n+1}$, ��� $P_2(x_{1:n+1})\geqslant P_1(x_{1:n+1})$.

��� ������ $P_1(M)$ ���������� �����������, ������� �� �����������
�� �������������� �������~\eqref{Vovkformula01}. ����������
��������������� ���� $R(x)$, ���������� ������������ ��� ��������
������������
\[
R(x_{1:m}a|x_{1:m})=\frac{\sqrt{P_1(x_{1:m}a|x_{1:m})
P_2(x_{1:m}a|x_{1:m})}}{\sum_b \sqrt{P_1(x_{1:m}b|x_{1:m})
P_2(x_{1:m}b|x_{1:m})}}.
\]
�������, ��� ��� ������������ ������������� ������������ $p_1$,
$p_2$ �� $A$ ����� ����������� $1-\frac12\rho(p_1,p_2)\leqslant
e^{-2\rho(p_1,q)}$, ��� $q$~--- �������������, ��������������
����� ���������� ���������� �� $p_1$ � $p_2$. (�������������, ����
���������� $\rho(p_1,p_2)$ ����� $\rho$, ��
$\rho(p_1,q)=2-\sqrt{4-\rho}$. �����������
$\ln(1-\frac\rho2)\leqslant-4+2\sqrt{4-\rho}$ ����� ��� $\rho=0$,
������� ���������� ��� ��������� ��� �����������:
$\frac{-1}{2-\rho}\leqslant\frac{-1}{\sqrt{4-\rho}}\Leftarrow
\sqrt{4-\rho}\geqslant2-\rho\Leftarrow\rho(\rho-3)\leqslant0$.)
������ �� �������� �~���������������
�����������~\eqref{Vovkformula01} �������� ������ ���
$x_{1:n+1}\in M$
\begin{multline*}
R(x_{1:n+1})=\frac{\sqrt{P_1(x_{1:n+1})P_2(x_{1:n+1})}}
{\prod_{i=0}^{n}(1-\frac12\rho(P_1(x_{1:i}b|x_{1:i}),
P_2(x_{1:i}b|x_{1:i})))}\geqslant\\
\geqslant\sqrt{\frac{P_2(x_{1:n+1})}{P_1(x_{1:n+1})}}
P_1(x_{1:n+1}) e^{2\sum_{i=0}^{n}\rho(P_1(x_{1:i}b|x_{1:i}),
Q(x_{1:i}b|x_{1:i}))}\geqslant P_1(x_{1:n+1})e^{2s-4+2\sqrt{2}},
\end{multline*}
�� ���� $e^{-2s+4-2\sqrt{2}}R(x_{1:n+1})\geqslant P_1(x_{1:n+1})$,
� ������������� �� $M$, ������� ���������.
\end{proof}

\begin{theorem}
        %
$\forall\varepsilon>0$ ���������� ����� �������� $P_1$,
$P_2$ � ����� $s_0$, ��� $\forall s>s_0$ � ��� ������ �������� $Q$
$\exists j$ $\F_{P_j,Q}(s)>e^{-(2+\varepsilon)s}$.
        %
\end{theorem}
        %
\begin{proof}
        %
���������� �������������� ��������� ������� $\{0,1\}$ � ����������
����� $\delta>0$. ����� $n>1/\delta^3$; $P_1$\� �����������
��������� ���������� ���� ������ ����� $(1+\delta)/2$,
$P_1$\� ����������� ��������� ��������� ������� ������ �����
$(1-\delta)/2$; $P_2$\� ����������� ��������� ���������� ���� ������
����� $(1-\delta)/2$, $P_2$\� ����������� ��������� ���������
������� ������ ����� $(1+\delta)/2$. ����������� �������������
�������� $Q$.

��������� ����� $M$ ��������� �������� ���� ����� $2n$, � �������
����� $n$ ����� � ����� $n$ ������. �������� ����� ���������
������ $\frac{2^{2n}}{2\sqrt{n}}$. ���� $P_1$ � ���� $P_2$ �������
�������� �� $M$ ����� $\frac{(1-\delta^2)^{n}}{2^{2n}}$. ��������
�~��������� $M_1$ �� $x$ �� $M$, ��� �������
$$\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))
\geqslant
\sum_{i=0}^{2n-1}\rho(P_2(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i})).$$
�������� � ��������� $M_2$ �� $x$ �� $M$, ��� �������
$$\sum_{i=0}^{2n-1}\rho(P_2(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))
\geqslant
\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i})).$$
�����������, ��� $|M_1|\geqslant |M|/2$ (�������������
$|M_2|\geqslant |M|/2$ ��������������� �����������). ��� $x$ ��
$M_1$ �����
\begin{multline*}
\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))\geqslant\\
{\geqslant}
\frac{1}{2}\!\!\left(\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))
\,{+}\!\sum_{i=0}^{2n-1}\rho(P_2(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))\!\!\right)\,{=}\\
=\sum_{i=0}^{2n-1}\frac{1}{2}(\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))
+\rho(P_2(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))).
\end{multline*}
��� ������� �� ����� 1,
\begin{multline*}
\frac{1}{2}(\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))
+\rho(P_2(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i})))\geqslant\\
\geqslant
2-\sqrt{4-\rho(P_1(x_{1:i}a|x_{1:i}),P_2(x_{1:i}a|x_{1:i}))}>
\delta^2(1-o(1))/4
\end{multline*}
(�������� $o(1)$ ��������� � 0 ��� $\delta\to 0$). ����� �������,
��� $x$ �� $M_1$
$$\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))>
n\delta^2(1-o(1))/2.$$ ���� $P_1$ ��������� $M_1$ �����
\[
|M_1|\frac{(1-\delta^2)^{n}}{2^{2n}}> e^{-n\delta^2(1+o(1))-O(\ln
n)}>e^{-n\delta^2(1+o(1))}.
\]

������� $s_0=1/\delta$. ���� $n=\Big\lceil
\frac{2s}{\delta^2}(1+o(1))\Big\rceil$ (��� ����������
��������~$o(1)$), �� ��� $s>s_0$ ����� $n>1/\delta^3$,
$n\delta^2(1-o(1))/2>s$ � $\F_{P_1,Q}(s)>e^{-(2+\varepsilon)s}$.
\end{proof}

\begin{theorem}
        %
$\forall\varepsilon>0$ ���������� ����� �������� $P_1$,
$P_2$ � ����� $s_0$, ��� $\forall s>s_0$ � ��� ������ ��������
$Q$, ������������ ������� �������������� �� $P_1$ � $P_2$,
$\exists j$ $\F_{P_j,Q}(s)>e^{-(1+\varepsilon)s}$.
        %
\end{theorem}
        %
\begin{proof}
        %
����������� �������� ���������� �������������� ���������� �������.
������� ������ �������. ����������\break $\rho(P_j(za|z),Q(za|z))$
������ ����� ��� 0, ��� $\delta^2(1-o(1))$. �������������, ��� $x$
�� $M_1$ $$
\sum_{i=0}^{2n-1}\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))>
n\delta^2(1-o(1)). $$ ������� �������� $n$ �� ���� ��� ������
$\Big\lceil \frac{s}{\delta^2}(1+o(1))\Big\rceil$ (��� ����������
��������~$o(1)$). ����� ����� $n>1/\delta^3$,
$n\delta^2(1-o(1))>s$ � $\F_{P_1,Q}(s)>e^{-(1+\varepsilon)s}$.
\end{proof}

\begin{theorem}
        %
$\exists\varepsilon_0>0\
\forall\varepsilon\in(0,\varepsilon_0)$ ���������� ����� ��������
$P_1$, $P_2$, ��� $\forall s_1>0$ � ��� ������ �������� $Q$
��������� ���� �� ���� �� ���� ����������:
$\F_{P_1,Q}(s_1)>e^{-s_1}$,\ \
$\F_{P_2,Q}(s_2)>e^{-s_2(1+\varepsilon)}$, ���
$s_2=s_1\varepsilon^{-4}$.
        %
\end{theorem}
        %
\begin{proof}
        %
���������� �������������� ��������� ������� $\{0,1\}$, �����
$s_1>1$ � ���������� ����� $\varepsilon>0$. �����
$P_1$\� ����������� ��������� ���������� ���� ������ ����� 1,
$P_1$\� ����������� ��������� ��������� ������� ������ ����� 0;
$P_2$\� ����������� ��������� ���������� ���� ������ �����
$1-\varepsilon$, $P_2$\� ����������� ��������� ��������� �������
������ ����� $\varepsilon$. ����������� ������������� ��������
$Q$.

�������
$$n=\lceil\varepsilon^{-5}(1+4\,\varepsilon^{1.5})s_1+0.3\,\varepsilon^{-4}s_1\rceil.$$
��������� ����� $M$ ����� ��� �������� $0^n$. ��������� ���
$P_1$\� ���� �����~1, ���������� ��������, ��� �� ����������� $$
\sum_{i=0}^{n}\rho(P_1(0^ia|0^i),Q(0^ia|0^i))\leqslant s_1 $$
������� $\F_{P_2,Q}(s_2)>e^{-(1+\varepsilon)s_2}$.

���� ��� ���������� $i$ ����� �����
$Q(0^{i+1}|0^i)<1-\frac{10}{3}\,\varepsilon^4$, �� ����� �����
$\rho(P_1(0^ia|0^i),Q(0^ia|0^i))>\frac{10}{3}\,\varepsilon^4$ (��
������������ $\delta\leqslant 1\Rightarrow
2-2\sqrt{1-\delta}\geqslant\delta$). ������� ���������� ����� $i$
�� ��������� $0{,}3\,\varepsilon^{-4}s_1$. ��� ��������� �� $i$
(������� ������ $\varepsilon^{-5}(1+4\,\varepsilon^{1{,}5})s_1$)
��������
\[
\rho(P_2(0^ia|0^i),Q(0^ia|0^i))>\varepsilon\bigg(1-\sqrt{\frac{40}{3}}\,\varepsilon^{1,5}\bigg).
\]
�������������, ��������� $Q(0^{i}1|0^i)$ ����� $z$ \smash{\Big(}��
������������� $z\in \Big[0,
\frac{10}{3}\,\varepsilon^4\Big]$\Big). �����
        %
\begin{multline*}
\rho(P_2(0^ia|0^i),Q(0^ia|0^i))=
2-2\sqrt{1-\varepsilon}\sqrt{1-z}-2\sqrt{\varepsilon}\sqrt{z}\geqslant\\
\geqslant
2-2\sqrt{1-\varepsilon}-2\sqrt{\frac{10}{3}}\,\varepsilon^{2{,}5}>
\varepsilon-\sqrt{\frac{40}{3}}\,\varepsilon^{2{,}5}.
\end{multline*}
        %
����� �������,
\[
\sum_{i=0}^{n}\rho(P_2(0^ia|0^i),Q(0^ia|0^i))>
s_1\varepsilon^{-4}(1+4\,\varepsilon^{1{,}5})\bigg(1-\sqrt{\frac{40}{3}}\,\varepsilon^{1{,}5}\bigg)>s_2.
\]
����� ����, $P_2$\� ���� ��������� $M$ �����
\begin{multline*}
(1-\varepsilon)^{n}
>e^{\ln(1-\varepsilon)s_1(\varepsilon^{-5}+4\,\varepsilon^{-3{,}5}+
0{,}3\,\varepsilon^{-4}+1)}
> e^{-(\varepsilon+0{,}6\,\varepsilon^2)s_1\varepsilon^{-5}(1+0{,}3\,\varepsilon+ 5\,\varepsilon^{1{,}5})}=\\
=e^{-s_1\varepsilon^{-4}(1+0{,}6\,\varepsilon)(1+0{,}3\,\varepsilon+5\,\varepsilon^{1{,}5})}
> e^{-s_2(1+\varepsilon)},
\end{multline*}
 ��� � ���������� �������.
\end{proof}

\begin{theorem}
        %
$\forall\varepsilon>0$ ���������� ����� �������� $P_1$,
$P_2$ � �����~$s_0$, ��� $\forall s>s_0$ ���� � �������� ��������
$Q$ ����� \�� ���������� �������\��\ ��� \�� ������������
�������������\��\ �� $P_1$ � $P_2$, �� $\exists j$
$\F_{P_j,Q}(s)>e^{-(0{,}5+\varepsilon)s}$.
        %
\end{theorem}
        %
\begin{proof}
        %
���������� �������������� ��������� ������� $\{0,1\}$, ����������
����� $\delta>0$ � $h=\lceil\delta^{-3}\rceil$. ����� ��� ������
$h$ ��������� $P_1$\� ����������� ��������� ���������� ���� �����
1, �~��������� �������~--- 0; $P_2$\� ����������� ���������
���������� ���� ����� $1-\delta$, �~��������� �������~---
$\delta$. ��� ��������� $h$ ���������, ��������, $P_2$\�
����������� ��������� ���������� ���� ����� 1, �~���������
�������\hbox{~---~}0; $P_1$\� ����������� ��������� ����������
���� ����� $1-\delta$, �~��������� �������~--- $\delta$. �����
�������� ����������� ��������� ���������� �~��������~$2h$.

������� $h_0=\lceil \delta^{-2}\rceil$. ����ף� ���������
��������������, ���� ��� ����� ������� �� ������-������
������������ ����� �������� $2h$ �����, ��� �� $h_0$. ������
�����������, ��� ���� $i$\� �� ��������� ���������������, �� ���
������������� ����� ��������� $W_1(0^i)>1-\delta^4$ �
$W_2(0^i)<\delta^4$ (��. ����������� ������������� \�� ����������
�������\��). ������� $\rho(P_2(0^ia|0^i),Q(0^ia|0^i))>\delta$.
���������� ������������ $s>\delta^{-3}$ � �������~$n$ ���������
������ � $\frac{hs}{\delta(h-h_0)}$ ������� $2h$. ��������� �����
$M$ ����� ��� �������� $0^n$. ��������, $$
\sum_{i=0}^{n}\rho(P_2(0^ia|0^i),Q(0^ia|0^i))>s. $$ ����� ����,
$n<s\delta^{-1}(1+O(\delta))$. �������������, $P_2$\� ����
��������� $M$ ����� $$
(1-\delta)^{n/2}>e^{-\delta(1+O(\delta))s\delta^{-1}(1+O(\delta))/2}>e^{-s(0{,}5+\varepsilon)},
$$ ��� � ���������� �������.
\end{proof}

\begin{theorem}
        %
C��������� ������� �������������, ������� �� ���������
$P_1$, $P_2$ ������ �������� $Q$ � $\forall j\ \forall s\
\F_{P_j,Q}(s)\leqslant e^2e^{-s}$.
        %
\end{theorem}
        %
\begin{proof}
����� $x$~--- ������������������ �������. �~������ ������ �������
$m$ ������������� ������ ��� ������������� ����� $c_1(x_{1:m})$,
$c_2(x_{1:m})$, ����� ��� $c_1(x_{1:m})c_2(x_{1:m})=1$. ��� �����
������������ ����������. ������� $c_1(x_{1:0})=c_2(x_{1:0})=1$. ��
������ ���� ������������� ������
$Q(x_{1:m}a|x_{1:m})=P_j(x_{1:m}a|x_{1:m})$ ��� ���� $j$, ���
�������� $c_j(x_{1:m})$ ������ (��������). �����, ����� ��� ������
�����-�� $Q(x_{1:m}a|x_{1:m})$. ����� ����� ��������������� $c_j$:
\begin{align*}
c_1(x_{1:m+1})&=c_1(x_{1:m})\sqrt{\frac{P_2(x_{1:m+1}|x_{1:m})}
{P_1(x_{1:m+1}|x_{1:m})}}
e^{\pm\frac12\rho(P_1(x_{1:m}a|x_{1:m}),P_2(x_{1:m}a|x_{1:m}))},\\
c_2(x_{1:m+1})&=c_2(x_{1:m})\sqrt{\frac{P_1(x_{1:m+1}|x_{1:m})}
{P_2(x_{1:m+1}|x_{1:m})}}
e^{\pm\frac12\rho(P_1(x_{1:m}a|x_{1:m}),P_2(x_{1:m}a|x_{1:m}))},
\end{align*}
���ޣ� ���� \��$+$\��\ �������� � ���������� ���������� ��� ����
$j$, ��� �������� $c_j(x_{1:m})$ ������; ��� ������� $j$ �
���������� ���������� ��������, ��������������, ���� \��$-$\��.

������ ������ ���� $P_1$ ��������� ���������
        $$
M=\Big\{x\,|\,\sum_{i=0}^\infty
\rho(P_1(x_{1:i}a|x_{1:i}),Q(x_{1:i}a|x_{1:i}))>s\Big\}
        $$
(�~����
��������� ����������� ���~$P_2$ ����� ����������). ������ �����
������������� ������ ��������� ������ ������ ������ �� �����~$n$.
��������� ���~$K_n$. ����� ��������� $L_n$ ����������� �� �������
�� $K_n$, ������ ��� �������� ������� �~$M$. ��������� �����������
������ ��~$L_n$ ��������� �����~$M_n$ (���� ��� ������� $n$ ������
���� ����� �������� ��� ��������� ����������� �������
�~����������� �� $M_n$, �� ��� ����� �������� � ���~$M$). �������
��������� �� �������� $m$ (��~������� � �����), ��� ��� ������
$x_{1:m}\in K_n$ ����������� �����������
\begin{equation}
\label{cformula01} e^2c_1(x_{1:m})\geqslant\frac1{P_1(x_{1:m})}
\sum_{\substack{z\in
M_n,\\z_{1:m}=x_{1:m}}}P_1(z)e^{\sum_{i=m}^{|z|}
\rho(P_1(z_{1:i}a|z_{1:i}),Q(z_{1:i}a|z_{1:i}))}.
\end{equation}
���� ��� �������� $x_{1:m}$ ��� ������ �� $M_n$ (� ���� ��� �� ��
$M_n$), �� ����������� ���������� � �������� ������:
$e^2c_1(x_{1:m})\geqslant0$ (����� � ������ ����� ������). ����
$x_{1:m}\in M_{n}$, �� ������ ��� ��� ��� ������ �� $M_n$, �
����������� ��������� ��� $e^2c_1(x_{1:m})\geqslant
e^{\rho(P_1(x_{1:m}a|x_{1:m}), Q(x_{1:m}a|x_{1:m}))}$. ���������
����������� ������� �� ����, ��� $\forall p_1,p_2\
\rho(p_1,p_2)\leqslant2$ � $c_1(x_{1:m})\geqslant1$
(�������������, ��� ��� $x_{1:m}$~--- ����������� ������� �� ���, �
������� ����� ���������� ���������� �� $Q$ �� $P_1$ ����� ������
$s$, �� �� ���� $m$ ���� ������� $P_2$, �~�� $P_1$, � ������,
$c_1(x_{1:m})\geqslant c_2(x_{1:m})$). ����� �������, ����
�������� ��������.

������ �����ģ� ����������� �������. ����� ��������, ���
$x_{1:m}\notin M$, � ����� ����, ��� ������� ������ $b$
$$e^2c_1(x_{1:m}b)\geqslant\frac1{P_1(x_{1:m}b)}
\sum_{\substack{z\in M_n,\\z_{1:m+1}=x_{1:m}b}}P_1(z)
e^{\sum_{i=m+1}^{|z|}
\rho(P_1(z_{1:i}a|z_{1:i}),Q(z_{1:i}a|z_{1:i}))}.$$ ����� ������
����� ������������ �����������~\eqref{cformula01} �����
������������� ��������� ������� (��� ��������� ����� ������
$x_{1:m}$ ������ ������ $x$; ������������� ������������
$P_j(z_{1:i}a|z_{1:i})$, $Q(z_{1:i}a|z_{1:i}))$ ����� ����������
$p_j(z_{1:i})$ � $q(z_{1:i})$, ��������������):
\begin{multline*}
\frac1{P_1(x)} \sum_{\substack{z\in
M_n,\\z_{1:m}=x}}P_1(z)e^{\sum_{i=m}^{|z|}
\rho(p_1(z_{1:i}),q(z_{1:i}))}=\\ =e^{\rho(p_1(x),q(x))}\sum_{b}
\frac1{P_1(x)} \sum_{\substack{z\in M_n,\\z_{1:m+1}=xb}}P_1(z)
e^{\sum_{i=m+1}^{|z|}\rho(p_1(z_{1:i}),q(z_{1:i}))}=\\
=e^{\rho(p_1(x),q(x))}\sum_{b} \frac{P_1(xb|x)}{P_1(xb)}
\sum_{\substack{z\in M_n,\\z_{1:m+1}=xb}}P_1(z)
e^{\sum_{i=m+1}^{|z|}\rho(p_1(z_{1:i}),q(z_{1:i}))}\leqslant\\
\leqslant e^{\rho(p_1(x),q(x))} \sum_{b} P_1(xb|x) e^2c_1(xb).
\end{multline*}
����� ������ �������� ��������� �����������
\begin{equation}
\label{cformula02} e^{\rho(p_1(x),q(x))}\sum_{b} P_1(xb|x)c_1(xb)
\leqslant c_1(x),
\end{equation}
����� ��������� ��� ������. ���� � ������� $x$ ���� �������
$q=p_1$, �� $e^{\rho(p_1(x),q(x))}=1$ � $\forall b\
c_1(xb)=c_1(x)\sqrt{\frac{P_2(xb|x)}
{P_1(xb|x)}}e^{\frac12\rho(p_1(x),p_2(x))}$, �~\eqref{cformula02}
����������~�
\begin{equation}
\label{cformula03} \sum_{b}\sqrt{P_1(xb|x)P_2(xb|x)}\leqslant
e^{-\frac12\rho(p_1(x),p_2(x))}.
\end{equation}
�������������� �����������~\eqref{cformula03} ��� ����������� ���
�������������� �������~\eqref{Vovkformula01}. ���� �� � �������
$x$ ���� ������� $q=p_2$, �� $\forall b\
c_1(xb)=c_1(x)\sqrt{\frac{P_2(xb|x)}
{P_1(xb|x)}}e^{-\frac12\rho(p_1(x),p_2(x))}$, �
�����������~\eqref{cformula02} ���������� �
$$e^{\rho(p_1(x),p_2(x))}\sum_{b}
\sqrt{P_1(xb|x)P_2(xb|x)}c_1(x)e^{-\frac12\rho(p_1(x),p_2(x))}
\leqslant c_1(x),$$ ������ ����� ��������~\eqref{cformula03}.

����� ����, ��� �����������~\eqref{cformula01} ��������, ��������
��� � �����. �����: $e^2\geqslant\sum_{z\in
M_n}P_1(z)e^{\sum_{i=0}^{|z|}
\rho(P_1(z_{1:i}a|z_{1:i}),Q(z_{1:i}a|z_{1:i}))}
\geqslant\sum_{z\in M_n}P_1(z)e^s=P_1(M_n)e^s$, ������ ��������
��������� ������.
\end{proof}

\section{�������� �������}

�����������, �������� �� ��� ������� ���������� ��������� �����
�������������� ������������ �������������, ������������ ��������
�������������, ������ ���� �������������� � ������ ���� �������
��������������.

�� �� �������� ��������� ���� �� ������ ��� ������ ���������,
����� ������������� ����� ������������ ������ ��������� ����� (�
�������� �����������, ������� ��������� � ��������� ������,
������������� �������� ������������������ �����������).

\begin{thebibliography}{99}

%\bibitem{Vovk}
%�. �. ����. \emph{�� ����� �������� �����������.} ������� ��������
%���� ����, �.~294, N6, ���.~1298-1302, 1987.

%\bibitem{Solomonov}
%R. J. Solomonoff. \emph{Complexity-Based Induction Systems:
%Comparisons and Convergence Theorems}. IEEE Transactions on
%Information Theory, vol.~24, N4, pp.~422-432, 1978.

%\bibitem{Li}
%M. Li and P.M.B. Vit\'anyi. \emph{An Introduction to Kolmogorov
%Complexity and its Applications}. Springer, Berlin, 2nd edition,
%1997.

\bibitem{Vovk}
\textit{�.\,�. ����.} �� ����� �������� ����������� // �������
�� ����. 1987. �.\,294, \No\,6. C.~1298--1302.

\bibitem{Solomonov}
\textit{R.\,J. Solomonoff.} Complexity-Based Induction Systems:
Comparisons and Convergence Theorems // IEEE Transactions on
Information Theory. 1978. V.\,24, \No\,4. P.\,422--432.

\bibitem{Li}
\textit{M. Li and P.\,M.\,B. Vit\'anyi.} An Introduction to
Kolmogorov Complexity and its Applications, 2nd edition. Berlin:
Springer, 1997.

\end{thebibliography}

\end{document}
