Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications of Mark Huber    :chronological  alphabetical  combined listing:

%% Papers Published   
   Author = {M. Huber},
   Title = {Perfect simulation with exponential tails},
   Journal = {Random Structures and Algorithms},
   Volume = {33},
   Number = {1},
   Pages = {29--43},
   Publisher = {Wiley InterScience},
   Year = {2008},
   Month = {August},
   Abstract = {Monte Carlo algorithms typically need to generate random
             variates from a probability distribution described by an
             unnormalized density or probability mass function. Perfect
             simulation algorithms generate random variates exactly from
             these distributions, but have a running time T that is
             itself an unbounded random variable. This paper shows that
             commonly used protocols for creating perfect simulation
             algorithms, such as Coupling From the Past can be used in
             such a fashion that the running time is unlikely to be very
             much larger than the expected running time.},
   Key = {fds147643}

   Author = {M. Huber and J. Law},
   Title = {Fast approximation of the permanent for very dense
   Pages = {681--689},
   Booktitle = {Proceedings of the nineteenth annual ACM-SIAM Symposium on
             Discrete Algorithms},
   Publisher = {SIAM},
   Address = {Philadelphia, PA, USA},
   Year = {2008},
   Abstract = {Approximation of the permanent of a matrix with nonnegative
             entries is a well studied problem. The most successful
             approach to date for general matrices uses Markov chains to
             approximately sample from a distribution on weighted
             permuations, and Jerrum, Sinclair, and Vigoda developed such
             a method they proved runs in polynomial time in the input.
             The current bound on the running time of their method is
             O(n^7(ln n)^4). Here we present a very different approach
             using sequential acceptance/rejection, and show that for a
             class of very dense problems, this method has an O(n^4 ln n)
             running time. In the process we prove a more general form of
             Bregman's theorem that applies not just to 0-1 matrices, but
             ot any matrix with entries in [0,1].},
   Key = {fds146748}

   Author = {M. Huber},
   Title = {Perfect simulation for image restoration},
   Journal = {Stochastic Models},
   Volume = {23},
   Number = {3},
   Pages = {475--487},
   Publisher = {Taylor and Francis},
   Year = {2007},
   Month = {August},
   Abstract = {The coupling method has been an enormously useful tool for
             studying the mixing time of Markov chains and as the basis
             of perfect sampling algorithms such as Coupling From the
             Past. Several methods such as Wilson's layered multishift
             coupling and Breyer and Roberts' catalytic coupling have
             been introduced to use the coupling approach on continuous
             state spaces. This work builds upon these approaches by
             using a simple coupling for small Metropolis moves together
             with catalytic coupling. As an application, the analysis of
             the Autonormal model in the Wasserstein metric of A. Gibbs
             is extended to an analysis in total variation distance.
             Moreover, a perfect sampling algorithm is constructed that
             provably runs in $O(N \ln N)$ time for fixed values of the
             parameters of the model.},
   Key = {fds70713}

   Author = {D. Hearn and M. Huber},
   Title = {The Ancestral Distance test: A topdown approach to detect
             correlated evolution in large lineages with missing
             character data and incomplete phylogenies},
   Journal = {Systematic Biology},
   Volume = {55},
   Number = {5},
   Pages = {803--817},
   Publisher = {Taylor & Francis},
   Year = {2006},
   Month = {October},
   Abstract = {We present the ancestral distance test, a new test to detect
             correlated evolution between two binary traits. It is
             appropriate for use with phylogenies that lack resolved
             subclades, branch lengths, and/or comparative data. We
             define the ancestral distance as the time separating a
             randomly sampled taxon from its most recent common ancestor
             (MRCA) that has one or more descendants possessing an
             independent trait. The sampled taxon either has (target
             sample) or lacks (non-target sample) a dependent trait.
             Modeled as a Markov process, we show that the distribution
             of ancestral distances for the target sample is identical to
             the non-target sample when characters are uncorrelated,
             whereas ancestral distances are smaller on average for the
             target sample when characters are correlated. Simulations
             suggest that the ancestral distance can be estimated using
             the time, total branch length, taxonomic rank, or number of
             speciation events between a sampled taxon and the MRCA.
             These results are shown to be robust to deviations from
             Markov assumptions. We also provide a Monte Carlo technique
             to estimate p-values when full resolved phylogenies with
             branch lengths are available. Software is available from
             Hearn. We apply this Monte Carlo approach to a published
             data set.},
   Key = {fds69199}

   Author = {M. Huber and Y. Chen and I. Dinwoodie and A. Dobra and M.
   Title = {Monte Carlo algorithms for Hardy-Weinberg
   Journal = {Biometrics},
   Volume = {62},
   Number = {1},
   Pages = {49--53},
   Publisher = {Blackwell Synergy},
   Year = {2006},
   Month = {March},
   Abstract = {The Hardy-Weinberg law is among the most important
             principles in the study of biological systems (Crow, 1988,
             Genetics 119, 473--476). Given its importance, many tests
             have been devised to determines whether a finite population
             folows Hardy-Weinberg proportions. Because asymptotic tests
             can fail, Guo and Thompson (1992, Biometrics 48, 361--372)
             devloped an exact test; unfortunately, the Monte Carlo
             method they proposed to evaluate their test has a running
             time that grows linearly in the size of the population N.
             Here, we propose a new algorithm whose expected running time
             is linear in the size of the table produced, and completely
             independent of N. In practice, this new algorithm can be
             considerably faster than the original method.},
   Key = {fds47824}

   Author = {Mark L. Huber},
   Title = {Fast perfect sampling from linear extensions},
   Journal = {Discrete Mathematics},
   Volume = {306},
   Pages = {420--428},
   Publisher = {Elsevier},
   Year = {2006},
   Abstract = {In this paper we study the problem of sampling (exactly)
             uniformly from the set of linear extensions of an arbitrary
             partial order. Previous Markov chain techniques have yielded
             algorithms that generate approximately uniform samples. Here
             we create a bounding chain for one such Markov chain, and by
             using a non-Markovian coupling together with a modified form
             of coupling from the past, we build an algorithm for
             perfectly generating samples. The expected running time of
             the procedure is $O(n^3 \ln n)$, making the technique as
             fast than the mixing time of the Karzanov/Khachiyan chain
             upon which it is based.},
   Key = {fds47822}

   Author = {M. Huber},
   Title = {Exact sampling from perfect matchings in dense regular
   Journal = {Algorithmica},
   Volume = {44},
   Pages = {183--193},
   Publisher = {Springer Science+Business Media, Inc.},
   Year = {2006},
   Abstract = {e present the first algorithm for generating random variates
             exactly uniformly from the set of perfect matchings of a
             bipartite graph with a polynomial expected running time over
             a nontrivial set of graphs. Previous Markov chain results
             obtain approximately uniform variates for arbitrary graphs
             in polynomial time, but their running time is Θ(n^10 (ln
             n)^2). Other algorithms (such as Kasteleyn's O(n^3)
             algorithm for planar graphs) concentrated on restricted
             versions of the problem. Our algorithm employs
             acceptance/rejection together with a new upper limit on the
             permanent of a form similar to Bregman's theorem. For graphs
             with 2n nodes, where the degree of every node is γn for a
             constant γ, the expected running time is O(n^{1.5 +
             .5/γ}). Under these conditions, Jerrum and Sinclair showed
             that a Markov chain of Broder can generate approximately
             uniform variates in Θ(n^{4.5 + .5 / γ} ln n) time, making
             our algorithm significantly faster on this class of graphs.
             The problem of counting the number of perfect matchings in
             these types of graphs is #P complete. In addition, we give a
             1 + σ approximation algorithm for finding the permanent of
             0-1 matrices with identical row and column sumns that runs
             in &O(n^{1.5 + .5/γ} (1 / σ^2) ln (1 / σ)) time, where
             the probability that the output is within 1 + σ of the
             permanent is at least 1 - &delta.},
   Key = {fds47823}

   Author = {B. P. Tighe and J. E.S. Socolar and D.G. Schaeffer and W. G.
             Mitchener and M. L. Huber},
   Title = {Force distributions in a triagonal lattice of rigid
   Journal = {Physical Review E},
   Volume = {72},
   Number = {031306},
   Publisher = {APS Journals},
   Year = {2005},
   url = {},
   Abstract = {We study the uniformly weighted ensemble of force balanced
             configurations on a triangular isotropic compressive stress,
             we find that the probability distribution for
             single-contract forces decays faster than exponentially.
             This super-exponential decay persists in lattice diluted to
             the rigidity percolation threshold. On the other hand, for
             anisotropic imposed stresses, a broader tail emerges in the
             force ditstirubiton, becoming a pure exponential in the
             limit of infinite lattice size and infinitely strong
   Key = {fds44038}

   Author = {Yuguo Chen and Ian Dinwoodie and Adrian Dobra and Mark
   Title = {Lattice Point, contingency tables and sampling},
   Journal = {Contemporary Mathematics},
   Volume = {374},
   Pages = {65--78},
   Publisher = {American Mathematical Society},
   Year = {2005},
   Abstract = {Markov chains and sequential importance sampling (SIS) are
             described as two leading sampling methods for Monte Carlo
             computations in exact conditional inference on discrete data
             in contingency tables. Examples are explained from genotype
             data analysis, graphical models, and logistic regression. A
             new Markov chain and implementation of SIS are described for
             logistic regression.},
   Key = {fds38507}

   Author = {Mark Huber},
   Title = {Perfect sampling using bounding chains},
   Journal = {The Annals of Applied Probability},
   Volume = {14},
   Number = {2},
   Pages = {734--753},
   Publisher = {Institute of Mathematical Statistics},
   Year = {2004},
   Month = {August},
   Abstract = {Bounding chains are a technique that offers three benefits
             to Markov chain practitioners: a theoretical bound on the
             mixing time of the chain under restricted conditions,
             experimental bounds on the mixing time of the chain that are
             provably accurate, and construction of perfect sampling
             algorithms when used in conjunction with protocols such as
             coupling from the past. Perfect sampling algorithms generate
             variates exactly from the target distribution without the
             need to know the mixing time of a Markov chain at
   Key = {fds29377}

   Author = {M. Huber and G. Reinert},
   Title = {The Stationary Distribution in the Antivoter Model: Exact
             Sampling and Approximations},
   Pages = {79--94},
   Booktitle = {Stein's Method: Expository Lectures and Applications},
   Year = {2004},
   Abstract = {The antivoter model is a Markov cahin on regular graphs
             which has a unique stationary distribution, but is not
             reversible. This makes the stationary distribution difficult
             to describe. Despite the fact that in general nothing is
             known about the stationary distribution other than it exists
             and is unique, we present a method for sampling exactly from
             this distirubiton. The method has running time O(n^3r/c),
             where n is the number of nodes in the graph, c is the size
             of the minimum cut in the graph, and r is the degree of each
             node in the graph. We also show that the original chain has
             O(n^3r/c) mixing time. For the antivoter model on the
             complete graph we derive a closed form solution for the
             stationary distribution. Moreover, we bound the total
             variation distance between the stationary distribution for
             the antivoter model on multipartite graph and the stationary
             distirubiton on the complete graph.},
   Key = {fds41201}

   Author = {Y. Chen and I. Dinwoodie and A. Dobra and M. Huber},
   Title = {Lattice points, contingency tables, and sampling},
   Journal = {6th SIAM Conference on Dynamical Systems},
   Year = {2003},
   Key = {fds41202}

   Author = {Mark L. Huber},
   Title = {A bounding chain for Swendsen-Wang},
   Journal = {Random Structures and Algorithms},
   Volume = {22},
   Number = {1},
   Pages = {53--59},
   Year = {2002},
   Abstract = {The greatest drawback to Monte Carlo Markov chain methods is
             lack of knowledge of the mixing time of the chain. The use
             of bounding chains solves this difficulty for some chains by
             giving theoretical and experimental upper bounds on the
             mixing time. Moreover, when used with methodologies such as
             coupling from the past, bounding chains allow the user to
             take samples drawn exactly from the stationary distribution
             without knowledge of the mixing time. Here we present a
             bounding chain for the Swendsen-Wang process. The
             Swendsen-Wang bounding chain allows us to efficiently obtain
             exact samples from the ferromagnetic Q-state Potts model for
             certain classes of graphs. Also, by analyzing this bounding
             chain we show that Swendsen-Wnag is rapidly mixing over a
             larger range of parameters than was known
   Key = {fds14018}

   Author = {J. A. Fill and M. L. Huber},
   Title = {The Randomness Recycler approach to perfect
   Journal = {53rd Annual Meeting of the ISI},
   Pages = {69--72},
   Year = {2001},
   Abstract = {This is a short abstract for an invited talk at the 53rd
             Annual Meeting of the International Statistical Institute.
             It outlines the main ideas behind the Randomness Recycler
             approach to perfect sampling.},
   Key = {fds10156}

   Author = {A. Benjamin and M. Huber and M. Fluet},
   Title = {Optimal Token Allocations in Solitaire Knock 'm
   Journal = {The Electronic Journal of Combinatorics},
   Volume = {8},
   Number = {2},
   Pages = {1--8},
   Year = {2001},
   Abstract = {In the game Knock 'm Down, tokens are placed in N bins. At
             each step of the game, a bin is chosen at random according
             to a fixed probability distribution. If a token remains in
             that bin, it is removed. When all the token have been
             removed, the player is done. In the solitaire version of
             this game, the goal is to minimize the expected number of
             moves needed to remove all the tokens. Here we present
             necessary conditions on the number of tokens needed for each
             bin in an optimal solution, leading to an asymptotic
   Key = {fds10384}

   Author = {James A. Fill and Mark L. Huber},
   Title = {The Randomness Recycler: A new technique for perfect
   Journal = {Proceeding of the 41th Annual IEEE Symposium on the
             Foundations of Computer Science},
   Year = {2001},
   Abstract = {The Randomness Recycler is an entirely new appraoch to
             generation of samples from high dimensional distributions.
             In RR the sample is built up one dimension at a time in such
             a way that the sample comes from the desired distribution
             restricted to the current set of dimensions. While not
             universally applicable, the RR technique applies in a wide
             variety of problems, giving the first linear time algorithms
             for many problems of interest.},
   Key = {fds10387}

   Author = {Mark L. Huber},
   Title = {A faster method for sampling independent
   Journal = {Proceedings of the 11th Annual ACM-SIAM Symposium on
             Discrete Algorithms},
   Pages = {624-626},
   Year = {2000},
   Abstract = {In the hard core gas model from statistical physics, the
             goal is to sample from a weighted distribution of
             independent sets of a graph. The probability of choosing a
             particular independent set is proportional to a parameter k
             raised to the size of the independent set. Currently, a
             Markov chain of Dyer and Greenhill is known to be mixing
             over the widest ranges of k. In this paper, it is shown how
             to use bounding chains and coupling from the past to
             generate exactly random samples from the hard core gas model
             using the Dyer/Greenhill chain.},
   Key = {fds10388}

   Author = {Stephen Ahearn and Mark L. Huber and Gary Sherman},
   Title = {Finite groups can be arbitrarily Hamiltonian},
   Journal = {Communications in Algebra},
   Volume = {27},
   Number = {3},
   Pages = {1013--1016},
   Year = {1999},
   Abstract = {In finite groups that are not abelian, at most 3/4 of pairs
             of elements will commute. A natural question is whether this
             gap extends to measures of "Hamiltonianess". In fact, this
             paper shows that for any rational number r between 0 and 1,
             there exist groups where the probability that a subgroup
             chosen uniformly at random from the set of subgroups is
             normal is exactly r. The proof technique was suggested
             through computer experimentation.},
   Key = {fds10391}

   Author = {M. Huber},
   Title = {Exact Sampling and Approximate Counting Techniques},
   Journal = {Proc. 30th ACM Symposium on Theory of Computing},
   Pages = {31--40},
   Year = {1998},
   Abstract = {We present two algorithms for uniformly sampling from the
             proper colorings of a graph using k colors. We use exact
             sampling from the stationary distribution of a Markov chain
             with states that are the k-colorings of a graph with maximum
             degree Delta. As opposed to approximate sampling algorithms
             based on rapid mixing, these algorithms have termination
             criteria that allow them to stop on some inputs much more
             quickly than in the worst case running time bound. For the
             first algorithm we show that when k > Delta*(Delta + 2), the
             algorithm has an upper limit on the expected running time
             that is polynomial. For the second algorithm we show that
             for k > r*Delta, where r is an integer that satisfies r^r >
             n, the running time is polynomial. Previously, Jerrum showed
             that it was possible to approximately sample uniformly in
             polynomial time from the set of k-colorings when k >=
             2*Delta, but our algorithm is the first polynomial time
             exact sampling algorithm for this problem. Using aprpoximate
             sampling, Jerrum also showed how to approximately count the
             number of k-colorings. We give a new procedure for
             approximately counting the number of k-colorings that
             improves the running time of the procedure of Jerrum by a
             factor of (m/n)^2 when k >= 2*Delta, where n is the number
             of nodes in the graph to be colored and m is the number of
             edges. In addition, we present an improved analysis of the
             chain of Luby and Vigoda for exact sampling from the
             independent sets of a graph. Finally, we present the first
             polynomial time method for exactly sampling from the sink
             free orientations of a graph. Bubley and Dyer showed how to
             approximately sample from this state space in Theta(m^3 ln
             (epsilon^(-1)) time, our algorithms takes O(m^4) expected
   Key = {fds70394}

%% Papers Accepted   
   Author = {M. Huber},
   Title = {Spatial point processes},
   Booktitle = {Handbook of MCMC},
   Editor = {Brooks, Gelman and Jones, Meng},
   Year = {2008},
   Month = {April},
   Key = {fds148510}

   Author = {D. B. Woodard and S. C. Schmidler and M. Huber},
   Title = {Conditions for Rapid Mixing of Parallel and Simulated
             Tempering on Multimodal Distributions},
   Journal = {Annals of Applied Probability},
   Year = {2007},
   Key = {fds148507}

%% Papers Submitted   
   Author = {M. L. Huber and R. L. Wolpert},
   Title = {Perfect Simulation of Matern Type III Repulsive Point
   Year = {2008},
   Month = {September},
   Abstract = {In a repulsive point process, points act as if they are
             repelling one another, leading to configurations that are
             overdispersed when compared to a standard Poisson point
             process. These models are useful wherever competition for
             resources exists, such as in the locations of towns and
             trees. Bertil Matern introduced three approaches to modeling
             repulsive point processes but described only two in detail,
             now called the Matern processes of Types I and II; the third
             he regarded as overly complex. In fact it is only this third
             process, which we call Matern Type III, which has a
             tractable likelihood function. In this paper a perfect
             simulation method is developed that allows for arbitrarily
             accurate approximation of the likelihood for data modeled by
             the Matern Type III, thereby enabling its use for inference.
             This method is shown to be fast in practice, generating
             samples in time that grows nearly linearly in the intensity
             parameter of the model, while the running times for more
             naive methods grow exponentially.},
   Key = {fds150242}

   Author = {M. Huber},
   Title = {Spatial Birth-Death-Swap Chains},
   Journal = {Bernoulli},
   Year = {2008},
   Month = {May},
   Abstract = {Markov chains have long been used for generating random
             variates from spatial point processes. Broadly speaking,
             these chains fall into two categories: Metropolis-Hastings
             type chains running in discrete time and spatial birth death
             chains running in continuous time. These birth death chains
             only allow for removal of a point or addition of a point. In
             this work it is shown that the addition of transitions where
             a point is moved from one location to the other can aid in
             shortening the mixing time of the chain. Here the mixing
             time of the chain is analyzed through coupling, and use of
             the swap moves allows for analysis of a broader class of
             chains. Furthermore, these swap moves can be employed in
             perfect sampling algorithms via the dominated Coupling from
             the Past procedure of Kendall and Møller. This method can
             be applied to any pairwise interaction model with repulsion.
             In particular, an application to the Strauss process is
             developed in detail, and the swap chains are shown to be
             much faster than standard birth death chains.},
   Key = {fds69197}

   Author = {D. B. Woodard and S. Schmidler and M. Huber},
   Title = {Conditions for Torpid Mixing of Parallel and Simulated
             Tempering on Multimodal Distributions},
   Journal = {Stochastic Processes and their Applications},
   Year = {2007},
   Key = {fds139608}

   Author = {F. Mitha and M. Huber},
   Title = {Monotonic Multigamma coupling for perfect
   Journal = {TOMACS},
   Year = {2006},
   Abstract = {We employ a monotonic version of the Multgamma Coupler
             introduced by Murdoch and Green (1998) in the context of
             bounded multivariate distributions, using the Gibbs sampler.
             Use of monotonicity greatly increases the fficiency of the
             coupler. In addition we observe that the multgamma coupler
             does not require the value of the rho parameter to be
             constant, further improving efficiency. We apply our
             algorithm on a pump dataset also examined by Murdoch and
             Green in order to compare the respective
   Key = {fds50249}

%% Preprints   
   Author = {James A. Fill and Mark L. Huber},
   Title = {Linear expected time perfect generation of proper colorings
             of low degree graphs},
   Year = {2008},
   Abstract = {A proper coloring assigns colors to nodes of a graph so that
             no two endpoints of an edge receive the same color. Here we
             present the first algorithm for sampling uniformly from the
             set of proper colorings of a graph (in expected linear time)
             when the number of colors is linear in the maximum degree of
             the graph.},
   Key = {fds10385}
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320