Archive for category AMS
I would like to congratulate Jason Xu, who worked with me this past summer during the Claremont REU. He presented a poster at the Joint Math Meetings this month in New Orleans, talking about the work on perfect simulation for spatial point processes that he did with Elise McCall and Daniel Rozenfeld. His poster won the prize for best poster in Probability & Statistics. Congratulations, Jason!
Update: The list of this year’s poster prizes (including Jason’s) can be found at http://www.maa.org/students/undergrad/pastwinners.html
The AMS meeting was an exciting two days. My talk (which can be downloaded here) went over well, and there was a lot of exciting stuff going on. This includes several sessions organized by folks from Microsoft Research. Allan Sly has brought the upper bound on the computational threshold for the hard core gas model down to meet the lower bound (see here.) My third published paper was on generating random variates from this model, so I was excited to see this result.
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/δ)).