Compositional Construction of Finite State Abstractions
for Stochastic Control Systems

arXiv:1709.09546v1 [] 27 Sep 2017

Kaushik Mallik, Sadegh Esmaeil Zadeh Soudjani, Anne-Kathrin Schmuck and Rupak Majumdar
Abstract— Controller synthesis techniques for continuous systems with respect to temporal logic specifications typically use a
finite-state symbolic abstraction of the system. Constructing this
abstraction for the entire system is computationally expensive,
and does not exploit natural decompositions of many systems
into interacting components. We have recently introduced a
new relation, called (approximate) disturbance bisimulation for
compositional symbolic abstraction to help scale controller
synthesis for temporal logic to larger systems.
In this paper, we extend the results to stochastic control
systems modeled by stochastic differential equations. Given
any stochastic control system satisfying a stochastic version of
the incremental input-to-state stability property and a positive
error bound, we show how to construct a finite-state transition
system (if there exists one) which is disturbance bisimilar to the
given stochastic control system. Given a network of stochastic
control systems, we give conditions on the simultaneous existence of disturbance bisimilar abstractions to every component
allowing for compositional abstraction of the network system.

I. I NTRODUCTION
In abstraction-based controller synthesis, a finite-state
symbolic model of a continuous system is used to synthesize
a symbolic controller for a logical specification, and the
controller is then refined to a controller for the original
system. This technique has recently gained a lot of attention due to two main advantages. First, it allows for fully
automated controller synthesis for systems with continuous
dynamics while handling complex specifications (given e.g.
as ω-regular languages) in addition to stability. Second,
it naturally accounts for the complex interplay between
discrete and continuous components within a control loop.
The soundness of the abstraction-based synthesis technique
relies on notions of behavioral closeness of the original
system and its abstraction, which is formalized using system
equivalence relations (see e.g. [11], [8] and the references
therein). Recently, abstraction-based controller synthesis has
been extended to stochastic control systems [12], [2]. In the
stochastic setting, behavioral closeness of the original system
and its abstraction is formalized using the n-th moment of
the trajectories.
Despite its nice theoretical properties and applicability
to many different system classes, abstraction based controller synthesis does not scale very well because both
the abstraction step and the controller synthesis step are
exponential in the dimension of the continuous state space.
This issue motivated us to propose disturbance bisimulation
[5], an equivalence relation that exploits the intrinsic compositionality of systems. Given a network of metric systems
All authors are with MPI-SWS, Kaiserslautern, Germany {kmallik,
sadegh, akschmuck, rupak}@mpi-sws.org

and their equivalently interconnected disturbance bisimilar
abstractions, the main result of [5] shows that the overall network system is also disturbance bisimilar to the network of
the abstractions. This result has an interesting consequence:
given a construction of a disturbance bisimilar abstraction
for a given system class, we can compositionally abstract
a network of systems from this class whenever all local
abstractions are guaranteed to exist simultaneously. In [5] we
exploited this fact for large networks of incremental input-tostate stable deterministic control systems and demonstrated
the effectiveness of our approach in a case study.
In this paper, we extend these results to the class of
stochastic control systems which satisfy a stochastic version
of the incremental input-to-state stability condition. Our main
contribution in this paper is to show how a stochastic control
system, which may be connected to other components within
a network, allows for the algorithmic computation of (1) a
metric system capturing its time-sampled dynamics and (2) a
metric system capturing its abstract symbolic dynamics, such
that the two constructed systems are disturbance bisimilar.
This construction allows us to use the results from [5] to provide a compositional abstraction-based controller synthesis
technique for a given network of continuous and stochastic
dynamical systems.
Our results relate to recent results in [13] on compositional
abstraction for stochastic systems. The main difference between our work and [13] is the type of abstraction: while
we work with finite state symbolic abstractions, their abstractions are infinite state. There have been some efforts for
improving scalability of abstraction techniques for stochastic
systems in a different setting, where abstract models are
Markov chains and the goal is to match distributions on states
up to a fixed horizon. In [9], the state space discretization
is done adaptively and, in [10], the abstract state space of a
monolithic system is represented compositionally.
The paper is organized as follows. After introducing preliminaries on stochastic control systems in Sec. II, we define
metric systems in Sec. III, and present how the two particular
metric systems discussed above can be obtained from a
stochastic control system. Given these two metric systems,
we give sufficient conditions for them to be disturbance
bisimilar in Sec. IV, after recalling the notion of disturbance
bisimulation from [5]. In Sec. V, we invoke results from [5]
to extend our result from a single stochastic control system
to a network of such systems. All proofs can be found in the
appendix.

II. S TOCHASTSIC C ONTROL S YSTEMS
Most part of this section is adapted from [12] to systems
with stochastic disturbance inputs.
A. Notation
We use the symbols N, R, R>0 , R≥0 and Z to denote the
set of natural, real, positive real, non-negative real numbers,
and integers, respectively. The symbols In , 0n , and 0n×m
denote the identity matrix, the zero vector, and the zero
matrix in Rn×n , Rn , and Rn×m , respectively. Given a vector
x ∈ Rn , we denote by xi the i-th element of x and by k x k
the infinity norm of x.
A continuous function γ : R≥0 → R≥0 is said to belong
to class K if it is strictly increasing and γ(0) = 0; γ is said
to belong to class K∞ if γ ∈ K and limr→∞ γ(r) = ∞.
A continuous function β : R≥0 × R≥0 → R≥0 is said to
belong to class KL if, for each fixed s, the function
β(·, s) : R≥0 → R≥0 belongs to class K∞ and, for each
fixed r, the map β(r, ·) : R≥0 → R≥0 is decreasing and
lims→∞ β(r, s) = 0. Let f : R≥0 → Rk be a measurable function. We define the (essential) supremum k f k
of f as k f k := ess(sup){k f (t) k | t ≥ 0}. A function
f is bounded if k f k < ∞. Given a square matrix M ,
we denote by T r(M ) the trace of M , and by λmin (M )
and λmax (M ) the minimum and maximum eigenvalue of
M respectively. Given a matrix
M = {mij } ∈ Rn×m , we
Pm
denote by k M k := max1≤i≤n j=1 |mij | the infinity norm
p
of M , and by kM kF := Tr (M M T ) the Frobenius norm
of M . We denote by Diag(a1 , . . . , an ) the diagonal matrix
with diagonal entries a1 , . . . , an ∈ R. If a1 , . . . , an are
matrices, then Diag(a1 , . . . , an ) is a block diagonal matrix
of appropriate dimension.
B. Stochastic Control System
We fix the probability space for the whole paper as
(Ω, F , P), where Ω is a sample space, F is a sigma algebra
over Ω representing the set of events, and P is a probability
measure. Let (Ω, F , P) admits a filtration F = (Fs )s≥0
which is complete and right continuous [4, p. 89]. Let
(Bs )s≥0 be a r-dimensional F-Brownian motion.
Definition 2.1: A stochastic control system is a tuple Σ =
(X, U, U, W, W, f, σ), where X = Rn is the state space,
U ⊆ Rm is the input set that is assumed to be compact, U is
a subset of set of all measurable, locally essentially bounded
functions of time from R≥0 to U , W ⊆ Rp is the disturbance
input space that is assumed to be compact, W is a set of
stochastic processes with elements ν : Ω × R≥0 → W , f :
X × U × W → X is a continuous function of its arguments
representing the drift of Σ, σ : X → Rn×r is a function
representing the diffusion of Σ.
A stochastic process ξ : Ω × R≥0 → X is called a solution
process of Σ if there exists µ ∈ U and ν ∈ W satisfying the
following stochastic differential equation:

