论文标题
随机步行，等距和图形设计
Random Walks, Equidistribution and Graphical Designs
论文作者
论文摘要
令$ g =（v，e）$为$ n $顶点上的$ d $ regartar图，让$μ_0$是$ v $的概率度量。转移到随机选择的邻居的行为导致一系列概率度量的顺序，由$μ_{k+1}给出的$ V $支持的序列量度，其中$ a $是$ d $的$ a $是$ g $的角度矩阵。订购$ a d^{ - 1} $的特征值$ 1 =λ_1\ geq |λ_2| \ geq \ dots \ geq |λ_n| \ geq 0 $，众所周知，$ |λ_2| $很小的图形是随机步行过程迅速收敛到均匀分布的图：对于所有初始概率测量$μ_0$和所有$ k \ geq 0 $，$ sum_ \ sum_ \ sum_ \ sum_ { μ_k（v） - \ frac {1} {n} \ right |^2 \leqλ_2^{2k}。我们表明，如果$ g $是常规的，那么对于任何$ 1 \ leq \ ell \ leq n $，都存在概率度量$μ_0$，最多$ \ ell $ dertices上的$ \ ell $ vertices，以便$ \ ell $ \ sum_ {v \ in v} \ in v} \ left | μ_k（v） - \ frac {1} {n} \ right |^2 \leqλ_{\ ell+1}^{2k} {2K} {2K}。$$该结果在图抽样问题中具有应用程序：我们显示这些度量具有重建全球均值的良好采样属性。
Let $G=(V,E)$ be a $d$-regular graph on $n$ vertices and let $μ_0$ be a probability measure on $V$. The act of moving to a randomly chosen neighbor leads to a sequence of probability measures supported on $V$ given by $μ_{k+1} = A D^{-1} μ_k$, where $A$ is the adjacency matrix and $D$ is the diagonal matrix of vertex degrees of $G$. Ordering the eigenvalues of $ A D^{-1}$ as $1 = λ_1 \geq |λ_2| \geq \dots \geq |λ_n| \geq 0$, it is well-known that the graphs for which $|λ_2|$ is small are those in which the random walk process converges quickly to the uniform distribution: for all initial probability measures $μ_0$ and all $k \geq 0$, $$ \sum_{v \in V} \left| μ_k(v) - \frac{1}{n} \right|^2 \leq λ_2^{2k}.$$ One could wonder whether this rate can be improved for specific initial probability measures $μ_0$. We show that if $G$ is regular, then for any $1 \leq \ell \leq n$, there exists a probability measure $μ_0$ supported on at most $\ell$ vertices so that $$ \sum_{v \in V} \left| μ_k(v) - \frac{1}{n} \right|^2 \leq λ_{\ell+1}^{2k}.$$ The result has applications in the graph sampling problem: we show that these measures have good sampling properties for reconstructing global averages.
