Accession Number : ADA328566

Title :   Convergence Bonds for Markov Chains and Applications to Sampling.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Gangolli, Anil R.

PDF Url : ADA328566

Report Date : MAY 1991

Pagination or Media Count : 155

Abstract : Consider a discrete-time ergodic Markov chain on a finite state space S with stationary distribution pi. By simulating such a chain, it is possible to draw random samples from S that have distribution pi or nearly pi. This thesis treats some basic questions that arise when one wants to apply such a sampling method in a rigorous way. We begin by reviewing recently developed techniques for proving convergence bounds for Markov chains, and give some new convergence bounds for a number of chains related to urn models.' We then exhibit tight spectral bounds on the variance of natural mean-value estimators computed from a time-reversible Markov chain, and we use these hounds to study issues of efficiency when computing mean-value estimates by this method. Combining the variance hounds with a construction of expander graphs, we obtain an efficient pseudo-random generator for mean-value estimation. Finally, we present some experimental results obtained using the Markov chain sampling method on a statistical problem.

Descriptors :   *ALGORITHMS, *MARKOV PROCESSES, MATHEMATICAL MODELS, PROBABILITY DISTRIBUTION FUNCTIONS, RANDOM VARIABLES, ANALYSIS OF VARIANCE, THESES, EIGENVALUES, STATISTICAL SAMPLES, CONVERGENCE, COMBINATORIAL ANALYSIS, PSEUDO RANDOM SYSTEMS, RANDOM WALK.

Subject Categories : Statistics and Probability
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE