Convergence Bonds for Markov Chains and Applications to Sampling.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1991
Accession Number
ADA328566

Entities

People

  • Anil R. Gangolli

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computer Programming
  • Data Science
  • Estimators
  • Information Science
  • Markov Chains
  • Markov Processes
  • Mathematical Analysis
  • Probability
  • Random Variables
  • Sampling
  • Statistical Algorithms
  • Statistical Analysis
  • Statistics
  • Stochastic Processes
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Molecular and Cellular Biochemistry
  • Regression Analysis.

Technology Areas

  • Space