process of Σ from the initial condition ξaµν (0) = a P-a.s.,
and under effect of input signal µ ∈ U and disturbance signal
ν ∈ W. Note that given any time instant t, ξaµν (t) represents
a random variable from Ω to X measurable in Ft .
We make the following two assumptions on stochastic control systems to ensure a unique global continuous solution.
Assumption 1 (Lipschitz condition): There exist constants
Lf , Lσ ∈ R≥0 such that the following inequalities hold
kf (x, u, w)−f (x′ , u′ , w′ )k ≤ Lf (kx−x′ k+ku−u′k+kw−
w′ k), and kσ(x) − σ(x′ )k ≤ Lσ kx − x′ k, for all x, x′ ∈ X,
u, u′ ∈ U and w, w′ ∈ W .
Assumption 2 (Linear growth): There exists a positive
constant K such that for all x ∈ X, u, ∈ U and w ∈ W ,

max(kf (x, u, w)k2 , kσ(x)k2 ) ≤ K 1 + kxk2 . (II.2)
Assump. 1 on Lipschitz continuity gives uniqueness and
Assump. 2 on linear growth gives global existence ([7,
Thm. 5.2.1]). The latter will also be used in Sec. V-B
(cf. Prop. 5.3) to provide an upper bound on the second
moment of the solution process.
In this paper the disturbances in the set W are allowed to
be stochastic. This is necessary because, as will be described
later, in our setting the disturbances play the role of trajectories of other stochastic control systems after interconnection.
For the results of this paper to hold, we require the process
(ξ, ν) : Ω × R≥0 → X × W to be an Itô process, i.e., (ξ, ν)
has to be the solution of a possibly time-inhomogeneous Itô
diffusion.
C. δ-ISS-Mq
We now generalize the notion of incremental input-tostate stability in the q-the moment (δ-ISS-Mq ) for stochastic
control systems from [12] by considering disturbances. In
the absence of noise, these notions correspond to δ-ISS for
deterministic systems [1].
Definition 2.2: A stochastic control system Σ =
(X, U, U, W, W, f, σ) is stochastically incrementally inputto-state stable in the q-th moment (δ-ISS-Mq ), if there exists
a KL function β and K∞ functions ρu and ρd such that
for any t ∈ R≥0 , any µ, µ′ ∈ U, any ν, ν ′ ∈ W, and any
Rn -valued random variables a and a′ that are measurable in
F0 , the following condition is satisfied:

(II.1)


q 
q
E [kξaµν (t) − ξa′ µ′ ν ′ (t)k ] ≤ β E ka − a′ k , t

q 
+ ρu (k µ − µ′ k) + ρd E k ν − ν ′ k . (II.3)
The δ-ISS-Mq property can be characterized in terms of
the existence of stochastic incremental Lyapnuov functions.
Definition 2.3: [12, Def. 3.2] Define the diagonal set ∆ as
∆ = {(x, x) | x ∈ Rn }. Consider a stochastic control system
Σ = (X, U, U, W, W, f, σ) and a continuous function V :
X × X → R≥0 which is smooth on {Rn × Rn }\∆. Function
V is called a δ-ISS-Mq Lyapunov function for Σ if there exist
K∞ functions α, α, σu , σd , and a constant κ ∈ R>0 such
that

P-almost surely (P-a.s.). For succinctness of representation,
we use the notation ξaµν to denote a stochastic solution

(i) α is a convex function, and α and σd are concave
functions;

d ξ(t) = f (ξ(t), µ(t), ν(t)) d t + σ(ξ(t)) d Bt ,

(ii) for any x, x′ ∈ X,
α(kx − x′ kq ) ≤ V (x, x′ ) ≤ α(kx − x′ kq );
(iii) for any x, x′ ∈ X, x 6= x′ , any u, u′ ∈ U , and any
w,w′ ∈ W ,


′
′
f (x, u, w)
Lu,u ,w,w V (x, x′ ) := [∂x V ∂x′ V ]
f (x′ , u′ , w′ )




 ∂x,x V ∂x,x′ V
1
σ(x)  T
T
′
σ (x) σ (x )
+ Tr
σ(x′ )
∂x′ ,x V ∂x′ ,x′ V
2
′
′
≤ −κV (x, x ) + σu (k u − u k) + σd (k w − w′ kq ),
′

′

where Lu,u ,w,w is the infinitesimal generator ([7, Section
7.3]) associated to the stochastic control system (II.1), which
depends on two separate controls u, u′ ∈ U and two separate
disturbances w, w′ ∈ W . In this case we say that the
stochastic control system Σ admits a δ-ISS-Mq Lyapunov
function, witnessed by α, α, σu , σd , and κ ∈ R>0 .
Note that condition (i) is not required in the context of
deterministic control systems. Condition (ii) implies that the
growth rates of the functions α and α are linear, as a concave
function is supposed to dominate a convex one. These
conditions are not restrictive provided we are interested in
the dynamics of Σ on a compact subset D ⊂ Rn , which is
often the case in practice. It can be readily verified that the
δ-ISS-Mq Lyapunov function in Definition 2.3 is a stochastic
bisimulation function between Σ and itself, as defined in [3],
Def. 5.
The following theorem describes δ-ISS-Mq in terms of
the existence of δ-ISS-Mq Lyapunov functions. It generalizes
the corresponding theorem [12, Thm. 3.3] in the presence of
disturbances.
Theorem 2.4: A stochastic control system Σ is δ-ISS-Mq
if it admits a δ-ISS-Mq Lyapunov function.
In order to keep the notation simple, we present the
results only for second moment in the rest of paper with
the understanding that they can be generalized for other
moments.
The following lemma (compare [12, Lemma 3.4]) provides
a sufficient condition on a particular function V to be a δISS-Mq Lyapunov function.
Lemma 2.5: Let Σ = (X, U, U, W, W, f, σ) be a stochastic control system. Let P ∈ Rn×n be a symmetric positive
definite matrix. Consider the function V : Rn × Rn → R≥0
defined as:
V (x, x′ ) :=

