6
$\begingroup$

A balanced assignment from from $N$ objects to $K$ classes is a mapping $\sigma\colon \{ 1, \ldots, N\} \rightarrow \{ 1, \ldots, K\}$ such that $$ \textrm{Card}( \sigma^{-1} \{j \} ) = \textrm{Card} ( \{ i\colon \sigma (i) = j\} ) = N /K,~~ \forall j \in \{ 1, \ldots, K\}. $$ That is, $\sigma$ maps exactly $N/K$ elements to each class. Here we assume $N/K$ is an integer. We denote by $\mathcal P_{N,K}$ the set of all balanced assignments.

For $\sigma, \tau \in \mathcal P_{N,K}$, we define the distance between $\sigma$ and $\tau$ as $$ d(\sigma, \tau) = \min_{\phi \in \Pi_K} \sum_{i=1}^N \mathbf{1} \{ \sigma (i) \neq \phi ( \tau(i) ) \}, $$ where $\Pi_K$ is the set of all permutations of $\{ 1, \ldots, K\}$. Thus $d(\sigma, \tau)$ is the minimum number of elements assigned to different classes up to permutation of labels.

Now we fix $\tau $ to be any fixed balanced assignment and let $\sigma$ be chosen uniformly over $\mathcal{P}_{N,K}$, what is the distribution of $d(\sigma, \tau)$?

Improve this question
$\endgroup$
1
  • $\begingroup$ I'll record a tiny observation. Switch perspective to talk about similarity rather than difference, and forget temporarily about permutation of labels: that is, consider $s(\sigma, \tau) = \sum_{i=1}^N \mathbf{1}\{\sigma(i) = \tau(i)\}$. Each summand has a hypergeometric distribution, so for fixed $K$ and large $N$ is concentrated near $N/K^2$. The same is true for the similarity of $\sigma$ and every permutation of the labels of $\tau$, so we can at least say that, for fixed $K$, $d(\sigma, \tau) = \frac{K-1}K(N + O(\sqrt N))$ with high probability. $\endgroup$
    – Ben Barber
    Commented Aug 28, 2017 at 10:36

0

Reset to default

You must log in to answer this question.