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
Distribution Statement : APPROVED FOR PUBLIC RELEASE