# An Excursion-Theoretic Approach to Stability of Discrete-Time Stochastic
Hybrid Systems

Debasish Chatterjee  ETL I19
Physikstrasse 3
ETH Zürich
8092 Zürich
Switzerland
Ph. +41-44-632-2326
Fax: +41-44-632-1211<EMAIL_ADDRESS>and  Soumik Pal  C-547
Padelford Hall
Department of Mathematics
University of Washington, Seattle
WA 98195
Ph. +1-206-543-7832<EMAIL_ADDRESS>
###### Abstract.

We address stability of a class of Markovian discrete-time stochastic hybrid
systems. This class of systems is characterized by the state-space of the
system being partitioned into a safe or target set and its exterior, and the
dynamics of the system being different in each domain. We give conditions for
$\boldsymbol{L}_{1}$-boundedness of Lyapunov functions based on certain
negative drift conditions outside the target set, together with some more
minor assumptions. We then apply our results to a wide class of randomly
switched systems (or iterated function systems), for which we give conditions
for global asymptotic stability almost surely and in $\boldsymbol{L}_{1}$. The
systems need not be time-homogeneous, and our results apply to certain systems
for which functional-analytic or martingale-based estimates are difficult or
impossible to get.

###### Key words and phrases:

stochastic stability, excursion theory, Markov process

###### 2000 Mathematics Subject Classification:

Primary: 93E15; Secondary: 60J05

Debasish Chatterjee’s research is partially supported by the Swiss National
Science foundation grant 200021-122072.

##  1\. Introduction

Increasing complexity of engineering systems in the modern world has led to
the hybrid systems paradigm in systems and control theory [vS00, Lib03]. A
hybrid system consists of a number of domains in the state-space and a
dynamical law corresponding to each domain; thus, at any instant of time the
dynamics of the system depends on the domain that its state is in. One would
then restrict attention to behavior of the system in individual domains, which
is typically a simpler problem. However, understanding how the dynamics in the
individual domains interact among each other is necessary in order to ensure
smooth operation of the overall system. This article is a step towards
understanding the behavior of (possibly non-Markovian) stochastic hybrid
systems which undergo excursions into different domains infinitely often. Here
we consider the simplest and perhaps the most important hybrid system,
consisting of a compact target or safe set and its exterior, with different
dynamics inside and outside the safe set. Our objective is to introduce a new
method of analysis of systems that are outside the safe set infinitely often
in course of their evolution. The analysis carried out here provides a basis
for controller synthesis of systems with control inputs—it gives clear
indications about the type of controllers to be designed in order to ensure
certain natural and basic stability properties in closed loop.

Let us look at two interesting and practically important examples of hybrid
systems with two domains—a compact safe set and its exterior, with different
dynamics in each. The first concerns optimal control of a Markov process with
state constraints. Markov control processes have been extensively studied; we
refer the reader to the excellent monographs and surveys [BS78, Bor91, HLL96,
HLL99] for further information, applications and references. For our purposes
here, consider the canonical example of a linear controlled system perturbed
by additive Gaussian noise and having probabilistic constraints on the states.
A hybrid structure of the controlled system naturally presents itself in the
following fashion. Except in the most trivial of cases, computing the
constrained optimal control over an infinite horizon is impossible, and one
resorts to a a rolling-horizon controller. (Rolling-horizon controllers are
considerably popular, for basic definitions, comparisons and references see
e.g., [Mac01] in the deterministic context, and [CHL09] and the references
therein in the stochastic context.) Computational overheads restrict the size
of the window in the rolling-horizon controller, and determine the maximal
(typically bounded) region—called the safe set—in which this controller can be
active. No matter how good the resulting controller is, the additive nature of
the Gaussian noise ensures that the states are subjected to excursions away
from the safe set infinitely often almost surely. Once outside the safe set,
the rolling-horizon controller is switched off and a recovery strategy is
activated, whose task is to bring the states back to the safe set quickly and
efficiently. This problem is of great practical interest and a subject of
current research, see e.g., [CHL09] and the references in them for possible
strategies inside the safe set, and [CCCL08] for one possible recovery
strategy. Evidently, stability of this hybrid system depends largely on the
recovery strategy, since as long as the states stay inside the safe set, they
are bounded. However, traditional methods of stability analysis do not work
well precisely because of the unlimited number of excursions. Theorem (2.2) of
this article addresses this issue, and provides a method of ensuring strong
boundedness and stability properties of the hybrid system. Intuitively it says
that under the recovery strategy there exists a well-behaved supermartingale
until the states hit the safe set, then the system state is bounded in
expectation uniformly over time. A complete picture of stability and ergodic
properties of a general controlled hybrid system is beyond the scope of the
present article, and will be reported elsewhere. We refer the reader to
[CFM05, Chapter 3] for earlier work pertaining to stability of a class of
hybrid systems, and to [MT09] for stability of general discrete-time Markov
processes.

The second example is one that we shall pursue further in this article,
namely, a class of discrete-time Markov processes called iterated function
systems [BDEG88, LM94] (ifs). They are widely applied, for instance, in the
construction of fractals [LM94], in studies on the process of generation of
red blood corpuscles [LM02, LS04], in statistical physics [Kif86], and
simulation of important stochastic processes [Wer05]. Of late they are being
employed in key problems of physical chemistry and computational biology,
namely, the behavior of the chemical master equation [Wil06, Chapter 6] (CME),
which governs the continuous-time stochastic (Markovian) reaction-kinetics at
very low concentrations (of the order of tens of molecules). Invariant
distributions, certain finite-time properties, and robustness properties with
respect to disturbances of the underlying Markov process are of interest in
modeling and analysis of unicellular organisms. It is well-known that the CME
is analytically intractable (see [JH07, ACK08] for special cases), but the
invariant distribution of the Markov process can be recovered from simulation
of the embedded Markov chain in a computationally efficient way [MA08]. This
embedded chain is an ifs taking values in a nonnegative integer lattice. From
a biological perspective, good health of a cell corresponds to the ifs
evolving in a safe region on an average, despite moderate disturbances to the
numbers of molecules involved in the key reactions. However, in most cases
compact invariant sets do not exist. It is therefore of interest to find
conditions under which, even though there are excursions of the states away
from a safe set infinitely often, the ifs is stochastically bounded, or some
strong stability properties hold. Theorem (2.2) of this article leads to
results (in §3) which address this issue.

This article unfolds as follows. §2 contains our main results—Theorem (2.2)
and (2.9), which provide conditions under which a Lyapunov function of the
states is $\boldsymbol{L}_{1}$-bounded. We establish this
$\boldsymbol{L}_{1}$-boundedness under the assumptions that a certain derived
process is a supermartingale outside a compact set, and some more minor
conditions.111It also seems conceivably possible that relaxed Foster-Lyapunov
inequalities as in [DFMS04, Condition $\mathbf{D}(\phi,V,C)$, p. 1356] arising
in the context of subgeometric convergence to a stationary distribution can be
employed in the construction of the aforementioned supermartingale; this
constitutes future work. (The supermartingale condition alone is not enough,
as pointed out in [PR99], where the authors establish variants of our results
for scalar, possibly non-Markovian processes having increments with bounded
$p$-th moments for $p>2$.) For our results to hold, the underlying process
need not be time-homogeneous or Markovian. To wit, in §2.2 we define a class
of hybrid processes that switch between two Markov processes depending on
whether they inside or outside a fixed set in the state-space, and demonstrate
that although the resulting process may be non-Markovian, our results continue
to hold. Connections to optimal stopping problems are drawn in §2.3, which
gives a systematic procedure for verifying our assumptions. In §2.4 we apply
the techniques our techniques to a class of sampled diffusion processes. In
addition to the cases considered here, the results in §2 will be of interest
in queueing theory, along the lines of the works [HLR96, BKR+01]. §3 contains
some applications of the results in §2 to stability and robustness of ifs. The
classical weak stability questions concerning the existence and uniqueness of
invariant measures of ifs, addressed in e.g., [DF99, JT01, Sza06], revolve
around average contractivity hypotheses of the constituent maps and continuity
of the probabilities. In §3.1 we look at stronger stability properties of the
ifs, namely, global asymptotic stability almost surely and in expectation, for
which we give sufficient conditions. There are no assumptions of global
contractivity or memoryless choice of the maps at each iterate; we just
require a condition resembling average contractivity in terms of Lyapunov
functions with a suitable coupling condition with the Markovian transition
probabilities. We mention that although some of the assumptions in [JT01]
resemble ours, the conditions needed to establish existence of invariant
measures in [JT01] are stronger than what we employ; see §3.1 for a detailed
comparison. We also demonstrate in §3.2 that under mild assumptions, iterated
function systems possess strong stability and robustness properties with
respect to bounded disturbances. In this subsection the exogenous bounded
disturbance is not modeled as a random process.

#### Notations

Let $\mathbb{N}\coloneqq\\{1,2,\ldots\\}$,
$\mathbb{N}_{0}\coloneqq\\{0,1,2,\ldots\\}$, and $\mathbb{R}_{\geqslant
0}\coloneqq[0,\infty[$. We let $\left\lVert\cdot\right\rVert$ denote the
standard Euclidean norm on $\mathbb{R}^{d}$. We let $\bar{B}_{r}$ denote the
closed Euclidean ball around $0$, i.e.,
$\bar{B}_{r}\coloneqq\bigl{\\{}y\in\mathbb{R}^{d}\big{|}\left\lVert
y\right\rVert\leqslant r\bigr{\\}}$. For a vector $v\in\mathbb{R}^{d}$ let
$v^{\scriptscriptstyle{\mathrm{T}}}$ denote its transpose, and $\left\lVert
v\right\rVert_{P}$ denote $\sqrt{v^{\scriptscriptstyle{\mathrm{T}}}Pv}$ for a
$d\times d$ real matrix $P$. The maximum and minimum of two real numbers $a$
and $b$ is denoted by $a\vee b$ and $a\wedge b$, respectively.

##  2\. General results

Before we get into hybrid systems, it will be simpler to follow the arguments
if we start by considering a discrete-time Markov chain.

###  2.1. Obtaining $\boldsymbol{L}_{1}$ Bound using Excursions

Let $X\coloneqq(X_{t})_{t\in\mathbb{N}_{0}}$ be a discrete time Markov chain
with a state space $\mathcal{S}$. We denote the transition kernel of this
chain by $\mathsf{P}$, i.e., for every $x\in\mathcal{S}$, the probability
measure $\mathsf{P}_{x}(\cdot)\coloneqq\mathsf{P}(x,\cdot)$ determines the law
of $X_{t+1}$, conditioned on $X_{t}=x$. At this point we only assume the state
space $\mathcal{S}$ to be any Polish space.

######  (2.1) Assumption.

There exists a nonnegative function
$\varphi:\mathbb{N}_{0}\times\mathcal{S}\longrightarrow\mathbb{R}_{\geqslant
0}$ satisfying the following.

  1. (i)

There exists a subset $K\subset\mathcal{S}$ such that the process
$(Y_{t})_{t\in\mathbb{N}_{0}}$ defined by $Y_{t}=\varphi(t,X_{t})$ is a
supermartingale under $\mathsf{P}_{x_{0}}$, for every
$x_{0}\in\mathcal{S}\setminus K$ until the first time $X_{t}$ hits $K$. To
wit, if $X_{0}=x_{0}\in\mathcal{S}\setminus K$ and we define

$\tau_{K}^{\vphantom{T}}=\inf\bigl{\\{}t>0\;\big{|}\;X_{t}\in K\bigr{\\}},$

then the process
$\bigl{(}Y_{t\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}_{t\in\mathbb{N}_{0}}$ is a
supermartingale under $\mathsf{P}_{x_{0}}$.

  2. (ii)

There exists a nonnegative measurable real-valued function
$V:\mathcal{S}\longrightarrow\mathbb{R}$ and a positive sequence
$(\theta(t))_{t\in\mathbb{N}_{0}}$ such that

$\varphi(t,x)\geqslant V(x)/\theta(t)\quad\text{for all
}(t,x)\in\mathbb{N}_{0}\times\mathcal{S},$

and $C\coloneqq\sum_{t\in\mathbb{N}_{0}}\theta(t)<\infty$.

  3. (iii)

$\delta\coloneqq\sup_{x\in K}V(x)<\infty$. $\diamondsuit$

Our objective is to prove under the above condition (and another minor
assumptions) that there exists a bound on
$\sup_{t}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}$ depending on $x_{0}$.

######  (2.2) Theorem.

Consider the setup in Assumption (2.1), and assume that

((2.3)) $\beta\coloneqq\sup_{x_{0}\in
K}\mathsf{E}\bigl{[}\varphi(0,X_{1})\boldsymbol{1}_{\\{X_{1}\in\mathcal{S}\setminus
K\\}}\;\big{|}\;X_{0}=x_{0}\bigr{]}<\infty.$

Let $\gamma\coloneqq\sup_{t\in\mathbb{N}_{0}}\theta(t)$. Then we have

$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}\leqslant
C\beta+\delta+\gamma\varphi(0,x_{0}).$

In the rest of this section we prove the above theorem. Fix a time
$t\in\mathbb{N}_{0}$, and define two random times

$g_{t}\coloneqq\sup\bigl{\\{}s\in\mathbb{N}_{0}\;\big{|}\;s\leqslant
t,\;X_{s}\in K\bigr{\\}}\quad\text{and}\quad
h_{t}\coloneqq\inf\bigl{\\{}s\in\mathbb{N}_{0}\;\big{|}\;s\geqslant
t,\;X_{s}\in K\bigr{\\}}.$

We follow the standard custom of defining supremum over empty sets to be
$-\infty$, and the infimum over empty sets to be $+\infty$.

Note that $g_{t}$ is not a stopping time with respect to the natural
filtration generated by the process $X$, although $h_{t}$ is. The random
interval $[g_{t},h_{t}]$ is a singleton if and only if $X_{t}\in K$.
Otherwise, we say that $X_{t}$ is within an excursion outside $K$.

Now we have the following decomposition:

((2.4))
$\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}=\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=-\infty\\}}\bigr{]}+\sum_{s=0}^{t}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=s\\}}\bigr{]}.$

