The rapid mixing of random walks defined by an \(n\)-cube
type: Item
instance of: scholarly article
title: The rapid mixing of random walks defined by an \(n\)-cube
zbMATH Open document ID: 1057.60043
published in: Advances in Applied Mathematics
publication date: 2004-10-12T00:00:00Z
review text: Consider the Markov chain \(X_k\), \(k=0,1,2,\dots\), with state space \(Q_n= \{0,1\}^n\) and stationary transition matrix \(P\) with \(p(x,y)=p^d (1-p)^{n-d}\) where \(d=d(x,y)=\#\{i\leq n:x_i\neq y_i\}\) and \(0<p<1\). This is an aperiodic irreducible Markov chain with stationary distribution \(\pi(x)=2^{-n}\), \(x\in Q_n\). The authors show that this chain is rapidly mixing. A random walk \(Y_k\) on a weighted graph of order \(N\) is rapidly mixing if there exists a polynomial \(f\) such that for \(0<3\varepsilon<1\) and \(k\geq f(\log N)\log 1/\varepsilon\) one has \(\sum_y|\pi(y)- P(Y_k=y)| \leq\varepsilon\). Rapid mixing means that the random walk is close to stationarity after a number of steps bounded by polynomial input, which restricts computational complexity. It is connected with the value of the second largest eigenvalue of \(P\) and also with the conductance \(\Phi\) of \(P\) defined as \(\min\{\sum_{x\in U}\sum_{y\not \in U}\pi(x)p(x,y)/ \pi(U): \pi(U)\leq 1/2\}\). The problem is reduced to the `lazy random walk' on \(Q_n\) with transition matrix \(P'=(I+P)/2\) having positive eigenvalues. The eigenvalues of \(P\) are computed as \((1-2p)^k\), \(k=0,\dots,w\), with multiplicity \(n\choose k\). The conductance of \(P'\) is shown to be equal to \(\Phi/2\), i.e., \(p/2\) when \(0<p<1/2\) and \(p(1-p)\) when \(1/2<p<1\). Note that \(\Gamma(v)\) on p. 137 refers to the complete graph with vertex set \(Q_n\) and in Lemma 3.1 to the graph with vertex set \(Q_n\) and edges only between neighbours.
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 2107242
zbMATH Keywords: Markov chain
zbMATH Keywords: rapid mixing
zbMATH Keywords: conductance
zbMATH Keywords: random walk on graph
author: Haiyan Chen
author: Fuji Zhang
MaRDI profile type: Publication
full work available at URL: j.aam.2003.08.001
OpenAlex ID: W2031941385
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Q4398864
cites work: Q3706275
cites work: Problems in algebraic combinatorics
cites work: Expansion and isoperimetric constants for product graphs
cites work: Isoperimetric invariants for product Markov chains and graph products
cites work: Q4549234
cites work: Finite Continuous Time Markov Chains
cites work: Q4276003
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains
cites work: Q5731217
cites work: Resistances and currents in infinite electrical networks
DOI: 10.1016/J.AAM.2003.08.001
description: scientific article; zbMATH DE number 2107242