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

  • $\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 Aug 28 '17 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.