Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624496 | Advances in Applied Mathematics | 2016 | 28 Pages |
Abstract
We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Sinan Aksoy, Fan Chung, Xing Peng,