Perturbing trees

Question

I have a collection of labelled directed trees, and from these input trees I would like to generate permuted trees that have the same node set but whose edges and labels have been permuted with some probability $p$, such that if $p=0$ the output trees are identical and if $p=1$ the trees are random. The string version of this would be that each character in the string is replaced with a random character with probability $p$. Is there an established algorithm for this task?

My current best effort is to traverse the nodes of the tree in either post order or reverse breadth-first order and for each node with probability $p$ find a new parent node for it, with the candidate set being the nodes that are not descendants of the node (they can't be the parent of the node as this would create a cycle), but I'm pretty sure both of these options are not the correct ones.

EDIT: More specifically, I would like the trees at $p=1$ to be drawn from the same distribution as if we draw a tree uniformly at random from the set of possible trees over the node set (I know this is problematic due to this number generally being bigger than the period of most random number generators, but let's leave that for now). My intuition here (which is likely overly simplistic, but might be useful) is that I'd like to create a kind of linear interpolation between the input tree and a tree drawn uniformly at random from the set of all possible trees over the node set. Of course, linear interpolation doesn't make an awful lot of sense between trees (as far as I can figure it out

The trees represent natural language syntactic analyses (dependency trees, for those familiar with NLP) where the nodes are the words of the sentence, and I am generating the perturbed trees as controlled simulations of errors made by human annotators when describing the syntactic structure of sentences to evaluate metrics for measuring annotator agreement. I know the permutation I have (post-order traversal, selecting a new parent uniformly at random from the set of non-descendants of the target) is wrong because if I assign new parents to every single node ($p = 1$) and create two trees, a bit more than 20% of nodes have matching heads whereas labels match lot of sense between trees (as far as I can figure it out, anyways), so the formulation as perturbation of the input tree has been more fruitful for me so far.

The trees represent natural language syntactic analyses (dependency trees, for those familiar with NLP) where the nodes are the words of the sentence, and I am generating the perturbed trees as controlled simulations of errors made by human annotators when describing the syntactic structure of sentences to evaluate metrics for measuring annotator agreement. I know the permutation I have (post-order traversal, selecting a new parent uniformly at random from the set of non-descendants of the target) is wrong because if I assign new parents to every single node ($p = 1$) and create two trees, a bit more than 20% of nodes have matching heads whereas labels on the edge to the parent match on only about 4% of nodes. So I'm clearly sampling less uniformly for tree structure than for labels, since the sample space for trees is far larger than for labellings.

Answer 1

What you need is a Markov chain on the set of labelled directed trees, whose stationary distribution is the uniform distribution. You might be able to find such a Markov chain in the literature. It is then natural to run this chain, starting from your given tree, for $T$ steps, where $T$ has Poisson distribution with expectation $-\log(1-p)$ (say). Notice that when $p = 0$ you just get your original tree back, and when $p \to 1$ you run the chain for many steps, and so you get an almost uniform sample.

Why use the specific distribution $\operatorname{Poisson}(-\log(1-p))$? The Poisson distribution here describes the outcome of a Poisson process with a certain rate. The parameter $-\log(1-p)$ interpolates between your two values, and is similar to the noise operator in analysis of Boolean functions. However, since you haven't defined semantics for $p$, this is an arbitrary choice.