Let $M$ be a random permutation matrix of size $N \times N$, i.e. a uniform random choice out of the set of all permutation matrices of size $N \times N$. Furthermore, let $v = (v_1, v_2, \dots, v_N)^{T}$ be an $N$-vector of integers. What is the probability that the random permutation $M$ changes exactly $k$ elements of $v$, i.e. that the Hamming distance $H(v,M.v)$ between $v$ and $M \cdot v$ equals $k$?

When all elements are unique ($\forall i, j \in [1, N]: i \neq j \Rightarrow v_i \neq v_j$), then the solution is more straightforward. There are $N!$ possible permutations of the entries of $v$. There are $\text{binomial}(N, k)$ ways of selecting $k$ items from a list of $N$, and there are $\text{subfactorial}(k)$ permutations of $k$ items that change the positions of all $k$ items. Therefore, the probability that a random permutation changes exactly $k$ out of $N$ entries is

$$P(H(v,M.v) = k\,|\,i \neq j \Rightarrow v_i \neq v_j) = \frac{\text{binomial}(N, k) \, \text{subfactorial}(k)}{N!}.$$

This distribution has almost all probability mass where $k$ is close to $N$.

But what is the probability that the random permutation $M$ changes exactly $k$ elements of $v$, when some of the elements in $v$ repeat?

I expect the probability mass to shift towards zero. For example, in the extreme case where all $v_i$ are identical, the probability is 1 for $H(v, M.v) = 0$ and 0 otherwise. We can use that it should not matter how the elements in $v$ are ordered initially, so we may assume some practical ordering for $v$, e.g. $v = (1, 1, 1, 1, 2, 2, 2, 3, 4, 5)$, where $N=10$.


1 Answer 1


A (quite obvious) approximation for large $N$, is to consider that the probability of coincidence for each element are independent.

Let $L$ be the number of concidences (so the Hamming distance is $N-L$).

Let the $N$ elements be grouped in $J$ groups, with $n_j$ ($j=1 \cdots J$) equally valued elements in each group. Hence $\sum_{j=1}^J n_j = N$.


$$ \mu=E[L] = \sum_{j=1}^J \frac{n_j^2}{N} \tag1$$ $$ \sigma^2 =Var[L] = \sum_{j=1}^J \frac{n_j^2}{N} \left(1-\frac{n_j}{N}\right) \tag2$$

The mean $(1)$ is exact, because of linearity. The variance $(2)$ is only true as an approximation (it would be exact if the coincidences were independent, which is not true).

Further, we can approximate the mass probabilities function $P(L=\ell)$ by a Gaussian (CLT), with the parameters as computed above. I would expect this to be a good approximation for values not too far from the mean (and large $N$).

A better (empirically) approximation is to fit a Binomial with mean and variance from $(1)$ and $(2)$; i.e. a $Binom(\tilde N,\tilde p)$, where

$$\tilde p=1-\sigma^2/\mu \tag3$$ $$\tilde n=\mu/\tilde p \tag4$$

Hence, under this approximation, $$ P(L=\ell)=\binom{\tilde n}{ \ell}\tilde p^{\ell} (1- \tilde p)^{\tilde n-\ell} \tag5$$

(notice that $\tilde n$ is non integer, so you should either use the Beta function, or round)

Here's an example, for $N=30$ and $n_j=(8, 7, 5, 3, 3, 2, 1, 1 )$

enter image description here

tries: $5000000$, $\mu=5.4000 $ (simulation : $5.3992$) , $\sigma^2 =4.2400 $ (simulation : $4.1940$)


You must log in to answer this question.

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