0
$\begingroup$

I'm looking for closed (possibly approximate) formulae for the following problem.

I am trying to generate (uniformly distributed) random trees of a given size n. The "size" is the number of symbols in the tree, and I have fixed numbers of distinct nullary, unary and binary symbols available. To create a uniform distribution I need to know the number of trees of a certain characteristics, or at least their relative frequencies. "Uniform" means in this case that every possible tree of size n is picked with equal probability.

The trees can be seen as strings of symbols in Polish notation, and instead of just counting the full strings of a fixed size one can count prefixes of those strings with respect to a certain arity (number of holes in a tree, 0 holes is a complete tree). These numbers obey a straightforward recurrence relation: if, at size n, we have $k_0$ tree fragments of arity 0, $k_1$ of arity 1, etc. (write it as n:[$k_0,k_1,k_2,k_3,...$]) then at size n+1 this list becomes: n+1:[$z*k_1,u*k_1+z*k_2,u*k_2+b*k_1+z*k_3,u*k_3+b*k_2+z*k_4,...$], where z,u,b are the numbers of nullary, unary, and binary symbols - because a unary symbol does not change the arity of a tree, binary/nullary make it go up/down by 1, and trees of arity 0 cannot be further extended. For example, trees of arity 0 must have a nullary symbol in last position, so the number of those trees at size n+1 is z times the number of unary trees of size n.

I can use this recurrence to compute precise numbers, but they get huge quickly, and for large n the computation takes very long, as we are talking here arbitrary precision integers and exponential growth. (For n=10000, my computer is huffing and puffing for several minutes to compute those numbers. n=100000 would be hopeless.)

The kind of numbers I need to generate random trees are probabilities such as $\frac{u*k_2}{u*k_2+b*k_1+z*k_3}$, which in this case would be the probability that a prefix string of length n+1 and arity 2 has a unary function symbol in its last position. So, are there closed formulae that describe the numbers of those tree fragments (or their relative proportions)?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Are these labelled or unlabelled trees? The question is, what trees count as "the same" or "different"? $\endgroup$
    – Robert Israel
    Commented Jun 6, 2019 at 16:50
  • 1
    $\begingroup$ I didn't understand the problem in detail, but for practical use it might be sufficient to calculate the number to floating-point precision. $\endgroup$
    – Brendan McKay
    Commented Jun 6, 2019 at 18:09
  • 1
    $\begingroup$ Search for "Boltzmann sampling" for some approximate algorithms. $\endgroup$
    – F. C.
    Commented Jun 6, 2019 at 18:31
  • 1
    $\begingroup$ Assuming your trees are ordered (labeled or not), there is a simple (and very efficient) algorithm to sample them uniformly. See M. D. Atkinson, "Uniform Generation of Rooted Ordered Trees with Prescribed Degrees", The Computer Journal 36 (1993), 593–594. $\endgroup$
    – Timothy Budd
    Commented Jun 7, 2019 at 9:25
  • 1
    $\begingroup$ 10^8000 is not a problem. Use pairs $(d,i)$ where $d$ is double-precision and $i$ is integer. This represents $d\times 10^i$. I do this often. The only question is whether enough precision is maintained. $\endgroup$
    – Brendan McKay
    Commented Jun 7, 2019 at 17:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .