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?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ by "with high probability", do you mean "almost surely"? $\endgroup$– mathworker21Commented Dec 26, 2020 at 13:46
-
$\begingroup$ i didn't mean that in the original post but i guess it is true $\endgroup$– Christian ChapmanCommented Dec 26, 2020 at 14:08
-
$\begingroup$ what does "with high probability" mean? $\endgroup$– mathworker21Commented Dec 26, 2020 at 14:11
-
$\begingroup$ sorry, i misspoke. meant converges "in probability" not "with high probability" $\endgroup$– Christian ChapmanCommented Dec 26, 2020 at 14:18
-
$\begingroup$ I guess I could have meant something by "with high probability"... it could have been that there was a sequence of $S_n$ put together so that the quotient only goes to 1 with probability $f(\alpha,\varepsilon)< 1$. $\endgroup$– Christian ChapmanCommented Dec 31, 2020 at 2:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Dec 26, 2020 at 14:05