Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. (EDIT: see explanation in J.W.'s answer below.)

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure" [EDIT: corrected, thanks to J.W.'s comment below]. Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Let $T_w$ be the tree of minimal cost, if $w$ is thought of as the cost of an edge. Many constructions are possible. For example, an edge $e$ belongs to $T_w$ if any path between its endpoints ($e$ excluded) contains an edge $e'$ with $w(e')>w(e)$.

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

  • 2
    $\begingroup$ The "minimal measure" is not quite as you describe. I think what you mean is to take the tree of minimal total weight under $w$ (this doesn't in general have the form $\{e\in E : w(e)<x\}$ for any $x$). It is worth pointing out that the resulting distribution on trees doesn't depend on taking the weights from uniform distribution on $[0,1]$, as long as they are i.i.d. An equivalent description is to consider the edges in random uniform order, and "accept" an edge iff it does not form a cycle together with already accepted edges, and "discard" if it does. $\endgroup$ Jul 1 '13 at 18:44
  • $\begingroup$ Of course, thanks for your correction... $\endgroup$
    – ARG
    Jul 1 '13 at 19:12

You might be interested in Loop Erased Random Walks and David Wilson's algorithm, see for instance http://research.microsoft.com/en-us/um/people/schramm/memorial/usf-talk.ps

  • $\begingroup$ Thanks! I could only get a quick look just now, but this seems to completely answers the (bracketed sub-)question on the uniform measure. However, I must confess I fail to see how this helps about the minimal measure. $\endgroup$
    – ARG
    Jul 1 '13 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.