Expected length of longest arithmetic sequence

Question

Given a natural number $n$, we define the vector valued random variable $\vec Y_n := (X_1, \ldots X_n)$ where all $X_i$ are independently uniformely distributed on $S_n := \{1, \ldots, n\}$.

Further we define the function $f: S_n^n \to \mathbb N$ where $f( \vec s )$ denotes the length of the longest subsequence of $(s_i)_{i=1}^n$ that forms an arithmetic progression.

Is it somehow possible to say anything (e.g. calculate the expected value) about the distribution of $f(\vec Y_n)$ or even calculate the distribution?

I have no idea how to work with the condition of the arithmetic subsequence.

Answer 1

This doesn't answer your exact question as stated, but in this paper it is proven that if $\vec{Y}_n$ is a random permutation of the first $n$ integers, then the expected length of its longest subsequence is roughly $\log n/\log\log n$. My suspicion is that one could use nearly identical ideas from that paper to show that the same thing holds for your variant of the problem.