If you have a uniform sample of size $\ell$ of integers taken from $[1,\dots,n]$ which is then sorted, how do you calculate the probability that there exists an equally spaced subsequence of length $k$ (or at least $k$)?
As an example, if the sample is $\{1,5,10, 15,18,20\}$ so $\ell = 6$ and let us say that $n= 30$, then there is a subsequence of length $4$ which are equally spaced from each other.
Here is an attempt. It seems that unless $\ell$ is a constant fraction of $n$ we expect to see only very short arithmetic progressions (APs). On the other hand, if $\ell > \epsilon n$ for some constant $\epsilon>0$, then there will be APs of logarithmic length.
Here is the proof:
Let us first count how many arithmetic progressions of length $t$ there are in the interval $[1,n]$.
Claim1: The number of arithmetic progressions of length $t$ in the interval $[1,n]$ is $\approx n^2/2t$
Proof:The number of $t$-APs with difference 1 is $n-t$. The number of $t$-APs with difference 2 is $n-2t$. And so on. Therefore, the number of APs in the interval $[1,n]$ is $$ (n-t) + (n-2t) + (n-3t) + \dots + (n - \frac{n}{t}t) \approx n^2/2t. $$
Let us fix a $t$-AP. We ask what is the probability that a random sample $S \subseteq [n]$ of size $|S| = \ell$ contains this AP.
Claim2: $(\frac{\ell-t}{n-t})^t \leq \Pr[\{1,\dots,t\} \in S] \leq (\frac{\ell}{n})^t$.
Proof: Suppose we choose $S$ without repetitions. Then $\Pr[\{1,\dots,t\} \subseteq S] = \frac{{n-t \choose \ell - t}}{{n \choose \ell}}$.
Therefore, the expected number of $t$-APs in a random $S$ is $$ \frac{n^2}{2t} \cdot (\frac{\ell-t}{n-t})^t \leq \mathbb{E}[\text{number of $t$-APs in $S$}] \leq \frac{n^2}{2t} \cdot (\frac{\ell}{n})^t $$ Therefore, if $t > \frac{2\log(n)}{\log(n) - \log(\ell)}$, then we don't expect to see $t$-APs in a random sample of length $\ell$.
On the other hand, if $\ell > n^{1-2/t}$ then we expect to see $t$-APs.
