Return to Revisions

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 without replacement. The log likelihood that $\pi\in M_n$ is not covered by the composition is $\leq\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.