Ergodic Randomized Algorithms and Dynamics over Networks
arXiv:1309.1349
Abstract
Algorithms and dynamics over networks often involve randomization, and randomization may result in oscillating dynamics which fail to converge in a deterministic sense. In this paper, we observe this undesired feature in three applications, in which the dynamics is the randomized asynchronous counterpart of a well-behaved synchronous one. These three applications are network localization, PageRank computation, and opinion dynamics. Motivated by their formal similarity, we show the following general fact, under the assumptions of independence across time and linearities of the updates: if the expected dynamics is stable and converges to the same limit of the original synchronous dynamics, then the oscillations are ergodic and the desired limit can be locally recovered via time-averaging.
arXiv comment11 pages; submitted for publication. revised version with fixed technical flaw and updated references
References in corpus (5)
- PageRank Optimization by Edge Selection
- Ergodic Control and Polyhedral approaches to PageRank Optimization
- Gossips and Prejudices: Ergodic Randomized Dynamics in Social Networks
- Almost sure convergence of a randomized algorithm for relative localization in sensor networks
- Convergence of Distributed Randomized PageRank Algorithms