For $k \ge 4$, the expected time until the first duplicate is $O(\sqrt{n})$. This leaves the case $k=3$ [Edit: The case of $k=3$ is resolved below with a construction with expected first duplicate at about $n/4$].

Let $D_i$ be the number of duplicates in the first $i$ values. The expected time until the first duplicate equals $\sum_{i=0}^n P(D_i = 0)$. We can use the second moment method to estimate these probabilities well enough when $k\ge 4$.

$E(D_i) = {i \choose 2}/n$.

$E(D_i^2) = {i \choose 2}^2/n^2 + {i \choose 2}(1/n - 1/n^2)$.

$\text{Var}(D_i) = E(D_i^2) -E(D_i)^2 = {i \choose 2}(1/n - 1/n^2) \le {i \choose 2}/n$.

So, $0$ is at least $\sqrt{{i \choose 2}/n}$ standard deviations away from the mean of $D_i$. By Chebyshev's inequality, $P(D_i =0)$ is at most $n/{i \choose 2} \le \frac{2n}{(i-1)^2}$. As a probability, it is also at most $1$, and we'll use that estimate for small $i$.

$$\sum_{i=0}^n P(D_i = 0)$$

$$\le \sum_{i=0}^{\lceil \sqrt{2n}\rceil} 1 + \sum_{i=\lceil \sqrt{2n}\rceil+1}^n \frac{2n}{(i-1)^2}$$

$$ \le 3 + \sqrt{2n} + \int_{\sqrt{2n}}^n \frac {2n}{x^2}dx$$

$$ = 1 + 2\sqrt{2n}.$$

This is about a factor of $4\sqrt{2}$ off of the lower bound in the comments.

To solve the $k=3$ case, we'll construct some processes which are not $3$-independent, then take a mixture which is $3$-independent and which has an expected first duplicate of about $n/4$.

For simplicity, we'll ignore times beyond $n$. Any random prefix on the first $n$ can be extended by appending an independent uniform sequence, and the choice of extension has no effect on the expected first duplicate.

Consider random functions $f$ which are symmetric both on the domain $\lbrace 1,...,n \rbrace$ and range $\lbrace 1,...,n \rbrace$. Such a function corresponds to a $3$-independent process if and only if $P(f(1) = f(2) = f(3)) = 1/n^2$ and $P(f(1)=f(2)\ne f(3))=(n-1)/n^2.$

Let $f_0$ denote random bijections between the domain and range. $P(f_0(1) = f_0(2) = f_0(3))=0.$ $P(f_0(1)=f_0(2)\ne f_0(3))=0.$

Let $f_1$ denote random constant maps. $P(f_1(1) = f_1(2) = f_1(3))=1.$ $P(f_1(1)=f_1(2)\ne f_1(3))=0.$

Suppose $n = 9m$. Choose a random set partition of $\lbrace 1,...,n \rbrace$ into $3m$ pairs and $m$ triplets. Choose $4m$ distinct values for the parts, and let $f_2$ take these values on the parts. $P(f_2(1) = f_2(2) = f_2(3)) = m/{n \choose 3} \approx \frac 2{3n^2} \lt 1/n^2.$ $P(f_2(1)=f_2(2)\ne f_2(3)) = \frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2} = \frac{4(n^2-3n+1)}{3 n(n^2-3n+2)}\approx \frac{4}{3n} \gt (n-1)/n^2.$ The first term, $\frac{2}{3n},$ corresponds to the possibility that $1$ is part of a pair and $2$ is the second point in the pair. The second term corresponds to the possibility that $1$ and $2$ are part of a triplet and $3$ is not the third point of the triplet.

$(1/n^2, (n-1)/n^2)$ is in the convex hull of $(0,0)$, $(1,0)$, and $(m/{n \choose 3},\frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2})$. So, some mixture of $f_0$, $f_1$, and $f_2$ is $3$-independent. Specifically,

$$\frac{n^4-13n^2+16n-4}{4n^4-12n^3+4n}f_0 + \frac{n^2-5n+2}{2n^4-6n^3+2n^2}f_1 + \frac{3n^3 - 12n^2+15n-6}{4n^3-12n^2+4n}f_2 $$

is $3$-independent. This mixture gives a weight of $1/4 + o(1)$ to $f_0$, which has expected first duplicate time of $n+1$, so the expected first duplicate of the mixture is at least $(1/4+o(1))n$.

We can use slightly different set partitions when $n$ is not a multiple of $9$. The $2/3:1/3$ split into pairs and triplets was not optimized, so perhaps some other ratio would give a better proportion of $f_0$ in the mixture, hence a better coefficient of $n$ in the expected time of the first duplicate.

7more comments