Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 651.60072
Autor: Erdös, Paul; Chen, Robert W.
Title: Random walks on Zn2. (In English)
Source: J. Multivariate Anal. 25, No.1, 111-118 (1988).
Review: Let Zn2 be the set of all (a1, a2, ..., an) such that ai = 0 or ai = 1 for all i = 1,2,...,n. Further let (Wnt)t \geq 0 be a random walk on Zn2 such that P(Wn0 = A) = 2-n for all A in Zn2 and such that, given a1,a2,...,an, the next transition is equally probable to (a2,a3,...,an,0) or (a2,a3,...,an,1).
This paper studies the behaviour of the random time Cn taken by the random walk to visit all states in Zn2. The main result is P(c2n 1n(2n) < Cn < d 2n 1n(2n) a.e.) = 1, for all constants c < 1 < d. We note that (Wnt)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