Our first objective is to bound each of the expectations
$\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=s\\}}\bigr{]}$.

Before we move on, let us first prove a Lemma which follows readily from
Assumption 1.

######  (2.5) Lemma.

Let $X_{0}=x_{0}\in\mathcal{S}\setminus K$. Then

((2.6))
$\mathsf{E}_{x_{0}}\bigl{[}V(X_{s})\boldsymbol{1}_{\\{\tau^{\vphantom{T}}_{K}>s\\}}\bigr{]}\leqslant\varphi(0,x_{0})\theta(s)\qquad\text{for
}s\in\mathbb{N}_{0},$

where $(\theta(t))_{t\in\mathbb{N}_{0}}$ is defined in Assumption (2.1).

###### Proof.

This is a straightforward application of Optional Sampling Theorem (OST) for
discrete-time supermartingales. Applying OST for the bounded stopping time
$s\wedge\tau^{\vphantom{T}}_{K}$ to the supermartingale
$\bigl{(}\varphi(t,X_{t})\bigr{)}_{t\in\mathbb{N}_{0}}$, in view of
$\varphi\geqslant 0$, we have

$\begin{split}\varphi(0,x_{0})&\geqslant\mathsf{E}_{x_{0}}\\!\bigl{[}\varphi(s\wedge\tau_{K}^{\vphantom{T}},X_{s\wedge\tau_{K}^{\vphantom{T}}})\bigr{]}\geqslant\mathsf{E}_{x_{0}}\bigl{[}\varphi(s,X_{s})\boldsymbol{1}_{\\{\tau^{\vphantom{T}}_{K}>s\\}}\bigr{]}.\end{split}$

Now, by condition (i) in Assumption (2.1), we can write $\varphi(s,x)\geqslant
V(x)/\theta(s)$. Thus, substituting back, one has

$\varphi(0,x_{0})\geqslant\mathsf{E}_{x_{0}}\bigl{[}V(X_{s})\boldsymbol{1}_{\\{\tau^{\vphantom{T}}_{K}>s\\}}\bigr{]}/\theta(s).$

Since $(\theta(t))_{t\in\mathbb{N}_{0}}$ is positive, we arrive at ((2.6)). ∎

We are ready for the proof of Theorem (2.2).

###### Proof of Theorem (2.2).

Let us consider three separate cases:

Case 1. ($-\infty<g_{t}<t$). In this case $g_{t}$ can take values
$\\{0,1,2,\ldots,t-1\\}$. Now, if $s\in\\{0,1,2,\ldots,t-1\\}$, then

$\begin{split}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})&\boldsymbol{1}_{\\{g_{t}=s\\}}\bigr{]}=\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{X_{s}\in
K\\}}\boldsymbol{1}_{\\{X_{i}\notin K,\;i=s+1,\ldots,t\\}}\bigr{]}\\\
&=\int_{K}\mathsf{P}^{s}(x_{0},\mathrm{d}x)\int_{\mathcal{S}\setminus
K}\mathsf{P}(x,\mathrm{d}y)\;\mathsf{E}_{y}\bigl{[}V(X_{t-s-1})\boldsymbol{1}_{\\{\tau_{K}^{\vphantom{T}}>t-s-1\\}}\bigr{]},\end{split}$

and by ((2.5)) it follows that the right-hand side is at most

$\int_{K}\mathsf{P}^{s}(x_{0},\mathrm{d}x)\int_{\mathcal{S}\setminus
K}\mathsf{P}(x,\mathrm{d}y)\;\varphi(0,y)\theta(t-s-1).$

Thus, one has

((2.7))
$\begin{split}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=s\\}}\bigr{]}&\leqslant\theta(t-s-1)\int_{K}\mathsf{P}^{s}(x_{0},\mathrm{d}x)\int_{\mathcal{S}\setminus
K}\mathsf{P}(x,\mathrm{d}y)\;\varphi(0,y)\\\ &\leqslant\theta(t-s-1)\sup_{x\in
K}\mathsf{E}_{x}\bigl{[}\varphi(0,X_{1})\boldsymbol{1}_{\\{X_{1}\in\mathcal{S}\setminus
K\\}}\bigr{]}\\\ &=\theta(t-s-1)\beta.\end{split}$

Case 2. ($g_{t}=t$). This is easy, since $X_{t}\in K$ implies
$V(X_{t})\leqslant\delta$. Thus

$\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=t\\}}\bigr{]}\leqslant\delta\mathsf{P}_{x_{0}}(X_{t}\in
K)\leqslant\delta.$

Case 3. ($g_{t}=-\infty$). This is the case when the chain started from
outside $K$ and has not yet hit $K$, and therefore,

$\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{g_{t}=-\infty\\}}\bigr{]}=\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\boldsymbol{1}_{\\{\tau_{K}^{\vphantom{T}}>t\\}}\bigr{]}\leqslant\varphi(0,x_{0})\theta(t).$

Combining all three cases above, we get the bound:

((2.8))
$\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}\leqslant\sum_{s=0}^{t-1}\theta(t-s-1)\beta+\delta+\varphi(0,x_{0})\theta(t).$

Maximizing the right-hand side of ((2.8)) over $t$, we arrive at

$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}\leqslant\beta\sum_{s=0}^{\infty}\theta(s)+\delta+\varphi(0,x_{0})\sup_{t\in\mathbb{N}_{0}}\theta(t),$

which is the bound stated in the theorem. ∎

Often it will turn out that $\varphi(t,x)$ is a function $\psi(t,V(x))$ as in
the case of the classical Foster-Lyapunov type supermartingales [MT09]. In
that case $\varphi(t,x)=\mathrm{e}^{\alpha t}V(x)$, for some positive
$\alpha$. Thus $\varphi(t,\cdot)$ is a linear function of $V(x)$ for each
fixed $t$, with $\theta(t)=\mathrm{e}^{-\alpha t}$, which shows that the
sequence $(\theta(t))_{t\in\mathbb{N}_{0}}$ is summable. See also [FK04] and
the references therein for more general Foster-Lyapunov type conditions. For
examples which are not linear see §2.4.

###  2.2. A Class of Hybrid Processes

The preceding analysis can be extended for processes which switch their
behavior depending on whether the current value is within $K$ or not. They
constitute a particularly useful class of controlled processes in which a
controller attempts to drive the system into a _target_ or safe set
$K\subset\mathcal{S}$ whenever the system gets out of $K$ due to its inherent
randomness. Below we give a rigorous construction of such a process.

### A process $X$ that is $(Y,Z)$-hybrid with respect to $K$

Consider a pair of Markov chains $(Y,Z)$ where $Y$ is a time-homogeneous
Markov chain, and $Z$ is a (possibly) time inhomogeneous Markov chain. We
construct a _hybrid discrete-time stochastic process_ $X$ by the following
recipe:

Firstly, let the state space for the process be $\mathcal{S}^{\mathbb{N}_{0}}$
along with the natural filtration

$\mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\ldots$

generated by the coordinate maps.

Secondly, we define the sequence of stopping times
$\sigma_{0}\coloneqq\tau_{0}\coloneqq-\infty$ and
$\tau_{1}\leqslant\sigma_{1}\leqslant\tau_{2}\leqslant\sigma_{2}\leqslant\ldots$
by

$\begin{split}\tau_{i}&\coloneqq\inf\bigl{\\{}t>\sigma_{i-1}\;\big{|}\;X_{t}\in
K\bigr{\\}}\quad\text{and}\\\
\sigma_{i}&\coloneqq\inf\bigl{\\{}t>\tau_{i}\;\big{|}\;X_{t}\notin
K\bigr{\\}}\end{split}$

for $i\in\mathbb{N}_{0}$.

Finally, we define the process $X$ as follows: for a measurable
$B\subset\mathcal{S}$,

$\displaystyle\text{if }X_{t}=x,\exists\,i:\tau_{i}\leqslant t<\sigma_{i},\;$
$\displaystyle\begin{cases}X_{t}=Y_{t},\\\ \mathsf{P}\bigl{(}X_{t+1}\in
B\;\big{|}\,\mathcal{F}_{t}\bigr{)}=\mathsf{P}\bigl{(}Y_{1}\in
B\;\big{|}\;Y_{0}=x\bigr{)},\end{cases}$ $\displaystyle\text{if
}X_{t}=x,\exists\,i:\sigma_{i}\leqslant t<\tau_{i+1},\;$
$\displaystyle\begin{cases}X_{t}=Z_{t},\\\ \mathsf{P}\bigl{(}X_{t+1}\in
B\;\big{|}\,\mathcal{F}_{t}\bigr{)}=\mathsf{P}\bigl{(}Z_{t+1-\sigma_{i}}\in
B\;\big{|}\;Z_{t-\sigma_{i}}=x\bigr{)}.\end{cases}$

To wit, the process defined above behaves as the homogeneous chain $Y$
whenever it is inside $K$. Once the process $X$ exits the set $K$, a
controller alters the behavior of the chain which, until it enters $K$ again,
behaves as a copy of the inhomogeneous chain $Z$ starting from a point outside
$K$. The process $X$ is in general non-Markovian due to the possible time
inhomogeneity of $Z$. Nevertheless, it is a natural class of examples of
switching systems whose Markovian behavior switches in different regions on
the state space. We say that $X$ is _$(Y,Z)$ -hybrid with respect to $K$_.

