Mathematicians Lyons,Pemantle and Peres have proved in the paper entitled "Ergodic Theory on Galton-Watson Trees: Speed of Random Walk and Dimension of Harmonic Measure" that the speed of a simple random walk on a Galton Watson tree is obtained by formula:

$$\sum_{k=1}^\infty p_k \frac{k-1}{k+1}$$

when $p_k$ is the probability that an individual has $k$ offspring.

I'm looking for a much simpler proof of this theorem rather than what mentioned in the paper.

or any hint to start proving by myself.

Thank you very much.

  • $\begingroup$ By a "simple" random walk to you mean the for each node, the probabilities of picking edges incident to that node are all equal? $\endgroup$ – Michael Hardy Aug 20 '16 at 13:08
  • $\begingroup$ Lyons has written an "informal version" of this paper: MR1395615 Lyons, Russell. How fast and where does a random walker move on a random tree? Random discrete structures (Minneapolis, MN, 1993), 185–198, IMA Vol. Math. Appl., 76, Springer, New York, 1996. dx.doi.org/10.1007/978-1-4612-0719-1_12 pages.iu.edu/~rdlyons/ps/dimTalk.ps You might like to start by reading that. $\endgroup$ – Nate Eldredge Aug 20 '16 at 15:56
  • 1
    $\begingroup$ @MichaelHardy yes $\endgroup$ – user115608 Aug 20 '16 at 18:14

I am not aware of any other argument. Conceptually it is actually quite simple. The main idea consists in changing the viewpoint and considering, instead of the simple random walk on a single tree, the random walk on the whole ensemble of Galton-Watson trees. In other words, one has to pass from a countable state space (the set of vertices of a single tree) to the continuous state space $\mathcal T$ which consists of (the isomorphism classes) of all pointed ($\equiv$ rooted) trees (this is a tree together with a distinguished vertex). There is a naturally defined simple random walk on $\mathcal T$, which consists in replacing the root of a tree $\tau\in\mathcal T$ with one of its neighbours with equal probabilities, and the key ingredient of the proof is the observation that the simple random walk on $\mathcal T$ has a stationary probability measure $\pi$ naturally related to the original branching process.

The original Galton-Watson measure is not stationary because the simple random walk is not stochastically homogeneous with respect to it: the root is an orphan and therefore has fewer neighbours than the offspring. However, this drawback is easy to repair; one has to add "by force" one more offspring to the first generation, and to let it multiply at the following steps in the same way as the other offspring. Let $\pi$ be the resulting measure on $\mathcal T$. The measure $\pi$ can also be described by saying that it is obtained by running the branching process not from a single progenitor, but from two progenitors joined with an edge.

The fact that the measure $\pi$ is stationary implies, by the subadditive ergodic theorem, existence of a rate of escape $\ell$ for the simple random walk on $\pi$-a.e. tree. Therefore, by the above description of the measure $\pi$, the rate of escape for the simple random walk on a.e. Galton-Watson tree also exists and equals $\ell$.

Let $$ \ell_n = \mathbf E_\pi d(x_0,x_n) $$ be the expectation, with respect to the stationary measure $\pi$, of the distance between the positions $x_0$ and $x_n$ of the simple random walk at times 0 and $n$, respectively. Then $\ell=\lim \ell_n/n$ by the definition of $\ell$. However, the limit of the differences $\ell_{n+1}-\ell_n$ also exists (and therefore must coincide with $\ell$).

For finding $\lim(\ell_{n+1}-\ell_n)$ one has to notice that $\ell_{n+1}$ coincides, by the stationarity of $\pi$, with the expectation of $d(x_{-1},x_n)$. Now, if $x_n\neq x_0$ and the degree of $x_0$ is $\delta$, then the expectation of $d(x_{-1},x_n)-d(x_0,x_n)$ is precisely $(\delta-2)/\delta$. Therefore, by transience of a.e. Galton-Watson tree (I will skip an explanation), one obtains that $$ \ell = \mathbf E_\pi \frac{\delta-2}{\delta}. $$ Since the distribution of the degree $\delta$ of the root with respect to the measure $\pi$ is $p'_k=p_{k-1}$, this is precisely the formula you are asking about.

  • $\begingroup$ @R W i don't understand completely,you say we can consider the space of trees instead of the space of vertices,right? $\endgroup$ – user115608 Aug 21 '16 at 11:33
  • $\begingroup$ @R W , if it is true,what do you mean by : "The simple random walk on TT has a stationary probability measure $\pi $ naturally related to the original branching process."?i don't know that measure. $\endgroup$ – user115608 Aug 21 '16 at 11:35
  • $\begingroup$ This measure is explicitly described in the 3rd paragraph of my answer. Once again: this is the distribution of the random rooted trees obtained in the following way: take a random GW tree, add an edge to its root, and then grow another independent GW tree from the other end of this edge. $\endgroup$ – R W Aug 21 '16 at 12:28
  • $\begingroup$ @R W ok thanks.and what does "Galton-Watson measure" mean exactly?u mean precisely the measure u said in last comment? $\endgroup$ – user115608 Aug 21 '16 at 12:31
  • $\begingroup$ The GW measure on $\mathcal T$ is the distribution of usual Galton-Watson trees (the root being the progenitor). $\endgroup$ – R W Aug 21 '16 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.