43  Stochastic stability

Author

Affiliation

Aditya Mahajan

McGill University

Consider a discrete-time stochastic system that starts from a constant initial condition $x_0$ and evolves according to $$\begin{array}{}\text{(1)}& X_{t+1}=f(X_t,W_t)\end{array}$$ where $X_t\in {\mathbb{R}}^n$, $\{Y_t{\}}_{t\ge 1}$ is a ${\mathbb{R}}^d$-valued stochastic process on a probabilty space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. Define ${\mathcal{F}}_t=\sigma (W_{1:t})$. Then $\{X_t{\}}_{t\ge 1}$ is an $\{{\mathcal{F}}_t{\}}_{t\ge 1}$ adapted process. In addition, if $\{W_t{\}}_{t\ge 1}$ is an independent process, then $\{X_t{\}}_{t\ge 1}$ is Markov.

A point $x^{\ast }$ is said to be an equilibrium of $\text{(1)}$ if $f(x^{\ast },y)=x^{\ast }$ for all $w\in {\mathbb{R}}^d$. Without loss of generality, we assume that the origin $x=0$ is an equilibrium.

43.1 Different notions of stability

First we recall some terminology related to almost sure convergence.

1. A random sequence $\{X_t{\}}_{t\ge 1}$ in a sample space $\mathrm{\Omega }$ converges to a random variable $X$ almost surely if $$\mathbb{P}(\omega \in \mathrm{\Omega }:\underset{t\to \infty }{lim}\parallel X_t(\omega )-X(\omega )\parallel =0)=1.$$

2. The convergence is said to be exponentially fast with rate no slower than ${\gamma }^{-1}$ for some $\gamma >1$ (not dependent on $\omega$) if ${\gamma }^t\parallel X_t-X\parallel$ converges almost surely to some $\mathrm{\Delta }\ge 0$.

3. Given a set $\mathcal{D}\in {\mathbb{R}}^n$, a random sequence $\{X_t{\}}_{t\ge 1}$ is said to converge to $\mathcal{D}$ almost surely if $$\mathbb{P}(\omega \in \mathrm{\Omega }:\underset{t\to \infty }{lim}\mathrm{dist}(X_t(\omega ),\mathcal{D})=0)=1,$$ where $\mathrm{dist}(x,\mathcal{D})=\underset{\tilde{x}\in \mathcal{D}}{inf}\parallel x-\tilde{x}\parallel$.

Definition 43.1 The origin of $\text{(1)}$ is said to be:

1. Stable in probability if $\underset{x_0\to 0}{lim}\mathbb{P}(\underset{t\ge 1}{sup}\parallel X_t\parallel >\epsilon )=0$ for any $\epsilon >0$.

2. Asymptotically stable in prbability if it is stable in probability and moreover $\underset{x_0\to 0}{lim}\mathbb{P}(\underset{t\to \infty }{lim}\parallel X_t\parallel =0)=1$.

3. Exponentially stable in prbability if for some $\gamma >1$ (not dependent on $\omega$), $\underset{x_0\to 0}{lim}\mathbb{P}(\underset{t\to \infty }{lim}\parallel {\gamma }^t{X}_t\parallel =0)=1$.

43.2 Sufficient conditions for stochastic stability

Definition 43.2 Given a set $\mathcal{Q}\in {\mathbb{R}}^n$ containing the origin, the origin of $\text{(1)}$ is said to be:

1. locally a.s. asymptotically stable in $\mathcal{Q}$ if starting from $x_0\in \mathcal{Q}$ all the sample paths $X_t$ stay in $\mathcal{Q}$ for all $t\ge 1$ and converge to origin almost surely.

2. locally a.s. exponentially stable in $\mathcal{Q}$ if it is locally a.s. asymptotically stable and the convergence is exponentially fast.

If the above properties hold for $\mathcal{Q}={\mathbb{R}}^n$, the system is said to be globally a.s. asymptotically (or exponentially) stable.

Function class $\mathcal{K}$

A continuous function $h:[0,a)\to [0,\infty )$ is said to belong to class $\mathcal{K}$ if it is strictly increasing and $h(0)=0$.

Theorem 43.1 For the stochastic discrete-time system $\text{(1)}$, let $\{X_t{\}}_{t\ge 1}$ be Markov.

