I need to generate random ordered unranked trees that will be used to test some computer program. I'd like to incorporate some kind of control into the generation process, so that the generated trees have (in expectation) some desired properies, like: long chains (node with 1 child, its child also has 1 child, ...); or: there are many children on level 3, but not so many on level 1; or: if a node has few children, its children are more likely to have more children, but if it has many children, its children are more likely to have less; etc.

I've chosen this approach: define a tree as a prefix closed set of strings over some alphabet $\Sigma$ such that if $Sc$ is in the set ($S \in \Sigma^{*}$, $c \in \Sigma$), then for all $b \le c, b \in \Sigma$ $Sb$ is in the set. I fix $\Sigma$, and to generate a tree, I generate a few strings over this alphabet, treat them as nodes, and then generate all other nodes from them (by prefix closing the set, etc.)

The node string generation process is done symbol-by-symbol, with symbol on level $l$ generated as follows:

  1. Sample Bernoulli distribution with parameter $1\over d$ to see if we should stop. (That way, expected length of the generated strings is $d$.)
  2. Sample symbol from the distribution $p(s | l, t) = p(s|l)p(s|t)$ where $s\in\Sigma$ is the symbol being generated, $t\in\Sigma$ is the previous generated symbol. Here, $p(s|l)$ and $p(s|t)$ are parameters of the generation process.

I'd like the user of this generation process to specify discrete distribution $p(s|l)$ over symbols from $\Sigma$ for each $l$ using just two parameters: the expected symbol, and variance. (Same for $p(s|t)$ for each $t$.) The motivation is this: say, our symbols are $1,2,...,9$, then symbol $s$ at level $l$ determines the number of nodes at level $l$ under the already-generated node $S$. If we define $p(s|l)$ to be sharply distributed around $3$, in the generated trees nodes at level $l-1$ will in most cases have 3 children, and so on.

Now, to the question. I need a family of functions that will be my $p(s|l)$ and $p(s|t)$, with the following properties:

  1. The function is completely determined by 2 parameters, the first being its mode and the second being variance or something else that has the meaning of how sharp the values are distributed around the mean.
  2. The distribution is easy to sample from. I don't want to depend on some library for that, nor write lots of complicated code. (The overall task is of low priority, but of high curiosity for me.)
  3. The distribution behaves "as expected" if the mode is close to the beginning or end of the alphabet. Specifically, assume again that our symbols are $1,2,...,9$; if the mode is $1$, the function should be strictly decreasing, and if the mode is $5$, it should be symmetric.

Beta-binomial looked similar to what I wanted, but I don't know if there is an easy way to sample from it, and also I'm not that familiar with it to come up with a good second parameter. I'd like to know if there is a simple, well-known distribution with such properties.

  • $\begingroup$ Re. the beta-binomial distribution: It seems to me you can sample from it by just simulating the urn model. You can control the variance by scaling $\alpha$ and $\beta$ while keeping their ratio fixed; variance decreases as $\alpha$ and $\beta$ increase. $\endgroup$ – Rahul Mar 2 '13 at 10:44
  • $\begingroup$ Thanks for your comment! I'm having two problems regarding the beta-binomial distribution. First, I don't know the expression for its mode (and I actually want to specify the mode, not the mean as I originally said.) Second, does the urn model still work if $\alpha$ and $\beta$ are not integer numbers? $\endgroup$ – breader Mar 2 '13 at 19:08
  • $\begingroup$ I'd wager the urn model still works fine; the probability of drawing a red ball is $\alpha/(\alpha+\beta)$ which make sense even for nonintegral $\alpha$ and $\beta$. I don't know any nice way to find the mode, though. $\endgroup$ – Rahul Mar 4 '13 at 9:47
  • $\begingroup$ Yes, I've already implemented it this way. I was a bit worried about the parameter update: when a red ball is observed, the number of red balls in the urn should increase by 1; it's intuitively obvious that the same should hold for non-integer $\alpha$ and $\beta$, however I was a bit unsure. $\endgroup$ – breader Mar 4 '13 at 19:09

Your Answer

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

Browse other questions tagged or ask your own question.