MCMC Estimation of Set Sizes on the Hypercube

• Activity Number: 247
• Type: Contributed
• Date/Time: Monday, August 1, 2011 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Austen Wallace Head*+
• Companies: Stanford University
• Keywords: hypercube ; sampling ; MCMC ; Metropolis ; graph distributions ; variance reduction

Abstract

Markov chain methods are used to estimate the size of a set (a subset of a hypercube) which has a particular property (i.e. estimate µ=|S| for S={x:T(x)=1,x in O} where T:O?{0,1} is an indicator function and O is a hypercube). Estimates of µ are made by generating samples x in O with probability proportional to exp(T(x)ß) where ß is a parameter that we set to minimize the variance of m our estimate of µ. The estimate m based on r samples has a standard deviation approximately proportional to |O|/r. The Metropolis Hastings algorithm is used to generate samples, and the mixing time between samples to get near independence (based on total variation distance) is bounded as a function of ß and |O|. For small sets this method gives a substantially smaller variance than uniformly sampling on O. In addition to examples validating this methodology we show how this technique can be extended to problems which we do not already know how to answer. In graphs with n labelled vertices, this technique is used to estimate the distribution of the number of graphs with k triangles. Methodology is developed using this technique to estimate the how close an observed graph is to a threshold graph.