1
(x − x′ )T P (x − x′ )
2

(II.4)

and satisfying
(x − x′ )T P (f (x, u, w) − f (x′ , u, w))+
(II.5)
2
1 √
P (σ(x) − σ(x′ ))
≤ −2e
κV (x, x′ ),
+
2
F
or, if f is differentiable, satisfying
(x − x′ )T P ∂x f (z, u, w)(x − x′ )+
1 √
+
P (σ(x) − σ(x′ ))
2

(II.6)
2
F

≤ −2e
κV (x, x′ ),

for all x, x′ , z ∈ X, for all u ∈ U , for all w ∈ W , and for
some constant κ
e ∈ R>0 . Then V is a δ-ISS-M2 Lyapunov
function for Σ.
D. Noisy and Noise Free Trajectories

In this section we provide an upper bound on the distance
between a stochastic state trajectory and its associated noisefree trajectory at any instant of time. This bound is a
generalization of the bound in [12, Lemma 3.10] to the case
when there is disturbance in the system. The bound will be
instrumental in proving closeness between the trajectories of
a stochastic control system and its abstraction in Sec. III.
Lemma 2.6: Consider a stochastic control system Σ =
(X, U, U, W, W, f, σ). Suppose there exists a δ-ISS-M2 Lyapunov function V of Σ s.t. its Hessian matrix in R2n×2n
satisfies 0 ≤ ∂x,x V (x, x′ ) ≤ P , for some positive semidefinite matrix P ∈ R2n×2n and for any x, x′ ∈ Rn . Define
ξ xµν as the solution of the ordinary differential equation
(ODE)

ξ˙ xµν (t) = f ξ xµν (t), µ(t), ν(t)
(II.7)

starting from the initial condition x. Then for any x in a
compact set D ⊂ Rn , any µ ∈ U and any ν ∈ W, we have
i
h
2
≤ h(σ, t),
E ξxµν (t) − ξ xµν (t)
where

1 √
h(σ, t) := α−1 k P k2 · n · min{n, r} · e−κt · L2σ ·
2
Z t


β supx∈D k x k2 , s + ρu (supu∈U k u k)
·
0
 
+ρd supw∈W k w k2 ds .
(II.8)

The non-negative valued function h tends to zero as t → 0,
t → ∞, or as Lσ → 0, where Lσ is the Lipschitz constant
introduced in Assump. 1.
Remark 2.7: Eqn. (II.8) gives a representation of the function h in terms of ρu and ρd . This representation of h can
be translated into a form using σu and σd instead, as shown
in [12, Lemma 3.10, Cor. 3.11].
III. F ROM S TOCHASTIC C ONTROL S YSTEMS
S YSTEMS

TO

M ETRIC

We now introduce (deterministic) metric systems and
interpret stochastic control systems and their abstractions as
metric systems. As in [12], [5], we consider metric systems
that are time sampled w.r.t. a globally fixed time sampling
parameter τ ∈ R>0 .
Definition 3.1: Given the probability space Ω and a time
sampling parameter τ ∈ R>0 , a stochastic metric system1
S = (X, U, Uτ , W, Wτ , δτ ) consists of a (possibly infinite)
set of states X, given by a set of random variables, and
equipped with a metric d : X×X → R≥0 , a set of piece-wise
1 Often, metric systems are defined with an additional output space and
an output map from states to the output space. We omit the output space
for notational simplicity; for us, the state and the output space coincide, and
the output map is the identity function.

constant inputs Uτ of duration τ taking values in U ⊆ Rm ,
i.e.,
Uτ = {µ : [0, τ ] → U | ∀t1 , t2 ∈ [0, τ ] . µ(t1 ) = µ(t2 )},
(III.1)
a set of disturbances Wτ taking values in W ⊆ Rp , i.e.,
Wτ ⊆ {ν : Ω × [0, τ ] → W },

(III.2)

and a transition function δτ : X × Uτ × Wτ → 2X . We write
µ,ν
x −−→ x′ if x′ ∈ δτ (x, µ, ν), and we denote the unique value
τ
of µ ∈ U over [0, τ ] by uµ ∈ U .
A deterministic metric system is a special type of a
stochastic metric system where the states are deterministic points (i.e. random variables with Dirac delta distributions), and disturbances are deterministic signals of the form
[0, τ ] → W .
If the metric system S is undisturbed, we define W =
{0}. In this case we occasionally represent S by the tuple
S = (X, U, Uτ , δτ ) and use δτ : X × Uτ → 2X with
the understanding that x′ ∈ δτ (x, µ, ν) holds for the zero
trajectory ν : R≥0 → {0} whenever x′ ∈ δτ (x, µ). By
slightly abusing notation we write x′ = δτ (x, µ, ν) as a short
form when the set δτ (x, µ, ν) = {x′ } is a singleton. If X, Uτ
and Wτ are finite (resp. countable), S is called finite (resp.
countable). We also assign to a transition x′ = δτ (x, µ, ν)
any continuous time evolution ξ : [0, τ ] → X s.t. ξ(0) = x
and ξ(τ ) = x′ .
In the following we introduce two approaches to capture
an abstracted version of the dynamics of a stochastic control
systems Σ by a metric system conforming to Def. 3.1. The
first approach results in a sampled time abstraction which
we denote by Pτ (Σ).
Definition 3.2: Given a stochastic control system Σ =
(X, U, U, W, W, f, σ), a time-sampling parameter τ ∈ R>0 ,
and a probability space (Ω, F , P), the discrete-time stochastic metric system induced by Σ is defined by Pτ (Σ) =
(Xr , U, Uτ , W, Wτ , δτ ) s.t. Xr is the set of all X-valued
random variables, Uτ and Wτ are defined over U and W ,
respectively, as in Eqn. (III.1)-(III.2) and δτ (x, µ, ν) = x′
if x and x′ are measurable in Ft and Ft+τ , respectively,
for some t ∈ R≥0 , and there exists a solution process ξ :
Ω × R≥0 → Rn of Σ satisfying ξ(0) = x and ξxµν (τ ) = x′
P-a.s. Since we allow any state to be initial, all states in X
need to be measurable on F0 . We equip Xr with the metric
1/2
d(x, x′ ) := E[k x − x′ k2 ]
.
Remark 3.3: Recall that the disturbances in the set W
are stochastic. Hence the above metric system must be
constructed by looking at the sampled version of (ξ, ν),
which is the solution process of the Itô diffusion associated
with (x, w).
The second approach additionally imposes a
quantization of the state, input and disturbance spaces
and results in a metric system denoted by Pτ ηω (Σ).
Before defining this system formally we introduce
notation for quantization. For any A ⊆ Rn and any
vector η with elements ηi > 0, we define [A]η :=
{(a1 , . . . , an ) ∈ A | ai = 2kηi , k ∈ Z, i = 1, . . . , n}.

