The hitting time H_(xy) between two vertices x and y of a graph is the average time that the standard simple random walk takes to get from x to y. In this paper, we study the distribution of the hitting time between two randomly chosen vertices of a random tree. We consider both uniformly random labelled trees and a more general model with vertex weights akin to simply generated trees. We show that the r-th moment of the hitting time is of asymptotic order n~(3r/2) in trees of order n, and we describe the limiting distribution upon normalisation by means of its moments. Moreover, we also obtain joint moments with the distance between the two selected vertices. Finally, we discuss a somewhat different model of randomness, namely random recursive trees. In this setup, the root is of special importance, and so we study the hitting time from the root to a random vertex or from a random vertex to the root. Interestingly, the hitting time from the root is of order n log n, with a normal limit law, while the hitting time to the root is only of linear order and has a non-Gaussian limit law.
展开▼
