7
$\begingroup$

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am interested in the distribution of the length of the cycle $C$, i.e. the random variable $|C|$.

Section 5 of https://arxiv.org/pdf/1106.2226.pdf describes a lower bound on the probability that this cycle is at most $g$, where $g$ is a number such that every edge in $G$ lies on a cycle of length at most $g$.

(I also don't understand their claim that $$P( \text{the cycle in the $UST^+$ has length} \leq g) \geq \frac{1}{d(d-1)^{g - 2}},$$ and I would appreciate it if someone could give a hint on how to derive that from the correctness of Wilson's algorithm.) Resolved (I think) by Ben Barbers comment.

Are more precise statistics of this distribution known?

It seems that the distribution of the length of a LERW between two adjacent vertices of $G$ is very closely related to this problem. I would appreciate any information about that.

Some updates:

From this post Perimeters of random-walk polygons I learned about this paper https://journals.aps.org/pre/abstract/10.1103/PhysRevE.55.R2093 , which mentions that $|C|$ is expected to follow a power law. This is consistent with the experiments I conducted.

They relate the power law to certain scaling limit computations.

This paper argues (through what seems to be exact computation for small cases and then by computer simulation) about the distribution of the cycle in the square lattice: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.46.R4471

They also say that the burning time distribution can be used to easily compute the distribution of loops.

I don't follow most of what they are saying, but I'll study their methods.

Improve this question
$\endgroup$
4
  • $\begingroup$ For the parenthetical question, the right-hand side of the inequality is a lower bound on the probability that a random walk in $G$ follows a particular route in its first $g-1$ steps. So if you imagine running Wilson's algorithm starting from the endpoints of $e$, there is at least this probability of immediately putting the rest of any fixed cycle of length $g$ containing $e$ into $T$. This isn't a complete explanation, as you then need some way to handle the fact that you are not in fact choosing $e$ first. $\endgroup$
    – Ben Barber
    Commented Sep 23, 2018 at 12:18
  • $\begingroup$ @BenBarber Thanks, I think I understand. The same lower bound holds for the LERW from e^+ until e^-, since it has at least this probability of walking along that partial cycle and not having any loop erasures. (It will be larger than the SRW probability, as it can walk along a path that gets loop erased, and then continue to make this partial cycle.) So for each edge (there are no bridges), there is at least that given probability that a UST T from G-e contains a partial cycle of length at most g through that is completed by adding e. $\endgroup$
    – Elle Najt
    Commented Sep 23, 2018 at 21:26
  • $\begingroup$ We draw our random spanning tree with extra (marked) edge by picking an edge (weighted by # of spanning trees not containing that edge) and then a UST that does not contain that edge, using Wilson's algorithm with starting nodes the endpoints of e on G - e. For each edge, the probability that the tree makes a cycle of length at most g through is bounded below by the given quantity, so the same holds when we average over all edges. $\endgroup$
    – Elle Najt
    Commented Sep 23, 2018 at 21:27
  • $\begingroup$ So I think it should be possible to rephrase my question as asking about computing the distribution of the length of a LERW between two adjacent vertices. $\endgroup$
    – Elle Najt
    Commented Sep 23, 2018 at 21:35

0

Reset to default

You must log in to answer this question.