The following generalization of Theorem (2.2) can be proved along lines of the
original proof. The only requirement is a slight modification of the condition
((2.3)) which is needed to alter the second inequality in ((2.7)).

######  (2.9) Theorem.

Consider a stochastic process $X$ that is $(Y,Z)$-hybrid with respect to a
measurable $K\subset\mathcal{S}$ for some homogeneous Markov chain $Y$ and
some possibly inhomogeneous Markov chain $Z$. Suppose Assumption (2.1) holds
for the process $Z$ and

((2.10)) $\beta:=\sup_{y_{0}\in
K}\mathsf{E}\left[\varphi(0,Y_{1})1_{\\{Y_{1}\in\mathcal{S}\setminus
K\\}}\;\big{|}\;Y_{0}=y_{0}\right]<\infty.$

If the process $X$ starts from $x_{0}\in\mathcal{S}\setminus K$, we have

((2.11))
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x_{0}}\bigl{[}V(X_{t})\bigr{]}\leqslant
C\beta+\delta+\gamma\varphi(0,x_{0}).$

It is interesting to note that the right side of above bound is a total of
individual contributions by the control (for $C$), the choice of $K$ (for
$\delta$), and the initial configuration (for $x_{0}$). We stress that _the
conclusion holds even when $X$ is no longer a Markov chain due to the time
inhomogeneity of $Z$_. This is important, especially because operator-
theoretic bounds like Foster-Lyapunov, or martingale-based bounds do not work
in such a case.

###  2.3. Connection with Optimal Stopping Problems

Suppose that we are given a Markov chain $Z$ taking values in $\mathcal{S}$, a
function $V:\mathcal{S}\longrightarrow\mathbb{R}$, and a measurable target or
safe set $K\subset\mathcal{S}$. (Alternatively, we may assume that we are
given an $\mathcal{S}$-valued process $X$ that is $(Y,Z)$-hybrid with respect
to a measurable $K\subset\mathcal{S}$.) Our objective is to investigate
whether the sequence $\bigl{(}V(X_{t})\bigr{)}_{t\in\mathbb{N}_{0}}$ is
$\boldsymbol{L}_{1}$-bounded. To this end one can follow the two-step
procedure of first searching for a function $\varphi$ satisfying Assumption
(2.1), followed by an application of Theorem (2.9). A systematic procedure of
doing this is given by the following connection with Optimal Stopping
problems.

Let $(\theta(t))_{t\in\mathbb{N}_{0}}$ be some positive sequence of numbers
such that $\sum_{t\in\mathbb{N}_{0}}\theta(t)$ is finite. Define the pay-off
or the reward function as

$h(t,x)=\begin{cases}V(x)/\theta(t)&\quad\text{if}\;x\in\mathcal{S}\setminus
K,\;t\in\mathbb{N}_{0},\\\ 0&\quad\text{if}\;x\in
K,\;t\in\mathbb{N}_{0}.\end{cases}$

Recall that the Optimal Stopping problem [PS06, Chapter 1] for the process $Z$
and the reward function $h$ defined above consists of finding a stopping time
$\tau^{*}$ such that

((2.12))
$\mathsf{E}_{x}\Bigl{[}h\bigl{(}\tau^{*}\wedge\tau_{K}^{\vphantom{T}},Z_{\tau^{*}\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}\Bigr{]}=\operatorname*{ess\,sup}_{\tau}\mathsf{E}_{x}\Bigl{[}h\bigl{(}\tau\wedge\tau_{K}^{\vphantom{T}},Z_{\tau\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}\Bigr{]},$

where $\tau_{K}^{\vphantom{T}}$ is the hitting time to the set $K$, and
$\operatorname*{ess\,sup}$ refers to essential supremum over the set of all
possible stopping times (see [PS06, Chapter 1, Lemma 1.3]).

Define the value function as

((2.13))
$\varphi(n,x_{0})\coloneqq\operatorname*{ess\,sup}_{\tau\in\mathbb{T}_{n}}\mathsf{E}\bigl{[}h(\tau,V(Z_{\tau}))\,\big{|}\,Z_{n}=x_{0}\bigr{]},$

where $\mathbb{T}_{n}$ is the set of stopping times

$\bigl{\\{}(\tau\vee n)\wedge\tau_{K}^{\vphantom{T}}\,\big{|}\,\text{$\tau$ an
arbitrary stopping time}\bigr{\\}}.$

######  (2.14) Theorem.

Suppose that the value function $\varphi(0,x_{0})$ is finite for all
$x_{0}\in\mathcal{S}$, then

  1. (i)

$\varphi(t,x_{0})$ is finite for all $t\in\mathbb{N}_{0}$ and

$\varphi(t,x_{0})\geqslant V(x_{0})/\theta(t)\quad\text{for all
}(t,x_{0})\in\mathbb{N}_{0}\times(\mathcal{S}\setminus K).$

  2. (ii)

The process $(Y_{t})_{t\in\mathbb{N}_{0}}$ defined by

$Y_{t}\coloneqq\varphi\bigl{(}t\wedge\tau_{K}^{\vphantom{T}},Z_{t\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}$

is a supermartingale.

###### Proof.

The proof follows from the general theory of optimal stopping. See, for
example, [CRS71, Chapter 4]. The sequence of rewards is given by the process
$V(Z_{t\wedge\tau_{K}^{\vphantom{T}}})/\theta(t)$, $t=0,1,2,\ldots$. Applying
[CRS71, Theorem 4.1, p. 66] we get

$\varphi(n,x_{0})=\bigl{(}V(x_{0})/\theta(n)\bigr{)}\vee\Bigl{(}\mathsf{E}\Bigl{[}\varphi\bigl{(}n+1,Z_{(n+1)\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}\,\Big{|}\,Z_{n\wedge\tau_{K}^{\vphantom{T}}}=x_{0}\Bigr{]}\Bigr{)}.$

By considering the first of the two terms in the maximum on the right-hand
side above we obtain (i), and (ii) follows from the second. ∎

In other words, the value function $\varphi(t,x)$ defined in ((2.13))
satisfies the conditions of Theorem (2.9).

######  (2.15) Theorem.

Consider an $\mathcal{S}$-valued process $X$ that is $(Y,Z)$-hybrid with
respect to a measurable $K\subset\mathcal{S}$ as in §2.2. Suppose that for
some nonnegative integrable sequence $(\theta(t))_{t\in\mathbb{N}_{0}}$ the
optimal stopping problem ((2.12)) has a finite value function
$\varphi(t,x_{0})$. If additionally condition ((2.10)) is true, then the bound
((2.11)) holds.

Let us remark that the value function, being the envelope, is the smallest
supermartingale (hence the sharpest bound) that can satisfy Theorem (2.9).
Several methods of solving optimal stopping problems in the Markovian setting
are available and we refer the reader to [PS06] for a complete review.

######  (2.16) Remark.

There is a parallel converse result employing standard Foster-Lyapunov
techniques for the verification of $f$-ergodicity and $f$-regularity [MT09,
Chapter 14] of Markov processes. The analysis is based on the functional
inequality $\mathsf{E}[V(X_{1})\mid
X_{0}=x]-V(x)\leqslant-f(x)+b\boldsymbol{1}_{C}(x)$ for measurable functions
$V:\mathcal{S}\longrightarrow[0,\infty]$ and
$f:\mathcal{S}\longrightarrow[1,\infty[$, a scalar $b>0$, and a Borel subset
$C$ of $\mathcal{S}$; [MT09, Theorem 14.2.3] asserts that the minimal solution
to this inequality, which exists if $C$ is petite (see [MT09] for precise
details), is a “value function” given by
$G_{C}(x,f)\coloneqq\mathsf{E}\bigl{[}\sum_{t=0}^{\sigma_{C}}f(X_{t})\,\big{|}\,X_{0}=x]$,
where $\sigma_{C}$ is the first hitting-time to $C$. The proof is also based
on the existence of a certain supermartingale, and the Markov property is
employed crucially.$\vartriangleleft$

###  2.4. A Class of Sampled Diffusions

In the setting of the process $X$ being $(Y,Z)$-hybrid with respect to a given
set $K$, suppose that the state-space for the Markov chains $Y$ and $Z$ is
$\mathbb{R}^{d}$ and the safe set $K$ is compact. Observe that the only
challenge in applying Theorem (2.9) is to find a suitable function $\varphi$
given the Markov chain $Z$ and the function $V$. In applications, a natural
choice for the function $V$ is given by square of the Euclidean norm, i.e.,
$V(x)=\sum_{i=1}^{d}x_{i}^{2}$. For this choice of $V$, we describe below a
natural class of examples of Markov chains for which one can construct a
$\varphi$ that satisfies part (i) of Assumption (2.1).

Consider a diffusion with a possibly time-inhomogeneous drift function, given
by the $d$-dimensional stochastic differential equation

((2.17)) ${\mathrm{d}}X_{t}=b(t,X_{t})\mathrm{d}t+\mathrm{d}W_{t},$

where $W_{t}=(W_{t}(1),W_{t}(2),\ldots,W_{t}(d))$ is a vector of $d$
independent Brownian motions, and $b:\mathbb{R}_{\geqslant
0}\times\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$ is a measurable function.

We will abuse the notations somewhat and construct a function
$\varphi:\mathbb{R}_{\geqslant 0}\times\mathbb{R}_{\geqslant
0}\longrightarrow\mathbb{R}_{\geqslant 0}$ such that
$\bigl{(}\varphi(t,V(X_{t}))\bigr{)}_{t\in\mathbb{N}_{0}}$ is a
supermartingale outside a compact set $K$ and satisfies
$\varphi(t,\xi)\geqslant\xi/\theta(t)$ for some nonnegative sequence
$(\theta(t))_{t\in\mathbb{N}_{0}}$. We define
$Z_{i}=X_{i\wedge\tau_{K}^{\vphantom{T}}}$ for $i\in\mathbb{N}_{0}$; $Z$ is
the the diffusion sampled at integer time points before hitting $K$. It is
clear that $Z$ is a Markov chain such that
$\bigl{(}\varphi(i,V(Z_{i}))\bigr{)}_{i\in\mathbb{N}_{0}}$ is a
supermartingale that satisfies the Assumptions (2.1) as long as
$\sum_{t\in\mathbb{N}_{0}}\theta(t)<\infty$.

To construct such a $\varphi$, let us consider a well known family of one-
dimensional diffusion, known as the squared Bessel processes (BESQ). This
family is indexed by a single nonnegative parameter $\delta\geqslant 0$ and is
described as the unique strong solution of the SDE

((2.18))
$\mathrm{d}Y_{t}=2\sqrt{Y_{t}}\,\mathrm{d}\mathfrak{b}_{t}+\delta\,\mathrm{d}t,\qquad
Y_{0}=y_{0}\geqslant 0,$

where $\mathfrak{b}\coloneqq(\mathfrak{b}_{t})_{t\in\mathbb{N}_{0}}$ is a one-
dimensional standard Brownian motion. We have the following Lemma:

######  (2.19) Lemma.

Let $F:\mathbb{R}\longrightarrow\mathbb{R}_{\geqslant 0}$ be a nonnegative,
increasing, and convex function, and fix any terminal time $S>0$. Define the
function

((2.20))
$\varphi(t,y)\coloneqq\mathsf{E}\bigl{[}F(Y_{S})\,\big{|}\,Y_{t}=y\bigr{]},\quad
t\in[0,S],$

where $Y$ solves the SDE ((2.18)). Then $\varphi$ satisfies the following
properties:

  1. (i)

$\varphi$ is increasing in $y$,

  2. (ii)

$\varphi$ is convex in $y$, and

  3. (iii)

$\varphi$ satisfies the partial differential equation

((2.21)) $\begin{cases}\dfrac{\partial\varphi}{\partial
t}+\delta\varphi^{\prime}+2y\varphi^{\prime\prime}=0,\quad y>0,\;t\in(0,S),\\\
\varphi(S,y)=F(y).\end{cases}$

Note that $\varphi^{\prime}$ and $\varphi^{\prime\prime}$ in the statement of
Lemma (2.18) refers to the first and second derivatives with respect to the
second argument of $\varphi$.

###### Proof.

The proof proceeds by coupling. Let us first show that $\varphi$ is increasing
as claimed in (i). Fix $S>0$. Consider any two starting points $0\leqslant
x<y$. Construct on the same sample space two copies of BESQ processes
$Y^{(1)}$ and $Y^{(2)}$ such that both of them satisfy ((2.18)) with respect
to the same Brownian motion $\mathfrak{b}$ but $Y^{(1)}_{0}=x$ and
$Y^{(2)}_{0}=y$. It is possible to do this since the SDE ((2.18)) admits a
strong solution (see [KS08, Chapter 5, Proposition 2.13]). Hence, by [KS08,
Chapter 5, Proposition 2.18], it follows that $Y^{(1)}_{t}\leqslant
Y^{(2)}_{t}$ for all $t\geqslant 0$. Since $F$ is an increasing function, we
get

$\varphi(t,x)=\mathsf{E}_{x}\Bigl{[}F\bigl{(}Y^{(1)}_{S-t}\bigr{)}\Bigr{]}\leqslant\mathsf{E}_{y}\Bigl{[}F\bigl{(}Y^{(2)}_{S-t}\bigr{)}\Bigr{]}=\varphi(t,y).$

This proves that $\varphi$ is increasing in the second argument.

For convexity of $\varphi$ claimed in (ii), we use a different coupling. We
follow arguments very similar to the one used in the proof of [Hob98, Theorem
3.1]. Consider three initial points $0<z<y<x$. And let
$\hat{X},\hat{Y},\hat{Z}$ be three independent BESQ processes that start from
$x,y$, and $z$ respectively. Define the stopping times

$\tau_{x}=\inf\Bigl{\\{}u\;\Big{|}\;\hat{Y}_{u}=\hat{X}_{u}\Bigr{\\}},\quad\tau_{z}=\inf\Bigl{\\{}u\;\Big{|}\;\hat{Y}_{u}=\hat{Z}_{u}\Bigr{\\}}.$

Fix a time $t\in[0,S]$, and let $T=S-t$. Define

$\sigma=\tau_{x}\wedge\tau_{z}\wedge T.$

Now, on the event $\sigma=\tau_{x}$, it follows from symmetry that

((2.22))
$\begin{split}\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{Y}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{x}\\}}\Bigr{]}&=\mathsf{E}\Bigl{[}\left(\hat{Y}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{X}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{x}\\}}\Bigr{]},\\\
\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Y}_{T}\right)F\bigl{(}\hat{Z}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{x}\\}}\bigr{]}&=0.\end{split}$

