Product of random stochastic matrices and distributed averaging

Touri, Behrouz

Permalink

https://hdl.handle.net/2142/29634 Copy

Description

Title

Product of random stochastic matrices and distributed averaging

Author(s)

Touri, Behrouz

Issue Date

2012-02-06T20:08:01Z

Director of Research (if dissertation) or Advisor (if thesis)

Nedich, Angelia

Doctoral Committee Chair(s)

Nedich, Angelia

Committee Member(s)

• Basar, Tamer
• Dullerud, Geir E.
• Kumar, P.R.
• Stipanović, Dušan M.

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Products of Random Stochastic Matrices
• Distributed Averaging
• Weighted Averaging
• Hegselmann-Krause model
• Comparison Functions
• Non-negative Matrix Theory

Abstract

This thesis is mainly concerned with the study of product of random stochastic matrices and random weighted averaging dynamics. It will be shown that a generalization of a fundamental result in the theory of ergodic Markov chains not only holds for inhomogeneous chains of stochastic matrices, but also remains true for random stochastic matrices. To do this, the concept of infinite flow property will be introduced for a deterministic chain of stochastic matrices and it will be proven that it is necessary for ergodicity of any stochastic chain. This result will further be extended to ergodic classes, through the development of the concept of the infinite flow graph and $\ell_1$-approximation technique. For the converse implications, the product of stochastic matrices will be studied in the more general setting of random adapted stochastic chains. Using a result of A.\ Kolmogorov, it will be shown that any averaging dynamics admits infinitely many comparison functions including a quadratic one. By identifying the decrease of the quadratic comparison function along the trajectories of the dynamics, it will be proven that under general assumptions on a random chain, the chain is infinite flow stable, i.e.\ the product of random stochastic matrices is convergent almost surely and, also, the limiting matrices admit certain structures that can be deduced from the infinite flow graph of the chain. It will be shown that a general class of stochastic chains, the balanced chains with feedback property, satisfy the conditions of this result. Some implications of the developed results for products of independent random stochastic matrices will be provided. Furthermore, it will be proven that under general conditions, an independent random chain and its expected chain exhibit the same ergodic behavior. It will be proven that an extension of a well-known result in the theory of homogeneous Markov chains holds for a sequence of inhomogeneous stochastic matrices. Then, link-failure models for averaging dynamics will be introduced and it will be shown that under general conditions, link failure does not affect the limiting behavior of averaging dynamics. Then, the application of the developed methods to the study of Hegselmann-Krause model will be considered. Using the developed results, an upper bound $O(m^4)$ will be established for the Hegselmann-Krause dynamics, which is an improvement to the previously known bound $O(m^5)$. As a final application for the developed tools, an alternative proof for the second Borel-Cantelli lemma will be provided. Motivated by the infinite flow property, a stronger one, the absolute infinite flow property will be introduced. It will be shown that this stronger property is in fact necessary for ergodicity of any stochastic chain. Moreover, the equivalency of the absolute infinite flow property with ergodicity of doubly stochastic chains will be proven. These results will be driven by introduction and study of the rotational transformation of a stochastic chain. Finally, motivated by the study of Markov chains over general state spaces, a framework for the study of averaging dynamics over general state spaces will be proposed. Several modes of ergodicity and consensus will be introduced and the relation between them will be studied. It will be shown that a generalization of the infinite flow property remains necessary for the weakest form of ergodicity over general state spaces. Inspired by the concept of an absolute probability sequence for stochastic chains, an absolute probability sequence for a chain of stochastic kernels will be introduced. Using an absolute probability sequence, a family of comparison functions for the averaging dynamics, which contains a quadratic one, will be introduced. Finally, an exact decrease rate of the quadratic comparison function along any trajectory of the averaging dynamics will be quantified.

Graduation Semester

2011-12

Permalink

http://hdl.handle.net/2142/29634

Copyright and License Information

Copyright 2011 Behrouz Touri

Owning Collections