%0 Generic %1 arXiv:math.PR/0611775 %A Alappattu, Jomy %A Pitman, Jim %D 2006 %K author_pitman_from_arxiv %T Colored loop-erased random walk on the complete graph. %U http://arxiv.org/abs/math.PR/0611775 %X 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, ..., N$, we condition the walk to start at $N$ and stop the walk when it first reaches the subset $k$, for some $1 k N-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 $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 $1j N-k$, the events $B_i$ for $1 i j-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 $N ınfty$.

@misc{arXiv:math.PR/0611775, 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, ..., N}$, we condition the walk to start at $N$ and stop the walk when it first reaches the subset $[k]$, for some $1 \leq k \leq N-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 $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 $1\leq j \leq N-k$, the events $B_i$ for $1 \leq i \leq j-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 $N \to \infty$.}, added-at = {2008-01-25T05:29:59.000+0100}, arxiv = {arXiv:math.PR/0611775}, author = {Alappattu, Jomy and Pitman, Jim}, biburl = {https://www.bibsonomy.org/bibtex/2814e0da303a845e421ebdfc0aa713002/pitman}, interhash = {a1fe2a4e564801cd53ac77268e48fa4b}, intrahash = {814e0da303a845e421ebdfc0aa713002}, keywords = {author_pitman_from_arxiv}, timestamp = {2008-01-25T05:33:08.000+0100}, title = {{Colored loop-erased random walk on the complete graph.}}, url = {http://arxiv.org/abs/math.PR/0611775}, year = 2006 }