Similarly, on the event $\sigma=\tau_{z}$, we have

((2.23))
$\begin{split}\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{Y}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{z}\\}}\Bigr{]}&=\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Y}_{T}\right)F\bigl{(}\hat{Z}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{z}\\}}\Bigr{]},\\\
\mathsf{E}\Bigl{[}\left(\hat{Z}_{T}-\hat{Y}_{T}\right)F\bigl{(}\hat{X}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=\tau_{z}\\}}\bigr{]}&=0.\end{split}$

And finally, when $\sigma=T$, we must have
$\hat{Z}_{T}<\hat{Y}_{T}<\hat{X}_{T}$. We use the convexity property of $F$ to
get

((2.24))
$\displaystyle\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{Y}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=T\\}}\Bigr{]}$
$\displaystyle\leqslant\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Y}_{T}\right)F\bigl{(}\hat{Z}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=T\\}}\Bigr{]}$
$\displaystyle\quad+\mathsf{E}\Bigl{[}\left(\hat{Y}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{X}_{T}\bigr{)}\boldsymbol{1}_{\\{\sigma=T\\}}\Bigr{]}.$

Combining the three cases in ((2.22)), ((2.23)), and ((2.24)) we get

((2.25))
$\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{Y}_{T}\bigr{)}\Bigr{]}\leqslant\mathsf{E}\Bigl{[}\left(\hat{X}_{T}-\hat{Y}_{T}\right)F\bigl{(}\hat{Z}_{T}\bigr{)}\Bigr{]}+\mathsf{E}\Bigl{[}\left(\hat{Y}_{T}-\hat{Z}_{T}\right)F\bigl{(}\hat{X}_{T}\bigr{)}\Bigr{]}.$

We now use the fact that $\hat{X},\hat{Y}$, and $\hat{Z}$ are independent.
Also, it is not difficult to see from the SDE ((2.18)) that
$\mathsf{E}_{x}\bigl{[}\hat{X}_{T}\bigr{]}-x=\mathsf{E}_{y}\bigl{[}\hat{Y}_{T}\bigr{]}-y=\mathsf{E}_{z}\bigl{[}\hat{Z}_{T}\bigr{]}-z=\delta
t$. Thus, from ((2.25)) we infer that

$(x-z)\varphi(t,y)\leqslant(x-y)\varphi(t,z)+(y-z)\varphi(t,x),\quad\text{for
all}\;0<z<y<x.$

This proves convexity of $\varphi$ in its second argument.

Finally, to see (iii), it suffices to observe that the equation ((2.21)) is
the classical generator relation for diffusions, for which we refer to [KS08,
Chapter 5.4]. The transition density of BESQ processes are smooth and have an
explicit representation that satisfy equation ((2.21)). The general case can
be obtained by differentiating under the integral with respect to $F$. ∎

Let us return to the multidimensional diffusion given by ((2.17)). We consider
the process $(\zeta_{t})_{t\in\mathbb{N}_{0}}$, where
$\zeta_{t}\coloneqq\varphi\bigl{(}t,\left\lVert
X_{t}\right\rVert^{2}\bigr{)}$, and $\varphi$ is the function in ((2.20)).
Note that, since $F$ is nonnegative, so is $\varphi$. Additionally, since
$\varphi$ is convex, we have

$\varphi(t,\xi)\geqslant\varphi(t,0)+\varphi^{\prime}(t,0+)\xi.$

Hence the sequence $(\theta(t))_{t=0}^{S}$ is given by

$\theta(t)=1/\varphi^{\prime}(t,0+),\quad t=0,1,\ldots,S.$

We have the following Theorem:

######  (2.26) Theorem.

Suppose that there exists a compact set $K\subset\mathbb{R}^{d}$ such that
that the drift function $b=(b_{1},b_{2},\ldots,b_{d})$ in the SDE ((2.17))
satisfies the sector condition

$\sum_{i=1}^{d}x_{i}b_{i}(t,x)<0\quad\text{for
}\;(t,x)\in\mathbb{R}_{\geqslant 0}\times(\mathcal{S}\setminus K).$

Fix any terminal time $T>0$. Define the process
$(\zeta_{t})_{t\in\mathbb{N}_{0}}\coloneqq\bigl{(}\varphi\bigl{(}t,\left\lVert
X_{t}\right\rVert^{2}\bigr{)}\bigr{)}_{t\in\mathbb{N}_{0}}$, , where $\varphi$
is the nonnegative, increasing, convex function defined in ((2.20)) with

$F(y)=\left\lVert y\right\rVert^{2}\quad\text{and}\quad\delta=d.$

Then, with the set-up as above, the stopped process
$\bigl{(}\zeta_{t\wedge\tau_{K}^{\vphantom{T}}\wedge T}\bigr{)}_{t\geqslant
0}$ is a (local) supermartingale.

###### Proof.

Applying Itô’s rule to $(\zeta_{t})_{t\in\mathbb{R}_{\geqslant 0}}$, we get

((2.27))
${\mathrm{d}}\zeta_{t}=\mathrm{d}M_{t}+\left[\frac{\partial\varphi}{\partial
t}+\mathcal{L}\varphi\right]\mathrm{d}t,$

where $M\coloneqq(M_{t})_{t\in\mathbb{R}_{\geqslant 0}}$ is in general a local
martingale ($M$ is a martingale under additional assumptions of boundedness on
the first derivative of $\varphi$), and $\mathcal{L}$ is the generator of $X$.
We compute

$\begin{split}\frac{\partial\varphi}{\partial
t}+\mathcal{L}\varphi&=\frac{\partial\varphi}{\partial
t}+\sum_{i=1}^{d}b_{i}\frac{\partial\varphi}{\partial
x_{i}}+\frac{1}{2}\sum_{i=1}^{d}\frac{\partial^{2}\varphi}{\partial
x^{2}_{i}}\\\ &=\frac{\partial\varphi}{\partial
t}+2\varphi^{\prime}\sum_{i=1}^{d}b_{i}x_{i}+\frac{1}{2}\left[2\mathrm{d}\varphi^{\prime}+\varphi^{\prime\prime}\sum_{i=1}^{d}4x_{i}^{2}\right]\\\
&=\frac{\partial\varphi}{\partial
t}+\mathrm{d}\varphi^{\prime}+2\left(\sum_{i}x_{i}^{2}\right)\varphi^{\prime\prime}+2\varphi^{\prime}\sum_{i=1}^{d}b_{i}x_{i}=2\varphi^{\prime}\sum_{i}b_{i}x_{i},\end{split}$

where the final equality holds since $\varphi$ satisfies ((2.21)) at
$y=\sum_{i}x_{i}^{2}$.

We know that $\varphi^{\prime}>0$ since $\varphi$ is increasing, and, by our
assumption, $\sum_{i}x_{i}b_{i}<0$ whenever $x\not\in K$. Thus,

$\frac{\partial\varphi}{\partial t}+\mathcal{L}\varphi\leqslant
0\quad\text{for }\;(t,x)\in[0,T]\times(\mathcal{S}\setminus K).$

Now the claim follows from the semimartingale decomposition given in ((2.27)).
∎

Note that the supermartingale $(\zeta_{t})_{t\in\mathbb{N}_{0}}$ has been
defined only for a bounded temporal horizon. Thus, to show that Theorem (2.9)
holds, some additional uniformity assumptions would be needed.

##  3\. Application to Discrete-Time Randomly Switched Systems

In this section we look at several cases of discrete-time randomly switched
systems (or, iterated function systems,) in which Theorem (2.2) of §2 applies
and gives useful uniform $\boldsymbol{L}_{1}$ bounds of Lyapunov functions. In
§3.1 we give sufficient conditions for global asymptotic stability almost
surely and in $\boldsymbol{L}_{1}$ of discrete-time randomly switched systems.
Assumptions of global contractivity in its standard form or memoryless choice
of the maps at each iterate are absent; we simply require a condition
resembling average contractivity in terms of Lyapunov functions with a
suitable coupling condition with the Markovian transition probabilities. In
§3.2 we demonstrate that under mild hypotheses iterated function systems
possess strong stability and robustness properties with respect to bounded
disturbances that are not modelled as random processes.222Recall the following
notation: We let $\mathcal{K}$ denote the collection of strictly increasing
continuous functions $\alpha:\mathbb{R}_{\geqslant
0}\longrightarrow\mathbb{R}_{\geqslant 0}$ such that $\alpha(0)=0$; we say
that a function $\alpha$ belongs to class-$\mathcal{K}_{\infty}$ if
$\alpha\in\mathcal{K}$ and $\lim_{r\to\infty}\alpha(r)=\infty$. A function
$\beta:\mathbb{R}_{\geqslant
0}\times\mathbb{N}_{0}\longrightarrow\mathbb{R}_{\geqslant 0}$ belongs to
class-$\mathcal{KL}$ if $\beta(\cdot,n)\in\mathcal{K}$ for a fixed
$n\in\mathbb{N}_{0}$, and if $\beta(r,n)\to 0$ as $n\to\infty$ for fixed
$r\in\mathbb{R}_{\geqslant 0}$. Recall that a function
$f:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$ is locally Lipschitz
continuous if for every $x_{0}\in\mathbb{R}^{d}$ and open set $O$ containing
$x_{0}$, there exists a constant $L>0$ such that $\left\lVert
f(x)-f(x_{0})\right\rVert\leqslant L\left\lVert x-x_{0}\right\rVert$ whenever
$x\in O$.

