Lower bound for Adjusted Rand Index? From the original paper, it's not clear whether the adjusted rand index has a lower bound.
Does it? If so, what partition yields the bound?
If now, how can I construct partitions with arbitrary low ARI?
A naive try gave
ARI([0, 1, 0, 1], [0, 0, 1, 1]) = -.5
(written as cluster assignments).
 A: ARI equation is
$$\dfrac{\sum_{i,j}{n_{ij} \choose 2} - \sum_{i}{n_{i.} \choose 2}\sum_{j}{n_{.j} \choose 2} / {n \choose 2}}{\frac{1}{2}[\sum_{i}{n_{i.} \choose 2}+\sum_{j}{n_{.j} \choose 2}]-\sum_{i}{n_{i.} \choose 2}\sum_{j}{n_{.j} \choose 2} / {n \choose 2}}$$
To minimize ARI, $\sum_{i,j}{n_{ij} \choose 2}$ is minimized.
In a contingency table, all entry has 1 or 0, $\sum_{i,j}{n_{ij} \choose 2}$  = 0.
So numerator is negative, we need to minimize denominator.
To minimize $\sum_{i}{n_{i.} \choose 2}+\sum_{j}{n_{.j} \choose 2}$, all entry in a contingency table is evenly distributed.
Therefore I think that ARI is minimum when all entry in a contingency table has 1. When all entry in 2x1 contingency table is 1, ARI is 0. When all entry in 2x2 contingency table(your case) is 1, ARI is -0.5. When all entry in 2x3 contingency table is 1, ARI is -0.36. When 3x3, ARI is -0.33 and so on.
So I think lower bound of ARI is -0.5. :-)
-Haesun Park
A: Look at the rand index and adjustment equation. Don't look at a single example.
Obviously, to find the lower bound, you need to construct the worst possible clustering. This depends very much on your input data (e.g. cluster sizes, data set size), so there is not a general rule.
