Dominant stochastic markets

[Vanessa Kosoy]

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

We generalize the formalism of dominant markets to account for stochastic “deductive processes,” and prove a theorem regarding the asymptotic behavior of such markets. In a following post, we will show how to use these tools to formalize the ideas outlined here.

---

Appendix A contains the key proofs. Appendix B contains the proofs of technical propositions used in Appendix A, which are mostly straightforward. Appendix C contains the statement of a version of the optional stopping theorem from Durret.

##Notation

Given $X$ a topological space:

• $P\left(X\right)$ is the space of Borel probability measures on $X$ equipped with the weak* topology.

• $C\left(X\right)$ is the Banach space of continuous functions $X\to R$ with uniform norm.

• $B\left(X\right)$ is the Borel $\sigma$-algebra on $X$.

• $U\left(X\right)$ is the $\sigma$-algebra of universally measurable sets on $X$.

• Given $\mu \in P\left(X\right)$, $\mathrm{supp}\mu$ denotes the support of $\mu$.

Given $X$ and $Y$ measurable spaces, $K:X\stackrel{\text{mk}}{\to }Y$ is a Markov kernel from $X$ to $Y$. For any $x\in X$, we have $K\left(x\right)\in P\left(Y\right)$. Given $\mu \in P\left(X\right)$, $\mu ⋉K\in P(X\times Y)$ is the semidirect product of $\mu$ and $K$ and $K_{\ast }\mu \in P\left(Y\right)$ is the pushforward of $\mu$ by $K$.

Given $X$, $Y$ Polish spaces, $\pi :X\to Y$ Borel measurable and $\mu \in P\left(X\right)$, we denote $\mu \mid \pi$ the set of Markov kernels $K:Y\stackrel{\text{mk}}{\to }X$ s.t.${\pi }_{\ast }\mu ⋉K$ is supported on the graph of $\pi$ and $K_{\ast }{\pi }_{\ast }\mu =\mu$. By the disintegration theorem, $\mu \mid \pi$ is always non-empty and any two kernels in $\mu \mid \pi$ coincide ${\pi }_{\ast }\mu$-almost everywhere.

##Results

The way we previously laid out the dominant market formalism, the sequence of observations (represented by the sets $\left\{X_i\right\}$) was fixed. To study forecasting, we instead need to assume this sequence is sampled from some probability measure (the true environment).

For each $n\in N$, let $O_n$ be a compact Polish space.$O_n$ represents the space of possible observations at time $n$. Denote

$$Y_n:=\prod _{m<n}{O}_m$$

Given $n\le m$, ${\pi }_{nm}:Y_m\to Y_n$ denotes the projection mapping and ${\pi }_n:={\pi }_{n,n+1}$. Denote

$$X=\prod _{n=0}^{\infty }{O}_n$$

$X$ is a compact Polish space. For each $n\in N$ we denote ${\pi }_{n\omega }:X\to Y_n$ the projection mapping. Given $y\in Y_n$, we denote $X_y:={\pi }_{n\omega }^{-1}\left(y\right)$, a closed subspace of $X$. Given $n\in Z$ and $x\in X$, we denote $x\left(n\right):={\pi }_{max(n,0)\omega }\left(x\right)$.

#Definition 1

A market is a sequence of mappings ${\{M_n:Y_n\to P(X\left)\right\}}_{n\in N}$ s.t.

• Each $M_n$ is measurable w.r.t.$U\left(Y_n\right)$ and $B\left(P\right(X\left)\right)$.

• For any $y\in Y_n$, $\mathrm{supp}{M}_n\left(y\right)\subseteq X_y$.

---

As before, we define the space of trading strategies $T\left(X\right):=C\left(P\right(X)\times X)$, but this time we regard it as a Banach space.

#Definition 2

A trader is a sequence of mappings ${\{T_n:Y_n\times P(X{)}^n\to T\left(X\right)\}}_{n\in N}$ which are measurable w.r.t.$U\left(Y_n\right)\otimes B\left(P\right(X{)}^n)$ and $B\left(T\right(X\left)\right)$.

---

Given a trader $T$ and a market $M$, we define the mappings $\{T_n^M:Y_n\to T(X){\}}_{n\in N}$ (measurable w.r.t.$U\left(Y_n\right)$ and $B\left(T\right(X\left)\right)$) and $\{{\overline{T}}_n^M:Y_n\to C(X){\}}_{n\in N}$ (measurable w.r.t.$U\left(Y_n\right)$ and $B\left(C\right(X\left)\right)$) as follows:

$$T_n^M\left(y\right):=T_n(y,M_0({\pi }_{0n}\left(y\right)),M_1({\pi }_{1n}\left(y\right))\dots M_{n-1}({\pi }_{n-1,n}\left(y\right)\left)\right)$$

$${\overline{T}}_n^M\left(y\right):=T_n^M(y,M_n(y\left)\right)$$

The “market maker” lemma now requires some additional work due to the measurability requirement:

#Lemma

