AMS Fall Western Meeting

Tomorrow I’ll be giving a talk at the Fall Western AMS meeting, at UCLA, in Boelter Hall 2444.  The talk is titled “Near-linear time perfect simulation of corrugated surfaces”.

Given a bipartite graph with n nodes, a corrugated surface can be viewed as a vector in [0,1]n such that all nodes in one partition are local maxima, and all the nodes in the other partition are local minima. In order to draw samples from this random landscape, Caracciolo, Rinaldi, and Sportiello (2008) constructed a Markov chain whose stationary distributionwas uniform over the set of corrugated surfaces. They conjectured from experiments that the mixing time of the chain was O(n ln n) for the special case of a square lattice. Here a new Markov chain is presented that provably mixes in O(n ln n) time for all bipartite graphs. Like the Caraccilo, et al. chain, this new chain can also be used with coupling from thepast to obtain samples drawn exactly from the desired distribution. Furthermore, this approach can then be combinedwith randomized cooling schedule methods in order to obtain a 1 + ε approximation (with probability at least 1 – δ) of the corrugated surface volume in time O(n2(ln n)ε-2 ln (1/δ)).

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: