 QUICK SEARCH:

The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

# Mathematical Statistics and Learning

Full-Text PDF (326 KB) | Metadata | Table of Contents | MSL summary
Online access to the full text of Mathematical Statistics and Learning is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
Volume 1, Issue 3/4, 2018, pp. 375–399
DOI: 10.4171/MSL/9

Published online: 2019-05-18

Estimating graph parameters with random walks

Anna Ben-Hamou, Roberto I. Oliveira and Yuval Peres

(1) Sorbonne Université, Paris, France
(2) Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil
(3) Microsoft Research, Redmond, USA

An algorithm observes the trajectories of random walks over an unknown graph $G$, starting from the same vertex $x$, as well as the degrees along the trajectories. For all finite connected graphs, one can estimate the number of edges $m$ up to a bounded factor in $O(t_{\mathrm {rel}}^{3/4}\sqrt{m/d}\,)$ steps, where $t_{\mathrm {rel}}$ is the relaxation time of the lazy random walk on $G$ and $d$ is the minimum degree in $G$. Alternatively, $m$ can be estimated in $O(t_{\mathrm {unif}} + t_{\mathrm {rel}}^{5/6}\sqrt{n}\,)$, where $n$ is the number of vertices and $t_{\mathrm {unif}}$ is the uniform mixing time on $G$. The number of vertices $n$ can then be estimated up to a bounded factor in an additional $O(t_{\mathrm {unif}}\frac{m}{n})$ steps. Our algorithms are based on counting the number of intersections of random walk paths $X,Y$, i.e. the number of pairs $(t,s)$ such that $X_t=Y_s$. This improves on previous estimates which only consider collisions (i.e.~times $t$ with $X_t=Y_t$). We also show that the complexity of our algorithms is optimal, even when restricting to graphs with a prescribed relaxation time. Finally, we show that, given either $m$ or the mixing time of $G$, we can compute the "other parameter" with a self-stopping algorithm.

Keywords: Graph inference, intersections of random walks

Ben-Hamou Anna, Oliveira Roberto, Peres Yuval: Estimating graph parameters with random walks. Math. Stat. Learn. 1 (2018), 375-399. doi: 10.4171/MSL/9