Coloured Loop-Erased Random Walk on the Complete Graph

DOI10.1017/S0963548308009115MaRDI QIDQ3608331zbMATH OpenOpenAlexFDO

Authors Jomy Alappattu, Jim Pitman

Publication date 4 March 2009

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0611775

zbMATH Keywords

independent random variablesrandom lengthcolour patternsdifferently coloured segmentsloop erased walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

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 coloring of these edges by painting edges with a fixed color as long as the walk does not loop back on itself, then switching to a new color whenever a loop is erased, with each new color distinct from all previous colors. The pattern of colors 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,\mathrm{...},N$, we condition the walk to start at $N$ and stop the walk when it first reaches the subset $[k]$, for some $1leqkleqN-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,\mathrm{...}$, let $B_i$ denote the event that the loop-erased walk from $N$ to $[k]$ has $i+1$ or more edges, and the $i^{th}$ and $(i+1{)}^{th}$ of these edges are colored differently. We show that given that the loop-erased random walk has $j$ edges for some $1leqjleqN-k$, the events $B_i$ for $1leqileqj-1$ are independent, with the probability of $B_i$ equal to $1/(k+i+1)$. This determines the distribution of the sequence of random lengths of differently colored segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as $Noinfty$.

Recommendations

• scientific article; zbMATH DE number 1984558
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Loop-erased random walk on finite graphs and the Rayleigh process
• Loop-erased random walks associated with Markov processes
• scientific article; zbMATH DE number 1405906

Cites work

• Loop-erased random walk on finite graphs and the Rayleigh process
• Rayleigh processes, real trees, and root growth with re-grafting
• The continuum random tree. I
• The distance between points in random trees

Cited in

(4)

• Regenerative random permutations of integers
• Generalized loop-erased random walks and approximate reachability
• Loop-erased random walk on finite graphs and the Rayleigh process
• scientific article; zbMATH DE number 1984558 (Why is no real title available?)

This page was built for publication: Coloured Loop-Erased Random Walk on the Complete Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608331)