2
This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $...
1
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
Only top voted, non community-wiki answers of a minimum length are eligible