Coalescing random walks on n-block Markov chains

Loading...
Thumbnail Image

Date

2014-01-11

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

341
views
463
downloads

Abstract

Fix a discrete-time Markov chain $(V,P)$ with finite state space $V$ and transition matrix $P$. Let $(V_n,P_n)$ be the Markov chain on n-blocks induced by $(V,P)$, which we call the n-block process associated with the base chain $(V,P)$. We study coalescing random walks on mixing n-block Markov chains in discrete time. In particular, we are interested in understanding the asymptotic behavior of $\mathbb{E} C_n$, the expected coalescence time for $(V_n,P_n)$, as $n\to\infty$. Define the quantity $L=-\log\lambda$, where $\lambda$ is the Perron eigenvalue of the matrix $Q$ that has entries $Q_{i,j}=P_{i,j}^2$. We prove the existence of four limits and show that all of them are equal to $L$: $\lim\limits_{n\to\infty}\frac{1}{n}\log\mathbb{E} C_n$, $\lim\limits_{n\to\infty}\frac{1}{n}\log m_n^$, $\lim\limits_{n\to\infty} \frac{1}{n}\log \bar{m}n$, and $\lim\limits{n\to\infty} -\frac{1}{n}\log\Delta_n$, where $m_n^$ and $\bar{m}_n$ are the maximum and average meeting times for $(V_n, P_n)$ respectively. We establish the inequalities $0<L\leq h$, where $h$ is the entropy of $P$, and show that $L=h$ iff $P$ is a measure of maximal entropy. The formulas and bounds for $L$ provide a complete characterization of $\mathbb{E} C_n$ on the exponential scale.

Department

Description

Provenance

Citation

Citation

Lan, Kathleen (2014). Coalescing random walks on n-block Markov chains. Honors thesis, Duke University. Retrieved from https://hdl.handle.net/10161/8309.


Except where otherwise noted, student scholarship that was shared on DukeSpace after 2009 is made available to the public under a Creative Commons Attribution / Non-commercial / No derivatives (CC-BY-NC-ND) license. All rights in student work shared on DukeSpace before 2009 remain with the author and/or their designee, whose permission may be required for reuse.