Random walks on \(Z^n_2\) (Q1106556)

Let \(Z^n_2\) be the set of all \((a_1, a_2, \ldots, a_n)\) such that \(a_i=0\) or \(a_i=1\) for all \(i=1,2,\ldots,n\). Further let \((W^n_t)_{t\geq0}\) be a random walk on \(Z^n_2\) such that \(P(W^n_0=A) = 2^{-n}\) for all \(A\) in \(Z^n_2\) and such that, given \(a_1,a_2,\ldots,a_n\), the next transition is equally probable to \((a_2,a_3,\ldots,a_n,0)\) or \((a_2,a_3,\ldots,a_n,1)\). This paper studies the behaviour of the random time \(C_n\) taken by the random walk to visit all states in \(Z^n_2\). The main result is \[ P(c_2^n 1n(2^n) < C_n < d 2^n 1n(2^n) \text{a.e.}) = 1,\quad \text{for all constants } c<1<d. \] We note that \((W^n_t)_{t\geq 0}\) is not the usual random walk in the sense that two (and not any neighboured) vertices are chosen with the same probability. (Also the walk permits jumps in the ``diagonal'', see e.g. \(n=3)\). The latter has been studied before by \textit{P. C. Mathews} [Covering problems for random walks on spheres and finite groups. Tech. Rep. 234, Dept. of Statistics, Stanford Univ. (1984)] and the results turn out here to be similar, but the technique used in this paper is different.