Kolmogorov's strong law of large numbers in game-theoretic probability: Reality's side
Vladimir Vovk
arXiv.tex
% -*-text-*-
% Last changed: 20 Mar 2013
% Spell checked: 17 Mar 2013
\newif\ifBASIC
\BASICfalse
\newif\ifWP
\WPfalse

%\BASICtrue	% choose BASIC or WP (also used for arXiv)
\WPtrue

\ifBASIC
  \documentclass[10pt]{article}
  \usepackage{amsmath,amsfonts,amssymb,amsthm,latexsym,graphicx,epigraph}
\fi

\ifWP
  \documentclass[12pt]{article}
  \usepackage{amsmath,amsfonts,amssymb,amsthm,latexsym,graphicx,epigraph,setspace}
  \input{gt.txt}
\fi

% \usepackage{refcheck}
% \usepackage{hyperref}

\emergencystretch=5mm
\tolerance=400
\allowdisplaybreaks[4]

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
% \newtheorem*{theorem*}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{definition}
% \newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark}{Remark}

\newcommand{\K}{\mathcal{K}}

\title{Kolmogorov's strong law of large numbers in game-theoretic probability: Reality's side}
\author{Vladimir Vovk}

\ifWP
  \author{Vladimir Vovk}
  \newcommand{\No}{40}
  % For the two dates option: uncomment the next 2 lines
  % \twodatestrue
  % \newcommand{\firstposted}{March 17, 2013}
\fi

\begin{document}
\maketitle

\section{Statement}

This note describes a simple explicit strategy for Reality
whose existence is asserted in Theorem 4.1 (part 2) of \cite{shafer/vovk:2001} (p.~80).
% (A version of this strategy was found by Volodya on 23 March 2006 when flying over Siberia;
% it answered Akimichi's question.)
We will be using the notation of \cite{shafer/vovk:2001}
complemented by $S_n:=x_1+\cdots+x_n$;
without loss of generality we can assume that $m_n=0$ for all $n$.
Namely, we construct an explicit strategy for Reality that guarantees
\begin{equation}\label{eq:goal}
  \K_n \text{ is bounded and }
  \left(
    \sum_{n=1}^{\infty}
    \frac{v_n}{n^2}
    =
    \infty
    \Longrightarrow
    \left(
      \frac{S_n}{n} \not\to 0
    \right)
  \right)
\end{equation}
provided Skeptic satisfies his collateral duty (keeping $\K_n$ non-negative).

For much more advanced results, see Theorems~4.12
% , 5.9,
and~5.10 of \cite{miyabe/takemura:2012}.
The main advantage of this note is its brevity.

\section{Reality's strategy and proof}

With Skeptic's move $(M_n,V_n)$ we associate the function $f_n(x):=M_nx+V_n(x^2-v_n)$;
the increase in his capital will be $f_n(x_n)$.
We will assume that $M_n=0$:
it will be clear that Reality can exploit $M_n\ne0$ by choosing the sign of $x_n$.
Our argument will also be applicable to the modified protocol of unbounded forecasting
in which Skeptic can choose any $V_n\in\mathbb{R}$:
Reality can easily win when $V_n<0$ by choosing $\lvert x_n\rvert$ large enough.

This is Reality's strategy:
\begin{enumerate}
\item\label{it:loop}
  Keep setting $x_n:=0$
  until Skeptic chooses a move for which $\K_{n-1}+f_n(n)\le1$.
\item\label{it:end}
  When Skeptic chooses such a move, set $x_n:=n$ or $x_n:=-n$.
  Go to \ref{it:loop}.
\end{enumerate}
Notice that Skeptic's capital is guaranteed to be bounded by 1,
and so Reality satisfies her collateral duty.
Consider two cases:
\begin{itemize}
\item
  Suppose that item \ref{it:end} is reached infinitely often.
  Since $S_n/n \not\to 0$ as $n\to\infty$,
  (\ref{eq:goal}) will be satisfied.
\item
  Now suppose Skeptic reaches item \ref{it:end} only finitely many times.
  From some $n$ on, we will have $f_n(n)>1-\K_{n-1}$,
  i.e., $V_n(n^2-v_n)>1-\K_{n-1}$,
  which implies $V_n>n^{-2}(1-\K_{n-1})$.
  Therefore, from some $n$ on Skeptic will lose at least
  % (and strictly more than when $v_n>0$)
  $\lvert f_n(0)\rvert=V_nv_n\ge v_nn^{-2}(1-\K_{n-1})$.
  Suppose, without loss of generality, $\sum_nv_nn^{-2}=\infty$
  (otherwise (\ref{eq:goal}) is satisfied).
  Since the sequence $1-\K_{n-1}$ is increasing from some $n$ on
  % and strictly increasing for $n\ge N$ such that $v_n>0$
  and there are arbitrarily large $n$ for which $v_n>0$ and hence $1-\K_n>1-\K_{n-1}\ge0$,
  Skeptic will eventually become bankrupt.
\end{itemize}

\subsection*{Acknowledgement}

This note was prompted by Akimichi Takemura's question in 2006;
I am also grateful to him for several useful discussions.

\begin{thebibliography}{2}

\bibitem{miyabe/takemura:2012}
Kenshi Miyabe and Akimichi Takemura.
\newblock Convergence of random series and the rate of convergence of the
  strong law of large numbers in game-theoretic probability.
\newblock {\em Stochastic Processes and their Applications}, 122:1--30, 2012.

\bibitem{shafer/vovk:2001}
Glenn Shafer and Vladimir Vovk.
\newblock {\em Probability and Finance: It's Only a Game!}
\newblock Wiley, New York, 2001.
\end{thebibliography}
\end{document}

1304.1074.extracted_bib
\begin{thebibliography}{2}

\bibitem{miyabe/takemura:2012}
Kenshi Miyabe and Akimichi Takemura.
\newblock Convergence of random series and the rate of convergence of the
  strong law of large numbers in game-theoretic probability.
\newblock {\em Stochastic Processes and their Applications}, 122:1--30, 2012.

\bibitem{shafer/vovk:2001}
Glenn Shafer and Vladimir Vovk.
\newblock {\em Probability and Finance: It's Only a Game!}
\newblock Wiley, New York, 2001.
\end{thebibliography}