##
**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 Z_{n} 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 X_{1},X_{2},... be i.i.d. rv's with p(X_{1} = 0) = p(X_{2} = 1) = ½, S_{0} = 0, S_{k} = X_{1}+...+X_{k}, I(n,k) = **max**_{0 \leq i \leq n-k}(S_{i+k}-S_{i}). Then Z_{n} is the largest integer for which I(n,Z_{n}) = Z_{n}. *P.Erdös* and *A.Rényi* [J. Anal. Math. 23, 103-111 (1970; Zbl 225.60015] proved that if 0 < c_{1} < 1 < c_{2} < oo, then for almost all \omega in \Omega (the basic space) there exists a finite n_{0} = n_{0}(\omega,c_{1},c_{2}) such that for n \geq n_{0}, [c_{1} log n] \leq Z_{n} < [c_{2} log n] ( log is with base 2, [.] means integer part x the smallest integer \geq x). Let \alpha_{n}(3) = [ log n- log log log n]+3, \alpha_{n}(0) = **{** log n- log log log n**}**. Here the authors prove that for almost all \omega there exists n_{0}, such that \alpha_{n}(3) \leq Z_{n}, for n \geq n_{0}. On the other hand, for almost all \omega there exists an infinite sequence n_{k}(\omega) such that Z_{nk} < \alpha_{nk}(0). Clearly Z_{n} can be much larger than \alpha_{n}(3) for some n. Concerning the largest possible values of Z_{n}, the following results are proved. If **{**\gamma_{n}**}** is a sequence of positive numbers such that \Sigma 2^{-\gamman} = oo, then for almost all \omega there exists an infinite sequence n_{k} = n_{k}(\omega,**{**\gamma_{n}**}**) of integers such that Z_{nk} \geq \gamma_{nk}. But if \Sigma 2^{-\gamman} < oo, then for almost all \omega there exists n_{0} = n_{0}(\omega,**{**\gamma_{n}**}**) such that Z_{n} < \gamma_{n} for n \geq n_{0}. 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 \alpha_{n}(3) and \alpha_{n}(0) where 0 < \epsilon is arbitrarily small.

**Reviewer: ** S.Csörgö

**Classif.: ** * 60F15 Strong limit theorems

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag