Lutz–De Panafieu–Stein–Scott active clustering query complexity conjecture

Let $p_1\geq \dots \geq p_k$ be a probability distribution over $k$ parts. If $n$ elements are partitioned at random into $k$ parts by putting each element in part $i$ with probability $p_i$, independently of the other elements, then the expected number of membership queries required to reconstruct the partition is

$$(1+o(1))\sum_{i=1}^k i p_i n.$$

Active clustering query complexity conjecture. The average number of membership queries required is $(1+o(1))\sum_{i=1}^k i p_i n$. This conjecture concerns the optimal average query complexity of active clustering under an independently generated random partition with prescribed part probabilities. The cited work provides the optimal average query complexity in the uniformly random unrestricted-partition setting, while this more general distributional formula is presented as a conjecture.