3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

See http://arxiv.org/abs/0707.3888 for the length of arithmetic progressions in random sequences

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – kodlu May 15 '16 at 22:24
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.