###  3.1. Stability of Discrete-Time Randomly Switched Systems

Consider the system

((3.1)) $X_{t+1}=f_{\sigma_{t}}(X_{t}),\qquad X_{0}=x_{0},\quad
t\in\mathbb{N}_{0}.$

Here
$\sigma:\mathbb{N}_{0}\longrightarrow\mathcal{P}\coloneqq\\{1,\ldots,\mathrm{N}\\}$
is a discrete-time random process, the map
$f_{i}:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$ is continuous and locally
Lipschitz, and there are points $x_{i}^{\star}\in\mathbb{R}^{d}$ such that
$f_{i}(x_{i}^{\star})=0$ for each $i\in\mathcal{P}$. The initial condition of
the system $x_{0}\in\mathbb{R}^{d}$ is assumed to be known. Our objective is
to study stability properties of this system by extracting certain nonnegative
supermartingales.

The system ((3.1)) can be viewed as an iterated function system:
$X_{t+1}=f_{\sigma_{t}}\circ\cdots\circ f_{\sigma_{1}}\circ
f_{\sigma_{0}}(x_{0})$. Varying the point $x_{0}$ but keeping the same maps
leads to a family of Markov chains initialized from different initial
conditions. The article [DF99] treats basic results on convergence and
stationarity properties of such systems with the process
$(\sigma_{t})_{t\in\mathbb{N}_{0}}$ being a sequence of independent and
identically distributed random variables taking values in $\mathcal{P}$, and
each map $f_{i}$ is a contraction. These results were generalized in [JT01]
with the aid of Foster-Lyapunov arguments.

The analysis carried out in [JT01] requires a Polish state-space, and employs
the following three principal assumptions: (a) the maps are non-separating on
an average, i.e., the average separation of the Markov chains initialized at
different points is nondecreasing over time; (b) there exists a set $C$ such
that the Markov chains started at different initial conditions contract after
the set $C$ is reached; and (c) there exists a measurable real-valued function
$V\geqslant 1$, bounded on $C$, and satisfying a Foster-Lyapunov drift
condition $QV(x)\leqslant\lambda V(x)+b\boldsymbol{1}_{C}(x)$ for some
$\lambda\in\>]0,1[$ and $b<\infty$, where $Q$ is the transition kernel. Under
these conditions the authors establish the existence and uniqueness of an
invariant measure which is also globally attractive, and the convergence to
this measure is exponential. In particular, this showed that the main results
of [DF99], which are primarily related to existence and uniqueness of
invariant probability measures, continue to hold if the contractivity
hypotheses on the family $\\{f_{i}\\}_{i\in\mathcal{P}}$ are relaxed. In this
subsection we look at stronger properties, namely, $\boldsymbol{L}_{1}$
boundedness and stability, and almost sure stability of the system ((3.1))
under Assumption (2.1). No contractivity inside a compact set is needed to
establish existence of an invariant measure under Assumption (2.1).

######  (3.2) Assumption.

The process $(\sigma_{t})_{t\in\mathbb{N}_{0}}$ is an irreducible Markov chain
with initial probability distribution $\pi^{\circ}$ and a transition matrix
$P\coloneqq[p_{ij}]_{\mathrm{N}\times\mathrm{N}}$.$\diamondsuit$

It is immediately clear that the discrete-time process
$(\sigma_{t},X_{t})_{t\in\mathbb{N}_{0}}$, taking values in the Borel space
$\mathcal{P}\times\mathbb{R}^{d}$, is Markovian under Assumption (3.2). The
corresponding transition kernel is given by

$\displaystyle Q\bigl{(}(i,x),\mathcal{P}^{\prime}\times
B\bigr{)}=\textstyle{\sum_{j\in\mathcal{P}^{\prime}}p_{ij}\boldsymbol{1}_{B}\bigl{(}f_{j}(x)\bigr{)}}\quad$
$\displaystyle\text{for }\mathcal{P}^{\prime}\subset\mathcal{P},B\text{ a
Borel subset of }\mathbb{R}^{d},$ $\displaystyle\text{and
}(i,x)\in\mathcal{P}\times\mathbb{R}^{d}.$

Our basic analysis tool is a family of Lyapunov functions, one for each
subsystem, and at different times we shall impose the following two distinct
sets of hypotheses on them.333It will be useful to recall here that the
deterministic system $x_{t+1}=f_{i}(x_{t}),\;t\in\mathbb{N}_{0},$ with initial
condition $x_{0}$ is said to be _globally asymptotically stable_ (in the sense
of Lyapunov) if (a) for every $\varepsilon>0$ there exists a $\delta>0$ such
that $\left\lVert x_{0}-x_{i}^{\star}\right\rVert<\delta$ implies $\left\lVert
x_{t}-x_{i}^{\star}\right\rVert<\varepsilon$ for all $t\in\mathbb{N}_{0}$, and
(b) for every $r,\varepsilon^{\prime}>0$ there exists a $T>0$ such that
$\left\lVert x_{0}-x_{i}^{\star}\right\rVert<r$ implies $\left\lVert
x_{t}-x_{i}^{\star}\right\rVert<\varepsilon$ for all $t>T$. The condition (a)
goes by the name of Lyapunov stability of the dynamical system (or of the
corresponding equilibrium point $x_{i}^{\star}$), and (b) is the standard
notion of global asymptotic convergence to $x_{i}^{\star}$.

######  (3.3) Assumption.

There exist a family $\\{V_{i}\\}_{i\in\mathcal{P}}$ of nonnegative measurable
functions on $\mathbb{R}^{d}$, functions
$\alpha_{1},\alpha_{2}\in\mathcal{K}$, numbers $\lambda_{\circ}\in\;]0,1[$,
$r>0$ and $\mu>1$, such that

  1. (V1)

$\alpha_{1}(\left\lVert x-x_{i}^{\star}\right\rVert)\leqslant
V_{i}(x)\leqslant\alpha_{2}(\left\lVert x-x_{i}^{\star}\right\rVert)\quad$ for
all $x$ and $i$,

  2. (V2)

$V_{i}(x)\leqslant\mu V_{j}(x)\quad$ whenever $\left\lVert x\right\rVert>r$,
for all $i,j$, and

  3. (V3)

$V_{i}(f_{i}(x))\leqslant\lambda_{\circ}V_{i}(x)\quad$ for all $x$ and
$i$.$\diamondsuit$

######  (3.4) Assumption.

There exist a family $\\{V_{i}\\}_{i\in\mathcal{P}}$ of nonnegative measurable
functions on $\mathbb{R}^{d}$, functions
$\alpha_{1},\alpha_{2}\in\mathcal{K}$, a matrix
$[\lambda_{ij}]_{\mathrm{N}\times\mathrm{N}}$ with nonnegative entries, and
numbers $r>0$, $\mu>1$, such that (V1)-(V2) of Assumption (3.3) hold, and

  1. (V3′)

$V_{i}(f_{j}(x))\leqslant\lambda_{ij}V_{i}(x)\quad$ for all $x$ and
$i,j$.$\diamondsuit$

The condition (V1) in Assumption (3.3) is standard in deterministic system
theory literature, ensuring, in particular, positive definiteness of each
$V_{i}$. (V2) stipulates that outside $\bar{B}_{r}$ the functions
$\\{V_{i}\\}_{i\in\mathcal{P}}$ are linearly comparable to each other. The
conditions (V1) and (V3) together imply that each subsystem is globally
asymptotically stable, with sufficient stability margin—the smaller the number
$\lambda_{\circ}$, the greater is the stability margin. In fact, standard
converse Lyapunov theorems show that (V1) and (V3) are necessary and
sufficient conditions for each subsystem to be globally asymptotically stable.
The only difference between Assumptions (3.3) and (3.4) is that the latter
keeps track of how each Lyapunov function evolves along trajectories of every
subsystem.

Let us define $\displaystyle{\hat{p}\coloneqq\max_{i\in\mathrm{N}}p_{ii}}$ and
$\displaystyle{\tilde{p}\coloneqq\max_{i,j\in\mathcal{P},i\neq j}p_{ij}}$.

######  (3.5) Proposition.

Consider the system ((3.1)), and suppose that either of the following two
conditions holds:

  1. _(S1)_

Assumptions (3.2) and (3.3) hold, and
$\lambda_{\circ}(\hat{p}+\mu\tilde{p})<1$.

  2. _(S2)_

Assumptions (3.2) and (3.4) hold, and
$\textstyle{\mu\cdot\left(\max_{i\in\mathcal{P}}\sum_{j\in\mathcal{P}}p_{ij}\lambda_{ji}\right)<1}$.

Let $\tau_{r}\coloneqq\inf\bigl{\\{}t\in\mathbb{N}_{0}\big{|}\left\lVert
X_{t}\right\rVert\leqslant r\bigr{\\}}$ and $V_{i}^{\prime}(x)\coloneqq
V_{i}(x)\boldsymbol{1}_{\mathbb{R}^{d}\setminus\bar{B}_{r}}(x)$. Suppose that
$\left\lVert x_{0}\right\rVert>r$. Then there exists $\alpha>0$ such that the
process
$\bigl{(}\mathrm{e}^{\alpha(t\wedge\tau_{r})}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}(X_{t\wedge\tau_{r}})\bigr{)}_{t\in\mathbb{N}_{0}}$
is a nonnegative supermartingale.

######  (3.6) Corollary.

Consider the system ((3.1)), and assume that the hypotheses of Proposition
(3.5) hold. Then there exists a constant $c>0$ such that
$\displaystyle{\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\\!\left[\vphantom{\big{|}}\alpha_{1}(\left\lVert
X_{t}\right\rVert)\vphantom{\big{|}}\right]<c}$.

It is possible to derive simple conditions for stability of the system ((3.1))
from Proposition (3.5). To this end we briefly recall two standard stability
concepts.

######  (3.7) Definition.

If $\ker(f_{i}-\mathrm{id})=\\{0\\}$ for each $i\in\mathcal{P}$, the system
((3.1)) is said to be

  * $\circ$

_globally asymptotically stable almost surely_ if

    1. (AS1)

$\displaystyle{\mathsf{P}\Bigl{(}\forall\,\varepsilon>0\;\;\exists\,\delta>0\text{
s.t.\ }\sup_{t\in\mathbb{N}_{0}}\left\lVert
X_{t}\right\rVert<\varepsilon\text{ whenever }\left\lVert
x_{0}\right\rVert<\delta\Bigr{)}=1}$,

    2. (AS2)

$\displaystyle{\mathsf{P}\Bigl{(}\forall\,r,\varepsilon^{\prime}>0\;\;\exists\,T>0\text{
s.t.\ }\sup_{\mathbb{N}_{0}\ni t>T}\left\lVert
X_{t}\right\rVert<\varepsilon^{\prime}\text{ whenever }\left\lVert
x_{0}\right\rVert<r\Bigr{)}=1}$;

  * $\circ$

_$\alpha$ -stable in $\boldsymbol{L}_{1}$_ for some $\alpha\in\mathcal{K}$ if

    1. (SM1)

$\displaystyle{\forall\,\varepsilon>0\;\;\exists\,\delta>0\text{ s.t.\
}\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\\!\left[\vphantom{\big{|}}\alpha(\left\lVert
X_{t}\right\rVert)\vphantom{\big{|}}\right]<\varepsilon\text{ whenever
}\left\lVert x_{0}\right\rVert<\delta}$,

    2. (SM2)

