Convergent products of stochastic matrices : algorithms and complexity
(2018)
Files
Thesis_Global.pdf
Open Access - Adobe PDF
- 950.52 KB
Details
- Authors
- Supervisors
- Abstract
- Inhomogeneous products of stochastic matrices are ubiquitous in mathematics and engineering. They appear in consensus systems, inhomogeneous Markov chains, the analysis of distributed optimization methods and automata theory. Consensus systems have been the main motivation throughout this thesis. They represent how a group of agents can reach agreement on a common value by iterative averaging. This iterative averaging process can be modeled as a discrete-time linear switching system with stochastic transition matrices and the convergence to a consensus then amounts to limits of products of these stochastic transition matrices. The first part of the thesis considers sets of stochastic matrices for which all infinite products converge to a rank-one matrix (i.e., to a consensus or to a stable distribution in the corresponding applications). New characterizations of these sets are obtained and several complexity questions are answered, by analyzing the combinatorial structure of invariant polytopes. The second part of the thesis considers sets for which at least one infinite product converges. The problem of finding short products whose sequence of powers converges to a rank-one matrix is considered. Algorithms, bounds and negative complexity results are obtained and a strong connection with synchronizing automata and the Černý conjecture is established.
- Affiliations
Citations
Chevalier, P.-Y. (2018). Convergent products of stochastic matrices : algorithms and complexity. https://hdl.handle.net/2078.5/57741