# Estimating graph parameters with random walks

### Anna Ben-Hamou

Sorbonne Université, Paris, France### Roberto I. Oliveira

Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil### Yuval Peres

Microsoft Research, Redmond, USA

## Abstract

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_{rel}m/d )$ steps, where $t_{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_{unif}+t_{rel}n )$, where $n$ is the number of vertices and $t_{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_{unif}nm )$ 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.

## Cite this article

Anna Ben-Hamou, Roberto I. Oliveira, Yuval Peres, Estimating graph parameters with random walks. Math. Stat. Learn. 1 (2018), no. 3/4, pp. 375–399

DOI 10.4171/MSL/9