Sensitivity of Mixing Times in Eulerian Digraphs
Sensitivity of Mixing Times in Eulerian Digraphs
复制标题
欧拉有向图中混合时间的灵敏度
DOI：
--
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Perla Sousi
中科院分区：
文献类型：
--
作者：
Lucas Boczkowski;Y. Peres;Perla Sousi
设$X$是图$G$上的随机漫步。如果$G$是无向的，则混合时间以图的最大命中时间为上界。这对于有向链来说是失败的，正如循环$mathbb{Z}_n$上的有偏随机漫步所示。然而，我们建立了对于欧拉有向图，混合时间为$O(mn)$，其中$m$为边的数目，$n$为顶点的数目。在可逆情况下，混合时间对惰性参数的变化具有鲁棒性。令人惊讶的是，在定向设置中，混合时间对这种变化很敏感。我们还研究了欧拉有向图上随机漫步的探索和覆盖时间，并证明了与无向情况类似的普遍上界。
Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$, where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.