Retrieving minimum width that contains specified fraction of all values

I'd like to find the min/max boundaries of a sliding window of minimum size that contains a certain fraction of the total number of elements in an array or collection of numbers.

Example: taking integers to make it easier to explain, say the proportion of elements that we're looking for is 50% on this array:

[1,1,2,3,3,3,3,3,3,4,5,6,7,8,9,10]

The mystery function would return something like ( 2, 4 ), meaning that the minimum value is 2 and the max value is 4 (let's assume it's inclusive and note that these are VALUES, not indices). That little window contains 8 of the 16 values and it's only 2 units wide, the narrowest such window that contains half the number of values.

Note: the quartiles are [1,1,2,3], [3,3,3,3], [3,4,5,6], [7,8,9,10] so they are NOT what I'm looking for.

I can code it...may take some time to get it nice. Hopefully somebody has run across it before. Does it have a name? Is there an existing method that somebody knows about?

I am interested in Python implementations.

UPDATE:

Thanks to Glen_b who gave the names 'short-half' and 'shortest interval' I was able to come up with this: Find probability density intervals

• "I hope it's ok to put this on stats AND stackoverflow" -- It's discouraged, as the help indicates: "Please note, however, that cross-posting is not encouraged on SE sites. Choose one best location to post your question. Later, if it proves better suited on another site, it can be migrated.". So pick one, delete the other. Commented Nov 18, 2013 at 6:03
• When it's 50% such an interval is sometimes called a short half. More generally it might sometimes be called a shortest interval. Commented Nov 18, 2013 at 6:07
• oops. thanks for the heads up. I removed the post on stackoverflow. I'll look up 'short half' Commented Nov 18, 2013 at 6:10
• (looking at the link) Interestingly, I debated mentioning HPD intervals, but they really apply to distributions; I assumed people wouldn't apply the same term to samples but couldn't find what they should be called. Turns out I was wrong. Commented Nov 18, 2013 at 9:19
• Incidentally, what you think are quartiles aren't quartiles, but the data between consecutive quartiles (and below/above the first and third ones respectively) Commented Nov 18, 2013 at 9:25

• A keyword is shorth.

• For an R implementation and links to a current project with publications, see Günther Sawitzki's page at http://www.statlab.uni-heidelberg.de/people/gs/

• There is a Stata implementation, which can be installed by ssc inst shorth.

More slowly, and without trying to do justice to Sawitzki's work:

The order statistics of a sample of $n$ values of $x$ are defined by

$x_{(1)} \le x_{(2)} \le \cdots \le x_{(n-1)} \le x_{(n)}.$

Let $h = \lfloor n / 2\rfloor$. Then the shortest half of the data from rank $k$ to rank $k + h$ is identified to minimise $x_{(k + h)} - x_{(k)}$ over $k = 1, \cdots, n - h$. This interval we call the length of the shortest half.

The shorth was named by J.W. Tukey and introduced in the Princeton robustness study of estimators of location by Andrews, Bickel, Hampel, Huber, Rogers and Tukey (1972, p.26) as the mean of $x_{(k)}, \cdots, x_{(k + h)}$. It attracted attention for its unusual asymptotic properties (pp.50-52): on those, see also the later accounts of Shorack and Wellner (1986, pp.767-771) and Kim and Pollard (1990). Otherwise it quickly dropped out of sight for about a decade. Incidentally, Hampel (1997) shows that results available to the Princeton study on asymmetric situations, but not fully analysed at the time, put the shorth in better light than was then appreciated.

Interest revived in such ideas when Rousseeuw (1984), building on a suggestion by Hampel (1975), pointed out that the midpoint of the shortest half $(x_{(k)} + x_{(k + h)}) / 2$ is the least median of squares (LMS) estimator of location for $x$. See Rousseeuw (1984) and Rousseeuw and Leroy (1987) for applications of LMS and related ideas to regression and other problems. Note that this LMS midpoint is also called the shorth in some recent literature (e.g. David and Nagaraja 2003, p.223; Maronna, Martin and Yohai 2006, p.48). Further, the shortest half itself is also sometimes called the shorth, as the title of Grübel (1988) indicates.