Consider any trader $T$. Then, there is a market $M$ s.t. for all $n\in N$ and $y\in Y_n$

$$\mathrm{supp}{M}_n\left(y\right)\subseteq \underset{X_y}{argmax}{\overline{T}}_n^M\left(y\right)$$

---

As before, we have the operator $W:T\left(X\right)\to T\left(X\right)$ defined by

$$W\tau (\mu ,x):=\tau (\mu ,x)-E_{z\sim \mu }\left[\tau \right(\mu ,z\left)\right]$$

We also introduce the notation $\{W{\overline{T}}_n^M:Y_n\to C(X){\}}_{n\in N}$ and $\{\Sigma W{T}_n^M:Y_{max(n-1,0)}\to C(X){\}}_{n\in N}$ which are measurable mappings defined by

$$W{\overline{T}}_n^M\left(y\right)=W{T}_n^M(y,M_n(y\left)\right)$$

$$\Sigma W{T}_n^M\left(y\right)=\sum _{m<n}W{\overline{T}}_m^M\left({\pi }_{mn}\right(y\left)\right)$$

#Definition 3

A market $M$ is said to dominate a trader $T$ when for any $x\in X$, if

$$\underset{n\in N}{inf}\underset{z\in X_{x\left(n\right)}}{min}\Sigma W{T}_{n+1}^M\left(x\right(n),z)>-\infty$$

then

$$\underset{n\in N}{sup}\underset{z\in X_{x\left(n\right)}}{max}\Sigma W{T}_{n+1}^M\left(x\right(n),z)<+\infty$$

#Theorem 1

Given any countable set of traders $R$, there is a market $M$ s.t.$M$ dominates all $T\in R$.

---

Theorem 1 is proved exactly as before (modulo Lemma), and we omit the details.

We now describe a class of traders associated with a fixed environment ${\mu }^{\ast }\in P\left(X\right)$ s.t. if a market dominates a trader from this class, a certain function of the pricing converges to 0 with ${\mu }^{\ast }$-probability 1. In a future post, we will apply this result to a trader associated with an incomplete models $\Phi \subseteq P\left(X\right)$ by observing that the trader is in the class for any ${\mu }^{\ast }\in \Phi$.

#Definition 4

A trading metastrategy is a uniformly bounded family of measurable mappings $\{{\upsilon }_n:Y_n\to T(X){\}}_{n\in N}$. Given ${\mu }^{\ast }\in P\left(X\right)$, $\upsilon$ is said said to be profitable for ${\mu }^{\ast }$, when there are $\beta >0$ and $\{K_n\in {\mu }^{\ast }\mid {\pi }_{n\omega }{\}}_{n\in N}$ s.t. for any $n\in N$, ${\pi }_{n\omega \ast }{\mu }^{\ast }$-almost any $y\in Y_n$ and any $\mu \in P\left(X_y\right)$:

$$E_{K_n\left(y\right)}\left[\upsilon \right(y,\mu \left)\right]-E_{\mu }\left[\upsilon \right(y,\mu \left)\right]\ge \beta \left(\underset{X_y}{max}\upsilon \right(y,\mu )-\underset{X_y}{min}\upsilon (y,\mu \left)\right)$$

---

Even if a metastrategy is profitable, it doesn’t mean that a smart trader should use this metastrategy all the time: in order to avoid running out of budget, a trader shouldn’t place too many bets simultaneously. The following construction defines a trader that employs a metastrategy only when all previous bets are closed to being resolved.

#Definition 5

Fix a metastrategy $\upsilon$. We define the trader $T_{\upsilon }$ and the measurable mappings $\{U_{\upsilon n}:Y_n\times P(X{)}^n\to C\left(X\right){\}}_{n\in N}$ recursively as follows:

$$U_0:=0$$

$$T_{\upsilon 0}:={\upsilon }_0$$

$$U_{\upsilon ,n+1}(y,\{{\mu }_m{\}}_{m\le n}):=U_{\upsilon n}({\pi }_n\left(y\right),\left\{{\mu }_m{\}}_{m<n}\right)+T_{\upsilon n}(y,\{{\mu }_m{\}}_{m\le n})$$

