##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 651.60072

**Autor: ** Erdös, Paul; Chen, Robert W.

**Title: ** Random walks on Z^{n}_{2}. (In English)

**Source: ** J. Multivariate Anal. 25, No.1, 111-118 (1988).

**Review: ** Let Z^{n}_{2} be the set of all (a_{1}, a_{2}, ..., a_{n}) such that a_{i} = 0 or a_{i} = 1 for all i = 1,2,...,n. Further let (W^{n}_{t})_{t \geq 0} 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},...,a_{n}, the next transition is equally probable to (a_{2},a_{3},...,a_{n},0) or (a_{2},a_{3},...,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}) a.e.) = 1, 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 *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.

**Reviewer: ** F.T.Bruss

**Classif.: ** * 60J15 Random walk

60F20 Zero-one laws

60G50 Sums of independent random variables

**Keywords: ** Borel-Cantelli lemma; covering time

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag