1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

enter image description here

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

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