$$T_{\upsilon ,n+1}(y,\{{\mu }_m{\}}_{m\le n}):=\{\begin{array}{c}{\upsilon }_{n+1}\left(y\right)\text{if}{max}_{X_y}{U}_{\upsilon ,n+1}(y,\{{\mu }_m{\}}_{m\le n})-{min}_{X_y}{U}_{\upsilon ,n+1}(y,\left\{{\mu }_m{\}}_{m\le n}\right)\le 1\\ 0\text{otherwise}\end{array}$$

#Theorem 2

Consider ${\mu }^{\ast }\in P\left(X\right)$, $\{K_n\in {\mu }^{\ast }\mid {\pi }_{n\omega }{\}}_{n\in N}$, $\upsilon$ a metastrategy profitable for ${\mu }^{\ast }$ and $M$ a market. Assume $M$ dominates $T_{\upsilon }$. Then, for ${\mu }^{\ast }$-almost any $x\in X$:

$$\underset{n\to \infty }{lim}\left(E_{K_n\left(x\right(n\left)\right)}\right[\upsilon \left(x\right(n),M_n(x\left(n\right)\left)\right)]-E_{M_n\left(x\right(n\left)\right)}[\upsilon \left(x\right(n),M_n(x\left(n\right)\left)\right)\left]\right)=0$$

---

That is, the market price of the “stock portfolio” traded by $\upsilon$ converges to its true ${\mu }^{\ast }$-expected value.

##Appendix A

#Proposition A.1

Fix $X$ a compact Polish space and $\tau \in T\left(X\right)$. Then, there exists $\mu \in P\left(X\right)$ s.t.

$$\mathrm{supp}\tau \left(\mu \right)\subseteq \underset{}{argmax}\tau$$

#Proof of Proposition A.1

Follows immediately from “Proposition 1” from before and Proposition B.6.

#Proposition A.2

Fix $Y,Y^{\prime }$ compact Polish spaces. Denote $X:=Y\times Y^{\prime }$. Then, there exists $M:Y\times T\left(X\right)\to P\left(X\right)$ measurable w.r.t.$B(Y\times T(X\left)\right)$ and $B\left(P\right(X\left)\right)$ s.t. for any $y\in Y$ and $\tau \in T\left(X\right)$:

$$\mathrm{supp}M(y,\tau )\subseteq \underset{y\times Y^{\prime }}{argmax}\tau \left(M\right(y,\tau \left)\right)$$

#Proof of Proposition A.2

Define $Z_1,Z_2,Z\subseteq Y\times T\left(X\right)\times P\left(X\right)$ by

$$Z_1:=\left\{\right(y,\tau ,\mu )\in Y\times T(X)\times P(X)\mid \mathrm{supp}\mu \subseteq X_y\}$$

$$Z_2:=\left\{\right(y,\tau ,\mu )\in Y\times T(X)\times P(X)\mid E_{\mu }[\tau \left(\mu \right)]=\underset{y\in Y^{\prime }}{max}\tau (\mu ,y,y^{\prime }\left)\right\}$$

$$Z:=\left\{\right(y,\tau ,\mu )\in Y\times T(X)\times P(X)\mid \mathrm{supp}\mu \subseteq \underset{y\times Y^{\prime }}{argmax}\tau (\mu \left)\right\}$$

We can view $Z$ as the graph of a multivalued mapping from $Y_n\times T\left(X\right)$ to $P\left(X\right)$. We will now show this multivalued mapping has a selection, i.e. a single-valued measurable mapping whose graph is a subset. Obviously, the selection is the desired $M$.

$Z_1$ is closed by Proposition B.7.$Z_2$ is closed by Proposition B.5.$Z=Z_1\cap Z_2$ by Proposition B.6 and hence closed. In particular, the fiber $Z_{y\tau }$ of $Z$ over any $(y,\tau )\in Y\times T\left(X\right)$ is also closed.

For any $y\in Y$, $\tau \in T\left(X\right)$, define $i_y:Y^{\prime }\to X$ by $i_y\left(y^{\prime }\right):=(y,y^{\prime })$ and ${\tau }_y\in T\left(Y^{\prime }\right)$ by ${\tau }_y(\nu ,y^{\prime }):=\tau (i_{y\ast }\nu ,y,y^{\prime })$. Applying Proposition A.1 to ${\tau }_y$ we get $\nu \in P\left(Y^{\prime }\right)$ s.t.

$$\mathrm{supp}{\tau }_y\left(\nu \right)\subseteq \underset{}{argmax}{\tau }_y$$

It follows that $(y,\tau ,i_{y\ast }\nu )\in Z$ and hence $Z_{y\tau }$ is non-empty.

Consider any $U\subseteq P\left(X\right)$ open. Then, $A_U:=(Y\times T(X)\times U)\cap Z$ is locally closed and in particular $F_{\sigma }$. Therefore, the image of $A_U$ under the projection to $Y\times T\left(X\right)$ is also $F_{\sigma }$ and in particular Borel.

Applying the Kuratowski-Ryll-Nardzewski measurable selection theorem, we get the desired result.

#Proof of Lemma

For any $n\in N$, let $M_n:Y_n\times T\left(X\right)\to P\left(X\right)$ be as in Proposition A.2. We define $M_n$ recursively by:

$$M_n\left(y\right):=M_n(y,T_n^M(y\left)\right)$$

#Proposition A.3

Consider $X$ a probability space, $\{F_n\subseteq 2^X{\}}_{n\in N}$ a filtration of $X$, $t,\alpha ,\beta >0$, $\{S_n:X\to R{\}}_{n\in N}$ and $\{{\Delta }_n:X\to [0,t]{\}}_{n\in N}$ stochastic processes adapted to $F$. Assume that:

$$E\left[\right|S_0\left|\right]<\infty$$

$$\forall n^{\prime }\ge n:|S_{n^{\prime }}-S_n|\le \sum _{m=n}^{n^{\prime }-1}{\Delta }_m+\alpha$$

$$E[S_{n+1}-S_n\mid F_n]\ge \beta {\Delta }_n$$

Then, ${inf}_n{S}_n>-\infty$ with probability 1.

---

The proof will use the following definition:

#Definition A

Consider a sequence $\{t_n\in [0,1]{\}}_{n\in N}$. The accumulation times of $t$ are $\{n_k\in N\bigsqcup \{\infty \}{\}}_{k\in N}$ defined recursively by

$$n_0:=0$$

$$n_{k+1}=\{\begin{array}{c}inf\{n\in N\mid {\sum }_{m=n_k}^{n-1}{t}_m\ge 1\}\text{if}{n}_k<\infty \\ \infty \text{if}{n}_k=\infty \end{array}$$

Consider $X$ a probability space and $\{{\Delta }_n:X\to [0,1]{\}}_{n\in N}$ a stochastic process. The accumulation times of $\Delta$ are $\{N_k:X\to N\bigsqcup \{\infty \}{\}}_{k\in N}$ defined pointwise as above. Clearly, they are stochastic processes and whenever $\Delta$ is adapted to a filtration $\{F_n\subseteq 2^X{\}}_{n\in N}$, they are stopping times w.r.t. $F$.

#Proof of Proposition A.3

Without loss of generality, we can assume $t=1$ (otherwise we can renormalize $S$, $\Delta$ and $\alpha$ by a factor of $t^{-1}$). Define $\{S_n^0:X\to R{\}}_{n\in N}$ by

$$S_n^0:=S_n-\beta \sum _{m=0}^{n-1}{\Delta }_m$$

By Proposition B.8, $S^0$ is a submartingale. Let $\{N_n:X\to N\bigsqcup \{\infty \}{\}}_{n\in N}$ be the accumulation times of $\Delta$. By proposition N23, $\{S_{min(n,N_k)}^0{\}}_{n\in N}$ are submartingales for all $k$. By Proposition\ N24, each of them is uniformly integrable. Using the fact that $N_k\le N_{k+1}$ to apply Theorem C, we get

$$E[S_{N_{k+1}}^0\mid F_{N_k}]\ge S_{N_k}^0$$

Clearly, $\{S_{N_k}^0{\}}_{k\in N}$ is adapted to $\{F_{N_k}{\}}_{k\in N}$. Doob’s second martingale convergence theorem implies that $E\left[\right|S_{N_k}^0\left|\right]<\infty$ ($S_{N_k}^0$ is the limit of the uniformly integrable submartingale $\{S_{min(n,N_k)}^0{\}}_{n\in N}$). We conclude that $\{S_{N_k}^0{\}}_{k\in N}$ is a submartingale.

By Proposition B.12, $|S_{N_{k+1}}^0-S_{N_k}^0|\le \alpha +2$. Applying the Azuma-Hoeffding inequality, we conclude that for any positive integer $k$:

$$\mathrm{Pr}[S_{N_k}^0-S_0<-\beta k]\le \exp (-\frac{(\beta k{)}^2}{2(\alpha +2{)}^{2}k})=\exp (-\frac{{\beta }^{2}k}{2(\alpha +2{)}^2})$$

Since ${\sum }_k\exp (-\frac{{\beta }^{2}k}{2(\alpha +2{)}^2})<\infty$, it follows that

$$\mathrm{Pr}[\exists k\in N\forall l>k:S_{N_l}^0-S_0\ge -\beta l]=1$$

$$\mathrm{Pr}[\exists k\in N\forall l>k:S_{N_l}-S_0\ge \beta (\sum _{n=0}^{N_l-1}{\Delta }_n-l\left)\right]=1$$

By Proposition B.13

$$\mathrm{Pr}[\sum _{n=0}^{\infty }{\Delta }_n=\infty ⟹\exists k\in N\forall l>k:S_{N_l}-S_0\ge 0]=1$$

It remains to show that if $x\in X$ is s.t.${inf}_n{S}_n\left(x\right)=-\infty$ then the condition above fails. Consider any such $x\in X$. $\left|S_n\right(x)-S_0(x\left)\right|\le {\sum }_{m=0}^{n-1}{\Delta }_n\left(x\right)+\alpha$, therefore ${\sum }_{n=0}^{\infty }{\Delta }_n\left(x\right)=\infty$. On the other hand, by Proposition B.14, ${inf}_k{S}_{N_k\left(x\right)}\left(x\right)=-\infty$.

#Proposition A.4

Consider $X$ a probability space, $\{F_n\subseteq 2^X{\}}_{n\in N}$ a filtration of $X$, $t,\alpha ,\beta >0$, $\{S_n^{\prime }:X\to R{\}}_{n\in N}$ and $\{{\Delta }_n:X\to [0,t]{\}}_{n\in N}$ stochastic processes adapted to $F$ and $\{S_n:X\to R{\}}_{n\in N}$ an arbitrary stochastic process. Assume that:

$$|S_n-S_n^{\prime }|\le \frac{\alpha }{4}$$

$$E\left[\right|S_0\left|\right]<\infty$$

$$|S_{n+1}-S_n|\le {\Delta }_n$$

$$E[S_{n+1}-S_n\mid F_n]\ge \beta {\Delta }_n$$

Then, ${inf}_n{S}_n>-\infty$ (equivalently ${inf}_n{S}_n^{\prime }>-\infty$) with probability 1.

#Proof of Proposition A.4

Define $S_n^{\prime \prime }:=E[S_n\mid F_n]$. We have

$$E\left[\right|S_0^{\prime \prime }\left|\right]=E\left[\right|E[S_0\mid F_0]\left|\right]\le E\left[E\right[\left|S_0\right|\mid F_0\left]\right]=E\left[\right|S_0\left|\right]<\infty$$

$$|S_n^{\prime \prime }-S_n^{\prime }|=\left|E\right[S_n\mid F_n]-S_n^{\prime }|=\left|E\right[S_n-S_n^{\prime }\mid F_n\left]\right|\le \frac{\alpha }{4}$$

$$|S_n^{\prime \prime }-S_n|\le |S_n^{\prime \prime }-S_n^{\prime }|+|S_n^{\prime }-S_n|\le \frac{\alpha }{2}$$

$$\forall n^{\prime }\ge n:|S_{n^{\prime }}^{\prime \prime }-S_n^{\prime \prime }|\le |S_{n^{\prime }}-S_n|+\alpha \le \sum _{m=n}^{n^{\prime }-1}{\Delta }_m+\alpha$$

$$E[S_{n+1}^{\prime \prime }-S_n^{\prime \prime }\mid F_n]=E\left[E\right[S_{n+1}\mid F_{n+1}]-E[S_n\mid F_n]\mid F_n]=E[S_{n+1}-S_n\mid F_n]\ge \beta {\Delta }_n$$

By Proposition A.3, ${inf}_n{S}_n^{\prime \prime }>-\infty$ with probability 1. Since $|S_n^{\prime \prime }-S_n|\le \frac{\alpha }{2}$, we get the desired result.

#Proposition A.5

Consider $\{O_n{\}}_{n\in N}$, $\{Y_n:={\prod }_{m<n}{O}_m{\}}_{n\in N}$ and $X:={\prod }_n{O}_n$ as before. Consider ${\mu }^{\ast }\in P\left(X\right)$, $\{K_n\in {\mu }^{\ast }\mid {\pi }_{n\omega }{\}}_{n\in N}$, $\upsilon$ a metastrategy profitable for ${\mu }^{\ast }$ and $M$ a market. Then, for ${\mu }^{\ast }$-almost any $x\in X$:

$$\underset{n\in N}{inf}\underset{z\in X_{x\left(n\right)}}{min}\Sigma W{T}_{\upsilon ,n+1}^M\left(x\right(n),z)>-\infty$$

#Proof of Proposition A.5

We regard $X$ as a probability space using the $\sigma$-algebra $U\left(X\right)$ and the probability measure ${\mu }^{\ast }$. For any $n\in N$, we define $F_n\subseteq U\left(X\right)$ and $S_n,S_n^{\prime },{\Delta }_n:X\to R$ by

$$F_n:={\pi }_{n\omega }^{-1}\left(U\right(Y_n\left)\right)$$

$$S_n\left(x\right):=\Sigma W{T}_{\upsilon n}^M\left(x\right(n-1),x)$$

$$S_n^{\prime }\left(x\right):=\underset{z\in X_{x(n-1)}}{min}\Sigma W{T}_{\upsilon n}^M\left(x\right(n-1),z)$$

$${\Delta }_n\left(x\right):=\underset{z\in X_{x\left(n\right)}}{max}{\overline{T}}_{\upsilon n}^M\left(x\right(n),z)-\underset{z\in X_{x\left(n\right)}}{min}{\overline{T}}_{\upsilon n}^M\left(x\right(n),z)$$

Clearly, $F$ is a filtration of $X$, $S,S^{\prime },\Delta$ are stochastic processes and $S^{\prime },\Delta$ are adapted to $F$. $\upsilon$ is uniformly bounded, therefore $T_{\upsilon }$ is uniformly bounded and so is $\Delta$. Obviously, $\Delta$ is also non-negative.

By Proposition B.15, $|S_n-S_n^{\prime }|$ are uniformly bounded.$S_0$ is bounded and in particular $E\left[\right|S_0\left|\right]<\infty$. We have

$$\left|S_{n+1}\right(x)-S_n(x\left)\right|=\left|W{\overline{T}}_{\upsilon n}^M\right(x\left(n\right),x\left)\right|\le {\Delta }_n\left(x\right)$$

Let $\beta >0$ and $K_n\in {\mu }^{\ast }\mid {\pi }_{n\omega }$ be as in Definition 4.

$$E[S_{n+1}-S_n\mid F_n]=E_{z\sim K_n\left(x\right(n\left)\right)}\left[W{\overline{T}}_{\upsilon n}^M\right(x\left(n\right),z\left)\right]$$

$$E[S_{n+1}-S_n\mid F_n]=E_{z\sim K_n\left(x\right(n\left)\right)}\left[{\overline{T}}_{\upsilon n}^M\right(x\left(n\right),z\left)\right]-E_{z\sim M_n\left(x\right(n\left)\right)}\left[{\overline{T}}_{\upsilon n}^M\right(x\left(n\right),z\left)\right]$$

By definition of $T_{\upsilon }$, ${\overline{T}}_{\upsilon n}^M\left(x\right(n\left)\right)$ is equal to either ${\upsilon }_n\left(x\right(n),M_n(x\left(n\right)\left)\right)$ or 0. In either case, we get (almost everywhere)

$$E[S_{n+1}-S_n\mid F_n]\ge \beta \left(\underset{X_{x\left(n\right)}}{max}{\overline{T}}_{\upsilon n}^M\right(x\left(n\right))-\underset{X_{x\left(n\right)}}{min}{\overline{T}}_{\upsilon n}^M(x\left(n\right)\left)\right)=\beta {\Delta }_n$$

Applying Proposition A.4, we get the desired result.

#Proposition A.6

Consider the setting of Proposition A.3. Then, for almost all $x\in X$:

$$\underset{n\in N}{sup}{S}_n\left(x\right)<\infty ⟹\sum _{n=0}^{\infty }{\Delta }_n\left(x\right)<\infty$$

#Proof of Proposition A.6

Define $\{S_n^0:X\to R{\}}_{n\in N}$ by

$$S_n^0:=S_n-\beta \sum _{m=0}^{n-1}{\Delta }_m$$

Let $\{N_n{\}}_{n\in N}$ be the accumulation times of $\Delta$. Consider any $x\in X$ s.t.${sup}_n{S}_n\left(x\right)=s\left(x\right)<\infty$ but ${\sum }_n{\Delta }_n\left(x\right)=\infty$. Proposition B.13 implies that

$$S_{N_k\left(x\right)}^0\left(x\right)\le S_{N_k\left(x\right)}\left(x\right)-\beta k\le s\left(x\right)-\beta k$$

As in the proof of Proposition A.3, we can apply the Azuma-Hoeffding inequality to $S_N^0$ and get that for any positive integer $k$

$$Pr[S_{N_k}^0-S_0<-k^{\frac{3}{4}}]\le \exp (-\frac{k^{\frac{3}{2}}}{2(\alpha +2{)}^{2}k})=\exp (-\frac{k^{\frac{1}{2}}}{2(\alpha +2{)}^2})$$

It follows that

$$\sum _{k=1}^{\infty }Pr[S_{N_k}^0-S_0<-k^{\frac{3}{4}}]<\infty$$

$$Pr[\exists k\in N\forall l>k:S_{N_l}^0-S_0<-l^{\frac{3}{4}}]=0$$

$$Pr[\exists m\in N\forall k\in N:S_{N_k}^0\le m-\beta k]=0$$

Comparing with the inequality from before, we reach the desired conclusion.

#Proposition A.7

Consider the setting of Proposition A.4. Then, for almost all $x\in X$:

$$\underset{n\in N}{sup}{S}_n\left(x\right)<\infty ⟹\sum _{n=0}^{\infty }{\Delta }_n\left(x\right)<\infty$$

#Proof of Proposition A.7

Define $S_n^{\prime \prime }:=E[S_n\mid F_n]$. As in the proof of Proposition A.4, $S^{\prime \prime }$ meets the conditions of Proposition A.3 and thus of Proposition A.6 also. By Proposition A.6, for almost all $x\in X$:

$$\underset{n\in N}{sup}{S}_n^{\prime \prime }\left(x\right)<\infty ⟹\sum _{n=0}^{\infty }{\Delta }_n\left(x\right)<\infty$$

As in the proof of Proposition A.4, $|S_n^{\prime \prime }-S_n|$ is uniformly bounded, giving the desired result.

#Proof of Theorem 2

Let $F$, $S$, $S^{\prime }$ and $\Delta$ be as in the proof of Proposition A.5. Using Proposition A.5 and the assumption that $M$ dominates $T_{\upsilon }$, we conclude that for ${\mu }^{\ast }$-almost any $x\in X$, ${sup}_n{S}_n\left(x\right)<\infty$. As in the proof of Proposition A.5, the conditions of Proposition A.4 are satisfied, and therefore the conditions of Proposition A.7 are also satisfied. Applying Proposition A.7, we conclude that ${\sum }_n{\Delta }_n\left(x\right)<\infty$. By Proposition B.17, it follows that for any $n\gg 0$, $T_{\upsilon n}^M\left(x\right(n\left)\right)=\upsilon \left(x\right(n\left)\right)$. We get

$$E_{K_n\left(x\right(n\left)\right)}\left[\upsilon \right(x\left(n\right),M_n\left(x\right(n\left)\right)\left)\right]-E_{M_n\left(x\right(n\left)\right)}\left[\upsilon \right(x\left(n\right),M_n\left(x\right(n\left)\right)\left)\right]=E_{K_n\left(x\right(n\left)\right)}\left[{\overline{T}}_{\upsilon n}^M\right(x\left(n\right)\left)\right]-E_{M_n\left(x\right(n\left)\right)}\left[{\overline{T}}_{\upsilon n}^M\right(x\left(n\right)\left)\right])$$

$$E_{K_n\left(x\right(n\left)\right)}\left[\upsilon \right(x\left(n\right),M_n\left(x\right(n\left)\right)\left)\right]-E_{M_n\left(x\right(n\left)\right)}\left[\upsilon \right(x\left(n\right),M_n\left(x\right(n\left)\right)\left)\right]\le {\Delta }_n\left(x\right)$$

$$\underset{n\to \infty }{lim}\left(E_{K_n\left(x\right(n\left)\right)}\right[\upsilon \left(x\right(n),M_n(x\left(n\right)\left)\right)]-E_{M_n\left(x\right(n\left)\right)}[\upsilon \left(x\right(n),M_n(x\left(n\right)\left)\right)\left]\right)=0$$

##Appendix B

#Proposition B.1

If $X,Y$ are compact Polish spaces and $f:X\times Y\to R$ is continuous, then $F:X\to C\left(Y\right)$ defined by $F\left(x\right)\left(y\right):=f(x,y)$ is continuous.

---

We omit the proof of Proposition B.1, since it appeared as “Proposition A.2” before.

#Proposition B.2

Fix $X,Y$ compact Polish spaces. Define $e:C(Y\times X)\times Y\to C\left(X\right)$ by $e(f,y)\left(x\right):=f(y,x)$. Then, $e$ is continuous. In particular, we can apply this to $Y=P\left(X\right)$ in which case $e:T\left(X\right)\times P\left(X\right)\to C\left(X\right)$.

#Proof of Proposition B.2

Consider $f_k\to f$ and $y_k\to y$. We have

$$\underset{x\in X}{max}\left|f_k\right(y_k,x)-f(y_k,x\left)\right|\le \parallel f_k-f\parallel \to 0$$

By Proposition B.1

$$\underset{x\in X}{max}\left|f\right(y_k,x)-f(y,x\left)\right|\to 0$$

Combining, we get

$$\underset{x\in X}{max}\left|f_k\right(y_k,x)-f(y,x\left)\right|\to 0$$

#Proposition B.3

Fix $Y,Y^{\prime }$ compact Polish spaces and denote $X:=Y\times Y^{\prime }$. Define $F:Y\times C\left(X\right)\to R$ by

$$F(y,f):=\underset{y^{\prime }\in Y^{\prime }}{max}f(y,y^{\prime })$$

Then, $F$ is continuous.

#Proof of Proposition B.3

Consider $y_k\to y$, $f_k\to f$. By Proposition B.1, $y_k\to y$ implies that

$$\underset{k\to \infty }{lim}\underset{y^{\prime }\in Y^{\prime }}{max}f(y_k,y^{\prime })=\underset{y^{\prime }\in Y^{\prime }}{max}f(y,y^{\prime })$$

Since $f_k\to f$, we get

$$\underset{k\to \infty }{lim}\underset{y^{\prime }\in Y^{\prime }}{max}{f}_k(y_k,y^{\prime })=\underset{y^{\prime }\in Y^{\prime }}{max}f(y,y^{\prime })$$

#Proposition B.4

Fix $Y,Y^{\prime }$ compact Polish spaces. Denote $X:=Y\times Y^{\prime }$. Define $Z\subseteq Y\times P\left(X\right)\times C\left(X\right)$ by

$$Z:=\left\{\right(y,\mu ,f)\in Y\times P(X)\times C(X)\mid E_{\mu }[f]=\underset{y^{\prime }\in Y^{\prime }}{max}f(y,y^{\prime }\left)\right\}$$

Then, $Z$ is closed.

#Proof of Proposition B.4

Consider $y_k\to y$, ${\mu }_k\to \mu$, $f_k\to f$, $(y_k,{\mu }_k,f_k)\in Z$. By Proposition B.3, we get

$$\underset{y^{\prime }\in Y^{\prime }}{max}f(y,y^{\prime })=\underset{k\to \infty }{lim}\underset{y^{\prime }\in Y^{\prime }}{max}{f}_k(y_k,y^{\prime })=\underset{k\to \infty }{lim}{E}_{{\mu }_k}\left[f_k\right]=E_{\mu }\left[f\right]$$

Hence, $(y,\mu ,f)\in Z$.

#Proposition B.5

Fix $Y,Y^{\prime }$ compact Polish spaces. Denote $X:=Y\times Y^{\prime }$. Define $Z\subseteq Y\times P\left(X\right)\times T\left(X\right)$ by

$$Z:=\left\{\right(y,\mu ,\tau )\in Y\times P(X)\times T(X)\mid E_{\mu }[\tau \left(\mu \right)]=\underset{y^{\prime }\in Y^{\prime }}{max}\tau (\mu ,y,y^{\prime }\left)\right\}$$

Then, $Z$ is closed.

#Proof of Proposition B.5

By Proposition B.2, $Z$ is the continuous inverse image of a subset of $Y\times P\left(X\right)\times C\left(X\right)$ which is closed by Proposition B.4.

#Proposition B.6

Fix $X$ a compact Polish space. Consider $f\in C\left(X\right)$ and $\mu \in P\left(X\right)$ and denote $M:=maxf$. Then, $\mathrm{supp}\mu \subseteq f^{-1}\left(M\right)$ iff $E_{\mu }\left[f\right]=M$.

#Proof of Proposition B.6

If $\mathrm{supp}\mu \subseteq f^{-1}\left(M\right)$ then ${\mathrm{Pr}}_{x\sim \mu }\left[f\right(x)\ne M]=0$ and therefore $E_{\mu }\left[f\right]=M$.

Now, assume $E_{\mu }\left[f\right]=M$. For any $k\in N$, Markov’s inequality yields

$${\mathrm{Pr}}_{x\sim \mu }[M-f(x)\ge \frac{1}{k}]\le k{E}_{x\sim \mu }[M-f(x\left)\right]=0$$

Taking $k\to \infty$, we get ${\mathrm{Pr}}_{x\sim \mu }[M>f(x\left)\right]=0$ and hence $\mathrm{supp}\mu \subseteq f^{-1}\left(M\right)$.

#Proposition B.7

Consider $Y,Y^{\prime }$ compact Polish spaces. Denote $X:=Y\times Y^{\prime }$. Define $Z\subseteq Y\times P\left(X\right)$ by

$$Z:=\left\{\right(y,\mu )\in Y\times P(X)\mid \mathrm{supp}\mu \subseteq y\times Y^{\prime }\}$$

Then, $Z$ is closed.

#Proof of Proposition B.7

We fix metrizations for $Y$ and $Y^{\prime }$ and metrize $X$ by

$$d_X\left(\right(y_1,y_1^{\prime }),(y_2,y_2^{\prime }\left)\right):=max\left(d_Y\right(y_1,y_2),d_{Y^{\prime }}(y_1^{\prime },y_2^{\prime }\left)\right)$$

For each $y\in Y$, denote $d_y:=d_{y\times Y^{\prime }}$.

Consider $y_k\to y$, ${\mu }_k\to \mu$, $(y_k,{\mu }_k)\in Z$. We have $E_{{\mu }_k}\left[d_{y_k}\right]=0$. By Proposition B.1, $d_{y_k}\to d_y$, therefore $E_{\mu }\left[d_y\right]=0$. By Proposition B.6, $\mathrm{supp}\mu \subseteq y\times Y^{\prime }$ and hence $(y,\mu )\in Z$.

#Proposition B.8

Consider $X$ a probability space, $\{F_n\subseteq 2^X{\}}_{n\in N}$ a filtration of $X$, $\{S_n:X\to R{\}}_{n\in N}$ and $\{{\Delta }_n:X\to [0,1]{\}}_{n\in N}$ stochastic processes adapted to $F$. Assume that there are $\alpha ,\beta >0$ s.t.:

$$E\left[\right|S_0\left|\right]<\infty$$

$$|S_n-S_0|\le \sum _{m=0}^{n-1}{\Delta }_m+\alpha$$

$$E[S_{n+1}-S_n\mid F_n]\ge \beta {\Delta }_n$$

Define $\{S_n^0:X\to R{\}}_{n\in N}$ by

$$S_n^0:=S_n-\beta \sum _{m=0}^{n-1}{\Delta }_m$$

Then, $S^0$ is a submartingale.

#Proof of Proposition B.8

Obviously, $S^0$ is adapted to $F$. We have

$$E\left[\right|S_n^0\left|\right]\le E\left[\right|S_n\left|\right]+\beta n\le E\left[\right|S_0\left|\right]+E\left[\right|S_n-S_0\left|\right]+\beta n\le E\left[\right|S_0\left|\right]+2\beta n+\alpha <\infty$$

$$E[S_{n+1}^0\mid F_n]=E[S_{n+1}\mid F_n]-\beta \sum _{m=0}^n{\Delta }_m$$

$$E[S_{n+1}^0\mid F_n]\ge E[S_n\mid F_n]+\beta {\Delta }_n-\beta \sum _{m=0}^n{\Delta }_m$$

$$E[S_{n+1}^0\mid F_n]\ge E[S_n\mid F_n]-\beta \sum _{m=0}^{n-1}{\Delta }_m$$

$$E[S_{n+1}^0\mid F_n]\ge E[S_n^0\mid F_n]$$

#Proposition B.9

Let $X$ be a probability space, $\{F_n\subseteq 2^X{\}}_{n\in N}$ a filtration on