Files in this item
Files  Description  Format 

application/pdf BehrouThesisV1.pdf (720kB)  (no description provided) 
Description
Title:  Product of random stochastic matrices and distributed averaging 
Author(s):  Touri, Behrouz 
Director of Research:  Nedich, Angelia 
Doctoral Committee Chair(s):  Nedich, Angelia 
Doctoral Committee Member(s):  Basar, Tamer; Dullerud, Geir E.; Kumar, P.R.; Stipanović, Dušan M. 
Department / Program:  Industrial&Enterprise Sys Eng 
Discipline:  Industrial Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Products of Random Stochastic Matrices
Distributed Averaging Weighted Averaging HegselmannKrause model Comparison Functions Nonnegative 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 wellknown result in the theory of homogeneous Markov chains holds for a sequence of inhomogeneous stochastic matrices. Then, linkfailure 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 HegselmannKrause model will be considered. Using the developed results, an upper bound $O(m^4)$ will be established for the HegselmannKrause 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 BorelCantelli 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. 
Issue Date:  20120206 
URI:  http://hdl.handle.net/2142/29634 
Rights Information:  Copyright 2011 Behrouz Touri 
Date Available in IDEALS:  20120206 
Date Deposited:  201112 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Industrial and Enterprise Systems Engineering