Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 373.60035
Autor: Erdös, Pál; Revesz, Pál
Title: On a problem of T. Varga. (In Hungarian)
Source: Mat. Lapok 24(1973), 273-282 (1975).
Review: Toss a fair coin n times. What is the length Zn of the longest head-run? This question was initiated by an interesting teaching experiment of T. Varga. The problem can be formulated the following way. Let X1,X2,... be i.i.d. rv's with p(X1 = 0) = p(X2 = 1) = ½, S0 = 0, Sk = X1+...+Xk, I(n,k) = max0 \leq i \leq n-k(Si+k-Si). Then Zn is the largest integer for which I(n,Zn) = Zn. P.Erdös and A.Rényi [J. Anal. Math. 23, 103-111 (1970; Zbl 225.60015] proved that if 0 < c1 < 1 < c2 < oo, then for almost all \omega in \Omega (the basic space) there exists a finite n0 = n0(\omega,c1,c2) such that for n \geq n0, [c1 log n] \leq Zn < [c2 log n] ( log is with base 2, [.] means integer part x the smallest integer \geq x). Let \alphan(3) = [ log n- log log log n]+3, \alphan(0) = { log n- log log log n}. Here the authors prove that for almost all \omega there exists n0, such that \alphan(3) \leq Zn, for n \geq n0. On the other hand, for almost all \omega there exists an infinite sequence nk(\omega) such that Znk < \alphank(0). Clearly Zn can be much larger than \alphan(3) for some n. Concerning the largest possible values of Zn, the following results are proved. If {\gamman} is a sequence of positive numbers such that \Sigma 2-\gamman = oo, then for almost all \omega there exists an infinite sequence nk = nk(\omega,{\gamman}) of integers such that Znk \geq \gammank. But if \Sigma 2-\gamman < oo, then for almost all \omega there exists n0 = n0(\omega,{\gamman}) such that Zn < \gamman for n \geq n0. All the mentioned results are then generalised for the length of the longest run containing a fixed number of tails. The result in this paper are formulated in nonprobabilistic language, concerning 1-runs in the dyadic expansion of a number 0 \leq x \leq 1. A list of unsolved problems is also included. Note that in the English version of the paper [Top. Inf. Theory, Keszthely 1975, Colloq. Math. Soc. János Bolyai 16, 219-228 (1977; Zbl 362.60044)] the first two results appear in a finer form. Namely [ log n- log log log n+ log log e-2-\epsilon] and [ log n- log log log n+ log log e-1+\epsilon] play respectively the roles of \alphan(3) and \alphan(0) where 0 < \epsilon is arbitrarily small.
Reviewer: S.Csörgö
Classif.: * 60F15 Strong limit theorems
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag