Mathematical Sciences: Mixing Rate Calculations and Combinatorial Sampling

混合速率问题关注的是马尔可夫过程的分布收敛到平稳分布的速率。本研究的动机是从一个复杂的组合对象X进行蒙特卡罗采样。如果可以构造一个状态空间X和平稳分布均匀分布在X上的过程，并且如果可以证明该过程在分布上收敛到平稳分布相当快，这个过程的模拟可以模拟几乎均匀分布在x上的点。这种技术可以对问题给出精确的多项式时间概率近似。本研究将首先关注这类问题的两个案例。首先是从凸多面体随机生成一个点。第二种是生成一个自回避随机漫步的随机样本路径。覆盖问题涉及随机过程访问其状态空间的所有子集集合所花费的时间。通常，这个过程是在有限图上的随机漫步，而感兴趣的是访问所有顶点所花费的时间。这项工作将集中于覆盖时间的各个方面，而不是期望值的界限，特别是尾部概率。

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.