Merge Times and Hitting Times of Time-inhomogeneous Markov Chains

Loading...
Thumbnail Image

Date

2014-06-28

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

425
views
4237
downloads

Abstract

Concepts of Markov chains mixing, the study of the convergence to stationarity, emerged three decades ago. Studying times to convergence of Markov chains is crucial as it ties to many other mathematical areas, such as Markov Chain Monte Carlo, a method of sampling from a given probability distribution. The purpose of this thesis is to study the long term behavior of time-inhomogeneous Markov chains. We analyze under what conditions they converge, in what sense they converge and what the rate of convergence should be.

A Markov chain is a random process with the memoryless property: the next state only depends on the current state, and not on the sequence of events that preceded it. Time-inhomogeneous Markov chains refer to chains with different transition probability matrices at each step. What makes them interesting is that they don't necessarily have stationary distributions. Instead of comparing the chain to the stationary distribution, we look at the distance between two distributions started at different initial states. We refer to the time until the two distributions get sufficiently close as merge time. As a foundation for our simulations and proofs, we first show the convergence theorem for time-inhomogeneous Markov chains with a sufficient assumption. We then study the various ways of perturbing the random walk on the n-cycle, by forcing the random walker to move in a certain direction with higher probability if it is at a particular site. Changing perturbations at every step results in different one-step transition kernels throughout the chain, therefore making the chain time-inhomogeneous. We then compare the merge times, as a function of the number of states n, to those of the unperturbed time-homogeneous simple random walk on the n-cycle.

One of the perturbations represents the case in which the random walker has a varying probability of staying put at a particular site at every step. Simulations show that the merge times for this perturbed chain is almost identical to those of the unperturbed chains. We are able to show this result by proving an explicit bound on the hitting times.

Department

Description

Provenance

Subjects

Markov Chains, Merge Times, Hitting Times, Stochastic Processes, Random Walk

Citation

Citation

Shen, Jiarou (2014). Merge Times and Hitting Times of Time-inhomogeneous Markov Chains. Honors thesis, Duke University. Retrieved from https://hdl.handle.net/10161/8918.


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.