Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Random walks on the two dimensional uniform spanning tree

Speaker  Robert Masson

Affiliation  University of British Columbia

Host  Yuval Peres

Duration  00:56:01

Date recorded  29 April 2010

We study random walks on the uniform spanning tree (UST) on Z2. We obtain estimates for the transition probabilities of the random walk, the distance of the walk from its starting point after n steps, and exit times of both Euclidean balls and balls in the intrinsic graph metric. In particular, we prove that the spectral dimension of the uniform spanning tree on Z2 is 16/13 almost surely.

In order to prove these results, we use the work of Barlow, Jarai, Kumagai, Misumi and Slade on random walks on random graphs which implies that it suffices to establish volume and effective resistance bounds for the UST. Using Wilson's algorithm, we show that this reduces to obtaining estimates on the number of steps of loop-erased random walks (LERW) in subsets of Z2. If we let Mn be the number of steps of a LERW from the origin to the circle of radius n, then Kenyon showed that E[Mn] is logarithmically asymptotic to n5/4. In addition to this fact, we need to show that with high probability, Mn is close to its mean. In fact, we will obtain exponential moment bounds for Mn which implies that the tails of Mn decay exponentialy.

Joint work with Martin Barlow

©2010 Microsoft Corporation. All rights reserved.
> Random walks on the two dimensional uniform spanning tree