Estimates for the concentration functions in the Littlewood–Offord problem

Yu. S. Eliseeva   ; F. Götze   ; A. Yu. Zaitsev

Zapiski Nauchnykh Seminarov POMI, Probability and statistics. Part 20, Tome 420 (2013), pp. 50-69

Résumé

Let $X,X_1,\ldots,X_n$ be independent identically distributed random variables. In this paper we study the behavior of the concentration functions of the weighted sums $\sum_{k=1}^na_kX_k$ with respect to the arithmetic structure of coefficients $a_k$. Such concentration results recently became important in connection with investigations about singular values of random matrices. In this paper we formulate and prove some refinements of a result of Vershynin (2011).

Bibliographie

[1] T. V. Arak, “O skorosti skhodimosti v ravnomernoi predelnoi teoreme Kolmogorova. I”, Teoriya veroyatn. i ee primen., 26:2 (1981), 225–245 | MR | Zbl

[2] T. V. Arak, A. Yu. Zaitsev, Ravnomernye predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Tr. MIAN SSSR, 174, 1986, 214 pp. | MR | Zbl

[3] J. Bretagnolle, “Sur l'inégalité de concentration de Doeblin–Lévy, Rogozin–Kesten”, Parametric and semiparametric models with applications to reliability, survival analysis, and quality of life, Stat. Ind. Technol., Birkhäuser Boston, Boston, MA, 2004, 533–551 | MR

[4] Yu. S. Eliseeva, “Mnogomernye otsenki funktsii kontsentratsii vzveshennykh summ nezavisimykh odinakovo raspredelennykh sluchainykh velichin”, Zap. nauchn. semin. POMI, 412, 2012, 121–137 | MR

[5] Yu. S. Eliseeva, A. Yu. Zaitsev, “Otsenki funktsii kontsentratsii vzveshennykh summ nezavisimykh odinakovo raspredelennykh sluchainykh velichin”, Teoriya veroyatn. i ee primen., 57:4 (2012), 768–777 | DOI

[6] Yu. S. Eliseeva, F. Götze, A. Yu. Zaitsev, Estimates for the concentration functions in the Littlewood–Offord problem, 2012, arXiv: 1203.6763

[7] J. E. Littlewood, A. C. Offord, “On the number of real roots of a random algebraic equation”, Rec. Math. [Mat. Sbornik] N.S., 12(54):3 (1943), 277–286 | MR | Zbl

[8] P. Erdös, “On a lemma of Littlewood and Offord”, Bull. Amer. Math. Soc., 51 (1945), 898–902 | DOI | MR | Zbl

[9] C.-G. Esséen, “On the Kolmogorov–Rogozin inequality for the concentration function”, Z. Wahrscheinlichkeitstheorie Verw. Geb., 5 (1966), 210–216 | DOI | MR | Zbl

[10] C.-G. Esséen, “On the concentration function of a sum of independent random variables”, Z. Wahrscheinlichkeitstheorie Verw. Geb., 9 (1968), 290–308 | DOI | MR | Zbl

[11] O. Friedland, S. Sodin, “Bounds on the concentration function in terms of Diophantine approximation”, C. R. Math. Acad. Sci. Paris, 345 (2007), 513–518 | DOI | MR | Zbl

[12] F. Götze, A. Yu. Zaitsev, “Estimates for the rapid decay of concentration functions of $n$-fold convolutions”, J. Theoret. Probab., 11 (1998), 715–731 | DOI | MR | Zbl

[13] F. Götze, A. Yu. Zaitsev, “A multiplicative inequality for concentration functions of $n$-fold convolutions”, High dimensional probability (Seattle, WA, 1999), v. II, Progr. Probab., 47, Birkhäuser Boston, Boston, MA, 2000, 39–47 | MR | Zbl

[14] G. Halász, “Estimates for the concentration function of combinatorial number theory and probability”, Period. Math. Hung., 8 (1977), 197–211 | DOI | MR | Zbl

[15] V. Khengartner, R. Teodoresku, Funktsii kontsentratsii, Nauka, M., 1980 | MR

[16] H. Kesten, “A sharper form of the Doeblin–Levy–Kolmogorov–Rogozin inequality for concentration functions”, Math. Scand., 25 (1969), 133–144 | MR | Zbl

[17] J. E. Littlewood, A. C. Offord, “On the number of real roots of a random algebraic equation”, Rec. Math. [Mat. Sbornik] N.S., 12(54):3 (1943), 277–286 | MR | Zbl

[18] A. L. Miroshnikov, B. A. Rogozin, “Neravenstva dlya funktsii kontsentratsii”, Teoriya veroyatn. i ee primen., 25:1 (1980), 178–183 | MR | Zbl

[19] S. V. Nagaev, S. S. Khodzhabagyan, “Ob otsenke funktsii kontsentratsii summ nezavisimykh sluchainykh velichin”, Teoriya veroyatn. i ee primen., 41:3 (1996), 655–665 | DOI | MR | Zbl

[20] H. Nguyen, V. Vu, “Optimal inverse Littlewood–Offord theorems”, Adv. Math., 226 (2011), 5298–5319 | DOI | MR | Zbl

[21] V. V. Petrov, Summy nezavisimykh sluchainykh velichin, Nauka, M., 1972 | MR

[22] B. A. Rogozin, “Ob uvelichenii rasseivaniya summ nezavisimykh sluchainykh velichin”, Teoriya veroyatn. i ee primen., 6:1 (1961), 106–108 | MR

[23] M. Rudelson, R. Vershynin, “The Littlewood–Offord problem and invertibility of random matrices”, Adv. Math., 218 (2008), 600–633 | DOI | MR | Zbl

[24] M. Rudelson, R. Vershynin, “The smallest singular value of a random rectangular matrix”, Comm. Pure Appl. Math., 62 (2009), 1707–1739 | DOI | MR | Zbl

[25] T. Tao, V. Vu, “Inverse Littlewood–Offord theorems and the condition number of random discrete matrices”, Ann. Math., 169 (2009), 595–632 | DOI | MR | Zbl

[26] T. Tao, V. Vu, “From the Littlewood–Offord problem to the circular law: universality of the spectral distribution of random matrices”, Bull. Amer. Math. Soc., 46 (2009), 377–396 | DOI | MR | Zbl

[27] R. Vershynin, Invertibility of symmetric random matrices, 2011, arXiv: ; Random Structures and Algorithms (to appear) 1102.0300

[28] A. Yu. Zaitsev, “Ob ispolzovanii funktsii kontsentratsii dlya otsenivaniya ravnomernogo rasstoyaniya”, Zap. nauchn. semin. LOMI, 119, 1982, 93–107 | MR | Zbl

[29] A. Yu. Zaitsev, “O skorosti ubyvaniya funktsii kontsentratsii $n$-kratnykh svertok veroyatnostnykh raspredelenii”, Vestnik S.-Peterburgskogo un-ta. Seriya 1. Matematika. Mekhanika. Astronomiya, 1982, no. 2, 29–33