%% Papers Published
@article{fds14018,
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
previously.},
Key = {fds14018}
}
@article{fds10388,
Author = {Mark L. Huber},
Title = {A faster method for sampling independent
sets},
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}
}
@article{fds70394,
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
time.},
Key = {fds70394}
}
@article{fds47823,
Author = {M. Huber},
Title = {Exact sampling from perfect matchings in dense regular
graphs},
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}
}
@article{fds146748,
Author = {M. Huber and J. Law},
Title = {Fast approximation of the permanent for very dense
problems},
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}
}
@article{fds47822,
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}
}
@article{fds10391,
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}
}
@article{fds44038,
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
bars},
Journal = {Physical Review E},
Volume = {72},
Number = {031306},
Publisher = {APS Journals},
Year = {2005},
url = {http://link.aps.org/abstract/PRE/v72/e031306},
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
anisotropy.},
Key = {fds44038}
}
@article{fds38507,
Author = {Yuguo Chen and Ian Dinwoodie and Adrian Dobra and Mark
Huber},
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}
}
@article{fds41202,
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}
}
@article{fds47824,
Author = {M. Huber and Y. Chen and I. Dinwoodie and A. Dobra and M.
Nicholas},
Title = {Monte Carlo algorithms for Hardy-Weinberg
proportions},
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}
}
@article{fds10384,
Author = {A. Benjamin and M. Huber and M. Fluet},
Title = {Optimal Token Allocations in Solitaire Knock 'm
Down},
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
solution.},
Key = {fds10384}
}
@article{fds29377,
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
all.},
Key = {fds29377}
}
@article{fds70713,
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}
}
@article{fds147643,
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}
}
@article{fds69199,
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}
}
@article{fds10156,
Author = {J. A. Fill and M. L. Huber},
Title = {The Randomness Recycler approach to perfect
sampling},
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}
}
@article{fds10387,
Author = {James A. Fill and Mark L. Huber},
Title = {The Randomness Recycler: A new technique for perfect
sampling},
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}
}
@article{fds41201,
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}
}
%% Papers Accepted
@article{fds148507,
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}
}
@article{fds148510,
Author = {M. Huber},
Title = {Spatial point processes},
Booktitle = {Handbook of MCMC},
Editor = {Brooks, Gelman and Jones, Meng},
Year = {2008},
Month = {April},
Key = {fds148510}
}
%% Papers Submitted
@article{fds139608,
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}
}
@article{fds50249,
Author = {F. Mitha and M. Huber},
Title = {Monotonic Multigamma coupling for perfect
sampling},
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
algorithms.},
Key = {fds50249}
}
@article{fds150242,
Author = {M. L. Huber and R. L. Wolpert},
Title = {Perfect Simulation of Matern Type III Repulsive Point
Processes},
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}
}
@article{fds69197,
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}
}
%% Preprints
@article{fds10385,
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}
}
|
| 
Mathematics Department