Fix $\alpha, \epsilon \in(0,1)$. Take $(S\_n)\_n$ to be any sequence of sets with each $S\_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(S\_n^\ast)\_n$ by, for each $S^\ast\_n$, drawing $\lceil (n!)^{1-\alpha+\epsilon} \rceil$ permutations uniformly at random. Is it true that $|\{\pi \circ \pi^\ast: \pi\in S\_n, \pi^\ast \in S\_n^\ast\}|/n! \to 1$ in probability?



Do enough permutations of an initial set probably cover most permutations?
If $M\_n$ is all permutations of $n$ elements then $\{\pi \circ S\_n: \pi \in M\_n\}$ is precisely a $|S\_n|$-fold cover of $M\_n$. Choosing $S\_n^\ast$ and then forming the composition of $S\_n^\ast$ with $S\_n$ is like sampling this cover. The log likelihood that $\pi\in M\_n$ is not covered by the composition is $\log((1-|S\_n|/n!)^{|S\_n^\ast|})=\log(1-|S\_n|/n!)|S\_n^\ast|=[-|S\_n|/n! + O((|S\_n|/n!)^2)]|S\_n^\ast|$ which $\to -\infty$ if $|S\_n||S\_n^\ast|/n!\to \infty$, so the OP is true almost surely, not just in probability.


