Archive for November, 2010

Attending Joint Math Meetings in 2011

I’ll be attending the Joint Mathematics Meetings in New Orleans next January.  It’s going to be a busy time!

Perhaps the most important task I will have relates to the open positions at Claremont McKenna.  We have two searches this year, one in applied math and one in statistics.  I am on both committees, so will be interviewing as many people as possible.

In addition I am also on a panel:  “What I wish I had known before applying for a job.” which is scheduled for 2:45-4:15p.m. on Friday, January 7th, 2011 in Mardi Gras EFGH, 3rd Floor, Marriott.

To help launch the Journal of Humanistic Mathematics, I am coorganizing with Gizem Kaarali and Dagan Karp two sessions at JMM.  The first is Saturday January 8, 2011, 1:00 p.m.-6:00 p.m MAA Session on Humanistic Mathematics, I @ Mardi Gras BC, 3rd Floor, Marriott.  The second is Sunday January 9, 2011, 1:00 p.m.-6:00 p.m., MAA Session on Humanistic Mathematics, II @ Mardi Gras BC, 3rd Floor, Marriott

Finally, I am giving a talk on Sunday January 9, 2011, 10:30 a.m. AMS Session on Probability, I, @ Bayside B, 4th Floor, Sheraton. The talk is Using TPA to count linear extensions. and is based on the summer REU work that I did with Jacqueline Banks, University of California, Riverside, Scott Garrabrant, Pitzer College, and Anne Perizzolo, Columbia University.

Hope to see you there!

Leave a comment

Second REU paper up on the archive

The second paper to come out of the REU I ran this summer is now up on the arXiv here.  This paper brings a discrete problem:  counting the number of linear extensions of a partially ordered set into a continuous framework so that TPA can be utilized.  This paper has been submitted.

Title:  Using TPA to count linear extensions

(Submitted on 24 Oct 2010)

A linear extension of a poset $P$ is a permutation of the elements of the set that respects the partial order. Let $L(P)$ denote the number of linear extensions. It is a #P complete problem to determine $L(P)$ exactly for an arbitrary poset, and so randomized approximation algorithms that draw randomly from the set of linear extensions are used. In this work, the set of linear extensions is embedded in a larger state space with a continuous parameter ?. The introduction of a continuous parameter allows for the use of a more efficient method for approximating $L(P)$ called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing $n$ elements, this means we can approximate $L(P)$ to within a factor of $1 + \epsilon$ with probability at least $1 – \delta$ using an expected number of random bits and comparisons in the poset which is at most $O(n^3(ln n)(ln L(P))\epsilon^{-2}\ln \delta^{-1}).$


Leave a comment

Posted a paper up on the arXiv

The work that I did with the Claremont REU students has now started to be submitted.  The first paper is about perfect simulation from the hard core gas model.  In the dominated coupling from the past algorithm, there is an artificial phase transition where below a certain point the algorithm is slow and above the point the algorithm is fast.  Elise, Daniel, and Jason worked on pinning down this artificial phase transition through theory and experiment.  Not everything we tried panned out, but some things did work, and led to some improvements in the paper below.  You can find it here.

Title:  Bounds on the artificial phase transition for perfect simulation of repulsive point processes


Repulsive point processes arise in models where competition forces entities to be more spread apart than if placed independently. Simulation of these types of processes can be accomplished using dominated coupling from the past with a running time that varies as the intensity of the number of points. These algorithms usually exhibit what is called an artificial phase transition, where below a critical intensity the algorithm runs in finite expected time, but above the critical intensity the expected number of steps is infinite. Here the artificial phase transition is examined. In particular, an earlier lower bound on this artificial phase transition is improved by including a new type of term in the analysis. In addition, the results of computer experiments to locate the transition are presented.

Leave a comment