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.



Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$
**Answer added for completeness' sake:**


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.$ 