For x ∈ Rn and vector λ with elements λi > 0, let
Bλ (x) = {x′ ∈ Rn | k xi − x′i k ≤ λi } denote the closed
rectangle centered at x. Note that for any λ ≥ η (elementwise), the collection of sets Bλ (q) with q ∈ [Rn ]η is a cover
of Rn , that is, Rn ⊆ ∪{Bλ (q) | q ∈ [Rn ]η }. We will use
this insight to discretize the state and the input space of Σ
using discretization parameters η and ω, respectively.
Also we need to define a vector-valued metric for comparing two disturbance vectors. Let A1 , . . . , Ak be a finite set
of metric spaces, where each AiQ
, i = 1, . . . , k has a metric
k
di : Ai × Ai → R≥0 . Let A = i=1 Ai . We construct the
k
metric e : A × A → R≥0 as an extension of the metrics di
on Ai : for any a = (a1 , . . . , ak ) and a′ = (a′1 , . . . , a′k ), we
define
e(a, a′ ) := (d1 (a1 , a′1 ), . . . , dk (ak , a′k )).

(III.3)

For the disturbance space W we allow the discretization
of W to be predefined. We make the following general
assumptions on the discretizaion of W which will be useful
when we deal with networks of stochastic control systems
in Sec. V.
Assumption 3: Let Σ = (X, U, U, W, W, f, σ) be a
stochastic control system. Then we assume that there exists
f ⊆ W , that exists a vector ε̃ ∈ Rp , and a
a countable set W
≥0
vector-valued metric e : W × W → Rp≥0 , s.t. for all w ∈ W
f for which
there exists a w̃ ∈ W

