1
$\begingroup$

Given an ordered multiset, such as $\{1,2,2,3,3,3,4,4,4,4\}$, what is the expected number or proportion of matching elements under a random permutation? In other words, how many times would you expect to see an equivalent value in the same position as in the original?

Empirically the answer in this case seems to be approximately 3, but I would like a closed-form solution, if one exists. I'd also be interested to work out the distribution over the random variable denoting the number of matches, but its expectation is my primary focus.

If the multiset contains $n$ unique values with multiplicities $m_i$, where $i \in \{1,2,\ldots,n\}$ and $\sum_i m_i = N$, I know that the total number of unique permutations is given by the multinomial coefficient $$\frac{N!}{m_1!\,m_2!\,\cdots\, m_n!} \; .$$ It seems that the number of cases in which an element with original label $i$ retains that label is $$\frac{m_i!\,(N-m_i)!}{\prod_{j \neq i}m_j!}$$ (because we can imagine the elements being shuffled separately within and between the label of interest), but I can't see this line of reasoning getting me very far because the probabilities of each position retaining its value are not independent.

I believe the multivariate hypergeometric distribution governs the number of elements with each label in a partial permutation of such a multiset, but again it's not obvious to me that that helps me get at the distribution I really want.

$\endgroup$
  • 1
    $\begingroup$ For the expected number of matches, let $X_i = 1$ if the $i$th element in the sequence matches, zero otherwise. It should be easy to find $P(X_i=1) = E(X_i)$. Then use linearity of expectation to find the expected value of the sum of the $X_i$s. $\endgroup$ – awkward Jan 15 '18 at 12:58
  • $\begingroup$ Oh dear, I'd forgotten that linearity of expectation applies even when the constituent RVs are not independent. Thanks! $\endgroup$ – Jon Clayden Jan 15 '18 at 13:26
1
$\begingroup$

Thanks to @awkward's nudge I got the rest of the way myself. For posterity, this is the outline of it.

First of all, the second expression I gave above is not right. The number of cases preserving one element with label $i$ is actually $$\frac{(N-1)!}{(m_i-1)!\,\prod_{j \neq i}m_j!} \; ,$$ the number of combinations of all elements except the one staying the same.

Then, introducing $X_l$, with $l \in \{1,2,\ldots,N\}$, as the random variable with value 1 if element $l$ from group $i$ retains its label, and 0 otherwise, we divide the expression above by the total number of permutations, to obtain $$\mathbb{E}(X_l) = \Pr(X_l=1) = \frac{(N-1)!}{(m_i-1)!\,\prod_{j \neq i}m_j!} \frac{m_1!\,m_2!\,\cdots\, m_n!}{N!} = \frac{(N-1)!\, m_i!}{(m_i-1)!\,N!} = \frac{m_i}{N} \; .$$ Taking $X = X_1 + X_2 + \ldots + X_N$, we can use the linearity of expectations to arrive at $$\mathbb{E}(X) = \sum_l \mathbb{E}(X_l) = \sum_{i=1}^n m_i \frac{m_i}{N} = \frac{1}{N} \sum_{i=1}^n m_i^2 \; .$$ For the specific example I gave, the multiplicities are $\{1,2,3,4\}$, and $N=10$, so the resulting expectation is $$\mathbb{E}(X) = \frac{1+4+9+16}{10} = 3 \; ,$$ as determined empirically.

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