2
$\begingroup$

Let $S_n$ denote the group of permutations on $n$ letters, and consider a subset $A = \{\sigma_1, \dots, \sigma_k\} \subset S_n$. We will say $A$ has a collision if there are two permutations in $A$ that agree at some letter, i.e. if there exist $\sigma_i, \sigma_j \in A$ and a letter $x$ such that $\sigma_i(x) = \sigma_j(x)$. If not, we will say $A$ is collision-free. (I just made up this term, but maybe there is a different standard term for it?)

Now suppose $\sigma_1, \dots, \sigma_k$ are sampled iid uniformly from $S_n$. In terms of $n,k$, what is the probability $p_{n,k}$ that $\{\sigma_1, \dots, \sigma_k\}$ is collision-free?

Asymptotics would be of interest.

For $k=2$, this is equal to the probability that a single random permutation has no fixed points, i.e. is a derangement. It's well known that for large $n$ this is approximately $1/e$.

Trivially, for $k > n$, by the pigeonhole principle, the probability is 0.

This came from a real-life application, sort of. I have $n$ students in a class who are writing term papers. I wanted to assign each student's paper for another student to review; obviously, no student should review their own paper. So if I assign them randomly, the probability of getting an acceptable assignment is $p_{n,2} \approx 1/e$. In particular, if I want to generate a random acceptable assignment, a rejection algorithm is reasonably efficient.

Then I thought, what if I want each paper to be reviewed by $k-1$ other students? Obviously, no student should be assigned their own paper, and no student should be assigned the same paper more than once. So if I assign them randomly, the probability of an acceptable assignment is $p_{n,k}$.

(Note that this is not the same question as Probability of a Collision in Selection of Permutations, despite the similar terminology.)

$\endgroup$
0
$\begingroup$

Fix the first permutation. Then the probability that the second is collision free is $\approx (\frac {n-1}n)^n\approx e^{-1}$. Given that, probability that the third permutation is collision free is $\approx (\frac {n-2}n)^n\approx e^{-2}$ and so on. Hence if $k \ll n$ (though we might need $<\approx \sqrt n$ instead) we get $$p_{n,k}\approx e^{-k(k-1)/2}$$ Another way to look at it is that there are $P=k(k-1)/2$ pairs of permutations and for low $k$ their collisions are only weakly correlated - hence $$p_{n,k}\approx p_{n,2}^{P}$$ This approximation is an upper bound for $p_{n,k}$ (and for even $n$ we also have $p_{n,2}<e^{-1}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.