Continuity of imprecise Markov chains\\ with respect to the pointwise convergence\\of monotone sequences of gambles
Jasper De Bock
Gert de Cooman
The aim of these notes is to study the conditions under which the natural extension of an imprecise Markov chain is continuous with respect to the pointwise convergence of monotone---either non-decreasing or non-increasing---sequences of gambles that are $n$-measurable, with $n\in\natswith$. The framework in which we do this is that of the theory of random processes that is being developed in Ref.~\cite{deCooman2014. We find that for non-decreasing sequences, continuity is always guaranteed if the state space of the markov chain is finite. A similar result is obtained for non-increasing sequences, under the additional condition that the joint model is constructed using the Ville-Vovk-Shafer natural extension rather than the Williams natural extension. % As a direct consequence, we find that for finite state spaces, the Ville-Vovk-Shafer natural extension is continuous with respect to the pointwise convergence of any sequence of $n$-measurable gambles. The extent to which these results apply to general random processes is discussed as well.
1402.3056.tex
\documentclass[a4paper,reqno]{amsart}
\usepackage[british]{babel}
%\usepackage[garamond]{mathdesign}
\usepackage{mathptmx}
\usepackage{courier}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{tikz}
\usepackage{nicefrac}
%\usepackage{pdfsync}
\renewcommand{\ttdefault}{cmtt}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem*{remark*}{Remark}
% - macros

\newcommand{\nats}{\mathbb{N}}
\newcommand{\natswith}{\nats_{0}}

\newcommand{\values}{\mathcal{X}}

\newcommand{\lt}{\underline{T}}

\newcommand{\lexp}{\underline{E}}
\newcommand{\lexpW}{\lexp_\mathrm{W}}
\newcommand{\lexpV}{\lexp_\mathrm{V}}

\newcommand{\gambles}{\mathcal{L}} 

\newcommand{\paths}{\Omega}
\newcommand{\path}{\omega} 

\newcommand{\proc}{\mathcal{F}}
\newcommand{\sel}{\mathcal{S}}
\newcommand{\sels}{\mathbb{S}}

\DeclareMathOperator{\cyl}{cyl}

\newcommand{\init}{\square}




\newcommand{\pr}{P} 
\newcommand{\lpr}{\underline{\pr}}
\newcommand{\upr}{\overline{\pr}}
\newcommand{\lupr}{\underline{\overline{\pr}}} 
\newcommand{\precedes}{\sqsubseteq} 
\newcommand{\sprecedes}{\sqsubset}
\newcommand{\follows}{\sqsupseteq}
\newcommand{\incomp}{\parallel}
\newcommand{\sfollows}{\sqsupset}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\until}[1]{{{\downarrow}#1}}
\newcommand{\after}[1]{{{\uparrow}#1}}
\newcommand{\daughters}[1]{{\cut{D}(#1)}}
\newcommand{\daughter}[1]{d_{#1}}
\newcommand{\mother}[1]{m_{#1}}

\newcommand{\asa}{\Leftrightarrow}
\newcommand{\then}{\Rightarrow}
\newcommand{\indexact}[1]{I_{\exact{#1}}}

\begin{document}
\title[Continuity of imprecise Markov chains for monotone sequences of gambles]{Continuity of imprecise Markov chains\\ with respect to the pointwise convergence\\of monotone sequences of gambles}
\author{Jasper De Bock}
\address{Ghent University, SYSTeMS Research Group,
  Technologiepark -- Zwijnaarde 914, 9052 Zwijnaarde, Belgium}
\email{jasper.debock@ugent.be}
\author{Gert de Cooman}


\begin{abstract}
  The aim of these notes is to study the conditions under which the natural extension of an imprecise Markov chain is continuous with respect to the pointwise convergence of monotone---either non-decreasing or non-increasing---sequences of gambles that are $n$-measurable, with $n\in\natswith$. The framework in which we do this is that of the theory of random processes that is being developed in Ref.~\cite{deCooman2014}. We find that for non-decreasing sequences, continuity is always guaranteed if the state space of the markov chain is finite. A similar result is obtained for non-increasing sequences, under the additional condition that the joint model is constructed using the Ville-Vovk-Shafer natural extension rather than the Williams natural extension.
  % As a direct consequence, we find that for finite state spaces, the Ville-Vovk-Shafer natural extension is continuous with respect to the pointwise convergence of any sequence of $n$-measurable gambles.
  The extent to which these results apply to general random processes is discussed as well.
\end{abstract}

\maketitle

\section{Preliminaries}
\label{sec:prelim}

We consider an infinite horizon imprecise Markov chain of which the finite state space is denoted by $\values$. For every $n\in\nats$,\footnote{We use $\nats$ to denote the set of all natural numbers (without zero); if zero is included, we write $\natswith\coloneqq\nats\cup\{0\}$.} the random variable that corresponds to the state at time $n$ is denoted by $X_n$ and takes values in $\values$. We call any real-valued map on $\values$ a gamble. The set of all gambles on $\values$ is denoted by $\gambles(\values)$. For every $n\in\nats$, the lower transition operator $\lt_n\colon\gambles(\values)\rightarrow\gambles(\values)$ provides us with the lower expectation $\lexp(f\vert x_1\dots x_n)=\lexp(f\vert x_n)\coloneqq\lt_n(f)(x_n)$ of a gamble $f$ on the next state $X_{n+1}$ given the value $x_n$ of the current state. For the first variable $X_1$, we have an initial model, in the form of a lower expectation functional---a lower envelope of expectation operators or, equivalently, a superlinear functional that dominates the infimum---$\lexp_1$ on $\gambles(\values)$. For every gamble $f$ on $X_1$, the corresponding lower expectation is given by $\lexp_1(f)$.



% In order to streamline the notation further on, we regard this unconditional lower prevision as a conditional one, conditioning it on the abstract initial situation $\init$.

% In order to streamline the notation, we denote this (unconditional!)
% For every gamble $f$ on $X_1$, the corresponding lower expectation is given by $\lexp_\init(f)$.

A path $\path$ is an infinite sequence of states $x_1 \ldots x_n \ldots \in\values^\nats$. The possibility space $\paths$ is the set of all paths. We denote by $\gambles(\paths)$ the set of all gambles---real-valued\footnote{Gambles are often considered to be bounded as well; however, for the results in this note, such an assumption does not seem necessary.} maps---on $\paths$. An initial sequence of states $x_1 \ldots x_n\in\values^n$ is called a situation. We also allow for $n=0$, which corresponds to the (abstract) initial situation $\init$. Generic situations are denoted by $s$, in which case we denote its length by $\ell(s)$. For example: $\ell(\init)=0$ and, for $s=x_1\ldots x_n$, $\ell(s)=n$. For every $\path=x_1\ldots x_n\ldots\in\paths$ and every $n\in\natswith$, we also consider the situation $\path_n\coloneqq x_1\ldots x_n$, with $\path_0=\init$ as a special case. Furthermore, for every situation $s$, the cylinder set $\cyl(s)\coloneqq\{\path\in\paths\colon\path_{\ell(s)}=s\}$ is the set of all paths that have $s$ as their initial segment. Note that $\cyl(\init)=\paths$. A gamble $f$ on $\paths$ is said to be $n$-measurable if $f(\path)=f(\path')$ for all $\path,\path'\in\paths$ such that $\path_n=\path'_n$ or, equivalently, if for all situations $s\in\values^n$, $f$ is constant on $\cyl(s)$.

A process $\proc$ is a function defined on all situations. If $\proc$ is real-valued, we can associate with it, for every $n\in\natswith$, an $n$-measurable gamble $\proc_n$ on $\paths$, defined for all $\path\in\paths$ by $\proc_n(\path)\coloneqq\proc(\path_n)$. The limit superior of these gambles is denoted by $\limsup\proc$. For all $\path\in\paths$, we have that
\begin{equation}\label{eq:deflimsup}
\limsup\proc(\path)
\coloneqq\limsup_{n\rightarrow\infty}\proc_n(\path)
=\limsup_{n\rightarrow\infty}\proc(\path_n)
=\lim_{n\rightarrow\infty}\sup_{m\geq n}\proc(\path_n)
.
\end{equation}

A process that maps situations to gambles on $\values$ is called a selection, and will be denoted by $\sel$. With every such selection, we associate a real-valued process $\proc^\sel$, defined recursively by
\begin{equation*}
\proc^\sel(\init)\coloneqq0
\text{ and }
\proc^\sel(sx)\coloneqq\proc^\sel(s)+\sel(s)(x)
\text{ for all $x\in\values$ and all situations $s$.}
\end{equation*}
Hence, for every $\path=x_1\ldots x_n\ldots\in\paths$ and $n\in\natswith$, we find that
\begin{equation}\label{eq:Fnclosedform}
\proc_n^\sel(\path)=\proc^\sel(\path_n)=\sum_{i=1}^{n}\sel(\path_{i-1})(x_i).
\end{equation}
A selection $\sel$ is called almost-desirable when
\begin{equation*}
\lexp(\sel(s)\vert s)\geq0
\text{ for all situations $s$.}
\end{equation*}
In order for this to be well-defined for the initial situation $s=\init$, we introduce the notational convention that, for all gambles $f$ on $X_1$, $\lexp(f\vert\init)\coloneqq\lexp_1(f)$. The set of all almost-desirable selections is denoted by $\sels$.

We now have all the terminology needed to define a joint model for our imprecise Markov chain, in the form of a lower expectation operator on $\gambles(\paths)$. We consider two different options. For all gambles $f$ on $\paths$, the Williams natural extension is
\begin{equation}\label{eq:Williams}
\lexpW(f)\coloneqq
\sup\{
\alpha\in\reals
\colon 
f-\alpha\geq\proc^\sel_n
\text{ for some $n\in\natswith$ and $\sel\in\sels$}
\}
\end{equation}
and the Ville-Vovk-Shafer natural extension is 
\begin{equation}\label{eq:Ville}
\lexpV(f)\coloneqq
\sup\{
\alpha\in\reals
\colon 
f-\alpha\geq\limsup\proc^\sel
\text{ for some $\sel\in\sels$}
\}.
\end{equation}
\begin{remark*}\label{remark:conditional}
Both of these natural extensions can also be defined conditional on a situation $s$. The unconditional versions given above correspond to the special case $s=\init$. We do not consider conditional natural extensions in the present note because they overcomplicate the notation, thereby hiding the essence of the proofs of the results stated below. Nevertheless, all of the results below remain valid for these conditional natural extensions as well, simply because a conditional Markov chain can be identified with an unconditional one. It suffices to identify the new $\init$ with the conditioning situation $s$, to identify the new first random variable with $X_{\ell(s)+1}$, and to use $\lexp(\cdot\vert s)$ as the new initial model.
\end{remark*}

Of the two natural extensions that were defined above, the Williams natural extension is the more conservative one.
\begin{proposition}\label{prop:WversusV}
For any $f\in\gambles(\paths)$: $\lexpV(f)\geq\lexpW(f)$.
\end{proposition}
\begin{proof}
Due to Eqs.~\eqref{eq:Williams} and~\eqref{eq:Ville}, it clearly suffices to show that for any selection $\sel\in\sels$ and any $n\in\natswith$, there is a selection $\sel^*$ for which $\proc_n^\sel=\limsup\proc^{\sel^*}$. So consider any $\sel\in\sels$ and any $n\in\natswith$. Let $\sel^*$ be defined as
\begin{equation}\label{eq:selstar1}
\sel^*(s)
\coloneqq
\begin{cases}
\sel(s) & \text{if $\ell(s)<n$}\\
0 & \text{otherwise}
\end{cases}
\text{~~~for all situations $s$.}
\end{equation}
Consider now any $\path=x_1\ldots x_n\ldots\in\paths$. Then for all $k\geq n$, we have that
\begin{equation*}
\proc^{\sel^*}(\path_k)
=\sum_{i=1}^{k}\sel^*(\path_{i-1})(x_i)
=\sum_{i=1}^{n}\sel(\path_{i-1})(x_i)
=\proc^{\sel}_n(\path)
,
\end{equation*}
where the first and third equality are due to Eq.~\eqref{eq:Fnclosedform}, and the second equality is a consequence of Eq.~\eqref{eq:selstar1} and the fact that $\ell(\path_i)=i$. Hence, using Eq.~\eqref{eq:deflimsup}, we find that 
\begin{equation*}
\limsup\proc^{\sel^*}(\path)
=
\limsup_{k\rightarrow\infty}\proc^{\sel^*}(\path_k)
=\proc^{\sel}_n(\path).
\end{equation*}
Since this holds for all $\path\in\paths$, we conclude that $\proc_n^\sel=\limsup\proc^{\sel^*}$.
\end{proof}
\noindent
For gambles that are $n$-measurable, with $n\in\natswith$, both extensions coincide.
\begin{proposition}\label{prop:nWequalV}
For any $n\in\natswith$ and any $f\in\gambles(\paths)$ that is $n$-measurable: $\lexpV(f)=\lexpW(f)$.
\end{proposition}
\begin{proof}
Consider any $n\in\natswith$ and any $f\in\gambles(\paths)$ that is $n$-measurable. Then due to Proposition~\ref{prop:WversusV}, we are left to prove that $\lexpW(f)\geq\lexpV(f)$ or, equivalently, that $\lexpW(f)\geq\lexpV(f)-\epsilon$ for all $\epsilon>0$.

So choose any $\epsilon>0$. Then due to Eq.~\eqref{eq:Ville}, there is an almost-desirable selection $\sel\in\sels$ such that $f-\lexpV(f)+\epsilon\geq\limsup\proc^\sel$. Consider now any $\path\in\paths$ and let $s_n\coloneqq\path_n$. Since $\sel$ is almost-desirable, $\lexp(\sel(s_n)\vert s_n)\geq0$ and therefore, because $\lexp(\cdot\vert s_n)$ is a lower expectation operator, it is not possible for $\sel(s_n)$ to be uniformly negative. Hence, there is an $x_{k+1}^*\in\values$ such that $\sel(s_n)(x_{n+1}^*)\geq0$. Now consider the situation $s_{n+1}\coloneqq s_n x_{n+1}^*$. Then similarly, there is an $x_{n+2}^*\in\values$ such that $\sel(s_{n+1})(x_{n+2}^*)\geq0$. Continuing in this way, we construct a path\footnote{In doing so, we implicitly adopt the Axiom of Dependent Choice.}
$\path^*=s_nx^*_{n+1}x^*_{n+2}\ldots$ for which, for all $i\geq n$, $\sel(\path^*_i)(x^*_{i+1})\geq0$. Therefore, and due to Eq.~\eqref{eq:Fnclosedform}, we find that, for all $m\geq n$,
\begin{align*}
\proc_m^{\sel}(\path^*)
&=\sum_{i=1}^{m}\sel(\path^*_{i-1})(x^*_i)
=\sum_{i=1}^{n}\sel(\path^*_{i-1})(x^*_i)
+\sum_{i=n+1}^{m}\sel(\path^*_{i-1})(x^*_i)\\
&\geq\proc_n^{\sel}(\path^*)
=\proc^{\sel}(\path^*_n)
=\proc^{\sel}(s_n)
=\proc^{\sel}(\path_n)
=\proc^{\sel}_n(\path)
,
\end{align*}
and therefore also that 
\begin{align}
\proc^{\sel}_n(\path)
\leq
\limsup_{m\rightarrow\infty}\proc_m^{\sel}(\path^*)
=\limsup\proc^{\sel}(\path^*)
&\leq f(\path^*)-\lexpV(f)+\epsilon\notag\\
&=f(\path)-\lexpV(f)+\epsilon,\label{eq:VequalFinequality}
\end{align}
In this last equation, the last inequality holds because $f-\lexpV(f)+\epsilon\geq\limsup\proc^\sel$. The final equality holds because $f$ is $n$-measurable and because $\path_n^*=s_n=\path_n$. Since Eq.~\eqref{eq:VequalFinequality} is valid for all $\path\in\paths$, we infer that $\proc^{\sel}_n\leq f-\lexpV(f)+\epsilon$. Due to Eq.~\eqref{eq:Williams}, this implies that $\lexpW(f)\geq\lexpV(f)-\epsilon$.
\end{proof}


\section{Continuity with respect to non-decreasing sequences of gambles}
\label{sec:non-decreasing}

Since the Williams and Ville-Vovk-Shafer natural extension coincide on $n$-measurable gambles, we can ask ourselves whether this holds for limits of $n$-measurable gambles as well. The following result establishes that for non-decreasing sequences of $n$-measurable gambles, this is indeed the case. Furthermore, both extensions are continuous with respect to the convergence of such a sequence.

\begin{theorem}\label{theo:non-decreasing}
Let $f_n$, $n\in\natswith$, be any non-decreasing sequence of $n$-measurable gambles on $\paths$ such that the pointwise limit $\lim_{n\rightarrow\infty}f_n$ exists and is equal to some gamble $f\in\gambles(\paths)$. Then
\begin{equation}\label{eq:non-decreasing}
\lim_{n\rightarrow\infty}\lexpW(f_n)
=\lim_{n\rightarrow\infty}\lexpV(f_n)
=\lexpV(f)=\lexpW(f).
\end{equation}
\end{theorem}
\begin{proof}
The first equality in Eq.~\eqref{eq:non-decreasing} is a direct consequence of Proposition~\ref{prop:nWequalV}. Since $f_n$, $n\in\natswith$, is non-decreasing, it holds for all $n\in\natswith$ that $f_n\leq f$ and therefore also, using Eq.~\eqref{eq:Williams}, that $\lexpW(f_n)\leq\lexpW(f)$. Hence,
$\lim_{n\rightarrow\infty}\lexpW(f_n)\leq\lexpW(f)$. By combining this with Proposition~\ref{prop:WversusV}, we see that we are left to prove that $\lim_{n\rightarrow\infty}\lexpV(f_n)
\geq\lexpV(f)$.

Consider any $\epsilon>0$. Then due to Eq.~\eqref{eq:Ville}, there is an almost-desirable selection $\sel\in\sels$ such that $f-\lexpV(f)+\nicefrac{\epsilon}{2}\geq\limsup\proc^\sel$. Hence, due to Eq.~\eqref{eq:deflimsup}, for all $\path\in\paths$:
\begin{equation*}
\lim_{n\rightarrow\infty}f_n(\path)-\lexpV(f)+\frac{\epsilon}{2}\geq\limsup_{n\rightarrow\infty}\proc_n^\sel(\path)
\end{equation*}
and therefore also
\begin{align*}
-\lexpV(f)+\frac{\epsilon}{2}
\geq\limsup_{n\rightarrow\infty}\proc_n^\sel(\path)-\lim_{n\rightarrow\infty}f_n(\path)
&=\limsup_{n\rightarrow\infty}\proc_n^\sel(\path)-\liminf_{n\rightarrow\infty}f_n(\path)\\
&=\limsup_{n\rightarrow\infty}\proc_n^\sel(\path)+\limsup_{n\rightarrow\infty}\big[-f_n(\path)\big]\\
&\geq\limsup_{n\rightarrow\infty}\big[\proc_n^\sel(\path)-f_n(\path)\big]
,
\end{align*}
implying that there is an $n\in\natswith$ for which
\begin{equation*}%\label{eq:nstarinequality}
-\lexpV(f)+\epsilon\geq\proc_{n}^\sel(\path)-f_{n}(\path).
\end{equation*}
For any $\path\in\paths$, let $n^*(\path)$ be the first index for which this is the case. Then for any $\path'\in\cyl(\path_{n^*(\path)})$ and any $n\leq n^*(\path)$, we have that $\proc_n^\sel(\path)-f_n(\path)=\proc_n^\sel(\path')-f_n(\path')$ because $\path_n=\path_n'$ and because $\proc_n^\sel$ and $f_n$ are both $n$-measurable. Hence, for any $\path\in\paths$ and any $\path'\in\cyl(\path_{n^*(\path)})$:
\begin{equation}\label{eq:nstarconstant}
n^*(\path')=n^*(\path).
\end{equation}

% Then for all $n\geq n^*(\path)$, we have that
% \begin{equation}\label{eq:nstar}
% f_{n}(\path)-\sup_{m\geq n}\proc^\sel(\path_m)\geq
% f_{n^*(\path)}(\path)-\sup_{m\geq n^*(\path)}\proc^\sel(\path_m)\geq\lexpV(f)-\epsilon,
% \end{equation}
% where the first inequality in Eq.~\eqref{eq:nstar} holds because $f_n$, $n\in\natswith$, is non-decreasing by assumption and because the supremum on the left-hand side is taken over a smaller set than that on the right-hand side.

For all $n\in\natswith$, we now define $C_n\coloneqq\{\path\in\paths\colon n^*(\path)\geq n\}$. Then for all $n_1,n_2\in\natswith$ such that $n_1\leq n_2$, we have that $C_{n_1}\supseteq C_{n_2}$. Assume \emph{ex absurdo} that, for all $n\in\natswith$, $C_n\neq\emptyset$, implying that $\sup_{\path\in\paths}n^*(\path)=\infty$.  Then we have that
\begin{equation*}
\sup_{\path\in\paths}n^*(\path)=\sup_{x\in\values}\sup_{\path\in\cyl(x)}n^*(\path)=\infty
\end{equation*}
and therefore, since $\values$ is finite, there is an $x_1^*\in\values$ for which $\sup_{\path\in\cyl(x_1^*)}n^*(\path)=\infty$.
%Consequently, there is a path $\path\in\cyl(x^*_1)$ for which $n^*(\path)\geq1$
Similarly, we also have that
\begin{equation*}
\sup_{\path\in\cyl(x_1^*)}n^*(\path)=\sup_{x\in\values}\sup_{\path\in\cyl(x_1^* x)}n^*(\path)=\infty.
\end{equation*}
Since $\values$ is finite, this implies that there is an $x^*_2\in\values$ for which $\sup_{\path\in\cyl(x_1^* x_2^*)}n^*(\path)=\infty$.
By continuing in this way, we construct a path\footnote{Again, we implicitly adopt the Axiom of Dependent Choice.} 
$\path^*=x_1^*\ldots x_n^*\ldots$ for which, for all $n\in\natswith$:
\begin{equation*}
\sup_{\path\in\cyl(x_1^*\dots x_n^*)}n^*(\path)
=\sup_{\path\in\cyl(\path^*_n)}n^*(\path)
=\infty.
\end{equation*}
However, due to Eq.~\eqref{eq:nstarconstant}, we also have that
\begin{equation*}
\sup_{\path\in\cyl(\path^*_{n^*(\path^*)})}n^*(\path)
=\sup_{\path\in\cyl(\path^*_{n^*(\path^*)})}n^*(\path^*)
=n^*(\path^*)
\neq\infty.
\end{equation*}
% By the definition of $n^*(\path^*)$, we know that
% \begin{equation*}
% -\lexpV(f)+\epsilon\geq\proc_{n^*(\path^*)}^\sel(\path^*)-f_{n^*(\path^*)}(\path^*).
% \end{equation*}
% Since $\proc_{n^*(\path^*)}^\sel$ and $f_{n^*(\path^*)}$ are both $n^*(\path^*)$-measurable and therefore constant on the cylinder set $\cyl(x^*_1\dots x^*_{n^*(\path^*)})$, this implies that, for all $\path\in\cyl(x^*_1\dots x^*_{n^*(\path^*)})$:
% \begin{equation*}
% -\lexpV(f)+\epsilon\geq\proc_{n^*(\path^*)}^\sel(\path)-f_{n^*(\path^*)}(\path)
% \end{equation*}
% and therefore also $n^*(\path)\leq n^*(\path^*)$. Hence, we find that
% \begin{equation*}
% \sup_{\path\in\cyl(x_1^*\ldots x_{n^*(\path^*)}^*)}n^*(\path)\leq n^*(\path^*).
% \end{equation*}
%Since this contradicts the way in which $\path^*$ was constructed, 
Since this is a contradiction, we conclude that there is some $n^*\in\natswith$ for which $C_{n^*}=\emptyset$ and therefore also, for all $\path\in\paths$, $n^*(\path)<n^*$.

Next, we consider the selection $\sel^*\in\sels$, defined as
\begin{equation}\label{eq:selstar}
\sel^*(s)
\coloneqq
\begin{cases}
\sel(s) & \text{if $n^*(\path)>\ell(s)$ for all $\path\in\cyl(s)$}\\
0 & \text{otherwise}
\end{cases}
\text{~~~for all situations $s$.}
\end{equation}
For any $\path\in\paths$ and $n\in\natswith$, we have that $\path\in\cyl(\path_n)$ and $\ell(\path_n)=n$. Therefore, if $n\geq n^*(\path)$, we infer from Eq.~\eqref{eq:selstar} that $\sel^*(\path_n)=0$. If $n<n^*(\path)$, then for any $\path'\in\cyl(\path_n)$, we have that $n^*(\path')>n=\ell(\path_n)$. Indeed, assume \emph{ex absurdo} that there is some $\path'\in\cyl(\path_n)$ for which $n^*(\path')\leq n$. Then $\path'_{n^*(\path')}=\path_{n^*(\path')}$, implying that $\path\in\cyl(\path'_{n^*(\path')})$ and therefore, by Eq.~\eqref{eq:nstarconstant}, that $n^*(\path)=n^*(\path')\leq n$. This is a contradiction. 
%then by definition of $n^*(\path)$, we know that $-\lexpV(f)+\epsilon<\proc_{n}^\sel(\path)-f_{n}(\path)$.
%Since $\proc_n^\sel$ and $f_n$ are $n$-measurable, this implies that, for all $\path'\in\cyl(\path_n)$, $-\lexpV(f)+\epsilon<\proc_{n}^\sel(\path')-f_{n}(\path')$ and therefore also $n^*(\path')>n=\ell(\path_n)$. 
Using Eq.~\eqref{eq:selstar}, we find that $\sel^*(\path_n)=\sel(\path_n)$. Hence, in summary:
\begin{equation}\label{eq:selstarpath}
\sel^*(\path_n)
=
\begin{cases}
\sel(\path_n) & \text{if $n<n^*(\path)$}\\
0 & \text{otherwise}
\end{cases}
\text{~~~for all $\path\in\paths$ and $n\in\natswith$.}
\end{equation} 

Consider now any $\path=x_1\ldots x_n\ldots\in\paths$. Then for all $n\geq n^*$, we find that
\begin{equation*}
\proc^{\sel^*}_n(\path)
=\sum_{i=1}^{n}\sel^*(\path_{i-1})(x_i)
=\sum_{i=1}^{n^*(\path)}\sel(\path_{i-1})(x_i)
=\proc^\sel_{n^*(\path)}(\path)
,
\end{equation*}
where the first and third equality are due to Eq.~\eqref{eq:Fnclosedform}, and the second equality is a consequence of Eq.~\eqref{eq:selstarpath} and the fact that $n^*(\path)< n^*$. Hence, we also have that
\begin{equation}\label{eq:limsupstar}
\limsup_{n\rightarrow\infty}\proc^{\sel^*}_n(\path)=\proc^\sel_{n^*(\path)}(\path)\leq f_{n^*(\path)}(\path)-\lexpV(f)+\epsilon
\leq f_{n^*}(\path)-\lexpV(f)+\epsilon,
\end{equation}
where the first inequality follows from the definition of $n^*(\path)$, and the second inequality is a consequence of the non-decreasing nature of the sequence $f_n$, $n\in\natswith$, and the fact that $n^*(\path)<n^*$.

Since Eq.~\eqref{eq:limsupstar} holds for all $\path\in\paths$, we find that $\limsup\proc^{\sel^*}\leq f_{n^*}-\lexpV(f)+\epsilon$, implying that $\lexpV(f_{n^*})\geq\lexpV(f)-\epsilon$. Because $f_n$, $n\in\natswith$, is non-decreasing, we can infer from Eq.~\eqref{eq:Ville} that $\lexpV(f_n)$ is non-decreasing as well. Therefore, $\lexpV(f_{n^*})\geq\lexpV(f)-\epsilon$ implies that $\lim_{n\rightarrow\infty}\lexpV(f_n)\geq\lexpV(f)-\epsilon$. Since this holds for any $\epsilon>0$, we finally obtain that $\lim_{n\rightarrow\infty}\lexpV(f_n)\geq\lexpV(f)$.
\end{proof}


\section{Continuity with respect to non-increasing sequences of gambles}
\label{sec:non-increasing}

The proof of the results in the previous section crucially hinges on the fact that $f_n$, $n\in\natswith$, is a non-decreasing sequence. For non-increasing sequences of $n$-measurable gambles, the Williams natural extension is not as well-behaved, as it is not necessarily continuous with respect to pointwise convergence of such sequences. However, for the Ville-Vovk-Shafer natural extension, results analogous to those in Theorem~\ref{theo:non-decreasing} can be obtained.

\begin{theorem}\label{theo:non-increasing}
Let $f_n$, $n\in\nats$, be any non-increasing sequence of $n$-measurable gambles on $\paths$ such that the pointwise limit $\lim_{n\rightarrow\infty}f_n$ exists and is equal to some gamble $f\in\gambles(\paths)$. Then
\begin{equation}\label{eq:non-increasing}
\lim_{n\rightarrow\infty}\lexpW(f_n)
=\lim_{n\rightarrow\infty}\lexpV(f_n)
=\lexpV(f)\geq\lexpW(f).
\end{equation}
\end{theorem}
\begin{proof}
The first equality in Eq.~\eqref{eq:non-increasing} is a direct consequence of Proposition~\ref{prop:nWequalV} and the last inequality is due to Proposition~\ref{prop:WversusV}. Since $f_n$, $n\in\natswith$, is non-increasing, it holds for all $n\in\natswith$ that $f_n\geq f$ and therefore also, using Eq.~\eqref{eq:Ville}, that $\lexpV(f_n)\geq\lexpV(f)$. Hence, we find that $\lim_{n\rightarrow\infty}\lexpV(f_n)
\geq\lexpV(f)$, implying that we are left to prove that $\lim_{n\rightarrow\infty}\lexpV(f_n)
\leq\lexpV(f)$.

Choose any $\epsilon>0$. Then due to Eq.~\eqref{eq:Ville}, for any $n\in\natswith$, there is an almost-desirable selection $\sel_n\in\sels$ such that $f_n-\lexpV(f_n)+\nicefrac{\epsilon}{2}\geq\limsup\proc^{\sel_n}$. 

Consider now any $k,n\in\natswith$ such that $k\leq n$ and any $\path\in\paths$.
Let $s_k\coloneqq\path_k$. Since $\sel_n$ is almost-desirable, 
% $\lexp(\sel_n(s_k)\vert s_k)\geq0$ and therefore, because $\lexp(\cdot\vert s_k)$ is a lower expectation operator, it is not possible for $\sel_n(s_k)$ to be uniformely negative. Hence, there is an $x_{k+1}^*\in\values$ such that $\sel_n(s_k)(x_{k+1}^*)\geq0$. Now consider the situation $s_{k+1}\coloneqq s_k x_{k+1}^*$. Then similarly, there is an $x_{k+2}^*\in\values$ such that $\sel_n(s_{k+1})(x_{k+2}^*)\geq0$. Continuing in this way, we construct a path
% %\footnote{Again, we implicitly adopt the Axiom of Dependent Choice.} 
% $\path^*=s_kx^*_{k+1}x^*_{k+2}\ldots x^*_n\ldots$ for which, for all $i\geq k$, $\sel_n(\path^*_i)(x^*_{i+1})\geq0$. Therefore, and due to Eq.~\eqref{eq:Fnclosedform}, we find that, for all $m\geq k$,
% \begin{align*}
% \proc_m^{\sel_n}(\path^*)
% =\sum_{i=1}^{m}\sel_n(\path^*_{i-1})(x^*_i)
% &=\sum_{i=1}^{k}\sel_n(\path^*_{i-1})(x^*_i)
% +\sum_{i=k+1}^{m}\sel_n(\path^*_{i-1})(x^*_i)\\
% &\geq\proc_k^{\sel_n}(\path^*)
% =\proc^{\sel_n}(\path^*_k)
% =\proc^{\sel_n}(s_k)
% =\proc^{\sel_n}(\path_k)
% ,
% \end{align*}
we can use an argument similar to the one used in the proof of Proposition~\ref{prop:nWequalV} to construct a path $\path^*=s_kx^*_{k+1}x^*_{k+2}\ldots x^*_n\ldots$ for which, for all $m\geq k$, $\proc_m^{\sel_n}(\path^*)\geq\proc^{\sel_n}(\path_k)$
and therefore also  
\begin{align}
\proc^{\sel_n}(\path_k)
\leq
\limsup_{m\rightarrow\infty}\proc_m^{\sel_n}(\path^*)
=\limsup\proc^{\sel_n}(\path^*)
&\leq f_n(\path^*)-\lexpV(f_n)+\frac{\epsilon}{2}\notag\\
&\leq f_k(\path^*)-\lim_{r\rightarrow\infty}\lexpV(f_r)+\frac{\epsilon}{2}\notag\\
&=f_k(\path)-\lim_{r\rightarrow\infty}\lexpV(f_r)+\frac{\epsilon}{2}.\label{eq:knpath}
\end{align}
In this last equation, the second inequality holds because $f_n-\lexpV(f_n)+\nicefrac{\epsilon}{2}\geq\limsup\proc^{\sel_n}$. For the last inequality in Eq.~\eqref{eq:knpath}, first recall that $f_r$, $r\in\natswith$, is non-increasing. Therefore, since $k\leq n$, we have that $f_k(\path^*)\geq f_n(\path^*)$. Due to Eq.~\eqref{eq:Ville}, it also implies that, for all $r\geq n$, $\lexpV(f_r)\leq\lexpV(f_n)$. Hence, $\lim_{r\rightarrow\infty}\lexpV(f_r)\leq\lexpV(f_n)$. The final equality in Eq.~\eqref{eq:knpath} holds because $f_k$ is $k$-measurable and because $\path^*_k=s_k=\path_k$.

Next, we consider a process $\proc$, defined by
\begin{equation}\label{eq:defF}
\proc(s)\coloneqq\limsup_{n\rightarrow\infty}\proc^{\sel_n}(s)
\text{ for all situations $s$.}
\end{equation}
For any $\path\in\paths$ and any $k\in\natswith$, we then have that
\begin{equation}\label{eq:Fpathk}
\proc(\path_k)
=\limsup_{n\rightarrow\infty}\proc^{\sel_n}(\path_k)
\leq f_k(\path)-\lim_{r\rightarrow\infty}\lexpV(f_r)+\frac{\epsilon}{2},
\end{equation}
where the inequality follows because, for all $n\geq k$, Eq.~\eqref{eq:knpath} holds. Using Eq.~\eqref{eq:Fpathk}, we find that, for all $\path\in\paths$,
\begin{align*}
\limsup\proc(\path)
=\limsup_{k\rightarrow\infty}\proc(\path_k)
&\leq
\limsup_{k\rightarrow\infty}f_k(\path)-\lim_{r\rightarrow\infty}\lexpV(f_r)+\frac{\epsilon}{2}\\
&=f(\path)-\lim_{r\rightarrow\infty}\lexpV(f_r)+\frac{\epsilon}{2},
\end{align*}
where the last equality holds because $f_k$, $k\in\natswith$, converges pointwise to $f$. Hence, we find that 
\begin{equation}\label{eq:firstpart}
\limsup\proc\leq f-\lim_{n\rightarrow\infty}\lexpV(f_n)+\frac{\epsilon}{2}.
\end{equation}

We will now build a selection $\sel\in\sels$ by constructing, for every situation $s$, a gamble $\sel(s)$ on $\values$ for which $\lexp(\sel(s)\vert s)\geq0$. So fix any situation $s$. Then due to Eq.~\eqref{eq:defF}, for all $x\in\values$, $\proc(sx)=\limsup_{n\rightarrow\infty}\proc^{\sel_n}(sx)$, implying that there is an $n_x(s)\in\natswith$ for which, for all $n\geq n_x(s)$, $\proc(sx)\geq\proc^{\sel_n}(sx)-\nicefrac{\nu(s)}{2}$, with $\nu(s)\coloneqq\epsilon2^{-(\ell(s)+2)}>0$. Since $\values$ is finite, we can define $n_{\max}(s)\coloneqq\max_{x\in\values}n_x(s)$. Due to Eq.~\eqref{eq:defF}, we know that $\proc(s)=\limsup_{n\rightarrow\infty}\proc^{\sel_n}(s)$, implying that there is an $n^*(s)\geq n_{\max}(s)$ for which $\proc^{\sel_{n^*(s)}}(s)\geq\proc(s)-\nicefrac{\nu(s)}{2}$. We now define $\sel(s)\coloneqq\sel_{n^*(s)}(s)$. Since $\sel_{n^*(s)}$ is almost-desirable, we have that $\lexp(\sel(s)\vert s)\geq0$. Hence, the selection $\sel$ that is constructed in this way is almost-desirable: $\sel\in\sels$.

Consider now any $\path=x_1\ldots x_n\ldots\in\paths$. Then for every $i\in\natswith$, we have that
\begin{align*}
\proc(\path_{i+1})-\proc(\path_i)
&=\proc(\path_i x_{i+1})-\proc(\path_i)
%\notag
\\
&\geq
\big[\proc^{\sel_{n^*(\path_i)}}(\path_{i}x_{i+1})-\frac{\nu(\path_i)}{2}\big]+\big[-\proc^{\sel_{n^*(\path_i)}}(\path_i)-\frac{\nu(\path_i)}{2}\big]
%\notag
\\
&=
\proc^{\sel_{n^*(\path_i)}}(\path_{i}x_{i+1})-\proc^{\sel_{n^*(\path_i)}}(\path_i)-\nu(\path_i)
%\notag
\\
&=\sel_{n^*(\path_i)}(\path_i)(x_{i+1})-\nu(\path_i)
=\sel(\path_i)(x_{i+1})-\nu(\path_i)
,
%\label{eq:Fpathdiff}
\end{align*}
where the first inequality holds because $n^*(\path_i)\geq n_{\max}(\path_i)\geq n_{x_{i+1}}(\path_i)$ and the next to last equality follows from Eq.~\eqref{eq:Fnclosedform}. Therefore, for any $m\in\natswith$, it holds that
\begin{align*}
\proc^{\sel}(\path_m)
=\sum_{i=1}^m\sel(\path_{i-1})(x_i)
&\leq\sum_{i=1}^m
\big[\proc(\path_i)-\proc(\path_{i-1})+\nu(\path_{i-1})\big]\\
&=\proc(\path_m)-\proc(\path_0)+\sum_{i=1}^m\nu(\path_{i-1})\\
&=\proc(\path_m)-\proc(\init)+\sum_{i=1}^m\epsilon\frac{1}{2^{\ell(\path_{i-1})+2}}\\
&=\proc(\path_m)+\sum_{i=1}^m\epsilon\frac{1}{2^{(i-1)+2}}\\
&=\proc(\path_m)+\frac{\epsilon}{2}\sum_{i=1}^m\frac{1}{2^{i}}
\leq\proc(\path_m)+\frac{\epsilon}{2},
\end{align*}
where the first equality is due to Eq.~\eqref{eq:Fnclosedform}. As an immediate consequence, we find that
\begin{equation*}
\limsup\proc^\sel(\path)
=\limsup_{m\rightarrow\infty}\proc^\sel(\path_m)
\leq\limsup_{m\rightarrow\infty}\proc(\path_m)+\frac{\epsilon}{2}
=\limsup\proc(\path)+\frac{\epsilon}{2}
.
\end{equation*}
Since this holds for all $\path\in\paths$, we have that $\limsup\proc^\sel\leq\limsup\proc+\nicefrac{\epsilon}{2}$ and therefore also, due to Eq.~\eqref{eq:firstpart}, that
\begin{equation*}
\limsup\proc^\sel\leq f-\lim_{n\rightarrow\infty}\lexpV(f_n)+\epsilon.
\end{equation*}
Hence, using Eq.~\eqref{eq:Ville}, we find that $\lexpV(f)\geq\lim_{n\rightarrow\infty}\lexpV(f_n)-\epsilon$. Since this holds for all $\epsilon>0$, we finally obtain that $\lexpV(f)\geq\lim_{n\rightarrow\infty}\lexpV(f_n)$.
\end{proof}

% By combining Theorems~\ref{theo:non-decreasing} and~\ref{theo:non-increasing}, we find that the Ville-Vovk-Shafer natural extension is continuous with respect to the pointwise convergence of any sequence of $n$-measurable gambles.

% \begin{corollary}Let $f_n$, $n\in\nats$, be any sequence of $n$-measurable gambles on $\paths$ such that the pointwise limit $\lim_{n\rightarrow\infty}f_n$ exists and is equal to some gamble $f\in\gambles(\paths)$. Then
% \begin{equation}\label{eq:generallimit}
% \lim_{n\rightarrow\infty}\lexpV(f_n)
% =\lexpV(f).
% \end{equation}
% \end{corollary}
% \begin{proof}
% *** MOET IK NOG OPSCHRIJVEN ***
% \end{proof}

\section{Do these results apply to more general random processes as well?}

The results in this note were proved for---not necessarily stationary---Markov chains. However, as the reader may have noticed, none of our proofs have made use of the Markov property. The basic building blocks where the local models $\lexp(\cdot\vert s)=\lexp(\cdot\vert x_1\ldots x_n)$. At no point was it necessary for these models to depend on $x_n$ only, as is imposed by the Markov property. Hence, all of the results in this note remain true for random processes that are not Markovian. In fact, it is not even necessary for the graphical structure of $\paths$ to be a complete $\vert\values\vert$-ary infinite tree. Any discrete event tree can be used, as long as each of its situations has a finite---possibly different---number of children. The use of almost-desirable selections is not necessary either, similar results can be obtained for desirable selections. However, a formal justification for these and other related claims falls beyond the scope of the present note; see Ref.~\cite{deCooman2014} for more information.


\section*{Acknowledgements}
The results in this note have benefited from discussions with Enrique Miranda, Matthias C. M. Troffaes and Arthur Van Camp.

%\bibliographystyle{plain} 
%\bibliography{general}

\begin{thebibliography}{1}

\bibitem{deCooman2014}
G.~de~Cooman, E.~Miranda, and J.~De~Bock.
\newblock A theory of random processes.
\newblock Work in progress.

\end{thebibliography}

\end{document}

1402.3056.extracted_bib
{deCooman2014 G.~de~Cooman, E.~Miranda, and J.~De~Bock. \newblock A theory of random processes. \newblock Work in progress.