Random walks on \(Z^n_2\)
type: Item
instance of: scholarly article
title: Random walks on \(Z^n_2\)
zbMATH Open document ID: 0651.60072
DOI: 10.1016/0047-259X(88)90156-X
author: Robert W. Chen
author: P. Erdős
published in: Journal of Multivariate Analysis
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60F20
zbMATH DE Number: 4062295
zbMATH Keywords: Borel-Cantelli lemma
zbMATH Keywords: covering time
reviewed by: F. Thomas Bruss
MaRDI profile type: Publication
Wikidata QID: Q59701080
cites work: String overlaps, pattern matching, and nontransitive games
cites work: Limit Distributions of Random Variables Associated with Long Duplications in a Sequence of Independent Trials
cites work: Covering the circle with random arcs
cites work: A Combinatorial Identity and Its Application to the Problem Concerning the First Occurrence of a Rare Event
full work available at URL: 0047-259x(88)90156-x
OpenAlex ID: W1986715445
description: scientific article; zbMATH DE number 4062295