O(log n) bimodality analysis

摘要

The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P1 and P2. If P is a mixture of two (approximately) Gaussian subpopulations, then P1 and P2 are good approximations to the original Gaussians, if their Fisher distance is great enough. Moreover, good approximations to P1 and P2 can be obtained by dividing P into small parts; finding the maximum-distance (MD) subdivision of each part; combining small groups of these subdivisions into (approximate) MD subdivisions of larger parts; and so on. This divide-and-conquer approach yields an approximate MD subdivision of P in O(log n) computational steps using O(n) processors, where n is the size of P.