# Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$

It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^{(k)}_{n+2}}{2^n}\quad\quad(1)$$ where $F^{(k)}_l$ is the $l^{th}$ $k-$step Fibonacci number. For example if $k=6,$ the sequence $F_l^{(6)}$ starts with $1,1,2,4,8,16,32,63,\ldots$. The probability in (1) is of course the probability that no set of $1$'s supported on an arithmetic progression of length $k$ and difference $d=1$ exist. The numerator is the cardinality of all sequences which have no $k$ consecutive $1$'s.

What if I allowed an arbitrary $d$ (of course $kd\leq n$ must hold) and asked the question as follows:

How many sequences of length $n$ support no all $1$-valued arithmetic progression of length $k$?

How does the probability change? It goes down, of course. Is there any hope of a closed form solution? Is it tangentially related to Szemeredi's Theorem? There, the question is about the length that guarantees the existence of such a subsequence (when interpreted in characteristic function terms), given a density for a subset of $\{1,2,\ldots,n\}$ (relative number of 1's).

I am willing to assume a density that is not too far below $1/2$ for my question.

• Thanks! I was going to ask about $p\neq 1/2$ but a paper the authors of the note you refer to also settles that case. Do you mind stating the main result in your answer for completeness' sake, so I can accept it? – kodlu May 15 '16 at 22:24
In the paper "Maximal Arithmetic Progressions in Random Subsets" by Itai Benjamini, Ariel Yadin, and Ofer Zeitouni, arXiv:0707.3888, referred to in the first answer by user91686, the authors show that $$(U^{(N)}- 2 \ln(N))/\ln(2)$$ converges in law to an extreme type (asymmetric) distribution, where $U^{(N)}$ is the maximal length of arithmetic progressions in a random uniform subset of $\{0,1\}^N$. The same result holds for the maximal length $W^{(N)}$ of arithmetic progressions $(mod~ N)$.
M.-Z. Zhao and H.-Z. Zhang, in "On the longest length of arithmetic progressions", arXiv:1204.1149, consider a random subset of $\{1,\ldots,n\}$ obtained by choosing each point in $\{1,\ldots,n\}$ with probability $p_n\neq 1/2$ to be in the set. They then establish various limiting results for the variables $U^{(n,p_n)}$ and $W^{(n,p_n)}$ in this more general case.
Interestingly, assuming $p_n\rightarrow 0,$ and $n p_n \rightarrow \infty$ as $n\rightarrow \infty$ they examine the limit $$\lim_n \frac{2\ln n}{-\ln p_n}=b$$ and conclude that $U^{(n,p_n)}$ and $W^{(n,p_n)}$ take on only a few values for a number of positive limit regimes for $b.$