e(w, w̃) ≤ ε̃ and k w − w̃ k ≤ k e(w, w̃) k.
(III.4)
Using this assumption we formally define the abstract metric
system Pτ ηω (Σ) induced by Σ as follows.
Definition 3.4: Let Σ = (X, U, U, W, W, f, σ) be a
stochastic control system for which Assump. 3 holds. Given
three constants τ ∈ R>0 , η ∈ R>0 , and ω ∈ R>0 ,
the discrete-time discrete-space deterministic metric system
induced by Σ is defined by
f , Wτ ηω , δτ ηω )
Pτ ηω (Σ) = (Xτ ηω , [U ]ω , Uτ ηω , W

(III.5)

s.t. Xτ ηω = [X]η , Uτ ηω is defined over [U ]ω , as in (III.1),
f | ∀t, k ∈ [0, τ ] . ν(t) = ν(k)},
Wτ ηω := {ν : [0, τ ] → W

and

δτ ηω (x, µ, ν) = {x′ ∈ Xτ ηω | k ξ xµν (τ ) − x′ k ≤ η},
where ξ xµν (·) are the noise free trajectories of Σ defined via Eqn. (II.7). We equip Xτ ηω with the metric
d(x, x′ ) := k x − x′ k naturally inherited from X. We denote
f.
the unique value of ν ∈ Wτ ηω over [0, τ ] by wν ∈ W
Remark 3.5: Let us emphasize that even though Pτ (Σ) is
a stochastic metric system and Pτ ηω (Σ) is a deterministic
metric system, since we are interested in studying the closeness of their trajectories in the next section, it is important
that Xr and Xτ ηω are part of the same state space. We
interpret Xτ ηω to be contained in Xr , since a set of points
can be associated with a set of random variables with Dirac
delta distributions.

IV. D ISTURBANCE B ISIMULATION
This section contains the main contribution of the paper; after recalling the notion of disturbance bisimulation
from [5] we present sufficient conditions under which the
two metric systems Pτ ηω (Σ) and Pτ (Σ) associated with a
stochastic control system Σ are disturbance bisimilar. For
this analysis, we restrict our attention to δ-ISS-M2 stochastic
control systems with f (0n , 0m , 0p ) = 0n and σ(0n ) = 0n×r ,
whose evolution is restricted to a compact region D ⊂ Rn .
Definition 4.1: Let Si = (Xi , Ui , Uτ,i , Wi , Wτ,i , δτ,i ),
i = 1, 2, be two metric systems, with state-spaces X1 , X2 ⊆
X and disturbance sets W1 , W2 ⊆ W ⊆ Rp . Furthermore,
let X admit the metric d : X × X → R≥0 and W admit
the vector-valued metric e : W × W → Rp≥0 . A binary
relation R ⊆ X1 × X2 is a disturbance bisimulation with
parameters (ε, ε̃) where ε ∈ R≥0 and ε̃ ∈ Rp≥0 , iff for each
(x1 , x2 ) ∈ R:
(a) d(x1 , x2 ) ≤ ε;
(b) for every µ1 ∈ Uτ,1 there exists a µ2 ∈ Uτ,2 such that for
all ν2 ∈ Wτ,2 and ν1 ∈ Wτ,1 with e(ν1 (0), ν2 (0)) ≤ ε̃,
we have that (δτ,1 (x1 , µ1 , ν1 ), δτ,2 (x2 , µ2 , ν2 )) ∈ R; and
(c) for every µ2 ∈ Uτ,2 there exists a µ1 ∈ Uτ,1 such that for
all ν1 ∈ Wτ,1 and ν2 ∈ Wτ,2 with e(ν1 (0), ν2 (0)) ≤ ε̃,
we have that (δτ,1 (x1 , µ1 , ν1 ), δτ,2 (x2 , µ2 , ν2 )) ∈ R.
S1 and S2 are said to be disturbance bisimilar with parameters (ε, ε̃) if there is a disturbance bisimulation relation R
between S1 and S2 with parameters (ε, ε̃).
In order to prove the existence of a disturbance bisimulation between Pτ ηω (Σ) and Pτ (Σ) we require two additional
assumptions.
Assumption 4: Let Σ be a stochastic control system admitting a δ-ISS-M2 Lyapunov function V . There exists a
K∞ and concave function γ
b s.t. for any x, x′ , x′′ ∈ X,

|V (x, x′ ) − V (x, x′′ )| ≤ b
γ (k x′ − x′′ k).
(IV.1)
This assumption is not restrictive as we are interested in
the dynamics of Σ on a compact subset D ⊂ Rn .
Assumption 5: Let Σ be a stochastic control system with
the associated metric systems Pτ (Σ) and Pτ ηω (Σ) introduced in Sec. III. Then there exists a K∞ function ψ s.t.
for all disturbance pairs ν ∈ Wτ and ν̂ ∈ Wτ ηω with
d(ν(0), ν̂(0)) ≤ k ε̃ k, the following holds for all t ∈ [0, τ ]:
d(ν(t), ν̂(t)) = E[k ν̂(t) − ν(t) k2 ]

 21

≤ ψ(t) + k ε̃ k.
(IV.2)
Given Assump. 4 and Assump. 5, we present our first main
result in the following theorem.
Theorem 4.2: Let Σ be a stochastic control system admitting a δ-ISS-M2 Lyapunov function V witnessed by κ, α,
α, σu , and σd , that satisfies Assump. 4 with K∞ function γ
b.
f ⊆ W s.t. (III.4) holds and let Pτ ηω (Σ) be
Fix τ > 0 and W
the countable deterministic metric system associated wih Σ

according to Def. 3.4 such that Assump. 5 holds. If
n

b−1 (1 − e−κτ )α(ε2 )
0 ≤ η ≤ min (α)−1 ◦ α(ε2 ), γ
o

1
1
1
− σu (ω) − σd (ψ(τ ) + k ε̃ k) − (h(σ, τ )) 2 ,
eκ
eκ
(IV.3)
where h(σ, τ ) is as in (II.8), then the relation

Rε ε̃ = (x̂, x) ∈ Xτ ηω × Xr | E[V (x̂, x)] ≤ α(ε2 )

(IV.4)

is a disturbance bisimulation relation (in the second moment)
with parameters (ε, ε̃) between Pτ ηω (Σ) and Pτ (Σ).
Remark 4.3: Given any fixed τ and ε̃, one can always find
sufficiently small η and ω s.t. (IV.3) and (IV.4) hold, as long
as ε is lower bounded according to



1
1
2
σ
(ψ(τ
)
+
k
ε̃
k)
+
γ
b
h(σ,
τ
)
eκ d
 . (IV.5)
ε2 > α−1 
(1 − e−κτ )

The lower bound on ε can be minimized by choosing an
optimal Lyapunov function V for a given system Σ (see
e.g. [12, Rem. 3.6]). Note that, when the system does not
experience any disturbance, (IV.5) reduces to [12, V.5].
V. C OMPOSITIONAL A BSTRACTION

Let us first summarize what we have presented so far. In
Sec. III we have introduced two different metric systems
Pτ (Σ) and Pτ ηω (Σ) associated with a given stochastic
control system Σ. Recall that Pτ (Σ) is an infinite state
system, whereas Pτ ηω (Σ) is a finite state system under the
assumption that the state space of Pτ ηω (Σ) is restricted to a
compact subset of Rn . Then we gave sufficient conditions for
these two abstractions to be disturbance bisimilar in Sec. IV.
In this section, we consider a network of stochastic control systems {Σi }i∈I , and the respective local abstractions
{Pτ (Σi )}i∈I and {Pτ ηi ωi (Σi )}i∈I of {Σi }i∈I , s.t. for all
i ∈ I, Pτ (Σi ) and Pτ ηi ωi (Σi ) are disturbance bisimilar
with parameters (εi , ε̃i ). Then we adapt our result from [5],
and prove that the isomorphic networks of {Pτ (Σi )}i∈I and
{Pτ ηi ωi (Σi )}i∈I , which are isomorphic to the network of
{Σi }i∈I as well, are again disturbance bisimilar.
A. Network of Stochastic Control Systems
We first formalize networks of stochastic control systems
and their abstractions by locally treating state trajectories of
neighboring systems as disturbances.
Let I be an index set (e.g., I = {1, . . . , N } for some
natural number N ) and let I ⊆ I × I be a binary irreflexive
connectivity relation on I. Furthermore, let I ′ ⊆ I be a
subset of systems with I ′ := (I ′ ×I ′ )∩I. For i ∈ I we define
NI (i) = {j | (j, i) ∈ I} and extend this notion to subsets of
systems I ′ ⊆ I as NI (I ′ ) = {j | ∃i ∈ I ′ .j ∈ NI\I ′ (i)}.
Intuitively, a set of systems can be imagined to be the set
of vertices {1, 2, . . . , |I|} of a directed graph G, and I to
be the corresponding adjacency relation. Given any vertex
i of G, the set of incoming (resp. outgoing) edges are the

inputs (resp. outputs) of a subsystem i, and NI (i) is the
set of neighboring vertices from which the incoming edges
originate.
Let Σi = (Xi , Ui , Ui , Wi , Wi , fi , σi ), for i ∈ I, be a
collection of stochastic control systems. We say that the
set of stochastic control systems {Σi }i∈I is compatible for
composition w.r.t. the interconnection
relation I, if for each
Q
i ∈ I, we have Wi = Qj∈NI (i) Xj . By slightly abusing
notation we write wi = j∈NI (i) {xj } for xj ∈ Xj and
wi ∈ Wi as a short form for the single element of the set
Q
j∈NI (i) {xj }. We extend this notation to all sets with a
single element.
Let I ′ ⊂ I be a subset of systems in the network. We
divide the set of disturbances Wi for any i ∈ I ′ into the
c
sets of coupling and external
Q disturbances, defined by Wi =
Q
e
j∈NI\I ′ (i) Xj , respectively.
j∈NI ′ (i) Xj and Wi =
If {Σi }i∈I is compatible, we define the composition of
any subset I ′ ⊆ I of systems as the stochastic control
system JΣi Ki∈I ′ = (X, U, U,
Q X, U and
Q W, W, f, σ) where
W are Q
defined as X =
i∈I ′ Ui , and
i∈I ′ Xi , U =
W = j∈NI (I ′ ) Xj . Furthermore, U and W are defined
as the sets of functions µ : R≥0 → U and ν : Ω ×
R≥0 → W such that the projection µi of µ on to Ui
(written µi = µ|Ui ) belongs to Ui , and the projection νie
e
drift is
to W
of ν on to Wie belongs
Q
Qi . The composed
Q
e
{w
{u
},
{x
},
then
defined
as
f
(
i Q i∈I ′
i
i }) =
i∈I ′
i∈I ′
Q
c
e
c
{f
(x
,
u
,
w
×
w
)},
where
w
=
i i
i
i
i
i
j∈NI ′ (i) {xj },
i∈I ′
Q
and the composed diffusion is defined as σ( i∈I ′ {xi }) =
Diag σ1 (x1 ), . . . , σ|I| (x|I| ) . The Brownian motion of the

T
overall system is defined as: dBt = dB1,t . . . dB|I|,t .
If I ′ = I, then Σ is undisturbed, modeled by W := {0}.
It is easy to see that JΣi Ki∈I ′ is again a stochastic control
system in the sense of Def. 2.1. Networks of discrete time
stochastic metric systems (Pτ (Σi )) and of abstract metric
systems (Pτ ηi ωi (Σi )) are defined analogously.
Remark 5.1: Note that we assume a nice structure of the
network: the diffusion functions and the Brownian motions
of the systems in a network are decoupled from the states of
the other systems. This is explicitly induced via the SDE
(II.1) as the diffusion terms σi (·) are only functions of
system’s state and not the disturbance. However since the
states of the systems are coupled through the drift functions,
the respective random variables are implicitly dependent.
B. Simultaneous Approximation
Given I and I ′ ⊆ I, consider a set of compatible stochastic
control systems {Σi }i∈I , the subset composition JΣi Ki∈I ′ =
(X, U, U, W, W, f, σ) and a global time-sampling parameter
τ . Then we can apply Def. 3.2 and Def. 3.4 to each Σi
to construct the corresponding metric systems Pτ (Σi ) and
Pτ ηi ωi (Σi ). To be able to do that, we need to equip Wi
|N (i)|
with a vector-valued metric ei : Wi × Wi → R≥0I
fi for all i ∈ I s.t. Ass. 3 holds. Intuitively,
and define W
ei (wi , wi′ ) is a vector with dimension |NI (i)|, where the j th
entry measures the mismatch of the respective state vector
fi as the product of state
of the j th neighbor of i. We define W

spaces of Pτ ηj ωj (Σj ), i.e., the abstraction of its neighbors,
Q
fi :=
W
(V.1)
j∈NI (i) [Xj ]ηj .

Lemma 5.2: Let Σi = (Xi , Ui , Ui , Wi , Wi , fi , σi ),i ∈ I,
be a set of compatible stochastic control systems and
the set of abstract metric systems Pτ ηi ωi (Σi ) =
fi , Wi,τ ηi ωi , δi,τ ηi ωi )
are
([Xi ]ηi , [U ]ωi , Ui,τ ηi ωi , W
constructed according to Def. 3.4, where Wi is equipped
fi as defined in (V.1). Select local
with metric (III.3) and W
quantization parameters {ηi }i∈I s.t. ηi ≤ εi . Then Ass. 3
holds for every i ∈ I with ε̃i defined as
Q
ε̃i := j∈NI (i) {εj }.
(V.2)
Given Lemma 5.2, it immediately follows that the sets
{Pτ (Σi )}i∈I ′ and {Pτ ηi ωi (Σi )}i∈I ′ of metric systems are
again compatible.
In order to guarantee the result of Thm. 4.2 for the network, we have additionally used Assump. 5 which essentially
bounds the effect of the disturbances on the state evolution.
Given the particular choice of disturbances in the network as
state trajectories of neighboring systems, we can explicitly
compute function ψ(t) in Assump. 5 using the following
proposition from [6, Thm. 4.3].
Proposition 5.3: Under Assump. 2 the solution process
ξaµν (·) satisfies the inequality


E kξaµν (t) − ξaµν (s)k22 ≤ C|t − s|, ∀s, t ∈ [0, τ ],

for any τ > 0, where k · k2 indicates
of a vector.
 the 2-norm
ατ
2
(τ
+
1)e
with α :=
The constant
C
:=
2
1
+
Ekak
2
√
K + 2 K and K from Assump. 2.
The next lemma follows from Prop. 5.3.
Lemma 5.4: Given a set of stochastic control systems
{Σi }i∈I which is compatible for composition, let each
system Σi satisfy Assump. 2 with constant Ki in (II.2). Then
Assump. 5 holds for each Σi with K∞ function
i 12
h
P
ψi (t) := t(t + 1) j∈NI (i) βj eαj t ,
p
where
αj
:=
=
Kj + 2 Kj and βj

2 1 + supxj ∈Xj kxj k22 .
Lemmas 5.2-5.4 show that the assumptions of Sec. IV
on disturbance sets of Σi hold after composition. Then
the next theorem follows from Thm. 4.2 which establishes
simultaneous disturbance bisimilarity between abstractions
of components in a network. In this theorem, using the results
in Thm. 4.2, we give conditions on all local state, input, and
disturbance quantization parameters in a composed stochastic
control system JΣi Ki∈I which allow for a simultaneous
construction of local abstractions Pτ ηi ωi (Σi ) using Def. 3.4
such that they are disturbance bisimilar with parameters
(εi , ε̃i ) to their respective discrete-time stochastic metric
systems Pτ (Σi ).
Theorem 5.5: Let {Σi }i∈I be a set of compatible stochastic control systems, each admitting a δ-ISS-M2 Lyapunov
function Vi witnessed by κi , αi , αi , σu,i , and σd,i , and let
γ
bi be a K∞ function s.t. (IV.1) holds. Let {Pτ (Σi )}i∈I be
the set of discrete-time stochastic metric systems induced

by {Σi }i∈I and let {Pτ ηi ωi (Σi )}i∈I be the set of countable
fi as
deterministic metric systems induced by {Σi }i∈I and W
in (V.1). If all local quantization parameters {ηi , εi , ωi }i∈I
simultaneously fulfill ηi ≤ εi and
n

bi−1 (1 − e−κi τ )αi (ε2i )
0 ≤ ηi ≤ min (αi )−1 ◦ αi (ε2i ), γ
o

1
1
1
σu,i (ωi ) −
σd,i (ψi (τ ) + k ε̃i k) − (hi (σi , τ )) 2 ,
−
eκi
eκi
(V.3)

in the continuous and abstract disturbances, admits a disturbance bisimilar abstract system. Then we used the property
of disturbance bisimulation to show that given a network
of stochastic control systems, the abstract systems can be
computed compositionally. One can then use this paper’s
claim for compositional synthesis of controllers for networks
of stochastic control systems, as is done in [5, Sec. VII] for
network of deterministic systems.

with {ε̃i }i∈I defined as (V.2), then the relation

Rεi ε̃i = (x̂i , xi ) ∈ [Xi ]ηi × Xi,r | E[Vi (x̂i , xi )] ≤ αi (ε2i )

[1] D. Angeli. A Lyapunov approach to incremental stability properties.
IEEE Transactions on Automatic Control, 47(3):410–21, 2002.
[2] P. Jagtap and M. Zamani. Automated synthesis of infinite dimensional
stochastic hybrid systems. arXiv preprint arXiv:1704.03690, 2017.
[3] A. A. Julius and G. J. Pappas. Approximations of stochastic hybrid
systems. IEEE Transaction on Automatic Control, 54(6):1193–1203,
2009.
[4] I. Karatzas and S.E. Shreve. Brownian Motion and Stochastic
Calculus, volume 113 of Graduate Texts in Mathematics. SpringerVerlag, New York, 2 edition, 1991.
[5] K. Mallik, A.-K. Schmuck, S. Esmaeil Zadeh Soudjani, and R. Majumdar. Compositional abstraction-based controller synthesis for
continuous-time systems. arXiv preprint arXiv:1612.08515v3, 2017.
[6] X. Mao. Stochastic Differential Equations and Applications. Horwood
series in mathematics & applications. Horwood Pub., 2008.
[7] B. K. Oksendal. Stochastic differential equations: an introduction with
applications. Springer, 5th edition, November 2002.
[8] G. Reissig, A. Weber, and M. Rungger. Feedback refinement relations
for the synthesis of symbolic controllers. IEEE Transactions on
Automatic Control, PP(99):1–1, 2016.
[9] S. Esmaeil Zadeh Soudjani and A. Abate. Adaptive and sequential
gridding procedures for the abstraction and verification of stochastic
processes. SIAM J. Applied Dynamical Systems, 12(2):921–956, 2013.
[10] S. Esmaeil Zadeh Soudjani, A. Abate, and R. Majumdar. Dynamic
Bayesian networks as formal abstractions of structured stochastic
processes. In Luca Aceto and David de Frutos-Escrig, editors, 26th
International Conference on Concurrency Theory, CONCUR 2015,
Madrid, Spain, September 1.4, 2015, volume 42 of LIPIcs, pages 169–
183. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[11] P. Tabuada. Verification and Control of Hybrid Systems, A symbolic
approach. Springer, 1st edition, June 2009.
[12] M. Zamani, P. M. Esfahani, R. Majumdar, A. Abate, and J. Lygeros.
Symbolic control of stochastic systems via approximately bisimilar finite abstractions. IEEE Transactions on Automatic Control,
59(12):3135–3150, 2014.
[13] M. Zamani, M. Rungger, and P.M. Esfahani. Construction of approximations of stochastic control systems: A compositional approach. In
Decision and Control (CDC), 2015 IEEE 54th Annual Conference on,
pages 525–530. IEEE, 2015.

is a disturbance bisimulation relation in the second moment
with parameters (εi , ε̃i ) between Pτ ηi ωi (Σi ) and Pτ (Σi ) for
all i ∈ I.
C. Composition of Approximations
We have discussed in Sec. V-B that the sets {Pτ (Σi )}i∈I
and {Pτ ηi ωi (Σi )}i∈I of metric systems is compatible. We
also established conditions on local quantization parameters
under which the metric systems Pτ (Σi ) and Pτ ηi ωi (Σi ) are
disturbance bisimilar for any i ∈ I.
We now use the fundamental property of disturbance
bisimulation relation proved in [5] that disturbance bisimilarity is preserved under composition of components in a
network. This property together with Thm. 5.5 result in the
following theorem that explicitly gives the disturbance bisimulation relation on the composed abstractions of components
in a network.
Theorem 5.6: Given the preliminaries of Thm. 5.5 and
I ′ ⊆ I, let JPτ (Σi )Ki∈I ′ and JPτ ηi ωi (Σi )Ki∈I ′ be systems
with state spaces Xr and Xτ ηω , composed from the sets
{Pτ (Σi )}i∈I and {Pτ ηi ωi (Σi )}i∈I , respectively. Then the
relation
T T
T
T T
Rε ε̃ ={([q̂1T . . . q̂|I
. . . q|I
′ | ] , [q1
′ | ] ) ∈ Xτ ηω × Xr |

(q̂i , qi ) ∈ Rεi ε̃i , ∀i ∈ I ′ )}