$\displaystyle{\forall\,r,\varepsilon^{\prime}>0\;\;\exists\,T>0\text{ s.t.\
}\sup_{\mathbb{N}_{0}\ni
t>T}\mathsf{E}\\!\left[\vphantom{\big{|}}\alpha(\left\lVert
X_{t}\right\rVert)\vphantom{\big{|}}\right]<\varepsilon^{\prime}\text{
whenever }\left\lVert x_{0}\right\rVert<r}$.$\Diamond$

######  (3.8) Corollary.

Suppose that $\ker(f_{i}-\mathrm{id})=\\{0\\}$ for each $i\in\mathcal{P}$, and
that either of the hypotheses _(S1)_ and _(S2)_ of Proposition (3.5) holds
with $r=0$. Then

  * $\circ$

there exists $\alpha>0$ such that
$\lim_{t\to\infty}\mathsf{E}\bigl{[}\mathrm{e}^{\alpha
t}V_{\sigma_{t}}(X_{t})\bigr{]}=0$, and

  * $\circ$

the system ((3.1)) is globally asymptotically stable almost surely and
$\alpha_{1}$-stable in $\boldsymbol{L}_{1}$ in the sense of Definition (3.7).

The proofs of Proposition (3.5), Corollary (3.6) and Corollary (3.8) are given
after the following simple Lemma; the crude estimate asserted in it resembles
the distribution of a Binomial random variable, except that we have
$\hat{p}+\tilde{p}\geqslant 1$. For $t\in\mathbb{N}$ let the random variable
$N_{t}$ denote the number of times the state of the Markov chain changes on
the period of length $t$ starting from $0$, i.e.,
$N_{t}\coloneqq\sum_{i=1}^{t}\boldsymbol{1}_{\\{\sigma_{i-1}\neq\sigma_{i}\\}}$.

######  (3.9) Lemma.

Under Assumption (3.2) we have for $s<t$, $s,t\in\mathbb{N}_{0}$,

$\mathsf{P}\bigl{(}N_{t}-N_{s}=k\big{|}\sigma_{s}\bigr{)}\leqslant\begin{cases}\displaystyle{\left(\binom{t-s}{k}\hat{p}^{(t-s-k)}\tilde{p}^{k}\right)\wedge
1}\quad&\text{if $k=0,1,\ldots,t-s$},\\\ 0&\text{else}.\end{cases}$

###### Proof.

Fix $s<t$, $s,t\in\mathbb{N}_{0}$, and let
$\eta_{k}(s,t)\coloneqq\mathsf{P}\bigl{(}N_{t}-N_{s}=k\big{|}\sigma_{s}\bigr{)}$.
Then by the Markov property, for $k=0,1,\ldots,t-s$,

$\displaystyle\eta_{k}(s,t)$
$\displaystyle=\eta_{k}(s,t-1)\mathsf{P}\bigl{(}N_{t}-N_{s}=k\big{|}N_{t-1}-N_{s}=k,\sigma_{s}\bigr{)}$
$\displaystyle\qquad+\eta_{k-1}(s,t-1)\mathsf{P}\bigl{(}N_{t}-N_{s}=k\big{|}N_{t-1}-N_{s}=k-1,\sigma_{s}\bigr{)}$
$\displaystyle\leqslant\hat{p}\eta_{k}(s,t-1)+\tilde{p}\eta_{k-1}(s,t-1).$

The set of initial conditions $\eta_{i}(s,t)=0$ for all $i\geqslant t-s$,
follow from the trivial observation that there cannot be more than $t-s$
changes of $\sigma$ on a period of length $t-s$. This gives a well-defined set
of recursive equations, and a standard induction argument shows that
$\eta_{k}(s,t)\leqslant\binom{t-s}{k}\hat{p}^{(t-s-k)}\tilde{p}^{k}$. This
proves the assertion. ∎

###### Proof of Proposition (3.5).

First we look at the assertion under the condition (S1). Fix $s<t$,
$s,t\in\mathbb{N}_{0}$. Given
$(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})$, from (V3) we get
$V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{(s+1)\wedge\tau_{r}}\bigr{)}\leqslant\lambda_{\circ}V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}$,
and if $\sigma_{s+1}\neq\sigma_{s}$, we employ (V2) to get
$V^{\prime}_{\sigma_{(s+1)\wedge\tau_{r}}}\bigl{(}X_{(s+1)\wedge\tau_{r}}\bigr{)}\leqslant\mu
V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{(s+1)\wedge\tau_{r}}\bigr{)}$.
Therefore,

$\displaystyle
V^{\prime}_{\sigma_{(s+1)\wedge\tau_{r}}}\bigl{(}X_{(s+1)\wedge\tau_{r}}\bigr{)}\leqslant\mu\lambda_{\circ}V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}$
$\displaystyle\text{if
}\sigma_{(s+1)\wedge\tau_{r}}\neq\sigma_{s\wedge\tau_{r}},\quad\text{and}$
$\displaystyle
V^{\prime}_{\sigma_{(s+1)\wedge\tau_{r}}}\bigl{(}X_{(s+1)\wedge\tau_{r}}\bigr{)}\leqslant\lambda_{\circ}V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}$
$\displaystyle\text{otherwise}.$

Iterating this procedure we arrive at the pathwise inequality

((3.10))
$V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\leqslant\mu^{N_{t\wedge\tau_{r}}-N_{s\wedge\tau_{r}}}\lambda_{\circ}^{t\wedge\tau_{r}-s\wedge\tau_{r}}V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}.$

Since $s\wedge\tau_{r}=t\wedge s\wedge\tau_{r}$, and $t\wedge\tau_{r}$ is
measurable with respect to $\mathfrak{F}_{t\wedge s\wedge\tau_{r}}$, we invoke
the Markov property of $(\sigma_{t},X_{t})_{t\in\mathbb{N}_{0}}$to arrive at

$\displaystyle\mathsf{E}\Bigl{[}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}$
$\displaystyle\Big{|}(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})\Bigr{]}$
$\displaystyle\leqslant
V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}\lambda_{\circ}^{t\wedge\tau_{r}-s\wedge\tau_{r}}\mathsf{E}\Bigl{[}\mu^{N_{t\wedge\tau_{r}}-N_{s\wedge\tau_{r}}}\Big{|}(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})\Bigr{]}.$

We now apply the estimate in Lemma (3.9) to get
$\mathsf{E}\Bigl{[}\mu^{N_{t\wedge\tau_{r}}-N_{s\wedge\tau_{r}}}\Big{|}(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})\Bigr{]}\leqslant\sum_{k=0}^{t\wedge\tau_{r}-s\wedge\tau_{r}}\binom{t\wedge\tau_{r}-s\wedge\tau_{r}}{k}\hat{p}^{(t\wedge\tau_{r}-s\wedge\tau_{r}-k)}\tilde{p}^{k}\mu^{k}=\bigl{(}\hat{p}+\mu\tilde{p}\bigr{)}^{t\wedge\tau_{r}-s\wedge\tau_{r}}$,
and this leads to

$\mathsf{E}\Bigl{[}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\Big{|}(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})\Bigr{]}\leqslant
V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}\bigl{(}\lambda_{\circ}(\hat{p}+\mu\tilde{p})\bigr{)}^{t\wedge\tau_{r}-s\wedge\tau_{r}}.$

Since $\lambda_{\circ}(\hat{p}+\mu\tilde{p})<1$, letting
$\alpha^{\prime}\coloneqq\lambda_{\circ}(\hat{p}+\mu\tilde{p})\mathrm{e}^{\alpha}<1$,
the above inequality gives

((3.11))
$\displaystyle\mathsf{E}\Bigl{[}\mathrm{e}^{\alpha(t\wedge\tau_{r}-s\wedge\tau_{r})}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}$
$\displaystyle\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\Big{|}(\sigma_{s\wedge\tau_{r}},X_{s\wedge\tau_{r}})\Bigr{]}$
$\displaystyle\leqslant
V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}(\alpha^{\prime})^{t\wedge\tau_{r}-s\wedge\tau_{r}}\leqslant
V^{\prime}_{\sigma_{s\wedge\tau_{r}}}\bigl{(}X_{s\wedge\tau_{r}}\bigr{)}.$

This shows that
$\bigl{(}\mathrm{e}^{\alpha(t\wedge\tau_{r})}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\bigr{)}_{t\in\mathbb{N}_{0}}$
is a nonnegative supermartingale.

Let us now look at the assertion of the Proposition under the condition (S2).
Fix $t\in\mathbb{N}_{0}$. Then from (V3′),
$V^{\prime}_{j}\bigl{(}f_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\bigr{)}\leqslant\lambda_{j\sigma_{t\wedge\tau_{r}}}V^{\prime}_{j}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}$
for all $j\in\mathcal{P}$, and by (V2),
$V^{\prime}_{\sigma_{(t+1)\wedge\tau_{r}}}\bigl{(}f_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\bigr{)}\leqslant\lambda_{\sigma_{(t+1)\wedge\tau_{r}}\sigma_{t\wedge\tau_{r}}}V^{\prime}_{\sigma_{(t+1)\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\leqslant\mu\lambda_{\sigma_{(t+1)\wedge\tau_{r}}\sigma_{t\wedge\tau_{r}}}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}$.
This leads to

$\displaystyle\mathsf{E}\Bigl{[}V^{\prime}_{\sigma_{(t+1)\wedge\tau_{r}}}\bigl{(}X_{(t+1)\wedge\tau_{r}}\bigr{)}\Big{|}(\sigma_{t\wedge\tau_{r}},X_{t\wedge\tau_{r}})\Bigr{]}$
$\displaystyle\leqslant\mu\Biggl{(}\max_{i\in\mathcal{P}}\sum_{j\in\mathcal{P}}p_{ij}\lambda_{ji}\Biggr{)}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}.$

Since by hypothesis there exists $\alpha>0$ such that
$\mu\left(\max_{i\in\mathcal{P}}\sum_{j\in\mathcal{P}}p_{ij}\lambda_{ji}\right)\mathrm{e}^{\alpha}<1$,
the last inequality shows immediately that
$\bigl{(}\mathrm{e}^{\alpha(t\wedge\tau_{r})}V^{\prime}_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\bigr{)}_{t\in\mathbb{N}_{0}}$
is a supermartingale. This concludes the proof. ∎

###### Proof of Corollary (3.6).

First observe that since each map $f_{i}$ is locally Lipschitz, the diameter
of the set $D_{i}\coloneqq\bigl{\\{}f_{i}(x)\big{|}x\in\bar{B}_{r}\bigr{\\}}$
is finite, and since $\mathcal{P}$ is finite, so is the diameter of
$\bigcup_{i\in\mathcal{P}}D_{i}$. Therefore, if $Q$ is the transition kernel
of the Markov process $(\sigma_{t},X_{t})_{t\in\mathbb{N}_{0}}$, then
employing (V1) and the fact that $f_{i}$ is locally Lipschitz for each $i$, we
arrive at

$\displaystyle\mathsf{E}\Bigl{[}V_{\sigma_{1}}(X_{1})$
$\displaystyle\boldsymbol{1}_{\\{X_{1}\in\mathbb{R}^{d}\setminus\bar{B}_{r}\\}}\Big{|}(\sigma_{0},X_{0})=(i,x_{0})\Bigr{]}=\sum_{j\in\mathcal{P}}p_{ij}\boldsymbol{1}_{\mathbb{R}^{d}\setminus\bar{B}_{r}}(f_{j}(x_{0}))V_{j}(f_{j}(x_{0}))$
$\displaystyle\leqslant\sum_{j\in\mathcal{P}}p_{ij}\boldsymbol{1}_{\mathbb{R}^{d}\setminus\bar{B}_{r}}(f_{j}(x_{0}))\alpha_{2}(\left\lVert
f_{j}(x_{0})\right\rVert)\leqslant\sum_{j\in\mathcal{P}}p_{ij}L\left\lVert
x_{0}\right\rVert<Lr<\infty$

