×

A generalization of the Erdős-Rényi limit theorem and the corresponding multifractal analysis. (English) Zbl 1423.11135

It is known that the well-known Erdős-Rényi limit theorem characterizes the limit behaviour of the run-length functions showing especially that the run-length functions for almost all numbers in the unit interval are of the logarithmic growth rate \(\log_2n\).
The aim of the present paper is to give a generalization of the classic Erdős-Rényi limit theorem through the introduction of a more general concept of the run-length function, as well as to complement the above-mentioned generalized limit theorem to the case of \(m\)-adic expansions, and to study the sets in which the run-length functions are endowed with different growth rates from the viewpoint of dimensional theory.
In particular, the authors managed to give a generalization of the classic Erdős-Rényi theorem by studying the limit behaviour of the run-length function \(R^p_n(x)\) of \(x\in[0,1]\) in \(\overline\Sigma p\), where \(1\le p\le m-1\), \(m\ge 2\), are integers and \(\overline\Sigma p\subset\{0,1,\dots, m-1\}\) the alphabet with \(p\) elements, and to prove that \[\lim_{n\to \infty}\frac{R^p_n(x)}{\log_{m/p}n}= 1,\qquad\text{for almost all }x\in [0,1],\]
in the sense of the Lebesgue measure.
Furthermore, the authors manage to complement the generalized Erdős-Rényi theorem by finding that the level set in which the above limit equals to \(\alpha\), for any \(0\le\alpha\le+\propto\), is of full Hausdorff dimension. (It is known that for the level set \[E_m(\phi)= \Biggl\{x\in [0,1]: \lim_{n\to\infty} \frac{R^p_n(x)}{\varphi(n)}= 1\Biggr\},\] where \(\varphi\) is a positive function defined on \(N\), its Hausdorff dimension is determined when the function \(\varphi\) is of some particular growth rates.)

MSC:

