Arrow Research search

Author name cluster

Dana Randall

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

SODA Conference 2016 Conference Paper

Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions

  • Sarah Cannon
  • Dana Randall

Many statistical physics models are defined on an infinite lattice by taking appropriate limits of finite lattice regions, where a key consideration is how the boundaries are defined. For several models on planar lattices, such as 3-colorings and lozenge tilings, efficient sampling algorithms are known for regions with fixed boundary conditions, where the colors or tiles around the boundary are pre-specified [14], but much less is known about how to sample when these regions have free boundaries, where we want to include all configurations one could see within a finite window. We introduce a method using randomized extensions of a lattice region to relate sampling problems on regions with free boundaries to a constant number of sampling problems on larger regions with fixed boundaries. We demonstrate this principled approach to sample 3-colorings of regions of ℤ 2 and lozenge tilings of regions of the triangular lattice, building on arguments for the fixed boundary cases due to Luby et al. [14]. Our approach also yields an efficient algorithm for sampling 3-colorings with free boundary conditions on regions with one reflex corner, the first such result for a nonconvex region. This approach can also be generalized to a broad class of mixed boundary conditions. Sampling for these families of regions is significant because it allows us to establish self-reducibility, giving the first algorithm to approximately count the total number of 3-colorings of rectangular lattice regions.

Details

SODA Conference 2014 Conference Paper

Clustering and Mixing Times for Segregation Models on ℤ 2

  • Prateek Bhakta
  • Sarah Miracle
  • Dana Randall

The Schelling segregation model attempts to explain possible causes of racial segregation in cities. Schelling considered residents of two types, where everyone prefers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move, called the General Influence Model. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated (i. e. , there will not be clustering) if the racial bias is sufficiently low. Next we show complementary results for two broad classes of influence functions: Increasing Bias Functions (IBF), where an individual's likelihood of moving increases each time someone of the same color leaves (this does not include Schelling's threshold models), and Threshold Bias Functions (TBF) with the threshold exceeding one half, reminiscent of the model Schelling originally proposed. For both classes (IBF and TBF), we show that when the bias is sufficiently high, the dynamics take exponential time to mix and we will have segregation and a large “ghetto” will form.

Details

SODA Conference 2009 Conference Paper

Sampling biased lattice configurations using exponential metrics

  • Sam Greenberg
  • Amanda Pascoe Streib
  • Dana Randall

Monotonic surfaces spanning finite regions of ℤ d arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. We explore how we can sample these surfaces when the distribution is biased to favor higher surfaces. We show that a natural local chain is rapidly mixing with any bias for regions in ℤ 2, and for bias λ > d 2 in ℤ d, when d > 2. Moreover, our bounds on the mixing time are optimal on d-dimensional hyper-cubic regions. The proof uses a geometric distance function and introduces a variant of path coupling in order to handle distances that are exponentially large.

Details

FOCS Conference 2003 Conference Paper

Mixing

  • Dana Randall

In this paper, we introduce the notion of a Markov chain and explore how it can be used to sample from a large set of configurations. Our primary focus is determining how quickly a Markov chain "mixes, " or converges to its stationary distribution, as this is the key factor in the running time. We provide an overview of several techniques used to establish good bounds on the mixing time. The applications are mostly chosen from statistical physics, although the methods are much more general.

Details

MFCS Conference 2001 Invited Paper

Decomposition Methods and Sampling Circuits in the Cartesian Lattice

  • Dana Randall

Abstract Decomposition theorems are useful tools for bounding the convergence rates of Markov chains. The theorems relate the mixing rate of a Markov chain to smaller, derivative Markov chains, defined by a partition of the state space, and can be useful when standard, direct methods fail. Not only does this simplify the chain being analyzed, but it allows a hybrid approach whereby different techniques for bounding convergence rates can be used on different pieces. We demonstrate this approach by giving bounds on the mixing time of a chain on circuits of length 2n in ℤ d.

Details

FOCS Conference 2000 Conference Paper

Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method

  • Russell A. Martin
  • Dana Randall

Staircase walks are lattice paths from (0, 0) to (2n, 0) which take diagonal steps and which never fall below the x-axis. A path hitting the x-axis /spl kappa/ times is assigned a weight of /spl lambda//sup /spl kappa//, where /spl lambda/>0. A simple local Markov chain, which connects the state space and converges to the Gibbs measure (which normalizes these weights) is known to be rapidly mixing when /spl lambda/=1, and can easily be shown to be rapidly mixing when /spl lambda/ 1, known in the statistical physics community as adsorbing staircase walks. The main new ingredient is a decomposition technique which allows us to analyze the Markov chain in pieces, applying different arguments to analyze each piece.

Details

FOCS Conference 1996 Conference Paper

Factoring Graphs to Bound Mixing Rates

  • Neal Madras
  • Dana Randall

This paper develops a new technique for bounding the mixing rate of a Markov chain by decomposing the state space into factors. The first application is an efficient Monte Carlo Markov chain algorithm for generating random three-colorings of 2-dimensional lattice regions. This provides a rigorous tool for studying some properties of the 3-state Potts model and the ice model from statistical mechanics. As a second application, we develop similar techniques to bound the mixing rate of a Metropolis sampling algorithm by a type of "temperature factorization". Both factorization theorems work by using known mixing properties of related Markov chains to establish the efficiency of a new sampling algorithm.

Details

FOCS Conference 1995 Conference Paper

Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract)

  • Michael Luby
  • Dana Randall
  • Alistair Sinclair

Consider the following Markov chain, whose states are all domino tilings of a 2n/spl times/2n chessboard: starting from some arbitrary tiling, pick a 2/spl times/2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling and is a key tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. The paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

Details