 |
|
|
| | | | | |
|
|
|
|
|
Maximal Arithmetic Progressions in Random Subsets
|
Itai Benjamini, Weizmann Institute of Science
Ariel Yadin, Weizmann Institute of Science
Ofer Zeitouni, University of Minnesota
|
Abstract
Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to an extreme type (asymmetric) distribution. The same result holds for the maximal length W(N) of arithmetic progressions (mod N). When considered in the natural way on a common probability space, we observe that U(N)/log(N) converges almost surely to 2/log(2), while W(N)/log(N) does not converge almost surely (and in particular, limsup W(N)/log(N) is at least 3/log(2)).
|
Full text: PDF
Pages: 365-376
Published on: October 14, 2007
|
Bibliography
-
N. Alon, J. H. Spencer, The
Probabilistic Method (2000), John Wiley & Sons. New York.
Math. Review 1140703
-
R. Arratia, L. Goldstein, L. Gordon,
Two moments suffice for Poisson approximations: The Chen-Stein
method, Ann. Probab. 17 (1989), 9--25.
Math. Review 972770
-
P. Erdos, A. R'{e}nyi,
On a new law of large numbers, J. Analyse Math. 23 (1970), 103--111.
Math. Review 272026
-
P. Erdos, P. Revesz,
On the length of the longest head-run,
Colloq. Math. Soc. Janos Bolyai 16 (1977), 219--228.
Math. Review 478304
-
R. Gradwohl, A. Yehudayoff,
t-wise independence with local dependencies.
preprint
arXiv:math.PR/0706.1637
-
S. Janson,
Large deviations for sums of partly dependent random variables.
Random Structures Algorithms 24 (2004), no. 3, 234--248.
Math. Review 2068873
-
T. Tao,
What is good mathematics. (2007).
arXiv:math.HO/0702.5396
Math. Review number not available
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context