Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T13:02:06.186Z Has data issue: false hasContentIssue false

Lifting Markov Chains to Random Walks on Groups

Published online by Cambridge University Press:  11 April 2005

ONN CHAN
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, S119260, Republic of Singapore (e-mail: onn.chan@ubs.com,taokai@yahoo.com) Current address: Block 2 Everton Park #02-51, Singapore 081002 Republic of Singapore.
T. K. LAM
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, S119260, Republic of Singapore (e-mail: onn.chan@ubs.com,taokai@yahoo.com) Current address: 86, Marlborough St, #9, Boston, MA 02116, USA (e-mail: tklam@alum.mit.edu).
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In a 1947 paper [6], M. Kac derived the eigenvalues and eigenvectors of the probability transition matrix associated with the Ehrenfest urn model with $n$ balls, in which a ball is selected at random and moved to the other urn. The connection (see, for instance, [1, p. 19]) between the Markov chain defined by the Ehrenfest model and the nearest-neighbour uniform random walk on the abelian group $\Z^n_2$ prompted M. Kac to ask when a Markov chain may be lifted to a random walk on a group. More specifically, given a Markov chain $\{X_m\}_{m \geq 0}$ with state space $S = \{1, 2, \ldots, n \}$ and probability transition matrix ${\mbox{\bf $P$}} = [p_{ij}] (\mbox{here } p_{ij}:= P(X_{r + 1} = j | X_r = i) \mbox{ for all } r \geq 0)$, we say that the Markov chain $\{X_m\}_{m \geq 0}$ or equivalently ${\mbox{\bf $P$}}$ lifts to a random walk on a finite group $G$ if there exists a probability measure $\mu$ on $G$ and a surjective map $L:G \rightarrow S$ such that, for all $i, j \in S$, and for each $g \in L^{-1}(i)$, $$ p_{ij} = \sum_{h \in L^{-1}(j)} \!\! \mu (g^{-1}h).$$

Information

Type
Paper
Copyright
© 2005 Cambridge University Press