The length of the shortest half is a robust measure of scale or spread: see Rousseeuw and Leroy (1988), Grübel (1988), Rousseeuw and Croux (1993) and Martin and Zamar (1993) for further analysis and discussion.

The length of the shortest half in a Gaussian (normal) with mean 0 and standard deviation 1 is 1.349 to 3 d.p. Thus to estimate standard deviation from the observed length, divide by this Gaussian length.

Some broad-brush comments follow on advantages and disadvantages of shortest half ideas, from the standpoint of practical data analysts as much as mathematical or theoretical statisticians. Whatever the project, it will always be wise to compare shorth results with standard summary measures (including other means, notably geometric and harmonic means) and to relate results to graphs of distributions. Moreover, if your interest is in the existence or extent of bimodality or multimodality, it will be best to look directly at suitably smoothed estimates of the density function.

• Simplicity The idea of the shortest half is simple and easy to explain to students and researchers who do not regard themselves as statistical specialists. It leads directly to two measures of location and one of spread that are fairly intuitive. It is also relatively amenable to hand calculation with primitive tools (pencil and paper, calculators, spreadsheets).

• Connections The similarities and differences between the length of the shortest half, the interquartile range and the median absolute deviation from the median (MAD) (or for that matter the probable error) are immediate. Thus, shortest half ideas are linked to other statistical ideas that should already be familiar to many data analysts.

• Graphic interpretation The shortest half can easily be related to standard displays of distributions such as cumulative distribution and quantile plots, histograms and stem-and-leaf plots.

• Mode By averaging where the data are densest, the shorth and also the LMS midpoint introduce a mode flavour to summary of location. When applied to distributions that are approximately symmetric, the shorth will be close to the mean and median, but more resistant than the mean to outliers in either tail and more efficient than the median for distributions near Gaussian (normal) in shape. When applied to distributions that are unimodal and asymmetric, the shorth and the LMS will typically be nearer the mode than either the mean or the median. Note that the idea of estimating the mode as the midpoint of the shortest interval that contains a fixed number of observations goes back at least to Dalenius (1965). See also Robertson and Cryer (1974), Bickel (2002) and Bickel and Frühwirth (2006) on other estimators of the mode. The half-sample mode estimator of Bickel and Frühwirth is especially interesting as a recursive selection of the shortest half. Stata users can download a Stata implementation by ssc inst hsmode.

• Outlier identification A resistant standardisation such as (value - shorth) / length may help in identifying outliers. For discussions of related ideas, see Carey et al. (1997) and included references.

• Generalise to shortest fraction The idea can be generalised to proportions other than one-half.

At the same time, note that

• Not useful for all distributions When applied to distributions that are approximately J-shaped, the shorth will approximate the mean of the lower half of the data and the LMS midpoint will be rather higher. When applied to distributions that are approximately U-shaped, the shorth and the LMS midpoint will be within whichever half of the distribution happens to have higher average density. Neither behaviour seems especially interesting or useful, but equally there is little call for single mode-like summaries for J-shaped or U-shaped distributions; for J shapes, the mode is, or should be, the minimum and for U shapes, bimodality makes the idea of a single mode moot, if not invalid.

• Ties The shortest half may not be uniquely defined. Even with measured data, rounding of reported values may frequently give rise to ties. What to do with two or more shortest halves has been little discussed in the literature. Note that tied halves may either overlap or be disjoint. Different implementations may tackle this in slightly different ways.

• Rationale for window length Why half is taken to mean $1 + \lfloor n / 2\rfloor$ also does not appear to be discussed. Evidently we need a rule that yields a window length for both odd and even $n$; it is preferable that the rule be simple; and there is usually some slight arbitrariness in choosing a rule of this kind. It is also important that any rule behave reasonably for small $n$: even if a program is not deliberately invoked for very small sample sizes the procedure used should make sense for all possible sizes. Note that, with this rule, given $n = 1$ the shorth is just the single sample value, and given $n = 2$ the shorth is the average of the two sample values. A further detail about this rule is that it always defines a slight majority, thus enforcing democratic decisions about the data. However, there seems no strong reason not to use $\lceil n / 2\rceil$ as an even simpler rule, except that all authors on the shorth appear to have followed $1 + \lfloor n / 2\rfloor$.

• Use with weighted data Identification of the shortest half would seem to extend only rather messily to situations in which observations are associated with unequal weights.

• Length when most values identical When at least half of the values in a sample are equal to some constant, the length of the shortest half is 0. So, for example, if most values are 0 and some are larger, the length of the shortest half is not particularly useful as a measure of scale or spread.

Andrews, D.F., P.J. Bickel, F.R. Hampel, P.J. Huber, W.H. Rogers and J.W. Tukey. 1972. Robust estimates of location: survey and advances. Princeton, NJ: Princeton University Press.

Bickel, D.R. 2002. Robust estimators of the mode and skewness of continuous data. Computational Statistics & Data Analysis 39: 153-163.

Bickel, D.R. and R. Frühwirth. 2006. On a fast, robust estimator of the mode: comparisons to other estimators with applications. Computational Statistics & Data Analysis 50: 3500-3530.

Carey, V.J., E.E. Walters, C.G. Wager and B.A. Rosner. 1997. Resistant and test-based outlier rejection: effects on Gaussian one- and two-sample inference. Technometrics 39: 320-330.

Christmann, A., U. Gather and G. Scholz. 1994. Some properties of the length of the shortest half. Statistica Neerlandica 48: 209-213.

Dalenius, T. 1965. The mode - A neglected statistical parameter. Journal, Royal Statistical Society A 128: 110-117.

Grübel, R. 1988. The length of the shorth. Annals of Statistics 16: 619-628.

Hampel, F.R. 1975. Beyond location parameters: robust concepts and methods. Bulletin, International Statistical Institute 46: 375-382.

Hampel, F.R. 1997. Some additional notes on the "Princeton robustness year". In Brillinger, D.R., L.T. Fernholz and S. Morgenthaler (eds) The practice of data analysis: essays in honor of John W. Tukey. Princeton, NJ: Princeton University Press, 133-153.

Kim, J. and D. Pollard. 1990. Cube root asymptotics. Annals of Statistics 18: 191-219.

Maronna, R.A., R.D. Martin and V.J. Yohai. 2006. Robust statistics: theory and methods. Chichester: John Wiley.

Martin, R.D. and R.H. Zamar. 1993. Bias robust estimation of scale. Annals of Statistics 21: 991-1017.

Robertson, T. and J.D. Cryer. 1974. An iterative procedure for estimating the mode. Journal, American Statistical Association 69: 1012-1016.

Rousseeuw, P.J. 1984. Least median of squares regression. Journal, American Statistical Association 79: 871-880.

Rousseeuw, P.J. and C. Croux. 1993. Alternatives to the median absolute deviation. Journal, American Statistical Association 88: 1273-1283.

Rousseeuw, P.J. and A.M. Leroy. 1987. Robust regression and outlier detection. New York: John Wiley.

Rousseeuw, P.J. and A.M. Leroy. 1988. A robust scale estimator based on the shortest half. Statistica Neerlandica 42: 103-116.

Shorack, G.R. and J.A. Wellner. 1986. Empirical processes with applications to statistics. New York: John Wiley.

• Thanks; I knew there was an abbreviated term when I mentioned the short half, but couldn't think of what it was. Commented Nov 18, 2013 at 9:16
• +6 Amazing post: informative, insightful, and fun to read.
– whuber
Commented Nov 21, 2013 at 18:41
• @whuber Thanks very much; praise from the praiseworthy is praise indeed. It's mostly a version of documentation for my Stata implementation downloadable to Stata users by ssc inst shorth and otherwise visible at econpapers.repec.org/software/bocbocode/s456728.html (non-Stata users won't get anything extra by looking there). Commented Nov 21, 2013 at 19:06
• very nice! apologies for taking so long to accept it as the answer...it dropped off the radar pretty quickly. Commented Jan 25, 2018 at 21:13