Mathematical Sciences: Mixing Rate Calculations and Combinatorial Sampling

点击翻译按钮获取中文摘要

Mixing rate problems concern the rate of convergence in distribution of a Markov process to its stationary distribution. The motivation for this research is Monte Carlo sampling from a complicated combinatorial object X. If one can construct a process with state space X and stationary distribution uniform on X, and if one can show that the process converges in distribution to that stationary distribution rather rapidly, the simulation of the process allows simulation of points nearly uniformly distributed in X. This technique can give accurate polynomial-time probabilistic approximations to problems. This research will focus first on two cases of this kind of problem. This first is generating a point at random from a convex polytope. The second is generating a random sample path of a self-avoiding random walk. Covering problems concern the time taken by a stochastic process to visit all of the collection of subsets of its state space. Typically the process is a random walk on a finite graph, and interest is in the time taken to visit all vertices. This work will concentrate on aspects of covering times other than bounds on expected values, particularly tail probabilities.