Statistics and Its Interface

Volume 11 (2018)

Number 4

Sampling strategies for conditional inference on multigraphs

Pages: 649 – 656



Robert D. Eisinger (Department of Mathematics, Statistics, and Computer Science, St. Olaf College, Northfield, Minnesota, U.S.A.)

Yuguo Chen (Department of Statistics, University of Illinois, Urbana-Champaign, Il., U.S.A.)


We propose two new methods for sampling undirected, loopless multigraphs with fixed degree. The first is a sequential importance sampling method, with the proposal based on an asymptotic approximation to the total number of multigraphs with fixed degree. The multigraphs and their associated importance weights can be used to approximate the null distribution of test statistics and additionally estimate the total number of multigraphs. The second is a Markov chain Monte Carlo method that samples multigraphs based on similar moves used to sample contingency tables with fixed margins.We apply both methods to a number of examples and demonstrate excellent performance.


counting problem, exact test, Monte Carlo method, multigraph, sequential importance sampling, symmetric contingency table

Y. Chen was partially supported by the NSF grant DMS-1406455.

Received 15 January 2017

Published 19 September 2018