(V.4)

is a disturbance bisimulation relation between JPτ (Σi )Ki∈I ′
and JPτ ηi ωi (Σi )Ki∈I ′ with parameters
Q
Q
ε = k i∈I ′ {εi } k and ε̃ = j∈NI (I ′ ) {εj }.
Note that in the special case I ′ = I the composed
system replaces the overall network without extra external
disturbances. In this case it is easy to see that the relation in
Thm. 5.6 simplifies to a usual bisimulation relation.
Corollary 5.7: Given the premises of Thm. 5.6 and that
I ′ = I, the relation Rε ε̃ in (V.4) is an ε-approximate bisimulation relation between JPτ (Σi )Ki∈I and JPτ ηi ωi (Σi )Ki∈I .
VI. C ONCLUSION
In this paper, we extended our previous result on compositional abstraction based control for non-probabilistic control
systems to stochastic control systems. We gave sufficient
conditions s.t. a stochastic control system, admitting a δISS-Mq Lyapunov function and subjected to small mismatch

R EFERENCES

A PPENDIX
A. Proof of Thm. 4.2
First observe that Xτ ηω ⊂ Xτ , hence the metric d on Xτ
is also a metric on Xτ ηω . Now we prove the three parts of
Def. 4.1 separately.
(a) By definition of Rε ε̃ in (IV.4), (x̂, x) ∈ Rε ε̃ implies
1/2

