A Sharp Tail Bound for the Expander Random Sampler
A Sharp Tail Bound for the Expander Random Sampler
复制标题
用于扩展器随机采样器的尖尾约束
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
O. Regev
中科院分区：
文献类型：
--
作者：
Shravas Rao;O. Regev
考虑一个扩展图，其中一个$mu$分数的顶点被标记。随机游走从一个统一的顶点开始，每一步都继续到一个随机的邻居。吉尔曼在1993年表明，在长度为$n$的随机游走中看到的标记顶点的数量集中在其期望值周围，$Φ：= mu n$，与图的大小无关。在这里，我们提供了一个新的和尖锐的尾部界限，改善现有的界限，只要$mu$不是太大。
Consider an expander graph in which a $mu$ fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman showed in 1993 that the number of marked vertices seen in a random walk of length $n$ is concentrated around its expectation, $Phi := mu n$, independent of the size of the graph. Here we provide a new and sharp tail bound, improving on the existing bounds whenever $mu$ is not too large.