The effects of bias on sampling algorithms and combinatorial objects

[摘要] Markov chains are algorithms that can provide critical information from exponentially large sets efficiently through random sampling.These algorithms are ubiquitous across numerous scientific and engineering disciplines, including statistical physics, biology and operations research.In this thesis we solve sampling problems at the interface of theoretical computer science with applied computer science, discrete mathematics, statistical physics, chemistry and economics.A common theme throughout each of these problems is the use of bias.The first problem we study is biased permutations which arise in the context of self-organizing lists. Here we are interested in the mixing time of a Markov chain that performs nearest neighbor transpositions in the non-uniform setting.We are given "positively biased'' probabilities$\{p_{i,j} \geq 1/2 \}$ for all $i < j$ and let $p_{j,i} = 1-p_{i,j}$.In each step, the chain chooses two adjacent elements~$k,$ and~$\ell$ andexchanges their positions with probability$p_{ \ell, k}$.We define two general classes of bias and give the first proofs that the chain is rapidly mixing for both.We also demonstrate that the chain is not always rapidly mixingby constructing an examplerequiring exponential time to converge to equilibrium.Next we study rectangular dissections of an $n \times n$ lattice region into rectangles ofarea $n$, where $n=2^k$ for an even integer $k.$We consider a weighted version of a natural edge flipping Markov chain where, givena parameter $\lambda > 0,$ we would like to generate each rectangular dissection (or dyadic tiling)~$\sigma$ with probability proportional to $\lambda^{|\sigma|},$ where $|\sigma|$ is the total edge length. First we look at the restricted case of dyadic tilings, where each rectangle is required to have the form $R = [s2^{u},(s+1)2^{u}]\times [t2^{v},(t+1)2^{v}],$where $s, t, u$ and~$v$ are nonnegative integers.Here we showthere isa phase transition: when $\lambda < 1,$ the edge-flipping chain mixes in time $O(n^2 \log n)$, and when $\lambda > 1,$ the mixing time is $\exp(\Omega({n^2}))$.The behavior for general rectangular dissections is more subtle, and we show the chain requires exponential time when $\lambda >1$ and when $\lambda <1.$The last two problems we study arise directly from applications in chemistry and economics.Colloids are binary mixtures of molecules with one type of molecule suspended in another.It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters.We characterize the high and low density phases for a general family of discrete interfering colloid models by showing that they exhibit a "clustering property" at high density and not at low density.The clustering property states that there will be a region that has very high area to perimeter ratio and very high density of one type of molecule.A special case is mixtures of squares and diamonds on $\Z^2$ which correspond to the Ising model at fixed magnetization.Subsequently, we expanded techniques developed in the context of colloids to give a new rigorous underpinning to the Schelling model, which was proposed in 1971 by economist Thomas Schelling to understand the causes of racial segregation.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.We show that for any influence function in this class,the dynamics will be rapidly mixing and cities will be integrated if the racial bias is sufficiently low.However when the bias is sufficiently high, we show the dynamics take exponential time to mix and a large cluster of one type will form.

[发布机构] University:Georgia Institute of Technology;Department:Computer Science

[效力级别] Sampling

[关键词] Markov chain;Sampling;Phase transition;Permutation;Rectangular dissection;Colloids;Schelling