Estimating graph parameters with random walks (Q2319818)

Summary: 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.