The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms.Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems.This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives.First, we consider a dynamic growth process arising in the context of DNA-based self-assembly.The assembly process can be modeled as a simple Markov chain.We prove that the chain is rapidly mixing for large enough bias in regions of Z^d.The proof uses a geometric distance function and a variant ofpath coupling in order to handle distances that can be exponentially large.We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application.Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_mon requires exponential time to converge.Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists.The Markov chain M_nn in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters.It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x
【 预 览 】
附件列表
Files
Size
Format
View
Markov chains at the interface of combinatorics, computing, and statistical physics
PDF
download
878987797
028-85220240
