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.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
9001295
Program Officer
Peter Arzberger
Project Start
Project End
Budget Start
1990-07-01
Budget End
1992-12-31
Support Year
Fiscal Year
1990
Total Cost
$38,290
Indirect Cost
Name
University of Maryland Baltimore County
Department
Type
DUNS #
City
Baltimore
State
MD
Country
United States
Zip Code
21250