for $\left\lVert x_{0}\right\rVert<r$, where $L$ is such that
$\sup_{j\in\mathcal{P},y\in\bar{B}_{r}}\left\lVert
f_{j}(y)\right\rVert\leqslant L\left\lVert y\right\rVert$. This shows that
condition (2.3) of Theorem (2.2) holds under our hypotheses, and by
Proposition (3.5) we know that there exists $\alpha>0$ such that
$\Bigl{(}\mathrm{e}^{\alpha(t\wedge\tau_{r})}V_{\sigma_{t\wedge\tau_{r}}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\boldsymbol{1}_{\mathbb{R}^{d}\setminus\bar{B}_{r}}\bigl{(}X_{t\wedge\tau_{r}}\bigr{)}\Bigr{)}_{t\in\mathbb{N}_{0}}$
is a supermartingale. Theorem (2.2) now guarantees the existence of a constant
$C^{\prime}>0$ such that
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\\!\left[\vphantom{\big{|}}V_{\sigma_{t}}(X_{t})\boldsymbol{1}_{\mathbb{R}^{d}\setminus\bar{B}_{r}}(X_{t})\vphantom{\big{|}}\right]\leqslant
C^{\prime}$, and finally, from (V1) it follows that there exists a constant
$c>0$ such that
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\\!\left[\vphantom{\big{|}}\alpha_{1}(\left\lVert
X_{t}\right\rVert)\vphantom{\big{|}}\right]\leqslant c<\infty$, as asserted. ∎

###### Proof of Corollary (3.8).

We prove almost sure global asymptotic stability and $\alpha_{1}$ stability in
$\boldsymbol{L}_{1}$ of ((3.1)) under the condition (S1) of Proposition (3.5);
the proofs under (S2) are similar.

First observe that since $\ker(f_{i}-\mathrm{id})=\\{0\\}$ for each
$i\in\mathcal{P}$, i.e., $0$ is the equilibrium point of each individual
subsystem, $\mathsf{P}_{x_{0}}\bigl{(}\tau_{\\{0\\}}<\infty\bigr{)}=0$ for
$x_{0}\neq 0$, where $\tau_{\\{0\\}}$ is the first time that the process
$(X_{t})_{t\in\mathbb{N}_{0}}$ hits $\\{0\\}$. Indeed, since
$\ker(f_{i}-\mathrm{id})=\\{0\\}$ for each $i\in\mathcal{P}$ and $x_{0}\neq 0$
we have
$Q\bigl{(}(i,x_{0}),\mathcal{P}\times\\{0\\}\bigr{)}=\sum_{j\in\mathcal{P}}p_{ij}\boldsymbol{1}_{\\{0\\}}(f_{j}(x_{0}))=0$,
which shows that $Q^{n}\bigl{(}(i,x_{0}),\mathcal{P}\times\\{0\\}\bigr{)}=0$
whenever $x_{0}\neq 0$. The observation now follows from
$\mathsf{P}_{x_{0}}\bigl{(}\tau_{\\{0\\}}<\infty\bigr{)}=\mathsf{P}_{x_{0}}\bigl{(}\bigcup_{n\in\mathbb{N}}\bigl{\\{}\tau_{\\{0\\}}=n\bigr{\\}}\bigr{)}\leqslant\sum_{n\in\mathbb{N}}\mathsf{P}_{x_{0}}\bigl{(}\tau_{\\{0\\}}=n\bigr{)}$.
Therefore, with $\tau_{\\{0\\}}=\tau_{r}=\infty$, proceeding as in the proof
of Proposition (3.5) above, one can show that $\bigl{(}\mathrm{e}^{\alpha
t}V_{\sigma_{t}}\bigl{(}X_{t}\bigr{)}\bigr{)}_{t\in\mathbb{N}_{0}}$ is a
supermartingale for some $\alpha>0$. In particular, With $s=0$ and
$\tau_{r}=\infty$ in ((3.11)), we apply (V1) to arrive at
$\lim_{t\to\infty}\mathsf{E}\bigl{[}\mathrm{e}^{\alpha
t}V_{\sigma_{t}}\bigl{(}X_{t}\bigr{)}\bigr{]}=\lim_{t\to\infty}\mathsf{E}\Bigl{[}\mathsf{E}\bigl{[}\mathrm{e}^{\alpha
t}V_{\sigma_{t}}\bigl{(}X_{t}\bigr{)}\big{|}(\sigma_{0},x_{0})\bigr{]}\Bigr{]}\leqslant\lim_{t\to\infty}\alpha_{2}(\left\lVert
x_{0}\right\rVert)(\alpha^{\prime})^{t}=0$. Standard supermartingale
convergence results and the definition of $\tau_{\\{0\\}}$ imply that
$\mathsf{P}\Bigl{(}\lim_{t\to\infty}V_{\sigma_{t}}(X_{t})=0\Bigr{)}=1$. With
$s=0$ and $\tau_{r}=\tau_{\\{0\\}}=\infty$, the pathwise inequality ((3.10))
in conjunction with (V1) give
$V_{\sigma_{t}}(X_{t})\leqslant\alpha_{2}(\left\lVert
x_{0}\right\rVert)\mu^{N_{t}}\lambda_{\circ}^{t}$. The foregoing inequality
implies that for almost every sample path
$(\sigma_{t},X_{t}^{\prime})_{t\in\mathbb{N}_{0}}$ corresponding to initial
condition $X_{0}=x_{0}^{\prime}$ with $\left\lVert
x_{0}^{\prime}\right\rVert<\left\lVert x_{0}\right\rVert$, one has

$\lim_{t\to\infty}V_{\sigma_{t}}(X_{t}^{\prime})\leqslant\lim_{t\to\infty}\alpha_{2}(\left\lVert
x_{0}^{\prime}\right\rVert)\mu^{N_{t}}\lambda_{\circ}^{t}\leqslant\lim_{t\to\infty}\alpha_{2}(\left\lVert
x_{0}\right\rVert)\mu^{N_{t}}\lambda_{\circ}^{t}=0,$

which proves (AS2). Since the family $\\{f_{i}\\}_{i\in\mathcal{P}}$ is
finite, and each $f_{i}$ is locally Lipschitz, there exists $L>0$ such that
$\sup_{i\in\mathcal{P}}\left\lVert f_{i}(x)\right\rVert\leqslant L\left\lVert
x\right\rVert$ whenever $\left\lVert x\right\rVert\leqslant 1$. Fix
$\varepsilon>0$. By (AS2) we know that for almost all sample paths there
exists a constant $T>0$ such that $\sup_{t\geqslant T}\left\lVert
X_{t}\right\rVert<\varepsilon$ whenever $\left\lVert x_{0}\right\rVert<1$.
Then the choice of $\delta=\bigl{(}\varepsilon L^{-T}\bigr{)}\wedge 1$
immediately gives us the (AS1) property.

It remains to verify (SM1) and (SM2). Both the properties follow from ((3.11))
in the proof of Proposition (3.5), with $s=0$ and $\tau_{r}=\tau_{\\{0\\}}=0$.
Indeed, with these values of $s$ and $\tau_{r}$, ((3.11)) becomes

$\displaystyle\mathsf{E}\bigl{[}\mathrm{e}^{\alpha t}\alpha_{1}(\left\lVert
X_{t}\right\rVert)\bigr{|}(\sigma_{0},X_{0})\bigr{]}$
$\displaystyle\leqslant\mathsf{E}\bigl{[}\mathrm{e}^{\alpha
t}V_{\sigma_{t}}(X_{t})\bigr{|}(\sigma_{0},X_{0})\bigr{]}\leqslant
V_{\sigma_{0}}(X_{0})(\alpha^{\prime})^{t}\leqslant\alpha_{2}(\left\lVert
x_{0}\right\rVert)(\alpha^{\prime})^{t}$

in view of (V1), where
$\alpha^{\prime}=\lambda_{\circ}(\hat{p}+\mu\tilde{p})\mathrm{e}^{\alpha}<1$.
Therefore, given $\varepsilon>0$, we simply choose
$\delta<\alpha_{2}^{-1}(\varepsilon)$ to get (SM1). Given
$r,\varepsilon^{\prime}>0$, we simply choose
$T=0\vee\bigl{(}\ln(\alpha_{2}(r)/\varepsilon^{\prime})/\ln(\alpha^{\prime})\bigr{)}$
to get (SM2). This completes the proof. ∎

###  3.2. Robust Stability of Discrete-Time Randomly Switched Systems

Conditions for the existence of the supermartingale
$\bigl{(}\mathrm{e}^{\alpha(t\wedge\tau_{K}^{\vphantom{T}})}V\bigl{(}X_{t\wedge\tau_{K}^{\vphantom{T}}}\bigr{)}\bigr{)}_{t\in\mathbb{N}_{0}}$
in §2 can be easily expressed in terms of the transition kernel $Q$. However,
if $Q$ is not known exactly, which may happen if the model of the underlying
system generating the Markov process $(X_{t})_{t\in\mathbb{N}_{0}}$ is
uncertain, one needs different methods. We look at one such instance below.

Consider the system

((3.12)) $X_{t+1}=f_{\sigma_{t}}(X_{t},w_{t}),\qquad X_{0}=x_{0},\quad
t\in\mathbb{N}_{0},$

where we retain the definition $\sigma$ from §3.1,
$f_{i}:\mathbb{R}^{d}\times\mathbb{R}^{m}\longrightarrow\mathbb{R}^{d}$ is
locally Lipschitz continuous in both arguments with $f_{i}(0,0)=0$ for each
$i\in\mathcal{P}$, and $(w_{t})_{t\in\mathbb{N}_{0}}$ is a bounded and
measurable $\mathbb{R}^{m}$-valued disturbance sequence. We do not model
$(w_{t})_{t\in\mathbb{N}_{0}}$ as a random process; as such, the transition
kernel of ((3.12)) is not unique.

######  (3.13) Definition.

The system ((3.12)) is said to be _input-to-state stable in
$\boldsymbol{L}_{1}$_ if there exist functions
$\chi,\chi^{\prime}\in\mathcal{K}_{\infty}$ and $\psi\in\mathcal{KL}$ such
that $\mathsf{E}_{x_{0}}\bigl{[}\chi(\left\lVert
X_{t}\right\rVert)\bigr{]}\leqslant\psi(\left\lVert
x_{0}\right\rVert,t)+\sup_{s\in\mathbb{N}_{0}}\chi^{\prime}(\left\lVert
w_{s}\right\rVert)$ for all $t\in\mathbb{N}_{0}$.$\Diamond$

Our motivation for this definition comes from the concept of input-to-state
stability iss in the deterministic context [JW01]. Consider the $i$-th
subsystem of ((3.12)) $x_{t+1}=f_{i}(x_{t},w_{t})$ for $t\in\mathbb{N}_{0}$
with initial condition $x_{0}$; note that $(x_{t})_{t\in\mathbb{N}_{0}}$ is a
deterministic sequence. This nonlinear discrete-time system is said to be iss
if there exist functions $\psi\in\mathcal{KL}$ and
$\chi\in\mathcal{K}_{\infty}$ such that $\left\lVert
x_{t}\right\rVert\leqslant\psi(\left\lVert
x_{0}\right\rVert,t)+\sup_{s\in\mathbb{N}_{0}}\chi(\left\lVert
w_{s}\right\rVert)$ for $t\in\mathbb{N}_{0}$. A sufficient set of conditions
(cf. [JW01, Lemma 3.5]) for iss of this system is that there exist a
continuous function $V:\mathbb{R}^{d}\longrightarrow\mathbb{R}_{\geqslant 0}$,
$\alpha_{1},\alpha_{2}\in\mathcal{K}_{\infty}$, $\rho\in\mathcal{K}$, and a
constant $\lambda\in\;]0,1[$, such that $\alpha_{1}(\left\lVert
x\right\rVert)\leqslant V(x)\leqslant\alpha_{2}(\left\lVert x\right\rVert)$
for all $x\in\mathbb{R}^{d}$, and $V(f_{i}(x,w))\leqslant\lambda V(x)$
whenever $\left\lVert x\right\rVert>\rho(\left\lVert w\right\rVert)$.

In this framework we have the following Proposition.

######  (3.14) Proposition.

Consider the system ((3.12)), and suppose that

  1. (i)

Assumption (3.2) holds,

  2. (ii)

there exist continuous functions
$V_{i}:\mathbb{R}^{d}\longrightarrow\mathbb{R}_{\geqslant 0}$ for
$i\in\mathcal{P}$, $\alpha_{1},\alpha_{2},\rho\in\mathcal{K}_{\infty}$, a
constant $\mu>1$ and a matrix $[\lambda_{ij}]_{\mathrm{N}\times\mathrm{N}}$ of
nonnegative entries, such that

    1. (a)

$\alpha_{1}(\left\lVert x\right\rVert)\leqslant
V_{i}(x)\leqslant\alpha_{2}(\left\lVert x\right\rVert)\qquad$ for all $x$ and
$i$,

    2. (b)

$V_{i}(x)\leqslant\mu V_{j}(x)\qquad$ for all $x$ and $i,j$, and

    3. (c)

$V_{i}(f_{j}(x))\leqslant\lambda_{ij}V_{i}(x)\qquad$ whenever $\left\lVert
x\right\rVert>\rho(\left\lVert w\right\rVert)$ and all $i,j$,

  3. (iii)

$\mu\Bigl{(}\max_{i\in\mathcal{P}}\sum_{j\in\mathcal{P}}p_{ij}\lambda_{ji}\Bigr{)}<1$.

Then ((3.12)) is input-to-state stable in $\boldsymbol{L}_{1}$ in the sense of
Definition (3.13).

###### Proof.

We define the compact set
$K\coloneqq\bigl{\\{}(i,y)\in\mathcal{P}\times\mathbb{R}^{d}\big{|}\left\lVert
y\right\rVert\leqslant\sup_{s\in\mathbb{N}_{0}}\rho(\left\lVert
w_{s}\right\rVert)\bigr{\\}}$, and let
$\tau_{K}^{\vphantom{T}}\coloneqq\inf\bigl{\\{}t\in\mathbb{N}_{0}\big{|}X_{t}\in
K\bigr{\\}}$. In this setting we know from the preceding analysis that
$\varphi(t,\xi)=\mathrm{e}^{\alpha t}\xi$, $\theta(t)=\mathrm{e}^{-\alpha t}$,
and $C=1/(1-\mathrm{e}^{-\alpha})$. We see from the estimate ((2.8)) in the
proof of Theorem (2.2) that

$\displaystyle\mathsf{E}_{x_{0}}\bigl{[}V_{\sigma_{t}}(X_{t})\bigr{]}$
$\displaystyle\leqslant\varphi(0,V_{\sigma_{0}}(x_{0}))\theta(t)+\frac{\beta}{1-\mathrm{e}^{-\alpha}}+\delta\leqslant\alpha_{2}(\left\lVert
x_{0}\right\rVert)\mathrm{e}^{-\alpha
t}+\frac{\beta}{1-\mathrm{e}^{-\alpha}}+\delta.$

Standard arguments show that there exists some
$\chi^{\prime\prime}\in\mathcal{K}_{\infty}$ such that $\beta$ and $\delta$
are each dominated by
$\chi^{\prime\prime}\bigl{(}\sup_{s\in\mathbb{N}_{0}}\left\lVert
w_{s}\right\rVert\bigr{)}$, and therefore, there exists some
$\chi^{\prime}\in\mathcal{K}_{\infty}$ such that
$\beta/(1-\mathrm{e}^{-\alpha})+\delta$ is dominated by
$\chi^{\prime}\bigl{(}\sup_{s\in\mathbb{N}_{0}}\left\lVert
w_{s}\right\rVert\bigr{)}$. Applying (ii)(a) on the left-hand side of the last
inequality, we conclude that ((3.12)) is input-to-state stable with
$\chi=\alpha_{1}$ and $\psi(r,t)=\alpha_{2}(r)\mathrm{e}^{-\alpha t}$. ∎

## Acknowledgments

The authors thank Daniel Liberzon and John Lygeros for helpful comments,
Andreas Milias-Argeitis for useful discussions related to the chemical master
equation, and the anonymous reviewer for a thorough review of the manuscript,
several helpful comments, and drawing their attention to [MT09, Chapter 14].

## References

  * [ACK08] D. F. Anderson, G. Craciun, and T. G. Kurtz, _Product-form stationary distributions for deficiency zero chemical reaction networks_ , http://arxiv.org/abs/0803.3042, 2008.
  * [BDEG88] M. F. Barnsley, S. G. Demko, J. H. Elton, and J. S. Geronimo, _Invariant measures for Markov processes arising from iterated function systems with place-dependent probabilities_ , Annales de l’Institut Henri Poincaré. Probabilités et Statistique 24 (1988), no. 3, 367–394, Erratum in ibid., 24 (1989), no. 4, 589–590.
  * [BS78] D. P. Bertsekas and S. E. Shreve, _Stochastic Optimal Control: the Discrete-Time Case_ , Mathematics in Science and Engineering, vol. 139, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1978.
  * [Bor91] V. S. Borkar, _Topics in Controlled Markov Chains_ , Pitman Research Notes in Mathematics Series, vol. 240, Longman Scientific & Technical, Harlow, 1991.
  * [BKR+01] A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. P. Williamson, _Adversarial queuing theory_ , Journal of the ACM 48 (2001), no. 1, 13–38.
  * [CCCL08] D. Chatterjee, E. Cinquemani, G. Chaloulos, and J. Lygeros, _Stochastic control up to a hitting time: optimality and rolling-horizon implementation_ , http://arxiv.org/abs/0806.3008, 2008.
  * [CHL09] D. Chatterjee, P. Hokayem, and J. Lygeros, _Stochastic receding horizon control with bounded control inputs: a vector space approach_ , http://arxiv.org/abs/0903.5444, 2009.
  * [CRS71] Y. S. Chow, H. Robbins, and D. Siegmund _Great Expectations: The Theory of Optimal Stopping_ , Houghton Mifflin Company Boston, 1971.
  * [CFM05] O. L. V. Costa, M. D. Fragoso, and R. P. Marques, _Discrete-time Markov Jump Linear Systems_ , Probability and its Applications (New York), Springer-Verlag, London, 2005.
  * [DF99] P. Diaconis and D. Freedman, _Iterated random functions_ , SIAM Review 41 (1999), no. 1, 45–76 (electronic).
  * [DFMS04] R. Douc, G. Fort, E. Moulines, and P. Soulier, _Practical drift conditions for subgeometric rates of convergence_ , The Annals of Applied Probability 14 (2004), no. 3, 1353–1377.
  * [FK04] S. Foss and T. Konstantopoulos, _An overview of some stochastic stability methods_ , Journal of Operations Research Society of Japan 47 (2004), no. 4, 275–303.
  * [HLR96] J. Håstad, T. Leighton, and B. Rogoff, _Analysis of backoff protocols for multiple access channels_ , SIAM Journal on Computing 25 (1996), no. 4, 740–774.
  * [HLL96] O. Hernández-Lerma and J. B. Lasserre, _Discrete-Time Markov Control Processes: Basic Optimality Criteria_ , Applications of Mathematics, vol. 30, Springer-Verlag, New York, 1996\.
  * [HLL99] by same author, _Further Topics on Discrete-Time Markov Control Processes_ , Applications of Mathematics, vol. 42, Springer-Verlag, New York, 1999.
  * [Hob98] D. G. Hobson, _Volatility misspecification, option pricing and superreplication via coupling_ , The Annals of Applied Probability 8 (1998) no. 1, 193–205.
  * [JH07] T. Jahnke and W. Huisinga, _Solving the chemical master equation for monomolecular reaction systems analytically_ , Journal of Mathematical Biology 54 (2007), no. 1, 1–26.
  * [JT01] S. F. Jarner and R. L. Tweedie, _Locally contracting iterated functions and stability of Markov chains_ , Journal of Applied Probability 38 (2001), no. 2, 494–507.
  * [JW01] Z-P. Jiang and Y. Wang, _Input-to-state stability for discrete-time nonlinear systems_ , Automatica 37 (2001), no. 6, 857–869.
  * [KS08] I. Karatzas and S. Shreve, _Brownian Motion and Stochastic Calculus_ , 2 ed., Graduate Texts in mathematics, Springer, 2008.
  * [Kif86] Y. Kifer, _Ergodic Theory of Random Transformations_ , Progress in Probability and Statistics, vol. 10, Birkhäuser Boston Inc., Boston, MA, 1986\.
  * [Lib03] D. Liberzon, _Switching in Systems and Control_ , Systems & Control: Foundations & Applications, Birkhäuser, Boston, 2003.
  * [LM94] A. Lasota and M. C. Mackey, _Chaos, Fractals, and Noise_ , 2 ed., Applied Mathematical Sciences, vol. 97, Springer-Verlag, New York, 1994.
  * [LM02] A. Lasota and J. Myjak, _On a dimension of measures_ , Polish Academy of Sciences. Bulletin. Mathematics 50 (2002), no. 2, 221–235.
  * [LS04] A. Lasota and T. Szarek, _Dimension of measures invariant with respect to the Ważewska partial differential equation_ , Journal of Differential Equations 196 (2004), no. 2, 448–465.
  * [Mac01] J. M. Maciejowski, _Predictive Control with Constraints_ , Prentice Hall, 2001\.
  * [Mey08] S. P. Meyn, _Control Techniques for Complex Networks_ , Cambridge University Press, Cambridge, 2008.
  * [MT09] S. P. Meyn and R. L. Tweedie, _Markov Chains and Stochastic Stability_ , 2nd Ed., Cambridge University Press, Cambridge, UK, 2009.
  * [MA08] A. Milias-Argeitis, _Fast simulation of the chemical master equation with iterated function systems_ , In preparation, 2008.
  * [PR99] R. Pemantle and J. S. Rosenthal, _Moment conditions for a sequence with negative drift to be uniformly bounded in $L^{r}$_, Stochastic Processes and their Applications 82 (1999), no. 1, 143–155.
  * [PS06] G. Peskir and A. N. Shiryaev, _Optimal Stopping and Free-Boundary Problems_ , Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2006.
  * [RY99] D. Revuz and M. Yor, _Continuous Martingales and Brownian Motion_ , 3 ed., Grundlehren der Mathematischen Wissenschaften, vol. 293, Springer-Verlag, Berlin, 1999.
  * [Sza06] T. Szarek, _Feller processes on nonlocally compact spaces_ , The Annals of Probability 34 (2006), no. 5, 1849–1863.
  * [vS00] A. van der Schaft and H. Schumacher, _An Introduction to Hybrid Dynamical Systems_ , Lecture Notes in Control and Information Sciences, vol. 251, Springer-Verlag London Ltd., London, 2000.
  * [Wer05] I. Werner, _Contractive Markov systems_ , Journal of the London Mathematical Society. Second Series 71 (2005), no. 1, 236–258.
  * [Wil06] D. J. Wilkinson, _Stochastic Modelling for Systems Biology_ , Chapman & Hall/CRC Mathematical and Computational Biology Series, Chapman & Hall/CRC, Boca Raton, FL, 2006.