Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-04T19:45:19.695Z Has data issue: false hasContentIssue false

Coloured Loop-Erased Random Walk on the Complete Graph

Published online by Cambridge University Press:  01 November 2008

JOMY ALAPPATTU
Affiliation:
Department of Mathematics, University of California at Berkeley, 970 Evans Hall, Berkeley, CA 94720-3840, USA (e-mail: [email protected])
JIM PITMAN
Affiliation:
Department of Statistics, University of California at Berkeley, 367 Evans Hall, Berkeley, CA 94720-3860, USA (e-mail: [email protected])

Abstract

Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from i to j if the loop-erased walk makes a step from i to j. We introduce a colouring of these edges by painting edges with a fixed colour as long as the walk does not loop back on itself, then switching to a new colour whenever a loop is erased, with each new colour distinct from all previous colours. The pattern of colours along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on [N] := {1, 2, . . ., N}, we condition the walk to start at N and stop the walk when it first reaches the subset [k], for some 1 ≤ kN − 1. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayley's enumerations of trees, and via Wilson's algorithm. For fixed N and k, and i = 1, 2, . . ., let Bi denote the events that the loop-erased walk from N to [k] has i + 1 or more edges, and the ith and (i + 1)th of these edges are coloured differently. We show that, given that the loop-erased random walk has j edges for some 1 ≤ jNk, the events Bi for 1 ≤ ij − 1 are independent, with the probability of Bi equal to 1/(k + i + 1). This determines the distribution of the sequence of random lengths of differently coloured segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as N → ∞.

Type
Paper
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. J. (1991) The continuum random tree I. Ann. Probab. 19 128.CrossRefGoogle Scholar
[2]Camarri, M. and Pitman, J. (2000) Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab. 5 118.CrossRefGoogle Scholar
[3]Durrett, R. (1996) Probability: Theory and Examples, Duxbury.Google Scholar
[4]Evans, S., Pitman, J. and Winter, A. (2006) Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Rel. Fields 134 81126.CrossRefGoogle Scholar
[5]Feller, W. (1966) An Introduction to Probability Theory and Its Applications, Vol. 2, Wiley.Google Scholar
[6]Lawler, G. F. (1991) Intersections of Random Walks, Birkhäuser.Google Scholar
[7]Lyons, R. and Peres, Y. (2003) Probability on Trees and Networks, Cambridge University Press. In preparation. Current version available at http://php.indiana.edu/~rdlyons/.Google Scholar
[8]Meir, A. and Moon, J. W. (1970) The distance between points in random trees. J. Combin. Theory 8 99103.CrossRefGoogle Scholar
[9]Pittel, B. Note on exact and asymptotic distributions of the parameters of the loop-erased random walk on the complete graph. In Mathematics and Computer Science II (Versailles 2002), Trends in Mathematics, Birkhäuser.CrossRefGoogle Scholar
[10]Wilson, D. B. (1996) Generating random spanning trees more quickly than the cover time. In Proc. 28th Annual ACM Symposium on the Theory of Copmputing, ACM, pp. 296303.Google Scholar
[11]Schweinsberg, J. (2008) Loop-erased random walk on finite graphs and the Rayleigh process. J. Theoret. Probab. 21 378396.CrossRefGoogle Scholar