Lyapunov Criterion for Stochastic Systems and Its Applications in Distributed Computation
This work provides a theoretical tool for analyzing convergence of stochastic systems with applications in distributed computation, offering relaxed conditions compared to classical Lyapunov theory.
The paper develops a new Lyapunov criterion for stochastic discrete-time systems that relaxes the requirement of strict decrease at every step, and applies it to prove convergence of products of random stochastic matrices and to relax network structure conditions for distributed linear equation solving.
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.