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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .