The rapid mixing of random walks defined by an \(n\)-cube (Q1883396)

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.