HistogramValleyPartitionGenerator

Places cuts at the deepest valleys of a histogram of the data.

A mixture of well separated components shows as modes separated by troughs, and the trough is close to where the component densities cross. This generator therefore encodes a different belief about where a good partition lies than the within-group sum of squares criterion does: it looks for gaps in the data rather than for compact groups. Comparing fits initialized both ways is how the experiment measures whether that belief pays.

Bin boundaries are mapped to admissible cut positions, valleys are ranked by depth relative to the larger neighbouring peak, and the deepest are taken subject to leaving every group valid. When too few usable valleys are found, null is returned; the caller is expected to fall back to another generator rather than receive a partition that means nothing.

Bins are spaced by rank, not by value, and a bin's height is its density. Equal-width bins have no resolution where a skewed sample actually lives: on a production lead-time sample of 10,000 spanning four decades, fifty equal-width bins put 54% of the observations in the first bin, and every valley detectable in the remainder lay above the 95th percentile, so the generator could only ever report tail noise. Spacing the edges at equally spaced order statistics puts the resolution where the observations are and makes the rule scale-free, which matters because a positive quantity spanning decades is the ordinary case in input modeling rather than an awkward one.

Unequal widths make the two changes inseparable. With equal-width bins a count is proportional to a density and either may be compared; with rank-spaced bins every count is the same by construction, so counts carry no information at all and the height compared must be the count divided by the bin's width. A sparse stretch of the line then shows as a wide bin of low density, which is the gap this generator is looking for.

The bin count is set explicitly rather than left to automatic selection, since KSL's automatic binning is tuned for display and can return as few as two bins for a widely gapped sample. The default rule is the square root of the sample size, bounded to a sensible range.