An algorithm observes the trajectories of random walks over an unknown graph , starting from the same vertex , as well as the degrees along the trajectories. For all finite connected graphs, one can estimate the number of edges up to a bounded factor in steps, where is the relaxation time of the lazy random walk on and is the minimum degree in . Alternatively, can be estimated in , where is the number of vertices and is the uniform mixing time on . The number of vertices can then be estimated up to a bounded factor in an additional steps. Our algorithms are based on counting the number of intersections of random walk paths , i.e. the number of pairs such that . This improves on previous estimates which only consider collisions (i.e.~times with ). 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 or the mixing time of , 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–399DOI 10.4171/MSL/9