11K55 Metric theory of other algorithms and expansions; measure and Hausdorff dimension
28A80 Fractals
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arratia, R.; Gordon, L.; Waterman, M. S., The Erdös-Rényi law in distribution, for coin tossing and sequence matching, Ann. Statist., 18, 539-570, (1990) · Zbl 0712.92016
[2] Arratia, R.; Waterman, M. S., The Erdös-Rényi strong law for pattern matching with a given proportion of mismatches, Ann. Probab., 17, 1152-1169, (1989) · Zbl 0688.62019
[3] Bingham, N. H.; Goldie, C. M.; Teugels, J. L., Regular variation, (1987), Cambridge University Press Cambridge · Zbl 0617.26001
[4] Binswanger, K.; Embrechts, P., Longest runs in coin tossing, Insurance Math. Econom., 15, 139-149, (1994) · Zbl 0821.62008
[5] Book, S. A., The Erdös-Rényi new law of large numbers for weighted sums, Proc. Amer. Math. Soc., 38, 165-171, (1973) · Zbl 0251.60020
[6] Book, S. A., An extension of the Erdös-Rényi law of large numbers, Proc. Amer. Math. Soc., 48, 438-446, (1975) · Zbl 0267.60023
[7] Csáki, E.; Födes, A., On the length of the longest monotone word, Studia Sci. Math. Hungar., 31, 35-46, (1996) · Zbl 0851.60026
[8] Csörgő, M.; Steinebach, J., Improved Erdös-Rényi and strong approximation laws for increments of partial sums, Ann. Probab., 9, 988-996, (1981) · Zbl 0477.60034
[9] Chen, H. B.; Tang, J. M., The waiting spectra of the sets described by the quantitative waiting time indicators, Sci. China Math., 11, 57, 2335-2346, (2014) · Zbl 1303.11089
[10] Chen, H. B.; Wen, Z. X., The fractional dimensions of intersections of the Besicovitch sets and the Erdös-Rényi sets, J. Math. Anal. Appl., 401, 29-37, (2013) · Zbl 1261.28007
[11] Deheuvels, P., On the Erdös-Rényi theorem for random fields and sequences and its relationships with the theory of runs and spacings, Z. Wahrsch. Verw. Gebiete, 70, 91-115, (1985) · Zbl 0548.60027
[12] Deheuvels, P.; Devroye, L., Limit laws of Erdös-Rényi-Shepp type, Ann. Probab., 15, 4, 1363-1386, (1987) · Zbl 0637.60039
[13] Denker, M.; Nicol, M., Erdös-Rényi laws for dynamical systems, J. Lond. Math. Soc., 87, 497-508, (2013) · Zbl 1281.60028
[14] Drobot, V.; Turner, J., Hausdorff dimension and Perron-Frobenius theory, Illinois J. Math., 33, 1, 1-9, (1989) · Zbl 0661.10067
[15] Erdös, P.; Rényi, A., On a new law of the longest head run, J. Anal. Math., 22, 103-111, (1970)
[16] Erdös, P.; Révész, P., On the length of the longest head-run, (Topics in Information Theory, Colloquia Math. Soc. J. Bolyai, vol. 16, (1975)), 219-228
[17] Falconer, K. J., Fractal geometry-mathematical foundations and applications, (1990), John Wiley · Zbl 0689.28003
[18] Frolov, A. N.; Martikainen, A. I., On the length of the longest increasing run in \(\mathbb{R}^d\), Statist. Probab. Lett., 41, 153-161, (1999) · Zbl 0916.60031
[19] Galambos, J.; Seneta, E., Regularly varying sequences, Proc. Amer. Math. Soc., 41, 1, 110-116, (1973) · Zbl 0247.26002
[20] Gordon, L.; Schilling, M. F.; Waterman, M. S., An extreme value theory for long head runs, Probab. Theory Related Fields, 72, 279-287, (1986) · Zbl 0587.60031
[21] Li, J. J.; Wu, M., On exceptional sets in Erdös-Rényi limit theorem, J. Math. Anal. Appl., 436, 355-365, (2016) · Zbl 1408.11077
[22] Li, J. J.; Wu, M.; Yang, X. F., On the longest block in Lüroth expansion, J. Math. Anal. Appl., 457, 522-532, (2018) · Zbl 1434.11153
[23] Ma, J. H.; Wen, S. Y.; Wen, Z. Y., Egoroff’s theorem and maximal run length, Monatsh. Math., 151, 287-292, (2007) · Zbl 1170.28001
[24] Mason, D., An extended version of the Erdös-Rényi strong law of large numbers, Ann. Probab., 17, 1, 257-265, (1989) · Zbl 0677.60031
[25] Makria, F. S.; Philippoua, A. N.; Psillakisb, Z. M., Shortest and longest length of success runs in binary sequences, J. Statist. Plann. Inference, 137, 2226-2239, (2007) · Zbl 1128.60009
[26] Mao, Y. H.; Wang, F.; Wu, X. Y., Large deviation behavior for the longest head run in an i.i.d. Bernoulli sequence, J. Theoret. Probab., 28, 259-268, (2015) · Zbl 1319.60054
[27] Odlyzko, A. M., Asymptotic enumeration methods, Handbook of Combinatorics, vols. 1, 2, 1063-1229, (1995), Elsevier Amsterdam · Zbl 0845.05005
[28] Révész, P., Three problems on the lengths of increasing runs, Stochastic Process. Appl., 15, 169-179, (1983) · Zbl 0518.60049
[29] Révész, P., Random walk in random and non-random environments, (2005), World Scientific Singapore · Zbl 1090.60001
[30] Seneta, E., Karamata’s iteration theorem and normed regularly varying sequences in a historical light, Publ. Inst. Math., 48, 45-51, (1990) · Zbl 0731.26003
[31] Steinebach, J., On general versions of Erdös-Rényi laws, Z. Wahrsch. Verw. Gebiete, 56, 549-554, (1981) · Zbl 0443.60025
[32] Sun, Y.; Xu, J., A remark on exceptional sets in Erdös-Rényi limit theorem, Monatsh. Math., 184, 291-296, (2017) · Zbl 1386.11089
[33] Tong, X.; Yu, Y. L.; Zhao, Y. F., On the maximal length of consecutive zero digits of β-expansion, Int. J. Number Theory, 12, 625-633, (2016) · Zbl 1337.11053
[34] Wang, B. W.; Wu, J., On the maximal run-length function in continued fractions, Ann. Univ. Sci. Budapest. Sect. Comput., 34, 247-268, (2011)
[35] Zou, R. B., Hausdorff dimension of the maximal run-length in dyadic expansion, Czechoslovak Math. J., 61, 881-888, (2011) · Zbl 1249.11085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.