1/2
≤ α−1 (E [V (x̂, x)])
d(x̂, x) = E k x̂ − x k2
≤ ε.
(A.1)
We used the convexity assumption of α and the Jensen
inequality [7] to show the inequalities in (A.1).
(b) Given a pair (x̂, x) ∈ Rε ε̃ , for any µ ∈ Uτ , observe
that there exists a µ̂ ∈ Uτ ηω s.t. k uµ̂ − uµ k ≤ ω holds.
Given any ν̂ ∈ Wτ ηω and ν ∈ Wτ s.t. e(wν̂ , wν ) ≤ ε̃ holds,
observe that k wν̂ −wν k ≤ k e(wν̂ , wν ) k ≤ k ε̃ k from (III.4).
Now we can apply transitions δτ (x, µ, ν) = ξxµν (τ ) = x′ ,
ξx̂µ̂ν̂ (τ ) = z, ξ x̂µ̂ν̂ (τ ) = z, and observe that there exists

a x̂′ ∈ Xτ ηω s.t. k x̂′ − z k ≤ η, and hence we have
δτ ηω (x̂, µ̂, ν̂) = x̂′ . Now consider the following derivation:




E V (x̂′ , x′ )


= E V (z, x′ ) + V (x̂′ , x′ ) − V (z, x′ )




