Lyapunov Criterion for Stochastic Systems and Its Applications in Distributed Computation

Abstract

This paper presents new sufficient conditions for convergence and asymptotic or exponential stability of a stochastic discrete-time system, under which the constructed Lyapunov function always decreases in expectation along the system's solutions after a finite number of steps, but without necessarily strict decrease at every step, in contrast to the classical stochastic Lyapunov theory. As the first application of this new Lyapunov criterion, we look at the product of any random sequence of stochastic matrices, including those with zero diagonal entries, and obtain sufficient conditions to ensure the product almost surely converges to a matrix with identical rows; we also show that the rate of convergence can be exponential under additional conditions. As the second application, we study a distributed network algorithm for solving linear algebraic equations. We relax existing conditions on the network structures, while still guaranteeing the equations are solved asymptotically.

14 pages, 1 figure

Cited by in corpus (7)

• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Mean Field Behaviour of Collaborative Multi-Agent Foragers
• Almost Surely Stable Deep Dynamics
• A High-order Tuner for Accelerated Learning and Control
• On stochastic stabilization of sampled systems
• Neural Lyapunov Model Predictive Control: Learning Safe Global Controllers from Sub-optimal Examples
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches