Timeline for Random Balanced Assignment
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2017 at 10:36 | comment | added | Ben Barber | 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. | |
| Apr 3, 2017 at 7:46 | history | asked | Steve | CC BY-SA 3.0 |