= E V (z, x′ ) + E V (x̂′ , x′ ) − V (z, x′ )
1
1
σu (ω) +
σd (ψi (τ ) + k ε̃ k)
≤ α(ε2 )e−κτ +
eκ
eκ


′
+E γ
b k x̂ − z k
1
1
2 −κτ
≤ α(ε )e
+
σu (ω) +
σd (ψi (τ ) + k ε̃ k)
eκ
eκ

 ′
+b
γ E k x̂ − z + z − z k
1
1
2 −κτ
≤ α(ε )e
+
σu (ω) +
σd (ψi (τ ) + k ε̃ k)
eκ
eκ 
′
+b
γ E [k z − z k] + k x̂ − z k
1
1
2 −κτ
σu (ω) +
σd (ψi (τ ) + k ε̃ k)
≤ α(ε )e
+
eκ
eκ


1
+b
γ (h(σ, τ )) 2 + η

(A.2)

≤ α(ε2 ).

Hence by Eqn. (IV.4), (x̂′ , x′ ) ∈ Rε ε̃ .
(c) Given a pair (x̂, x) ∈ Rε ε̃ , for any µ̂ ∈ Uτ ηω , observe
that we can choose µ ∈ Uτ s.t. µ = µ̂, i.e., k uµ̂ − uµ k = 0.
Given any ν ∈ Wτ and ν̂ ∈ Wτ ηω s.t. e(wν̂ , wν ) ≤ ε̃, we
have as before δτ (x, µ, ν) = ξxµν (τ ) = x′ , ξx̂µ̂ν̂ (τ ) = z,
ξ x̂µ̂ν̂ (τ ) = z, and observe that there exists a x̂′ ∈ Xτ ηω s.t.
k x̂′ − z k ≤ η, and hence we have δτ ηω (x̂, µ̂, ν̂) = x̂′ . With a
very similar derivation as in (A.2) it follows from Eqn. (IV.4)
that (x̂′ , x′ ) ∈ Rε ε̃ .

B. Proof of other statements
Proof: [Lemma 2.5] The proof of Lemma 2.5 can be
obtained from the proof of Lemma 3.4 in [12] by replacing
all instances of f (x, u), f (z, u), f (x′ , u) and f (x′ , u′ )
with f (x, u, w), f (z, u, w) , f (x′ , u, w) and f (x′ .u′ , w′ )
respectively, and defining the positive
κ = κ
e, the
 √ constant
2
2 2
K∞ functions
σ
(r)
=
nL
/e
κ
k
P
k
r
and
σ
(r)
=
u
d
u
 √
nL2w /e
κ k P k2 r.
Proof: [Lemma 2.6] The proof of Lemma 2.6 follows
closely the proof of Lemma 3.8 in [12] and hence is omitted.
Proof: [Lemma 5.2]Q Pick any i ∈ I, wi ∈ Wi
and observe that wi = j∈NI (i) {xj }. By the choice of
Xj,τ ηj ωj as [Xj ]ηj we furthermore know that for any xj
there exists x̂j s.t. k xj − x̂j k ≤ ηj ≤ εj . Now recall
Q
Q
fi =
that W
j∈NI (i) [Xj ]ηj . Using
j∈NI (i) Xj,τ ηj ωj =
the definition of ε̃i in (V.2) and e in (III.3) we therefore
f
know that forQany wi ∈ Wi there exists
Q w̃i ∈ Wi s.t.
k} ≤ j∈NI (i) {εj } =
e(wi , w̃i ) = j∈NI (i) {k xj − x̂j Q
ε̃i .QFurthermore, k wi − w̃i k = k j∈NI (i) {xj − x̂j } k =
k j∈NI (i) {k xj − x̂j k} k = k e(wi , w̃i ) k.
Proof: [Lemma 5.4] The proof follows from the follow-

ing derivation:
d(νi (t), ν̂i (t))

 1
= E k νi (t) − ν̂i (t) k2 2

 1
= E k νi (t) − ν̂i (0) k2 2
 1

= E k νi (t) − νi (0) + νi (0) − ν̂i (0) k2 2
 1

 1

≤ E k νi (t) − νi (0) k2 2 + E k νi (0) − ν̂i (0) k2 2
 
 21
Y
= E k
{ξj (t) − ξj (0)} k2  + k ε̃i k
j∈NI (i)

 

!2  12
sup k ξj (t) − ξj (0) k  + k ε̃i k

= E 

 

≤ E 


≤

j∈NI (i)

X

j∈NI (i)

X

j∈NI (i)



≤

X

j∈NI (i)



≤

X

j∈NI (i)

 21

k ξj (t) − ξj (0) k2  + k ε̃i k
 21



E k ξj (t) − ξj (0) k22  + k ε̃i k

2

 12

2t 1 + Ekξj (0)k2 (t + 1)eαj t  + k ε̃i k
!

 21

2t 1 + sup kxj k22 (t + 1)eαj t  + k ε̃i k
xj ∈Xj

p
where αj = Kj + 2 Kj and Kj is the constant K as given
in Prop. 5.3 for the j-th system, and the last step follows
from Prop. 5.3. We define for system Σi the K∞ function
i 21
h
P
ψi (t) := t(t + 1) j∈NI (i) βj eαj t , which concludes the
proof.

