| This thesis addresses the question of how a theorem characterizing a combinatorial structure can be used to assist with generating random instances of the structure. Efficient sequential importance sampling algorithms for many such problems, such as generating random graphs with given degrees, connected graphs with given degrees, directed graphs (digraphs) with given indegrees and outdegrees, and tournaments with given scores, are presented and analyzed. The algorithms are proven to generate only the desired structures (and to be supported on the entire space of interest), and the methodology of designing such algorithms is studied. Unlike classical backtracking algorithms, the theory guarantees that the algorithms never get stuck, avoiding the extra computational effort needed in algorithms where one often has to restart or retrace one's steps.; In these algorithms, the characterization theorems are used to guide the algorithm towards the desired output, while at the same time sequential importance sampling is used to allow for estimation of expected values and probabilities with respect to a desired target distribution. A new variant of importance sampling is developed, in which estimation problems on the blocks of a partition of a space are lifted to the space itself. Applications such as estimating the size of a large state space and testing a natural exponential model are given. |
