Product of random stochastic matrices and distributed averaging

cover......Page 1
Front matter......Page 2
Product of Random Stochastic Matrices and Distributed Averaging......Page 4
Supervisor’s Foreword......Page 7
Acknowledgments......Page 9
Contents......Page 11
1 Introduction......Page 14
1.1 Past Work......Page 17
1.2 Overview and Contributions......Page 18
1.3.1 Sets, Vectors and Matrices......Page 20
1.3.2 Probability Theory......Page 22
1.3.4 Control Theory......Page 23
References......Page 24
2.1.1 Left Product of Stochastic Matrices......Page 28
2.1.2 Dynamic System Viewpoint......Page 30
2.1.3 Uniformly Bounded and  B-Connected Chains......Page 32
2.1.4 Birkhoff-von Neumann Theorem......Page 33
References......Page 34
3.1 Random Weighted Averaging Dynamics......Page 35
3.2 Ergodicity and Infinite Flow Property......Page 36
3.3 Infinite Flow Graph and   1-Approximation......Page 40
4.1 Infinite Flow Stability......Page 47
4.2 Feedback Properties......Page 49
4.3.1 Absolute Probability Process......Page 52
4.3.2 A Family of Comparison Functions......Page 54
4.3.3 Quadratic Comparison Functions......Page 57
4.3.4 An Essential Relation......Page 59
4.4 Class   P*......Page 61
4.5 Balanced Chains......Page 67
4.5.1 Absolute Probability Sequence for Balanced Chains......Page 70
References......Page 74
5.1 Independent Random Chains......Page 76
5.1.1 Rate of Convergence......Page 78
5.1.2 i.i.d. Chains......Page 84
5.2 Non-Negative Matrix Theory......Page 87
5.3 Convergence Rate for Uniformly Bounded Chains......Page 89
5.4 Link Failure Models......Page 91
5.5.1 Hegselmann-Krause Model......Page 93
5.5.2 Loose Bound for Termination Time of Hegselmann-Krause Dynamics......Page 94
5.5.3 An Improved Bound for Termination Time of Hegselmann-Krause Model......Page 96
5.6 Alternative Proof of Borel-Cantelli lemma......Page 102
References......Page 103
6.1 Absolute Infinite Flow......Page 104
6.2.1 Rotational Transformation......Page 108
6.3 Decomposable Stochastic Chains......Page 112
6.4 Doubly Stochastic Chains......Page 116
6.4.1 Rate of Convergence......Page 118
6.4.2 Doubly Stochastic Chains Without Absolute Infinite  Flow Property......Page 120
References......Page 123
7.1 Framework......Page 124
7.2 Modes of Ergodicity......Page 126
7.3 Infinite Flow Property in General State Spaces......Page 129
7.4 Quadratic Comparison Function......Page 132
References......Page 137
8.1 Conclusion......Page 138
8.2 Suggestions for Future Works......Page 139
A.1 Convergence of Random Variables......Page 142
A.2 Conditional Expectation and Martingales......Page 143
A.3.1 Borel–Cantelli Lemma......Page 145
A.3.3 Kolmogorov’s Three-Series Theorem......Page 146
B.1 Functional Analysis......Page 148
References......Page 149
About the Author......Page 150