# Hamming distance introduced by random permutation

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$$.

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$$.

Then

$$\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 )$$ tries: $$5000000$$, $$\mu=5.4000$$ (simulation : $$5.3992$$) , $$\sigma^2 =4.2400$$ (simulation : $$4.1940$$)