Controlled non uniform random generation of decomposable structures
arXiv:1006.0423 · doi:10.1016/j.tcs.2010.05.010
Abstract
Consider a class of decomposable combinatorial structures, using different types of atoms $\Atoms = \{\At_1,\ldots ,\At_{|{\Atoms}|}\}$. We address the random generation of such structures with respect to a size and a targeted distribution in of its \emph{distinguished} atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by real numbers $\TargFreq_1, \ldots, \TargFreq_k$ such that $0 < \TargFreq_i < 1$ for all and $\TargFreq_1+\cdots+\TargFreq_k \leq 1$. We aim to generate random structures among the whole set of structures of a given size , in such a way that the {\em expected} frequency of any distinguished atom $\At_i$ equals $\TargFreq_i$. We address this problem by weighting the atoms with a -tuple $\Weights$ of real-valued weights, inducing a weighted distribution over the set of structures of size . We first adapt the classical recursive random generation scheme into an algorithm taking $\bigO{n^{1+o(1)}+mn\log{n}}$ arithmetic operations to draw structures from the $\Weights$-weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i. e. for large values of . We derive systems of functional equations whose resolution gives an explicit relationship between $\Weights$ and $\TargFreq_1, \ldots, \TargFreq_k$. Lastly, we give an algorithm in $\bigO{k n^4}$ for the inverse problem, {\it i.e.} computing the frequencies associated with a given -tuple $\Weights$ of weights, and an optimized version in $\bigO{k n^2}$ 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 a natural numbers such that where is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size that contain {\em exactly} atoms $\At_i$ (). We give a $\bigO{r^2\prod_{i=1}^k n_i^2 +m n k \log n}$ algorithm for generating structures, which simplifies into a $\bigO{r\prod_{i=1}^k n_i +m n}$ for regular specifications.