Controlled non-uniform random generation of decomposable structures

Consider a class of decomposable combinatorial structures, using different types of atoms Z=Z1,...,Z|Z|. We address the random generation of such structures with respect to a size n and a targeted distribution in k of its distinguished atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by k real numbers μ1,...,μk such that 0<μi<1 for all i and μ1+⋯+μk≤ 1. We aim to generate random structures among the whole set of structures of a given size n, in such a way that the expected frequency of any distinguished atom Zi equals μi. We address this problem by weighting the atoms with a k-tuple π of real-valued weights, inducing a weighted distribution over the set of structures of size n. We first adapt the classical recursive random generation scheme into an algorithm taking O(n1+o(1)+mnlogn) arithmetic operations to draw m structures from the π-weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i.e. for large values of n. We derive systems of functional equations whose resolution gives an explicit relationship between π and μ1,...,μk. Lastly, we give an algorithm in O(kn4) for the inverse problem, i.e. computing the frequencies associated with a given k-tuple π of weights, and an optimized version in O(kn2) in the case of context-free languages. This allows for a heuristic resolution of the weights/frequencies relationship suitable for complex specifications. In the second alternative, the targeted distribution is given by k natural numbers n1,...,nk such that n1+⋯+nk+r=n where r<0 is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size n that contain exactly ni atoms Zi (1≤i≤k). We give a O(r2∏i= 1kni2+mnklogn) algorithm for generating m structures, which simplifies into a O(r∏i=1kni+mn) for regular specifications.