Archive for category arXiv

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