Expected Misclustering rate I am reading this paper on minimax clustering error rates on high-dimensional Gaussian mixtures. The authors define a metric for expected misclustering rate as follows: 
For a two-component equivariance mixture with parameters $\theta$, the cluster assingment of point $x$ is obtained using 
\begin{align}
F_{\theta}(x)=\underset{i \in\{1,2\}}{\operatorname{argmax}} f\left(x ; \mu_{i}, \sigma^{2} I\right)
\end{align}
Let $F$ be another cluster assignment function, the expected misclustering rate is defined as follows: 
$$ L_{\theta}(F)=\min _{\pi} P_{\theta}\left(\left\{x : F_{\theta}(x) \neq \pi(F(x))\right\}\right) $$
where the minimum is over all permutations $\pi : \{1, 2\} → \{1, 2\}$. This is the probability of misclustering relative to an oracle that uses the true distribution to do optimal clustering.
I am unable to understand the reason for defining the rate as a minimum over all the set of permutation functions. I would have defined the expected misclustering error as 
$$ L_{\theta}(F)= P_{\theta}\left(\left\{x : F_{\theta}(x) \neq F(x) \right\}\right) = E_{\theta}\left( \Bbb{I}(F_{\theta}(x) \neq F(x))\right) $$
where $\Bbb{I}$ is the indicator function.  
 A: A clustering algorithm does not know what labels you used.
It will assign arbitrary numbers to all partitions.
So your true labels could be "apple" and "banana", but the clustering algorithm assings them to clusters 0 and 1.
The permutation formulation is supposed to be a hack that tries all possible pairings of how these labels could align. But the notatiin only works when both the clustering and the "truth Oracle" use numbers 0...k - so this is not very general, it's a "I'm stuck thinking in arrays of numbers" world view.
There are much cleaner solutions to this problem: the Adjusted Rand Index and the Normalized Mutual Information, for example. These formalisms properly work woth any labeling domain, as it only needs identity within each domain. They work on the set partitioning induced by such labels, not on the actual labels. You want the labeling [1, 1, 2, 2] and [apple, apple, banana, banana] to be equivalent, as this is the same partitioning of the data.
Once you get hierarchical results, there are no good measures anymore.
Plus there is the big hidden assumption that the truth oracle actually labels cluster, and not classes. Which usually is wrong except for synthetic data.