Let $V:{\mathbb{R}}^n\to \mathbb{R}$ be a continuous positive definite and radially unbounded function. Define the level set ${\mathcal{Q}}_{\lambda }:=\{x:0\le V(x)<\lambda \}$ for some $\lambda >0$.

Let $\phi :{\mathbb{R}}^n\to \mathbb{R}$ be a continious function that satisfies $\phi (x)\ge 0$ for all $x\in {\mathcal{Q}}_{\lambda }$.

Suppose the following property holds: for all $x\in {\mathbb{R}}^n$, $$\mathbb{E}[V(X_{t+1})\mid X_t=x]-V(x)\le -\phi (x),\mathrm{\forall }t\ge 1.$$ Then:

1. For any initial condition $x_0\in {\mathcal{Q}}_{\lambda }$, $\{X_t{\}}_{t\ge 1}$ converges to ${\mathcal{D}}_1:=\{x\in {\mathcal{Q}}_{\lambda }:\phi (x)=0\}$ with probability at least $1-V(x_0)/\lambda$.

2. if moreover $\phi (x)$ is positive definite on ${\mathcal{Q}}_{\lambda }$ and there exist two calss $\mathcal{K}$ functions $h_1$ and $h_2$ such that $h_1(\parallel x\parallel )\le V(x)\le h_2(\parallel x\parallel )$, then $x=0$ is asymptotically stable in probability.

Under slightly stronger conditions, it is also possible to characterize the rate of convergence.

Theorem 43.2 For the stochastic discrete-time system $\text{(1)}$, let $\{X_t{\}}_{t\ge 1}$ be Markov.

Let $V:{\mathbb{R}}^n\to \mathbb{R}$ be a continous nonnegative function.

Suppose the following condition holds: there exists an $\alpha \in (0,1)$ such that $$\mathbb{E}[V(X_{t+1})\mid X_t=x]-V(x)\le -\alpha V(x),\mathrm{\forall }t\ge 1.$$ Then:

1. For any initial state $x_0$, $V(X_t)$ almost surely converges to $0$ exponentially fast with a rate no slower than $1-\alpha$.

2. If moreover $V$ satisfies $c_1\parallel x{\parallel }^p\le V(x)\le c_2\parallel x{\parallel }^p$ for some $c_1,c_2,p>0$, then $x=0$ is globally a.s. exponentially stable.

43.3 Weaker sufficient conditions for stochastic stability

Theorem 43.3 For the stochastic discrete-time system $\text{(1)}$, let $V:{\mathbb{R}}^n\to \mathbb{R}$ be a continuous nonnegative and radially unbounded function. Define the set $Q_{\lambda }:=\{x:V(x)<\lambda \}$ for some $\lambda >0$.

Suppose the following conditions hold:

1. For any $t$ such that $X_t\in {\mathcal{Q}}_{\lambda }$, we have $$\mathbb{E}[V(X_{t+1})\mid {\mathcal{F}}_t]-V(X_t)\le 0.$$

2. There is an integer $T\ge 1$ (not depent on $\omega$) and a continous function $\phi :{\mathbb{R}}^n\to \mathbb{R}$ that satisfies $\phi (x)\ge 0$ for all $x\in {\mathcal{Q}}_{\lambda }$ such that for any $t$, $$\mathbb{E}[V(X_{t+T})\mid {\mathcal{F}}_t]-V(X_t)\le -\phi (X_t)$$

Then, the implications of Theorem 43.1 hold.

The sufficient conditions for exponential stability can be weakened in a similar manner.

Theorem 43.4 Suppose assumptions a) and b) of Theorem 43.3 are satisfied with the inequality of b) strengthened to $$\mathbb{E}[V(X_{t+T})\mid {\mathcal{F}}_t]-V(X_t)\le -\alpha V(X_t)$$ for some $\alpha \in (0,1)$.

Then, the implications of Theorem 43.2 hold.

Notes

The material in this section is adapted from Qin et al. (2020).

Qin, Y., Cao, M., and Anderson, B.D.O. 2020. Lyapunov criterion for stochastic systems and its applications in distributed computation. IEEE Transactions on Automatic Control 65, 2, 546–560. DOI: 10.1109/tac.2019.2910948.