format: text

text:
# Finding an Upper Limit in the Presence of Unknown Background

## I Introduction

Suppose we have an experiment whose events are distributed along a one-dimensional interval. The events are produced by a process for which the expected shape of the event distribution is known, but with an unknown normalization. In addition to the signal, there may also be a background whose expectation value per unit interval is known, but one cannot completely exclude the possibility of an additional background whose expectation value per unit interval is non-negative, but is otherwise unknown. If the experimenters cannot exclude the possibility that the unknown background is large enough to account for all the events, they can only report an upper limit on the signal. Even experimenters who think they understand a background well enough to subtract it may wish to allow for the possibility that they are mistaken by also presenting results without subtraction. Methods based on likelihood, such as the approach of Feldman-Cousins FeldCous , or Bayesian analysis, cannot be applied because the likelihood associated with an unknown background is unknown. An example of this situation is analysis of an experiment which tries to detect recoil energies, $`E_{\mathrm{recoil}}`$, deposited by WIMPs bouncing off atoms in a detector. For a given WIMP mass, and assumed WIMP velocity distribution, the shape of the distribution in $`E_{\mathrm{recoil}}`$ can be computed, but the WIMP cross section is unknown, and it is hard to be certain that all backgrounds are understood. The simplest way of dealing with such a situation is to pick an interval in, say, $`E_{\mathrm{recoil}}`$, and take as upper limit the largest cross section that would have a significant probability, say 10%, of giving as few events as were observed, assuming all observed events were from WIMPs. One problem with this naive method is that it can be very sensitive to the interval chosen. It is typical for the bottom of a detector’s range of sensitivity to be limited by noise or other backgrounds. Thus if the interval extends to especially low $`E_{\mathrm{recoil}}`$, there will be many events, leading to a weaker (higher) upper limit than is required by the data. On the other hand, experimenters could inadvertently bias the result by choosing the interval’s endpoints to give especially few events, with an upper limit that is lower than is justified by the data. In order to avoid such a bias, it might be thought best to avoid using the observed events to select the interval used. But the procedures discussed here take the opposite approach. The range is carefully chosen to include especially few events compared with the number expected from a signal. The way the range is chosen makes the procedure especially insensitive to unknown background, which tends to be most harmful where there are especially many events compared with the number expected from a signal. It would be a mistake to compute the upper limit as if the interval were selected without using the data; so the computation is designed to be correct for the way the data are used.

While the methods described here cannot be used to identify a positive detection, they are appropriate for obtaining upper limits from experiments whose backgrounds are very low, but non-zero. These methods have been used by the CDMS experiment CDMS .

## II Maximum Gap Method

Figure 1 illustrates the maximum gap method. Small rectangles along the horizontal axis represent events, with position on the horizontal axis representing some measured parameter, say “energy”, $`E`$. The curve shows the event spectrum, $`dN/dE`$, expected from a proposed cross section, $`\sigma `$. If there is a completely known background, it is included in $`dN/dE`$. But whether or not there is a completely known background, we assume there is also an unknown background contaminating the data. To set an upper limit, we vary the proposed size of $`\sigma `$ until it is just high enough to be rejected as being too high. We seek a criterion for deciding if a proposed signal is too high. Since there are especially many events at low E, while $`dN/dE`$ is not especially high there, those events must be mostly from the unknown background. If we only looked at the low energy part of the data, we would have to set an especially weak (high) upper limit. To find the strongest (lowest) possible upper limit, we should look at energies where there aren’t many events, and therefore isn’t much background.

Between any two events, $`E_\mathrm{i}`$ and $`E_{\mathrm{i}+1}`$, there is a gap. For a given value of $`\sigma `$, the “size” of the gap can be characterized by the value within the gap of the expected number of events,

$$x_\mathrm{i}=_{E_\mathrm{i}}^{E_{\mathrm{i}+1}}\frac{dN}{dE}𝑑E.$$
(1)
The “maximum gap” is the one with the greatest “size”; it is the largest of all the $`x_\mathrm{i}`$. The bigger we assume $`\sigma `$ to be, the bigger will be the size of the maximum gap in the observed event distribution. If we want, we can choose $`\sigma `$ so large that there are millions of events expected in the maximum gap. But such a large $`\sigma `$ would be experimentally excluded, for unless a mistake has been made, it is almost impossible to find zero events where millions are expected. To express this idea in a less extreme form, a particular choice of $`\sigma `$ should be rejected as too large if, with that choice of $`\sigma `$, there is a gap between adjacent events with “too many” expected events. The criterion for “too many” is that if the choice of $`\sigma `$ were correct, a random experiment would almost always give fewer expected events in its maximum gap. Call $`x`$ the size of the maximum gap in the random experiment. If the random $`x`$ is lower than the observed maximum gap size with probability $`C_0`$, the assumed value of $`\sigma `$ is rejected as too high with confidence level $`C_0`$. Since $`x`$ is unchanged under a one-one transformation of the variable in which events are distributed, one may make a transformation at a point from whatever variable is used, say $`E`$, to a variable equal to the total number of events expected in the interval between the point and the lowest allowed value of $`E`$. No matter how events were expected to be distributed in the original variable, in the new variable they are distributed uniformly with unit density. Thus any event distribution is equivalent to a uniform distribution of unit density. The probability distribution of $`x`$ depends on the total length of this uniform unit density distribution, and in this new variable the total length of the distribution is equal to the total expected number of events, $`\mu `$, but it does not depend on the shape of the original event distribution. $`C_0`$, the probability of the maximum gap size being smaller than a particular value of $`x`$, is a function only of $`x`$ and $`\mu `$:

$$C_0(x,\mu )=\underset{k=0}{\overset{m}{}}\frac{(kx\mu )^ke^{kx}}{k!}\left(1+\frac{k}{\mu kx}\right),$$
(2)
where $`m`$ is the greatest integer $`\mu /x`$. For a 90% confidence level upper limit, increase $`\sigma `$ until $`\mu `$ and the observed $`x`$ are such that $`C_0`$ reaches 0.90.

Equation 2 can be evaluated relatively quickly when $`C_0`$ is near 0.9. When $`\mu `$ is small, so is $`m`$, and when $`\mu `$ is large, the series can be truncated at relatively small $`k`$ without making a significant error. Equation 2 is derived in Appendix A.

While this method can be used with an arbitrary number of events in the data, it is most appropriate when there are only a few events in the part of the range that seems relatively free of background (small $`\mu `$). The method is not dependent on a choice for binning because unbinned data are used. No Monte Carlo computation of the confidence level is needed because the same formula for $`C_0`$ applies independent of the functional form for the shape of the expected event distribution. The result is a conservative upper limit that is not too badly weakened by a large unknown background in part of the region under consideration; the method effectively excludes regions where a large unknown background causes events to be too close together for the maximum gap to be there.

## III Optimum Interval Method

If there is a relatively high density of events in the data, we may want to replace the “maximum gap” method by one in which we consider, for example, the “maximum” interval over which there is 1 event observed, or 2 events, or $`n`$ events, instead of the zero events in a gap.

Define $`C_n(x,\mu )`$ to be the probability, for a given cross section without background, that all intervals with $`n`$ events have their expected number of events $`x`$. As for $`C_0`$ of the maximum gap method, so long as $`x`$ and $`\mu `$ are fixed, $`C_n`$ is independent of the shape of the cross section and the parameter in which events are distributed. But $`C_n(x,\mu )`$ increases when $`x`$ increases, and it increases when $`n`$ decreases. $`C_n`$ can be tabulated with the help of a Monte Carlo program, although the special case of $`n=0`$ can be more accurately computed with Eq. 2. Once $`n`$ is chosen, $`C_n`$ can be used in the same way as $`C_0`$ for obtaining an upper limit: for $`x`$ equal to the maximum expected number of events taken over all intervals with $`n`$ events, $`C_n(x,\mu )`$ is the confidence level with which the assumed cross section is excluded as being too high. But since we do not want to allow $`n`$ to be chosen in a way that skews results to conform with our prejudices, the optimum gap method includes automatic selection of which $`n`$ to use.

For each interval within the total range of an actual experiment, compute $`C_n(x,\mu )`$ for the observed number of events, $`n`$, and expected number of events, $`x`$, in the interval. The bigger $`C_n`$ is, the stronger will be the evidence that the assumed cross section is too high. Thus for each possible interval, one may quantify how strongly the proposed cross section is excluded by the data. The “optimum interval” is the interval that most strongly indicates that the proposed cross section is too high. The optimum interval tends to be one in which the unknown background is especially small. The overall test quantity used for finding an upper limit on the cross section is then $`C_{\mathrm{Max}}`$, the maximum over all possible intervals of $`C_n(x,\mu )`$. A 90% confidence level upper limit on the cross section is one for which the observed $`C_{\mathrm{Max}}`$ is higher than would be expected from 90% of random experiments with that cross section and no unknown background.

The definition of $`C_{\mathrm{Max}}`$ seems to imply that its determination requires checking an infinite number of intervals. But given any interval with $`n`$ events, $`x`$, hence $`C_n(x,\mu )`$, can be increased without increasing $`n`$ by expanding the interval until it almost hits either another event or an endpoint of the total experimental range. For determination of $`C_{\mathrm{Max}}`$ one need only consider intervals that are terminated by an event or by an endpoint of the total experimental range. If the experiment has $`N`$ events, then there are $`(N+1)(N+2)/2`$ such intervals, one of which has $`C_n(x,\mu )=C_{\mathrm{Max}}`$.

The function $`\overline{C}_{\mathrm{Max}}(C,\mu )`$ is defined to be the value such that fraction $`C`$ of random experiments with that $`\mu `$, and no unknown background, will give $`C_{\mathrm{Max}}<\overline{C}_{\mathrm{Max}}(C,\mu )`$. Thus the 90% confidence level upper limit on the cross section is where $`C_{\mathrm{Max}}`$ of the experiment equals $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$, which is plotted in Fig. 2.

A Monte Carlo program was used to tabulate $`C_n(x,\mu )`$. A Fortran routine interpolates the table to compute $`C_n(x,\mu )`$ when $`n`$, $`x`$, and $`\mu `$ are within the tabulated range. The routine applies when $`0<\mu <54.5`$ and when $`0n50`$.

The function, $`\overline{C}_{\mathrm{Max}}(C,\mu )`$, has been computed by Monte Carlo and tabulated for $`\mu <54.5`$ and various $`C`$. Certain peculiarities of this function are discussed in Appendix B.

Routines to evaluate functions described in this paper, along with tables they use, are available on the web software .

## IV Comparisons of the Methods

We compare the maximum gap ($`C_0`$) and optimum interval ($`C_{\mathrm{Max}}`$) methods with each other, with the standard PDG  way of finding an upper limit (“Poisson”), and with another method ($`p_{\mathrm{Max}}`$) described in Appendix C.

The standard “Poisson” confidence level $`C`$ upper limit cross section is the one whose $`\mu `$ would result in fraction $`C`$ of random experiments having more events in the entire experimental range than the $`n`$ actually observed. This fraction $`C`$ is

$$P(\mu ,n+1)\underset{k=n+1}{\overset{\mathrm{}}{}}\frac{\mu ^k}{k!}e^\mu =_0^\mu 𝑑t\frac{t^n}{n!}e^t.$$
(3)
The last equality is proved by observing that both sides have the same derivative, and they have the same value at $`\mu =0`$. $`P(x,a)`$, the incomplete Gamma function, is in CERNLIB CERNLIB  as GAPNC(a,x), DGAPNC(a,x), and GAMDIS(x,a).

The description of the $`p_{\mathrm{Max}}`$ method is relegated to Appendix C because although $`p_{\mathrm{Max}}`$ is somewhat easier to implement than $`C_{\mathrm{Max}}`$, it was found to be less powerful.

Two comparisons of the effectiveness of the methods were performed: tests “(a)” and “(b)”. For test (a), $`500,000`$ zero-background Monte Carlo experiments were generated for each of 40 assumed cross sections. $`C_0`$, $`p_{\mathrm{Max}}`$, $`C_{\mathrm{Max}}`$, and the Poisson method were used to find the 90% confidence level upper limits on the cross section. For a given true cross section, $`\sigma _{\mathrm{True}}`$, there is a certain median value, $`\sigma _{\mathrm{Med}}`$, that is exceeded exactly 50% of the time by the computed upper limit. Fig. 3(a) shows $`\sigma _{\mathrm{Med}}/\sigma _{\mathrm{True}}`$ as a function of $`\mu `$. The dotted curve used $`C_0`$ to determine the upper limit, the dash-dotted curve used $`p_{\mathrm{Max}}`$, the dashed one used $`C_{\mathrm{Max}}`$, and the solid, jagged, curve used the Poisson method. The Poisson method gives a jagged curve because of the discrete nature of the variable used to calculate the upper limit, the total number of detected events. For any cross section shape, when there is no background, $`C_{\mathrm{Max}}`$ gives a stronger limit than $`p_{\mathrm{Max}}`$ in most random experiments, and both are stronger than $`C_0`$. Even without background, for some values of the true $`\mu `$, $`C_{\mathrm{Max}}`$ gives a stronger (lower) upper limit than the Poisson method. This happens because the discrete nature of the Poisson method causes it to have greater than 90% coverage.

Although test (a) is presented as a comparison of methods in the absence of background, it can also be considered to be a comparison of methods when the background is distributed the same as the signal. If the unknown background happens to have the same distribution as the signal would have, essentially no sensitivity is lost by using the optimum interval method with $`C_{\mathrm{Max}}`$ instead of the Poisson method.

Test (b) was similar to test (a), but the Monte Carlo program simulated a background unknown to the experimenters, and distributed differently from the expected signal. The total experimental region was split into a high part and a low part, with background only in the low part. Half the expected signal was placed in the low part, where the simulated background was twice the expected signal. For this case, the two lowest curves are almost exactly on top of each other; Fig. 3(b) shows that $`C_{\mathrm{Max}}`$ and $`p_{\mathrm{Max}}`$ get equally strong upper limits. $`C_0`$ produces a weaker limit, and the Poisson method is weakest of all.

From the definition of the 90% confidence level upper limit, test (a) results in an upper limit that is lower than the true value exactly 10% of the time; i.e., all methods except the Poisson make a mistake 10% of the time (the discrete nature of the Poisson distribution results in its making mistakes less than 10% of the time). But for test (b), the unknown background raises the upper limit; so all methods make a mistake less than 10% of the time. Figure 4 shows the fraction of mistakes with test (b) using $`C_0`$ (dotted), $`p_{\mathrm{Max}}`$ (dash-dotted) and $`C_{\mathrm{Max}}`$ (dashed). Although $`C_{\mathrm{Max}}`$ and $`p_{\mathrm{Max}}`$ give equally strong upper limits for test (b), $`C_{\mathrm{Max}}`$ makes fewer mistakes. $`C_0`$ makes the most mistakes of the tested methods. Not shown is the Poisson method; because its upper limit is so high, it makes almost no mistakes.

## V Conclusions

Judging from the tests shown in Fig. 3 and Fig. 4, the best of the methods discussed here is the optimum interval method, with $`C_{\mathrm{Max}}`$. This method is useful for experiments with small numbers of events when it is not possible to make an accurate model of the background, and it can also be used when experimenters want to show an especially reliable upper limit that doesn’t depend on trusting their ability to model the background. Because the optimum interval method automatically avoids parts of the data range in which there are large backgrounds, it is relatively insensitive to placement of the cuts limiting the experimental range. Because the optimum interval method doesn’t use binned data, it cannot be biased by how experimenters choose to bin their data. Unlike Bayesian upper limits with a uniform prior, the result of the optimum interval method is unchanged when a change in variable is made. The optimum interval method produces a true, though possibly conservative, classical (frequentist) confidence interval; at least 90% of the time the method is used its 90% confidence level upper limit will be correct, barring experimental systematic errors.

###### Acknowledgements.

Thanks are due to Richard Schnee for useful discussions, for suggesting improvements of this paper, and for being the first to apply its methods to an experimental analysis. This work has been supported by a grant from the U.S. Department of Energy No. DE-FG03-91ER40618.

## Appendix A Derivation of the Equation for $`C_0`$

In order to derive Eq. 2, let us first find the probability that the maximum gap size is less than $`x`$ when there are exactly $`n`$ events, then get $`C_0`$ by averaging $`n`$ over a Poisson distribution.

We assume $`n`$ events are distributed in some variable, $`y`$, according to a density distribution that integrates to a total of $`\mu `$ expected events, and define $`P(x;n,\mu )`$ to be the probability that the maximum gap size is less than $`x`$. As explained in Section II, one may make a change of variables to $`z(y)`$ such that the density distribution is uniform over $`0<z<\mu `$. $`P(x;n,\mu )`$ is the probability that the maximum $`z`$ coordinate distance between adjacent events is less than $`x`$ given that there are exactly $`n`$ events distributed randomly, independently, and uniformly between $`z=0`$ and $`z=\mu `$. The function $`P`$ depends only on $`x`$, $`n`$, and $`\mu `$, but not on the shape of the original density distribution.

The problem of finding $`P(x;n,\mu )`$ can be simplified by making a coordinate change $`w(z)=z/\mu `$. The new coordinate runs from 0 to 1 instead of 0 to $`\mu `$. With this coordinate change, any set of $`n`$ events with $`x`$ equal to the maximum gap between adjacent events becomes a set of $`n`$ events, still uniformly distributed, but with maximum new coordinate distance between adjacent events equal to $`x/\mu `$. It follows that $`P(x/\mu ;n,1)=P(x;n,\mu )`$, and we need only solve the problem of finding $`P`$ for $`\mu =1`$ to get the solution for any value of $`\mu `$. When $`\mu `$ is understood to be 1, it will be dropped, and we will write $`P(x;n)`$ to mean the same as $`P(x;n,1)`$. The problem has been reduced to one in which $`n`$ points have been scattered randomly in independent uniform probability distributions on the interval $`(0,1)`$. We want to find the probability that the maximum empty interval has length less than $`x`$. We do this with the help of a recursion relation that allows one to compute $`P(x;n+1)`$ from knowledge of $`P(x;n)`$.

$`P(x;n+1)`$ is the integral over $`t<x`$ of the probability that the lowest event is between $`t`$ and $`t+dt`$ and that the rest of the $`n`$ events in the remaining 1-t range has no gap greater than $`x`$. The probability that the lowest event is between $`t`$ and $`t+dt`$ is (number of ways of choosing one particular event of the $`n+1`$ events) times (probability that the particular event will be between $`t`$ and $`t+dt`$) times (probability that each of the other $`n`$ events will be greater than $`t`$). We get a factor in the integrand $`(n+1)\times dt\times (1t)^n`$. The other factor in the integrand is the probability that there is no gap greater than $`x`$ for the remaining $`n`$ events: $`P(x;n,1t)=P(x/(1t);n)`$. The recursion relation for $`0<x<1`$ is

$$P(x;n+1)=_0^x𝑑t(n+1)(1t)^nP(\frac{x}{1t};n).$$
(4)
It is convenient to distinguish between various pieces of the $`x`$ range between 0 and $`\mu `$, for it will turn out that $`P(x;n,\mu )`$ takes on different forms in different pieces of that range. If $`x`$ is in the range $`\mu /(m+1)<x<\mu /m`$, we say $`P(x;n,\mu )=P_m(x;n,\mu )`$, and we say $`x`$ is in the $`m`$’th range. Let us again restrict ourselves to $`\mu =1`$ and consider Eq. 4. If $`x`$ is in the $`m`$’th range and, as in Eq. 4, $`0<t<x`$, then $`x/(1t)`$ is in either range $`m`$ or range $`(m1)`$. The boundary between these two ranges is at $`x/(1t)=1/m`$; so $`t=1mx`$. For $`m>0`$ Eq. 4 becomes

$`{\displaystyle \frac{P_m(x;n+1)}{n+1}}=`$ $`{\displaystyle _0^{1mx}}𝑑t(1t)^nP_m({\displaystyle \frac{x}{1t}};n)`$
$`+`$ $`{\displaystyle _{1mx}^x}𝑑t(1t)^nP_{m1}({\displaystyle \frac{x}{1t}};n).`$
The appearance of $`m1`$ brings up the question of what happens if $`m=0`$. Let us interpret the $`m=0`$ range to be the one with $`1/1<x<1/0=\mathrm{}`$. Since the empty space between events is certainly less than the length of the whole interval, $`P_0(x;n)=1`$.

For $`m0`$ it can be shown that

$$P_m(x;n)=\underset{k=0}{\overset{m}{}}(1)^k({}_{k}{}^{n+1})(1kx)^n.$$
(6)
In this equation, we interpret $`({}_{k}{}^{n})`$ as

$$({}_{k}{}^{n})=\frac{n!}{k!(nk)!}\frac{\mathrm{\Gamma }(n+1)}{\mathrm{\Gamma }(k+1)\mathrm{\Gamma }(nk+1)}.$$

The gamma function is meaningful when analytically continued, in which case $`({}_{k}{}^{n})`$ is zero if $`k`$ is an integer that is less than zero or greater than $`n`$. In $`P(x;0)`$, the maximum (and only) gap is always 1; so $`P_0(x;0)=1`$ for $`x>1`$, while for $`m>0`$, when $`0<x<1`$, $`P_m(x;0)=0`$. Since Eq. 6 is easily verified to be correct for all $`m0`$ when $`n=0`$, one may use induction with Eq. LABEL:Pmeqn to prove Eq. 6 for all other $`n>0`$. The simple but somewhat tedious manipulations of sums will not be given here, except for a useful identity in the induction step:

$$({}_{k}{}^{n})+({}_{k1}{}^{n})=({}_{k}{}^{n+1}).$$

It follows from Eq. 6 that

$$P_m(x;n,\mu )=\underset{k=0}{\overset{m}{}}(1)^k({}_{k}{}^{n+1})(1kx/\mu )^n.$$
(7)
Let us now compute $`C_0`$, the probability for the maximum empty space between events in $`(0,\mu )`$ being less than $`x`$ given only that events are thrown according to a uniform unit density. Average Eq. 7 over a Poisson distribution with mean $`\mu `$ to get

$$C_0=\underset{k=0}{\overset{m}{}}\underset{n=0}{\overset{\mathrm{}}{}}e^\mu \frac{\mu ^n}{n!}(1)^k({}_{k}{}^{n+1})(1kx/\mu )^n,$$
(8)
which can be summed over n (again the manipulations will not be shown here) to give Eq. 2.

## Appendix B Peculiarities of $`\overline{C}_{\mathrm{Max}}`$

The function $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$ has certain peculiarities. For example, it cannot be defined for $`\mu <2.3026`$. Random experiments with $`\mu <2.3026`$ either give the largest possible value of $`C_{\mathrm{Max}}`$, which occurs for zero events, with probability $`e^\mu >10\%`$, or give smaller values with probability $`1e^\mu <90\%`$. There is therefore no number, $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$, for which there is exactly 90% probability of $`C_{\mathrm{Max}}<\overline{C}_{\mathrm{Max}}(.9,\mu )`$. No cross section resulting in $`\mu <2.3026`$ can be excluded to as high a confidence level as 90%.

Another peculiarity of $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$ is that it is not especially smooth; it tends to increase rapidly near certain values of $`\mu `$. To understand this behavior, note that for a given value of $`\mu `$, the maximum possible value of $`x`$ is $`x=\mu `$. Thus the maximum possible value over all $`x`$ of $`C_n(x,\mu )`$ is $`C_n(\mu ,\mu )`$. If $`C_n(\mu ,\mu )`$ is less than $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$ then intervals with $`n`$ events cannot have $`C_{\mathrm{Max}}=C_n`$ for that value of $`\mu `$. Furthermore, since $`C_n(x,\mu )`$ decreases with increasing $`n`$, intervals with $`m>n`$ events also have $`C_m<C_{\mathrm{Max}}`$. For low enough $`\mu `$, only intervals with $`n=0`$ need be considered. In this case, the 90% confidence upper limit for $`C_{\mathrm{Max}}`$ occurs when $`x`$ in $`C_0(x,\mu )`$ is equal to $`x_0(.9,\mu )`$, where $`x_0(C,\mu )`$ is the inverse of $`C_0(x,\mu )`$; it is defined as the value of $`x_0`$ for which $`C_0(x_0,\mu )=C`$. Thus for low enough $`\mu `$ (but above 2.3026)

$$\overline{C}_{\mathrm{Max}}(.9,\mu )=C_0(x_0(.9,\mu ),\mu ).$$
(9)
$`C_0(x_0(.9,\mu ),\mu )=0.9`$ from the definitions of $`C_0`$ and $`x_0`$. This formula for $`\overline{C}_{\mathrm{Max}}`$ breaks down as soon as $`\mu `$ is large enough to have $`C_1(\mu ,\mu )>\overline{C}_{\mathrm{Max}}(.9,\mu )`$, for at this value of $`\mu `$ it is possible for an interval with $`n=1`$ to be $`C_{\mathrm{Max}}`$. In general, the threshold $`\mu `$ for intervals with $`n`$ points being able to produce $`C_{\mathrm{Max}}`$ for confidence level $`C`$ is where

$$C_n(\mu ,\mu )=\overline{C}_{\mathrm{Max}}(C,\mu ).$$
(10)
Every time a threshold in $`\mu `$ is passed that allows another value of $`n`$ to participate in producing $`C_{\mathrm{Max}}`$, the value of $`\overline{C}_{\mathrm{Max}}(C,\mu )`$ spurts upward.

If one considers all intervals with $`n`$ events, then the largest expected number of events is less than $`\mu `$ if and only if there are more than $`n`$ events in the entire experimental range. Thus $`C_n(\mu ,\mu )`$ is the probability of $`>n`$ events in the entire experimental range: $`C_n(\mu ,\mu )=P(\mu ,n+1)`$ of Eq. 3. This equation, with Eq. 10, can be used to compute the thresholds in $`\mu `$ where $`n`$ events first need to be included when trying to find $`C_{\mathrm{Max}}`$ in a calculation of the 90% confidence level. These thresholds are tabulated in table 1. As an example of usage of this table, if you are evaluating $`C_{\mathrm{Max}}`$ for a 90% confidence level calculation with $`\mu =20`$, you can ignore intervals with more than 11 events.

The many rapid increases in $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$ of Fig. 2 occur when thresholds given in table 1 are crossed.

## Appendix C Probability of More Events Than Observed in an Interval

Instead of using $`C_n(x,\mu )`$ as a measure of how strongly a given interval with $`n`$ events excludes a given cross section, one may use $`p_n(x)`$, the calculated Poisson probability of there being more events in a random interval of that size than were actually observed. This probability is $`P(x,n+1)`$, as defined in Eq. 3. If $`p_n`$ is too large, then the cross section used in the calculation must have been too large. For a given cross section, find the interval that excludes the cross section most strongly; i.e., find the interval that gives the largest calculated probability of there being more events in the interval than were actually observed. In other words, as was done with $`C_{\mathrm{Max}}`$ of the optimum interval method, define $`p_{\mathrm{Max}}`$ to be the maximum over the $`p_n`$ for all possible intervals. If random experiments for the same given cross section would give a smaller $`p_{\mathrm{Max}}`$ 90% of the time, then the cross section is rejected as too high with 90% confidence level. The function, $`\overline{p}_{\mathrm{Max}}(C,\mu )`$, is defined as the $`p_{\mathrm{Max}}`$ for which confidence level $`C`$ is reached at the given $`\mu `$.

Although this method may not be as effective as the optimum gap method, it is much easier to calculate $`p_n(x)=P(x,n+1)`$ than it is to calculate $`C_n(x,\mu )`$.

Much of the reasoning applied to the optimum interval method applies here. As was the case for the optimum interval method, $`\overline{p}_{\mathrm{Max}}(C,\mu )`$ depends only on $`C`$ and $`\mu `$, but not otherwise on the shape of the cross section. As for the optimum interval method, $`\overline{p}_{\mathrm{Max}}(.9,\mu )`$ is not defined for $`\mu <2.3026`$. For sufficiently low $`\mu `$ above 2.3026 Eq. 9 becomes

$$\overline{p}_{\mathrm{Max}}(.9,\mu )=p_0(x_0(.9,\mu ))=e^{x_0(.9,\mu )}.$$
(11)
For the threshold $`\mu `$ at which intervals with $`n`$ points become able to contribute to $`p_{\mathrm{Max}}`$ for confidence level $`C`$, Eq. 10 becomes

$$P(\mu ,n+1)p_n(\mu )=\overline{p}_{\mathrm{Max}}(C,\mu ).$$
(12)
A Monte Carlo program was used to compute a table of $`\overline{p}_{\mathrm{Max}}(0.9,\mu )`$ for $`\mu 70`$, and the function is plotted in Fig. 5.

Table 2 shows approximate values of the threshold $`\mu `$ calculated using Eq. 12 with $`C=0.9`$ for each $`n`$ from 0 to 44. The third digit of $`\mu `$ does not really deserve to be trusted since $`\overline{p}_{\mathrm{Max}}`$ was computed from a Monte Carlo generated table.

Appendix B explained why the value of $`\overline{C}_{\mathrm{Max}}(.9,\mu )`$ spurts upward when $`\mu `$ crosses a threshold where intervals with more points can contribute to $`C_{\mathrm{Max}}`$. A much less obvious similar effect occurs with $`\overline{p}_{\mathrm{Max}}(.9,\mu )`$. Notice the irregularity in the curve of Fig. 5 just after $`\mu =5.156`$, where $`n=1`$ first begins to contribute. Between $`\mu =2.3026`$ and $`\mu =5.156`$, Eq. 11 applies, but after $`\mu =5.156`$, $`\overline{p}_{\mathrm{Max}}`$ shoots above this form. The smaller irregularity above $`\mu =7.584`$, where $`n=2`$ begins to contribute, is barely visible.


text:
# Entropy and the Combinatorial Dimension

## 1 Introduction

The fact that the covering numbers of a set are exponential in its linear algebraic dimension is fundamental and simple. Let $`A`$ be a class of functions bounded by $`1`$, defined on a set $`\mathrm{\Omega }`$. If $`A`$ is a finite dimensional class then for every probability measure on $`\mu `$ on $`\mathrm{\Omega }`$,

$$N(A,t,L_2(\mu ))\left(\frac{3}{t}\right)^{dim(A)},0<t<1,$$
(1)
where $`dim(A)`$ is the linear algebraic dimension of $`A`$ and the left-hand side of (1) is the covering number of $`A`$, the minimal number of functions needed to approximate any function in $`A`$ within an error $`t`$ in the $`L_2(\mu )`$-norm. This inequality follows by a simple volumetric argument (see e.g. \[Pi\] Lemma 4.10) and is, in a sense, optimal: the dependence both on $`t`$ and on the dimension is sharp (except, perhaps, for the constant $`3`$).

The linear algebraic dimension of $`A`$ is often too large for (1) to be useful, as it does not capture the “size” of $`A`$ in different directions but only determines in how many directions $`A`$ does not vanish. The aim of this paper is to replace the linear algebraic dimension by a combinatorial dimension originated from the classical works of Vapnik and Chervonenkis \[VC 71\], \[VC 81\].

We say that a subset $`\sigma `$ of $`\mathrm{\Omega }`$ is $`t`$-shattered by a class $`A`$ if there exists a level function $`h`$ on $`\sigma `$ such that, given any subset $`\sigma ^{}`$ of $`\sigma `$, one can find a function $`fA`$ with $`f(x)h(x)`$ if $`x\sigma ^{}`$ and $`f(x)h(x)+t`$ if $`x\sigma \sigma ^{}`$. The shattering dimension of $`A`$, denoted by $`\mathrm{vc}(A,t)`$ after Vapnik and Chervonenkis, is the maximal cardinality of a set $`t`$-shattered by $`A`$. Clearly, the shattering dimension does not exceed the linear algebraic dimension, and is often much smaller. Our main result states that the linear algebraic dimension in (1) can be essentially replaced by the shattering dimension.

###### Theorem 1

Let $`A`$ be a class of functions bounded by $`1`$, defined on a set $`\mathrm{\Omega }`$. Then for every probability measure $`\mu `$ on $`\mathrm{\Omega }`$,

$$N(A,t,L_2(\mu ))\left(\frac{2}{t}\right)^{K\mathrm{vc}(A,ct)},0<t<1,$$
(2)
where $`K`$ and $`c`$ are positive absolute constants.

There also exists a (simple) reverse inequality complementing (2): for some measure $`\mu `$, one has $`N(A,t,L_2(\mu ))2^{K\mathrm{vc}(A,ct)}`$, where $`K`$ and $`c`$ are some absolute constants, see e.g. \[T 02\].

The origins of Theorem 1 are rooted in the work of Vapnik and Chervonenkis, who first understood that entropy estimates are essential in determining whether a class of functions obeys the uniform law of large numbers. The subsequent fundamental works of Koltchinskii \[K\] and Ginè and Zinn \[GZ\] enhanced the link between entropy estimates and uniform limit theorems (see also \[T 96\]).

In 1978, R. Dudley proved Theorem 1 for classes of $`\{0,1\}`$-valued functions (\[Du\], see \[LT\] 14.3). This yielded that a $`\{0,1\}`$-class obeys the uniform law of large numbers (and even the uniform Central Limit Theorem) if and only if its shattering dimension is finite for $`0<t<1`$. The main difficulty in proving such limit theorems for general classes has been the absence of a uniform entropy estimate of the nature of Theorem 1 (\[T 88\], \[T 92\], \[T 96\], \[ABCH\], \[BL\], \[T 02\]). However, proving Dudley’s result for general classes is considerably more difficult due to the lack of the obvious property of the $`\{0,1\}`$-valued classes, namely that if a set $`\sigma `$ is $`t`$-shattered for some $`0<t<1`$ then it is automatically $`1`$-shattered.

In 1992, M. Talagrand proved a weaker version of Theorem 1: under some mild regularity assumptions, $`\mathrm{log}N(A,t,L_2(\mu ))K\mathrm{vc}(A,ct)\mathrm{log}^M(\frac{2}{t})`$, where $`K`$, $`c`$ and $`M`$ are some absolute constants (\[T 92\], \[T 02\]). Theorem 1 is Talagrand’s inequality with the best possible exponent $`M=1`$ (and without regularity assumptions).

Talagrand’s inequality was motivated not only by limit theorems in probability, but to a great extent by applications to convex geometry. A subset $`B`$ of $`^n`$ can be viewed as a class of real valued functions on $`\{1,\mathrm{},n\}`$. If $`B`$ is convex and, for simplicity, symmetric, then its shattering dimension $`\mathrm{vc}(B,t)`$ is the maximal cardinality of a subset $`\sigma `$ of $`\{1,\mathrm{},n\}`$ such that $`P_\sigma (B)[\frac{t}{2},\frac{t}{2}]^\sigma `$, where $`P_\sigma `$ denotes the orthogonal projection in $`^n`$ onto $`^\sigma `$. In the general, non-symmetric, case we allow translations of the cube $`[\frac{t}{2},\frac{t}{2}]^\sigma `$ by a vector in $`^\sigma `$.

The following entropy bound for convex bodies is then an immediate consequence of Theorem 1. Recall that $`N(B,D)`$ is the covering number of $`B`$ by a set $`D`$ in $`^n`$, the minimal number of translates of $`D`$ needed to cover $`B`$.

###### Corollary 2

There exist positive absolute constants $`K`$ and $`c`$ such that the following holds. Let $`B`$ be a convex body contained in $`[0,1]^n`$, and $`D_n`$ be the unit Euclidean ball in $`^n`$. Then for $`0<t<1`$

$$N(B,t\sqrt{n}D_n)\left(\frac{2}{t}\right)^{Kd},$$

where $`d`$ is the maximal cardinality of a subset $`\sigma `$ of $`\{1,\mathrm{},n\}`$ such that

$$P_\sigma (B)h+[0,ct]^\sigma \text{for some vector }h\text{ in }^n\text{.}$$

As M. Talagrand notices in \[T 02\], Theorem 1 is a “concentration of pathology” phenomenon. Assume one knows that a covering number of the class $`A`$ is large. All this means is that $`A`$ contains many well separated functions, but it tells nothing about the structure these functions form. The conclusion of (2) is that $`A`$ must shatter a large set $`\sigma `$, which detects a very accurate pattern: one can find functions in $`A`$ oscillating on $`\sigma `$ in all possible $`2^{|\sigma |}`$ ways around fixed levels. The “largeness” of $`A`$, a priori diffused, is a fortiori concentrated on the set $`\sigma `$.

The same phenomenon is seen in Corollary 2: given a convex body $`B`$ with large entropy, one can find an entire cube in a coordinate projection of $`B`$, the cube that certainly witnesses the entropy’s largeness.

When dualized, Corollary 2 solves the problem of finding the best asymptotics in Elton’s Theorem. Let $`x_1,\mathrm{},x_n`$ be vectors in the unit ball of a Banach space, and $`\epsilon _1,\mathrm{},\epsilon _n`$ be Rademacher random variables (independent Bernoulli random variables taking values $`1`$ and $`1`$ with probability $`1/2`$). By the triangle inequality, the expectation $`𝔼_{i=1}^n\epsilon _ix_i`$ is at most $`n`$, and assume that $`𝔼_{i=1}^n\epsilon _ix_i\delta n`$ for some number $`\delta >0`$.

In 1983, J. Elton \[E\] proved an important result that there exists a subset $`\sigma `$ of $`\{1,\mathrm{},n\}`$ of size proportional to $`n`$ such that the set of vectors $`(x_i)_{i\sigma }`$ is equivalent to the $`\mathrm{}_1`$ unit-vector basis. Specifically, there exist numbers $`s,t>0`$, depending only on $`\delta `$, such that

$$|\sigma |s^2n\text{and}\underset{i\sigma }{}a_ix_it\underset{i\sigma }{}|a_i|\text{for all real numbers }(a_i).$$
(3)
Several steps have been made towards finding the best possible $`s`$ and $`t`$ in Elton’s Theorem. A trivial upper bound is $`s,t\delta `$ which follows from the example of identical vectors and by shrinking the usual $`\mathrm{}_1`$ unit-vector basis. As for the lower bounds, J. Elton proved (3) with $`s\delta /\mathrm{log}(1/\delta )`$ and $`t\delta ^3`$. A. Pajor \[Pa\] removed the logarithmic factor from $`s`$. M. Talagrand \[T 92\], using his inequality discussed above, improved $`t`$ to $`\delta /\mathrm{log}^M(1/\delta )`$. In the present paper, we use Corollary 2 to solve this problem by proving the optimal asymptotics: $`s,t\delta `$.

###### Theorem 3

Let $`x_1,\mathrm{},x_n`$ be vectors in the unit ball of a Banach space, satisfying

$$𝔼\underset{i=1}{\overset{n}{}}\epsilon _ix_i\delta n\text{for some number }\delta >0.$$

Then there exists a subset $`\sigma \{1,\mathrm{},n\}`$ of cardinality $`|\sigma |c\delta ^2n`$ such that

$$\underset{i\sigma }{}a_ix_ic\delta \underset{i\sigma }{}|a_i|\text{for all real numbers }(a_i),$$

where $`c`$ is a positive absolute constant.

Furthermore, there is an interplay between the size of $`\sigma `$ and the isomorphism constant – they can not attain their worst possible values together. Namely, we prove that $`s`$ and $`t`$ in (3) satisfy in addition to $`s,t\delta `$ also the lower bound $`st\mathrm{log}^{1.6}(2/t)\delta `$, which, as an easy example shows, is optimal for all $`\delta `$ within the logarithmic factor. The power 1.6 can be replaced by any number greater than 1.5. This estimate improves one of the main results of the paper \[T 92\] where this phenomenon in Elton’s Theorem was discovered and proved with a constant (unspecified) power of logarithm.

The paper is organized as follows. In the remaining part of the introduction we sketch the proof of Theorem 1; the complete proof will occupy Section 2. Section 3 is devoted to applications to Elton’s Theorem and to empirical processes.

Here is a sketch of the proof of Theorem 1. Starting with a set $`A`$ which is separated with respect to the $`L_2(\mu )`$-norm, it is possible find a coordinate $`\omega \mathrm{\Omega }`$ (selected randomly) on which $`A`$ is diffused, i.e. the values $`\{f(\omega ),fA\}`$ are spread in the interval $`[1,1]`$. Then there exist two nontrivial subsets $`A_1`$ and $`A_2`$ of $`A`$ with their set of values $`\{f(\omega ),fA_1\}`$ and $`\{f(\omega ),fA_2\}`$ well separated from each other on the line. Continuing this process of separation for $`A_1`$ and $`A_2`$, etc., one can construct a dyadic tree of subsets of $`A`$, called a separating tree, with at least $`|A|^{1/2}`$ leaves. The “largeness” of the class $`A`$ is thus captured by its separating tree.

The next step evoked from a beautiful idea in \[ABCH\]. First, there is no loss of generality in discretizing the class: one can assume that $`\mathrm{\Omega }`$ is finite (say $`|\mathrm{\Omega }|=n`$) and that the functions in $`A`$ take values in $`\frac{t}{6}[1,1]`$. Then, instead of producing a large set $`\sigma `$ shattered by $`A`$ with a certain level function $`h`$, one can count the number of different pairs $`(\sigma ,h)`$ for which $`\sigma `$ is shattered by $`A`$ with the level function $`h`$. If this number exceeds $`_{k=0}^d\left(\genfrac{}{}{0pt}{}{n}{k}\right)(\frac{12}{t})^k`$ then there must exist a set $`\sigma `$ of size $`|\sigma |>d`$ shattered by $`A`$ (because there are $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ possible sets $`\sigma `$ of cardinality $`k`$, and for such a set there are at most $`(\frac{12}{t})^k`$ possible level functions).

The only thing remaining is to bound below the number of pairs $`(\sigma ,h)`$ for which $`\sigma `$ is shattered by $`A`$ with a level function $`h`$. One can show that this number is bounded below by the number of the leaves in the separating tree of $`A`$, which is $`|A|^{1/2}`$. This implies that $`|A|^{1/2}_{k=0}^d\left(\genfrac{}{}{0pt}{}{n}{k}\right)(\frac{12}{t})^k(\frac{n}{td})^d`$, where $`d=\mathrm{vc}(A,ct)`$. The ratio $`\frac{n}{d}`$ can be eliminated from this estimate by a probabilistic extraction principle which reduces the cardinality of $`\mathrm{\Omega }`$.

ACKNOWLEDGEMENTS

The first author was supported by an Australian Research Council Discovery grant. The second author thanks Nicole Tomczak-Jaegermann for her constant support. He also acknowledges a support from the Pacific Institute of Mathematical Sciences, and thanks the Department of Mathematical Sciences of the University of Alberta for its hospitality. Finally, we would like to thank the referee for his valuable comments and suggestions.

## 2 The Proof of Theorem 1

For $`t>0`$, a pair of functions $`f`$ and $`g`$ on $`\mathrm{\Omega }`$ is $`t`$-separated in $`L_2(\mu )`$ if $`fg_{L_2(\mu )}>t`$. A set of functions is called $`t`$-separated if every pair of distinct points in the set is $`t`$-separated. Let $`N_{\mathrm{sep}}(A,t,L_2(\mu ))`$ denote the maximal cardinality of a $`t`$-separated subset of $`A`$. It is standard and easily seen that

$$N(A,t,L_2(\mu ))N_{\mathrm{sep}}(A,t,L_2(\mu ))N(A,\frac{t}{2},L_2(\mu )).$$

This inequality shows that in the proof of Theorem 1 we may assume that $`A`$ is $`t`$-separated in the $`L_2(\mu )`$ norm, and replace its covering number by its cardinality.

We will need two probabilistic results, the first of which is straightforward.

###### Lemma 4

Let $`X`$ be a random variable and $`X^{}`$ be an independent copy of $`X`$. Then

$$𝔼|XX^{}|^2=2𝔼|X𝔼X|^2=2\underset{a}{inf}𝔼|Xa|^2.$$

The next lemma is a small deviation principle. Denote by $`\sigma (X)^2=𝔼|X𝔼X|^2`$ the variance of the random variable $`X`$.

###### Lemma 5

Let $`X`$ be a random variable with nonzero variance. Then there exist numbers $`a`$ and $`0<\beta \frac{1}{2}`$, so that letting

$`p_1`$ $`=\{X>a+\frac{1}{6}\sigma (X)\}\text{and}`$
$`p_2`$ $`=\{X<a\frac{1}{6}\sigma (X)\},`$
one has either $`p_11\beta `$ and $`p_2\frac{\beta }{2}`$, or $`p_21\beta `$ and $`p_1\frac{\beta }{2}`$.

Proof. Recall that a median of $`X`$ is a number $`M_X`$ such that $`\{XM_X\}1/2`$ and $`\{XM_X\}1/2`$; without loss of generality we may assume that $`M_X=0`$. Therefore $`\{X>0\}=1\{X0\}1/2`$ and similarly $`\{X<0\}1/2`$.

By Lemma 4,

$`\sigma (X)^2`$ $`𝔼|X|^2={\displaystyle _0^{\mathrm{}}}\{|X|>\lambda \}𝑑\lambda ^2`$
$`={\displaystyle _0^{\mathrm{}}}\{X>\lambda \}𝑑\lambda ^2+{\displaystyle _0^{\mathrm{}}}\{X<\lambda \}𝑑\lambda ^2`$ (4)
where $`d\lambda ^2=2\lambda d\lambda `$.

Assume that the conclusion of the lemma fails, and let $`c`$ be any number satisfying $`\frac{1}{3}<c<\frac{1}{\sqrt{8}}`$. Divide $`_+`$ into intervals $`I_k`$ of length $`c\sigma (X)`$ by setting

$$I_k=(c\sigma (X)k,c\sigma (X)(k+1)],k=0,1,2,\mathrm{}$$

and let $`\beta _0,\beta _1,\beta _2,\mathrm{}`$ be the non-negative numbers defined by

$$\{X>0\}=\beta _01/2,P\{XI_k\}=\beta _k\beta _{k+1},k=0,1,2,\mathrm{}$$

We claim that

$$\text{for all }k0\text{,}\beta _{k+1}\frac{1}{2}\beta _k.$$
(5)
Indeed, assume that $`\beta _{k+1}>\frac{1}{2}\beta _k`$ for some $`k`$ and consider the intervals $`J_1=(\mathrm{},c\sigma (X)k]`$ and $`J_2=(c\sigma (X)(k+1),\mathrm{})`$. Then $`J_1=(\mathrm{},0](_{0lk1}I_l)`$, so

$$\{XJ_1\}=(1\beta _0)+\underset{0lk1}{}(\beta _l\beta _{l+1})=1\beta _k.$$

Similarly, $`J_2=_{lk+1}I_l`$ and thus

$$\{XJ_2\}=\underset{lk+1}{}(\beta _l\beta _{l+1})=\beta _{k+1}>\frac{1}{2}\beta _k.$$

Moreover, since the sequence $`(\beta _k)`$ is non-increasing by its definition, then $`\beta _k\beta _{k+1}>\frac{1}{2}\beta _k0`$ and $`\beta _k\beta _0\frac{1}{2}`$. Then the conclusion of the lemma would hold with $`a`$ being the middle point between the intervals $`J_1`$ and $`J_2`$ and with $`\beta =\beta _k`$, which contradicts the assumption that the conclusion of the lemma fails. This proves (5).

Now, one can apply (5) to estimate the first integral in (2). Note that whenever $`\lambda I_k`$,

$$\{X>\lambda \}\{X>c\sigma (X)k\}=\left(\underset{lk}{}I_l\right)=\beta _k.$$

Then

$`{\displaystyle _0^{\mathrm{}}}\{X>\lambda \}𝑑\lambda ^2`$ $`{\displaystyle \underset{k0}{}}{\displaystyle _{I_k}}\beta _k2\lambda 𝑑\lambda `$
$`{\displaystyle \underset{k0}{}}\beta _k2c\sigma (X)(k+1)\mathrm{length}(I_k).`$ (6)
Applying (5) inductively, it is evident that $`\beta _k(\frac{1}{2})^k\beta _0\frac{1}{2^{k+1}}`$, and since $`\mathrm{length}(I_k)=c\sigma (X)`$, (6) is bounded by

$$2c^2\sigma (X)^2\underset{k0}{}\frac{k+1}{2^{k+1}}=4c^2\sigma (X)^2<\frac{1}{2}\sigma (X)^2.$$

By an identical argument one can show that the second integral in (2) is also bounded by $`\frac{1}{2}\sigma (X)^2`$. Therefore

$$\sigma (X)^2<\frac{1}{2}\sigma (X)^2+\frac{1}{2}\sigma (X)^2=\sigma (X)^2,$$

and this contradiction completes the proof.

### Constructing a separating tree

Let $`A`$ be a finite class of functions on a probability space $`(\mathrm{\Omega },\mu )`$, which is $`t`$-separated in $`L_2(\mu )`$. Throughout the proof we will assume that $`|A|>1`$. One can think of the class $`A`$ itself as a (finite) probability space with the uniform measure on it, that is, each element $`x`$ in $`A`$ is assigned probability $`\frac{1}{|A|}`$.

###### Lemma 6

Let $`A`$ be a $`t`$-separated subset of $`L_2(\mu )`$. Then, there exist a coordinate $`i`$ in $`\mathrm{\Omega }`$ and numbers $`a`$ and $`0<\beta 1/2`$, so that setting

$`N_1`$ $`=|\{xA:x(i)>a+\frac{1}{12}t\}|\text{and}`$
$`N_2`$ $`=|\{xA:x(i)<a\frac{1}{12}t\}|,`$
one has either $`N_1(1\beta )|A|`$ and $`N_2\frac{\beta }{2}|A|`$, or vice versa.

Proof. Let $`x,x^{}`$ be random points in $`A`$ selected independently according to the uniform (counting) measure on $`A`$. By Lemma 4,

$`𝔼xx^{}_{L_2(\mu )}^2`$ $`=𝔼{\displaystyle _\mathrm{\Omega }}|x(i)x^{}(i)|^2𝑑\mu (i)={\displaystyle _\mathrm{\Omega }}𝔼|x(i)x^{}(i)|^2𝑑\mu (i)`$
$`=2{\displaystyle _\mathrm{\Omega }}𝔼|x(i)𝔼x(i)|^2𝑑\mu (i)`$ (7)
$`=2{\displaystyle _\mathrm{\Omega }}\sigma (x(i))^2𝑑\mu (i)`$
where $`\sigma (x(i))^2`$ is the variance of the random variable $`x(i)`$ with respect to the uniform measure on $`A`$.

On the other hand, with probability $`1\frac{1}{|A|}`$ we have $`xx^{}`$ and, whenever this event occurs, the separation assumption on $`A`$ implies that $`xx^{}_{L_2(\mu )}t`$. Therefore

$$𝔼xx^{}_{L_2(\mu )}^2\left(1\frac{1}{|A|}\right)t^2\frac{t^2}{2}$$

provided that $`|A|>1`$.

Together with (2) this proves the existence of a coordinate $`i\mathrm{\Omega }`$, on which

$$\sigma (x(i))\frac{t}{2},$$
(8)
and the claim follows from Lemma 5 applied to the random variable $`x(i)`$.

This lemma should be interpreted as a separation lemma for the set $`A`$. It means that one can always find two nontrivial subsets of $`A`$ and a coordinate in $`\mathrm{\Omega }`$, on which the two subsets are separated with a “gap” proportional to $`t`$.

Based on Lemma 6, one can construct a large separating tree in $`A`$. Recall that a tree of subsets of a set $`A`$ is a finite collection $`T`$ of subsets of $`A`$ such that, for every pair $`B,DT`$ either $`B`$ and $`D`$ are disjoint or one of them contains the other. We call $`D`$ a son of $`B`$ if $`D`$ is a maximal (with respect to inclusion) proper subset of $`B`$ that belongs to $`T`$. An element of $`T`$ with no sons is called a leaf.

###### Definition 7

Let $`A`$ be a class of functions on $`\mathrm{\Omega }`$ and $`t>0`$. A $`t`$-separating tree $`T`$ of $`A`$ is a tree of subsets of $`A`$ such that every element $`BT`$ which is not a leaf has exactly two sons $`B_+`$ and $`B_{}`$ and, for some coordinate $`i\mathrm{\Omega }`$,

$$f(i)>g(i)+t\text{for all }fB_+\text{}gB_{}\text{.}$$

###### Proposition 8

Let $`A`$ be a finite class of functions on a probability space $`(\mathrm{\Omega },\mu )`$. If $`A`$ is $`t`$-separated with respect to the $`L_2(\mu )`$ norm, then there exists a $`\frac{1}{6}t`$-separating tree of $`A`$ with at least $`|A|^{1/2}`$ leaves.

Proof. By Lemma 6, any finite class $`A`$ which is $`t`$-separated with respect to the $`L_2(\mu )`$ norm has two subsets $`A_+`$ and $`A_{}`$ and a coordinate $`i\mathrm{\Omega }`$ for which $`f(i)>g(i)+\frac{1}{6}t`$ for every $`fA_+`$ and $`gA_{}`$. Moreover, there exists some number $`0<\beta 1/2`$ such that

$$|A_+|(1\beta )|A|\text{and}|A_{}|\frac{\beta }{2},\text{or vice versa}.$$

Thus, $`A_+`$ and $`A_{}`$ are sons of $`A`$ which are both large and well separated on the coordinate $`i`$.

The conclusion of the proposition will now follow by induction on the cardinality of $`A`$. The proposition clearly holds for $`|A|=2`$. Assume it holds for every $`t`$-separated class of cardinality bounded by $`N`$, and let $`A`$ be a $`t`$-separated class of cardinality $`N+1`$. Let $`A_+`$ and $`A_{}`$ be the sons of $`A`$ as above; since $`\beta >0`$, we have $`|A_+|,|A_{}|N`$. Moreover, if $`A_+`$ has a $`\frac{1}{6}t`$-separating tree with $`N_+`$ leaves and $`A_{}`$ has a $`\frac{1}{6}t`$-separating tree with $`N_{}`$ leaves then, by joining these trees, $`A`$ has a $`\frac{1}{6}t`$-separating tree with $`N_++N_{}`$ leaves, the number bounded below by $`|A_+|^{1/2}+|A_{}|^{1/2}`$ by the induction hypothesis. Since $`\beta 1/2`$,

$`|A_+|^{\frac{1}{2}}+|A_{}|^{\frac{1}{2}}`$ $`\left((1\beta )|A|\right)^{\frac{1}{2}}+\left({\displaystyle \frac{\beta }{2}}|A|\right)^{\frac{1}{2}}`$
$`=\left[(1\beta )^{\frac{1}{2}}+\left({\displaystyle \frac{\beta }{2}}\right)^{\frac{1}{2}}\right]|A|^{\frac{1}{2}}|A|^{\frac{1}{2}}`$
as claimed.

The exponent $`1/2`$ has no special meaning in Proposition 8. It can be improved to any number smaller that $`1`$ at the cost of reducing the constant $`\frac{1}{6}`$.

### Counting shattered sets

As explained in the introduction, our aim is to construct a large set shattered by a given class. We will first try to do this for classes of integer-valued functions.

Let $`A`$ be a class of integer-valued functions on a set $`\mathrm{\Omega }`$. We say that a couple $`(\sigma ,h)`$ is a center if $`\sigma `$ is a finite subset of $`\mathrm{\Omega }`$ and $`h`$ is an integer-valued function on $`\sigma `$. We call the cardinality of $`\sigma `$ the dimension of the center. For convenience, we introduce (the only) $`0`$-dimensional center $`(\mathrm{},\mathrm{})`$, which is the trivial center.

###### Definition 9

The set $`A`$ shatters a center $`(\sigma ,h)`$ if the following holds:

* either $`(\sigma ,h)`$ is trivial and $`A`$ is nonempty,
* or, otherwise, for every choice of signs $`\theta \{1,1\}^\sigma `$ there exists a function $`fA`$ such that for $`i\sigma `$

$$\{\begin{array}{cc}f(i)>h(i)\hfill & \text{when }\theta (i)=1,\hfill \\ f(i)<h(i)\hfill & \text{when }\theta (i)=1.\hfill \end{array}$$
(9)

It is crucial that both inequalities in (9) are strict: they ensure that whenever a $`d`$-dimensional center is shattered by $`A`$, one has $`\mathrm{vc}(A,2)d`$. In fact, it is evident that $`\mathrm{vc}(A,2)`$ is the maximal dimension of a center shattered by $`A`$.

###### Proposition 10

The number of centers shattered by $`A`$ is at least the number of leaves in any $`1`$-separating tree of $`A`$.

Proof. Given a class $`B`$ of integer-valued functions, denote by $`s(B)`$ the number of centers shattered by $`B`$. It is enough to prove that if $`B_+`$ and $`B_{}`$ are the sons of an element $`B`$ of a $`1`$-separating tree in $`A`$ then

$$s(B)s(B_+)+s(B_{}).$$
(10)
By the definition of the $`1`$-separating tree, there is a coordinate $`i_0\mathrm{\Omega }`$, such that $`f(i_0)>g(i_0)+1`$ for all $`fB_+`$ and $`gB_{}`$. Since the functions are integer-valued, there exists an integer $`t`$ such that

$$f(i_0)>t\text{for }fB_+\text{and}g(i_0)<t\text{for }gB_{}.$$

If a center $`(\sigma ,h)`$ is shattered either by $`B_+`$ or by $`B_{}`$, it is also shattered by $`B`$. Next, assume that $`(\sigma ,h)`$ is shattered by both $`B_+`$ and $`B_{}`$. Note that in this case $`i_0\sigma `$. Indeed, if the converse holds then $`\sigma `$ contains $`i_0`$ and hence is nonempty. Thus the center $`(x,\sigma )`$ is nontrivial and there exist $`fB_+`$ and $`gB_{}`$ such that $`t<f(i_0)<h(i_0)`$ (by (9) with $`\theta (i_0)=1`$) and $`t>g(i_0)>h(i_0)`$ (by (9) with $`\theta (i_0)=1`$), which is impossible. Consider the center $`(\sigma ^{},h^{})=(\sigma \{i_0\},ht)`$, where $`ht`$ is the extension of the function $`h`$ onto the set $`\sigma \{i_0\}`$ defined by $`(ht)(i_0)=t`$.

Observe that $`(\sigma ^{},h^{})`$ is shattered by $`B`$. Indeed, since $`B_+`$ shatters $`(\sigma ,h)`$, then for every $`\theta \{1,1\}^\sigma \times \{1\}^{\{i_0\}}`$ there exists a function $`fB_+`$ such that (9) holds for $`i\sigma `$. Also, since $`fB_+`$, then automatically $`f(i_0)>t=h^{}(i_0)`$. Similarly, for every $`\theta \{1,1\}^\sigma \times \{1\}^{\{i_0\}}`$, there exists a function $`fB_{}`$ such that (9) holds for $`i\sigma `$ and automatically $`f(i_0)<t=h^{}(i_0)`$.

Clearly, $`(\sigma ^{},h^{})`$ is shattered by neither $`B_+`$ nor by $`B_{}`$, because $`f(i_0)>t=h^{}(i_0)`$ for all $`fB_+`$, so (9) fails if $`\theta (i_0)=1`$; a similar argument holds for $`B_{}`$.

Summarizing, $`(\sigma ,h)(\sigma ^{},h^{})`$ is an injective mapping from the set of centers shattered by both $`B_+`$ and $`B_{}`$ into the set of centers shattered by $`B`$ but not by $`B_+`$ or $`B_{}`$, which proves our claim.

Combining Propositions 8 and 10, one bounds from below the number of shattered centers.

###### Corollary 11

Let $`A`$ be a finite class of integer-valued functions on a probability space $`(\mathrm{\Omega },\mu )`$. If $`A`$ is $`6`$-separated with respect to the $`L_2(\mu )`$ norm then it shatters at least $`|A|^{1/2}`$ centers.

To show that there exists a large dimensional center shattered by $`A`$, one must assume that the class $`A`$ is bounded in some sense, otherwise one could have infinitely many low dimensional centers shattered by the class. A natural assumption is the uniform boundedness of $`A`$, under which we conclude a preliminary version of Theorem 1.

###### Proposition 12

Let $`(\mathrm{\Omega },\mu )`$ be a probability space, where $`\mathrm{\Omega }`$ is a finite set of cardinality $`n`$. Assume that $`A`$ is a class of functions on $`\mathrm{\Omega }`$ into $`\{0,1,\mathrm{},p\}`$, which is $`6`$-separated in $`L_2(\mu )`$. Set $`d`$ to be the maximal dimension of a center shattered by $`A`$. Then

$$|A|\left(\frac{pn}{d}\right)^{Cd},$$
(11)
where $`C`$ is an absolute constant. In particular, the same assertion holds for $`d=\mathrm{vc}(A,2)`$.

Proof. By Corollary 11, $`A`$ shatters at least $`|A|^{1/2}`$ centers. On the other hand, the total number of centers whose dimension is at most $`d`$ that a class of $`\{0,1,\mathrm{},p\}`$-valued functions on $`\mathrm{\Omega }`$ can shatter is bounded by $`_{k=0}^d\left(\genfrac{}{}{0pt}{}{n}{k}\right)p^k`$. Indeed, for every $`k`$ there exist at most $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ subsets $`\sigma \mathrm{\Omega }`$ of cardinality $`k`$ and, for each $`\sigma `$ with $`|\sigma |=k`$ there are at most $`p^k`$ level functions $`h`$ for which the center $`(\sigma ,h)`$ can be shattered by such a class. Therefore $`|A|^{1/2}_{k=0}^d\left(\genfrac{}{}{0pt}{}{n}{k}\right)p^k`$ (otherwise there would exist a center of dimension larger than $`d`$ shattered by $`A`$, contradicting the maximality of $`d`$). The proof is completed by approximating the binomial coefficients using Stirling’s formula.

Actually, the ratio $`n/d`$ can be eliminated from (11) (perhaps at the cost of increasing the separation parameter $`6`$). To this end, one needs to reduce the size of $`\mathrm{\Omega }`$ without changing the assumption that the class is “well separated”. This is achieved by the following probabilistic extraction principle.

###### Lemma 13

There is a positive absolute constant $`c`$ such that the following holds. Let $`\mathrm{\Omega }`$ be a finite set with the uniform probability measure $`\mu `$ on it. Let $`A`$ be a class of functions bounded by $`1`$, defined on $`\mathrm{\Omega }`$. Assume that for some $`0<t<1`$

$`A`$ is $`t`$-separated with respect to the $`L_2(\mu )`$ norm.
If $`|A|\frac{1}{2}\mathrm{exp}(ct^4k)`$ for some positive number $`k`$, there exists a subset $`\sigma \mathrm{\Omega }`$ of cardinality at most $`k`$ such that

$`A`$ is $`\frac{t}{2}`$-separated with respect to the $`L_2(\mu _\sigma )`$ norm,
where $`\mu _\sigma `$ is the uniform probability measure on $`\sigma `$.

As the reader guesses, the set $`\sigma `$ will be chosen randomly in $`\mathrm{\Omega }`$. We will estimate probabilities using a version of Bernstein’s inequality (see e.g. \[VW\], or \[LT\] 6.3 for stronger inequalities).

###### Lemma 14 (Bernstein’s inequality)

Let $`X_1,\mathrm{},X_n`$ be independent random variables with zero mean. Then, for every $`u>0`$,

$$\left\{\left|\underset{i=1}{\overset{n}{}}X_i\right|>u\right\}2\mathrm{exp}\left(\frac{u^2}{2(b^2+au/3)}\right),$$

where $`a=sup_iX_i_{\mathrm{}}`$ and $`b^2=_{i=1}^n𝔼|X_i|^2`$.

Proof of Lemma 13.  For the sake of simplicity we identify $`\mathrm{\Omega }`$ with $`\{1,2,\mathrm{},n\}`$. The difference set $`S=\{fg|fg,f,gA\}`$ has cardinality $`|S||A|^2`$. For each $`xS`$ we have $`|x(i)|2`$ for all $`i\{1,\mathrm{},n\}`$ and $`_{i=1}^n|x(i)|^2t^2n`$. Fix an integer $`k`$ satisfying the assumptions of the lemma and let $`\delta _1,\mathrm{},\delta _n`$ be independent $`\{0,1\}`$-valued random variables with $`𝔼\delta _i=\frac{k}{2n}=:\delta `$. Then for every $`zS`$

$`\left\{{\displaystyle \underset{i=1}{\overset{n}{}}}\delta _i|x(i)|^2{\displaystyle \frac{t^2\delta n}{2}}\right\}`$ $`\left\{\left|{\displaystyle \underset{i=1}{\overset{n}{}}}\delta _i|x(i)|^2\delta {\displaystyle \underset{i=1}{\overset{n}{}}}|x(i)|^2\right|>{\displaystyle \frac{t^2\delta n}{2}}\right\}`$
$`=\left\{\left|{\displaystyle \underset{i=1}{\overset{n}{}}}(\delta _i\delta )|x(i)|^2\right|>{\displaystyle \frac{t^2\delta n}{2}}\right\}`$
$`2\mathrm{exp}\left({\displaystyle \frac{ct^4\delta n}{1+t^2}}\right)2\mathrm{exp}(ct^4k),`$
where the last line follows from Bernstein’s inequality for $`a=sup_iX_i2`$ and

$$b^2=\underset{i=1}{\overset{n}{}}𝔼|X_i|^2=\underset{i=1}{\overset{n}{}}|x(i)|^4𝔼(\delta _i\delta )^216\delta n.$$

Therefore, by the assumption on $`k`$

$$\{xS:\left(\frac{1}{k}\underset{i=1}{\overset{n}{}}\delta _i|x(i)|^2\right)^{1/2}\frac{t}{2}\}|S|2\mathrm{exp}(ct^4k)<1/2.$$

Moreover, if $`\sigma `$ is the random set $`\{i|\delta _i=1\}`$ then by Chebyshev’s inequality,

$$\{|\sigma |>k\}=\left\{\underset{i=1}{\overset{n}{}}\delta _i>k\right\}1/2,$$

which implies that

$$\{xS:x_{L_2(\mu _\sigma )}\frac{t}{2}\}<1.$$

This translates into the fact that with positive probability the class $`A`$ is $`\frac{t}{2}`$-separated with respect to the $`L_2(\mu _\sigma )`$ norm.

Proof of Theorem 1.  One may clearly assume that $`|A|>1`$ and that the functions in $`A`$ are defined on a finite domain $`\mathrm{\Omega }`$, so that the probability measure $`\mu `$ on $`\mathrm{\Omega }`$ is supported on a finite number of atoms. Next, by splitting these atoms (by replacing an atom $`\omega `$ by, say, two atoms $`\omega _1`$ and $`\omega _2`$, each carrying measure $`\frac{1}{2}\mu (\omega )`$ and by defining $`f(\omega _1)=f(\omega _2)=f(\omega )`$ for $`fA`$), one can make the measure $`\mu `$ almost uniform without changing neither the covering numbers nor the shattering dimension of $`A`$. Therefore, assume that the domain $`\mathrm{\Omega }`$ is $`\{1,2,\mathrm{},n\}`$ for some integer $`n`$, and that $`\mu `$ is the uniform measure on $`\mathrm{\Omega }`$.

Fix $`0<t1/2`$ and let $`A`$ be a $`2t`$-separated in the $`L_2(\mu )`$ norm. By Lemma 13, there is a set of coordinates $`s\{1,\mathrm{},n\}`$ of size $`|\sigma |\frac{C\mathrm{log}|A|}{t^4}`$ such that $`A`$ is $`t`$-separated in $`L_2(\mu _\sigma )`$, where $`\mu _\sigma `$ is the uniform probability measure on $`\sigma `$.

Let $`p=7/t`$, define $`\stackrel{~}{A}\{0,1,\mathrm{},p\}^\sigma `$ by

$$\stackrel{~}{A}=\left\{\left(\frac{7f(i)}{t}\right)_{i\sigma }\right|fA\},$$

and observe that $`\stackrel{~}{A}`$ is $`6`$-separated in $`L_2(\mu _\sigma )`$. By Proposition 12,

$$|A|=|\stackrel{~}{A}|\left(\frac{p|\sigma |}{d}\right)^{Cd}$$

where $`d=\mathrm{vc}(\stackrel{~}{A},2)`$, implying that

$$|A|\left(\frac{C\mathrm{log}|A|}{dt^5}\right)^{Cd}.$$

By a straightforward computation,

$$|A|\left(\frac{1}{t}\right)^{Cd},$$

and our claim follows from the fact that $`\mathrm{vc}(\stackrel{~}{A},2)\mathrm{vc}(A,t/7)`$.

Remark. Theorem 1 also holds for the $`L_p(\mu )`$ covering numbers for all $`0<p<\mathrm{}`$, with constants $`K`$ and $`c`$ depending only on $`p`$. The only minor modification of the proof is in Lemma 4, where the equations would be replaced by appropriate inequalities.

## 3 Applications: Gaussian Processes and Convexity

The first application is a bound on the expectation of the supremum of a Gaussian processes indexed by a set $`A`$. Such a bound is provided by Dudley’s integral in terms of the $`L_2`$ entropy of $`A`$; the entropy, in turn, can be majorized through Theorem 1 by the shattering dimension of $`A`$. The resulting integral inequality improves the main result of M. Talagrand in \[T 92\].

If $`A`$ be a class of functions on the finite set $`I`$, then a natural Gaussian process $`(X_a)_{aA}`$ indexed by elements of $`A`$ is

$$X_a=\underset{iI}{}g_ia(i)$$

where $`g_i`$ are independent standard Gaussian random variables.

###### Theorem 15

Let $`A`$ be a class of functions bounded by $`1`$, defined on a finite set $`I`$ of cardinality $`n`$. Then $`E=𝔼sup_{aA}X_a`$ is bounded as

$$EK\sqrt{n}_{cE/n}^1\sqrt{\mathrm{vc}(A,t)\mathrm{log}(2/t)}𝑑t,$$

where $`K`$ and $`c`$ are absolute positive constants.

The nonzero lower limit in the integral will play an important role in the application to Elton’s Theorem.

The first step in the proof is to view $`A`$ as a subset of $`^n`$. Dudley’s integral inequality can be stated as

$$EK_0^{\mathrm{}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t,$$

where $`D_n`$ is the unit Euclidean ball in $`^n`$, see \[Pi\] Theorem 5.6. The lower limit in this integral can be improved by a standard argument. This fact was first noticed by A. Pajor.

###### Lemma 16

Let $`A`$ be a subset of $`^n`$. Then $`E=𝔼sup_{aA}X_a`$ is bounded as

$$EK_{cE/\sqrt{n}}^{\mathrm{}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t,$$

where $`K`$ is an absolute constant.

Proof. Fix positive absolute constants $`c_1,c_2`$ whose values will be specified later. There exists a subset $`𝒩`$ of $`A`$, which is a $`(\frac{c_1E}{\sqrt{n}})`$-net of $`A`$ with respect to the Euclidean norm and has cardinality $`|𝒩|N(A,\frac{c_1E}{2\sqrt{n}}D_n)`$. Then $`A𝒩+\frac{c_1E}{2\sqrt{n}}D_n`$, and one can write

$$E=𝔼\underset{aA}{sup}X_a𝔼\underset{a𝒩}{\mathrm{max}}X_a+𝔼\underset{a\frac{c_1E}{\sqrt{n}}D_n}{sup}X_a.$$
(12)
The first summand is estimated by Dudley’s integral as

$$𝔼\underset{a𝒩}{\mathrm{max}}X_aK_0^{\mathrm{}}\sqrt{\mathrm{log}N(𝒩,tD_n)}𝑑t.$$
(13)
On the interval $`(0,\frac{c_2E}{\sqrt{n}})`$,

$`K{\displaystyle _0^{\frac{c_2E}{\sqrt{n}}}}\sqrt{\mathrm{log}N(𝒩,tD_n)}𝑑t`$ $`K{\displaystyle \frac{c_2E}{\sqrt{n}}}\sqrt{\mathrm{log}|𝒩|}`$
$`K{\displaystyle \frac{c_2E}{\sqrt{n}}}\sqrt{\mathrm{log}N(A,\frac{c_1E}{2\sqrt{n}}D_n)}.`$
The latter can be estimated using Sudakov’s inequality \[D, Pi\], which states that $`\epsilon \sqrt{\mathrm{log}(N,\epsilon D_n)}K𝔼sup_{aA}X_a`$ for all $`\epsilon >0`$. Indeed,

$$K\frac{c_2E}{\sqrt{n}}\sqrt{\mathrm{log}N(A,\frac{c_1E}{2\sqrt{n}}D_n)}K_1(2c_2/c_1)𝔼\underset{aA}{sup}X_a=K_1(2c_2/c_1)E\frac{1}{4}E,$$

if we select $`c_2`$ as $`c_2=c_1/8K_1`$. Combining this with (13) implies that

$$𝔼\underset{x𝒩}{\mathrm{max}}X_a\frac{1}{4}E+K_{\frac{c_2E}{\sqrt{n}}}^{\mathrm{}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t$$
(14)
because $`𝒩`$ is a subset of $`A`$.

To bound the second summand in (12), we apply the Cauchy-Schwarz inequality to obtain that for any $`t>0`$,

$$𝔼\underset{atD_n}{sup}X_at𝔼\left(\underset{iI}{}g_i^2\right)^{1/2}t\sqrt{n}.$$

In particular, if $`c_1<1/4`$ then

$$𝔼\underset{a\frac{c_1E}{\sqrt{n}}D_n}{sup}X_ac_1E\frac{1}{4}E.$$

This, (12) and (14) imply that

$$EK_2_{\frac{c_2E}{\sqrt{n}}}^{\mathrm{}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t,$$

where $`K_2`$ is an absolute constant.

Proof of Theorem 15.  By Lemma 16,

$$EK_{cE/\sqrt{n}}^{\mathrm{}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t.$$

Since $`A[1,1]^n\sqrt{n}D_n`$, the integrand vanishes for $`t\sqrt{n}`$. Hence, by Theorem 1

$`E`$ $`K{\displaystyle _{cE/\sqrt{n}}^\sqrt{n}}\sqrt{\mathrm{log}N(A,tD_n)}𝑑t`$
$`=K\sqrt{n}{\displaystyle _{cE/n}^1}\sqrt{\mathrm{log}N(A,t\sqrt{n}D_n)}𝑑t`$
$`K_1\sqrt{n}{\displaystyle _{cE/n}^1}\sqrt{\mathrm{vc}(A,c_1t)\mathrm{log}(2/t)}𝑑t.`$
The absolute constant $`0<c_1<1/2`$ can be made $`1`$ by a further change of variable.

The main consequence of Theorem 15 is Elton’s Theorem with the optimal dependence on $`\delta `$.

###### Theorem 17

There is an absolute constant $`c`$ for which the following holds. Let $`x_1,\mathrm{},x_n`$ be vectors in the unit ball of a Banach space. Assume that

$$𝔼\underset{i=1}{\overset{n}{}}g_ix_i\delta n\text{for some number }\delta >0.$$

Then there exist numbers $`s,t(c\delta ,1)`$, and a subset $`\sigma \{1,\mathrm{},n\}`$ of cardinality $`|\sigma |s^2n`$, such that

$$\underset{i\sigma }{}a_ix_it\underset{i\sigma }{}|a_i|\text{for all real numbers }(a_i).$$
(15)
In addition, the numbers $`s`$ and $`t`$ satisfy the inequality $`st\mathrm{log}^{1.6}(2/t)c\delta `$.

Before the proof, recall the interpretation of the shattering dimension of convex bodies. If a set $`B^n`$ is convex and symmetric then $`\mathrm{vc}(B,t)`$ is the maximal cardinality of a subset $`\sigma `$ of $`\{1,\mathrm{},n\}`$ such that $`P_\sigma (B)[\frac{t}{2},\frac{t}{2}]^\sigma `$. Indeed, every convex symmetric set in $`^n`$ can be viewed as a class of functions on $`\{1,\mathrm{},n\}`$. If $`\sigma `$ is $`t`$-shattered with a level function $`h`$ then for every $`\sigma ^{}\sigma `$ there is some $`f_\sigma ^{}`$ such that $`f_\sigma ^{}(i)h(i)+t`$ if $`i\sigma ^{}`$ and $`f_\sigma ^{}h`$ on $`\sigma \backslash \sigma ^{}`$. By selecting for every such $`\sigma ^{}`$ the function $`(f_\sigma ^{}f_{\sigma \backslash \sigma ^{}})/2`$ and since the class is convex and symmetric, it follows that $`P_\sigma (B)[\frac{t}{2},\frac{t}{2}]^\sigma `$, as claimed.

Taking the polars, this inclusion can be written as $`\frac{t}{2}(B^{}^\sigma )B_1^n`$, where $`B_1^n`$ is the unit ball of $`\mathrm{}_1^n`$. Denoting by $`_B^{}`$ the Minkowski functional (the norm) induced by the body $`B^{}`$, one can rewrite this inclusion as the inequality

$$\underset{i\sigma }{}a_ie_i_B^{}\frac{t}{2}\underset{i\sigma }{}|a_i|\text{for all real numbers }(a_i),$$

where $`(e_i)`$ is the standard basis of $`^n`$. Therefore, to prove Theorem 17, one needs to bound below the shattering dimension of the dual ball of a given Banach space.

Proof of Theorem 17. By a perturbation argument, one may assume that the vectors $`(x_i)_{in}`$ are linearly independent. Hence, using an appropriate linear transformation one can assume that $`X=(^n,)`$ and that $`(x_i)_{in}`$ are the unit coordinate vectors $`(e_i)_{in}`$ in $`^n`$. Let $`B=(B_X)^{}`$ and note that the assumption $`e_i_X1`$ implies that $`B[1,1]^n`$.

Set

$$E=𝔼\underset{i=1}{\overset{n}{}}g_ix_i_X=𝔼\underset{bB}{sup}\underset{i=1}{\overset{n}{}}g_ib(i).$$

By Theorem 15,

$$\delta nEK\sqrt{n}_{c\delta }^1\sqrt{\mathrm{vc}(B,t)\mathrm{log}(2/t)}𝑑t.$$

Consider the function

$$h(t)=\frac{c_0}{t\mathrm{log}^{1.1}(2/t)}$$

where the absolute constant $`c_0>0`$ is chosen so that $`_0^1h(t)𝑑t=1`$. It follows that there exits some $`c\delta t1`$ such that

$$\sqrt{\mathrm{vc}(B,t)/n\mathrm{log}(2/t)}\delta h(t).$$

Hence

$$\mathrm{vc}(B,t)\frac{c_0\delta ^2}{t^2\mathrm{log}^{3.2}(2/t)}n.$$

Therefore, letting $`s^2=\mathrm{vc}(B,t)/n`$, it follows that $`st\mathrm{log}^{1.6}(2/t)\sqrt{c_0}\delta `$ as required, and by the discussion preceding the proof there exists a subset $`\sigma `$ of $`\{1,\mathrm{},n\}`$ of cardinality $`|\sigma |s^2n`$ such that (15) holds with $`t/2`$ instead of $`t`$. The only thing remaining is to check that $`s\delta `$. Indeed, $`s\frac{\sqrt{c_0}\delta }{t\mathrm{log}^{1.6}(2/t)}c_1\delta `$, because $`t1`$.

Remarks.  1. As the proof shows, the exponent $`1.6`$ can be reduced to any number larger than $`3/2`$.

2. The relation between $`s`$ and $`t`$ in Theorem 17 is optimal up to a logarithmic factor for all $`0<\delta <1`$. This is seen from by the following example, shown to us by Mark Rudelson. For $`0<\delta <1/\sqrt{n}`$, the constant vectors $`x_i=\delta \sqrt{n}e_1`$ in $`X=`$ show that $`st`$ in Theorem 17 can not exceed $`\delta `$. For $`1/\sqrt{n}\delta 1`$, we consider the body $`D=\mathrm{conv}(B_1^n\frac{1}{\delta \sqrt{n}}D_n)`$ and let $`X=(^n,_D)`$ and $`x_i=e_i`$, $`i=1,\mathrm{},n`$. Clearly, $`𝔼g_ix_i_X𝔼\epsilon _ie_i_D=\delta n`$. Let $`0<s,t<1`$ be so that (15) holds for some subset $`\sigma \{1,\mathrm{},n\}`$ of cardinality $`|\sigma |s^2n`$. This means that $`x_Dtx_1`$ for all $`x^\sigma `$. Dualizing, $`\frac{t}{\delta \sqrt{n}}x_2tx_D^{}x_{\mathrm{}}`$ for all $`x^\sigma `$. Testing this inequality for $`x=_{i\sigma }e_i`$, it is evident that $`\frac{t}{\delta \sqrt{n}}\sqrt{|\sigma |}1`$ and thus $`st\delta `$.

We end this article with an application to empirical processes. A key question is when a class of functions satisfies the central limit theorem uniformly in some sense. Such classes of functions are called uniform Donsker classes. We will not define these classes formally but rather refer the reader to \[D, VW\] for an introduction on the subject. It turns out that the uniform Donsker property is related to uniform estimates on covering numbers via the Koltchinskii-Pollard entropy integral.

###### Theorem 18

\[D\] Let $`F`$ be a class of functions bounded by $`1`$. If

$$_0^{\mathrm{}}\underset{n}{sup}\underset{\mu _n}{sup}\sqrt{\mathrm{log}N(F,L_2(\mu _n),\epsilon )}d\epsilon <\mathrm{},$$

then $`F`$ is a uniform Donsker class.

Having this condition in mind, it is natural to try to seek entropy estimates which are “dimension free”, that is, do not depend on the size of the sample. In the $`\{0,1\}`$-valued case, such bounds where first obtained by Dudley who proved Theorem 1 for these classes (see \[LT\] Theorem 14.13) which implied through Theorem 18 that every VC class is a uniform Donsker class.

Theorem 1 solves the general case: the following corollary extends Dudley’s result on the uniform Donsker property from $`\{0,1\}`$ classes to classes of real valued functions.

###### Corollary 19

Let $`F`$ be a class of functions bounded by $`1`$ and assume that the integral

$$_0^1\sqrt{\mathrm{vc}(F,t)\mathrm{log}\frac{2}{t}}𝑑t$$

converges. Then $`F`$ is a uniform Donsker class.

In particular this shows that if $`\mathrm{vc}(F,t)`$ is “slightly better” than $`1/t^2`$, then $`F`$ is a uniform Donsker class.

This result has an advantage over Theorem 18 because in many cases it is easier to compute the shattering dimension of the class rather than its entropy (see, e.g. \[AB\]).


text:
# Proximity-induced sub-gaps in Andreev billiards

## Abstract

We examine the density of states of an Andreev billiard and show that any billiard with a finite upper cut-off in the path length distribution $`P(s)`$ will possess an energy gap on the scale of the Thouless energy. An exact quantum mechanical calculation for different Andreev billiards gives good agreement with the semiclassical predictions when the energy dependent phase shift for Andreev reflections is properly taken into account. Based on this new semiclassical Bohr-Sommerfeld approximation of the density of states, we derive a simple formula for the energy gap. We show that the energy gap, in units of Thouless energy, may exceed the value predicted earlier from random matrix theory for chaotic billiards.

Studies of sub-gap transport in hybrid superconductors are an important starting point for the design and simulation of superconducting nanoscale devices. For a given inhomogeneous structure, a fundamental question is the existence or otherwise of a finite density of states at the Fermi energy. This is important experimentally, since the sub-gap spectrum determines the tunneling conductance of an N-S contact. The ability to address this question is also important theoretically, since a well-posed problem of this kind provides a testing ground for complementary (and occasionally competing) theoretical techniques.

One important class of structures, for which a general analysis might be forthcoming, are known as Andreev billiards. These are formed when a classically-chaotic normal dot is placed in contact with a superconductor Kosztin ; Melsen ; Altland ; Lesovik ; Nazarov ; Heny ; Richter1 ; Richter2 . Consider a ballistic two dimensional normal dot of area $`A`$, with the mean level spacing of the isolated normal system $`\delta =\frac{2\pi \mathrm{}^2}{mA}`$ at the Fermi energy $`E_F`$. If a superconductor of width $`W`$ and bulk order parameter $`\mathrm{\Delta }`$ is placed in contact with such a billiard (see Fig. 1), then the question of interest is whether or not an energy gap on the scale of the Thouless energy $`E_T=\frac{M\delta }{4\pi }`$ note\_1 , exists in the sub-gap spectrum $`E<\mathrm{\Delta }`$, when $`\delta <<E_T<\mathrm{\Delta }`$. The number of open channels in the S region is the integer part of $`M=\frac{k_\mathrm{F}W}{\pi }`$, and the energy levels of the Andreev billiards are the positive eigenvalues $`E`$ (measured from the Fermi energy) of the Bogoliubov-de Gennes equationBdG-eq .

An initial study of this problem based on random matrix theoryMelsen , concluded that a classically chaotic billiard possesses an energy gap, whereas an integrable system is gapless. As a consequence it was suggested that the existence of such a gap could be used to distinguish between integrable and chaotic systems. Later it was shown that billiards with classically mixed phase space do possess a smaller gap comparing to the fully chaotic systemsHeny . Studying the existence of the gap for chaotic billiards Ihra et al. Richter1  have drawn the attention to the role of the non-diagonal terms of the scattering matrix which could explain the disagreement between the random matrix theory and the Bohr-Sommerfeld semiclassical approximation. The non-universal feature of the excitation spectra of the Andreev billiards has been recently studied by Ihra and Richter in Ref. Richter2 .

The aim of this Letter is to identify for the first time, a pseudo-integrable billiard which does possess an energy gap. Moreover, this gap can be larger than that predicted for chaotic billiards on the scale of $`E_T`$. To this end, we study the quasi-particle spectrum of the ballistic structure shown in Fig. 1, for different values of the angle $`\alpha `$ and length $`d`$. Our key result is illustrated in Fig. 2, which shows that for $`d=0`$, the counting function or integrated density of states $`N(E)=_0^En(E^{})𝑑E^{}`$ (where $`n(E)`$ is the density of states for the Andreev billiard) exhibits an energy gap $`E_{\mathrm{gap}}`$ varying between $`E_{\mathrm{gap}}0.5E_T`$ and $`E_{\mathrm{gap}}1.5E_T`$ as $`\alpha `$ varies from $`80^{}`$ to $`45^{}`$ (for the details of the calculation see below).

In contrast, as shown in Fig. 3, for $`d0`$, no such energy gap exists.

To understand this result, we start from the formula relating the integrated density of states $`N(E)`$ to the path length distribution $`P(s)`$ (which is the classical probability that an electron entering the billiard at the N-S contact exits after a path length $`s`$) derived by using the Bohr-Sommerfeld approximation,

$$N\left(E\right)=M\underset{n=0}{\overset{\mathrm{}}{}}_{s_n\left(E\right)}^{\mathrm{}}P(s)𝑑s,$$
(1)
where

$$s_n\left(E\right)=\frac{\left(n+\frac{1}{\pi }\mathrm{arccos}\frac{E}{\mathrm{\Delta }}\right)\pi }{E/\mathrm{\Delta }}\xi _0.$$
(2)
Here $`\xi _0=\frac{\mathrm{}v_\mathrm{F}}{\mathrm{\Delta }}=W\frac{2}{\pi M}\frac{E_F}{\mathrm{\Delta }}`$ is the coherence length and the distribution $`P(s)`$ is normalized to one, $`_0^{\mathrm{}}P(s)𝑑s=1`$. The density of states $`n(E)=\frac{dN(E)}{dE}`$ can be found from Eq. (1) yielding

$$n\left(E\right)=\frac{M}{E}\underset{n=0}{\overset{\mathrm{}}{}}P\left(s_n\left(E\right)\right)\left[\frac{\xi _0}{\sqrt{1\left(E/\mathrm{\Delta }\right)^2}}+s_n\left(E\right)\right].$$
(3)
This expression reduces to that of derived in a different way by Melsen et al. Melsen ; Heny , Lodder and NazarovNazarov , Ihra et al. Richter1 , in the limit $`E<<\mathrm{\Delta }`$ and $`\xi _0^2<<A`$, but more generally incorporates an energy dependent path length correction note\_2 .

To test the semiclassical expression, we perform an exact (numerical) diagonalization of the Bogoliubov-de Gennes equation by matching the wave functions at the N-S interface. This results in a secular equation including the scattering matrix, $`S_0(E)`$ of the normal billiard opened at the N-S interface elsewhere :

$$det\left[1e^{2i\mathrm{arccos}\frac{E}{\mathrm{\Delta }}}S_{\mathrm{eff}}(E)S_{\mathrm{eff}}^{}(E)\right]=0,$$
(4)
where

$`S_{\mathrm{eff}}(E)`$ $`=`$ $`[Q(E)+K(E)D(E)]^1\times `$ (5)
$`\left[Q^{}(E)K(E)D(E)\right],`$
$`D(E)`$ $`=`$ $`\left[1S_0(E)\right]\left[1+S_0(E)\right]^1.`$
Here $`Q`$ and $`K`$ are diagonal matrices with elements $`Q_{nm}(E)=i\delta _{nm}q_n(E)`$ and $`K_{nm}(E)=\delta _{nm}k_n(E)`$, where $`q_n(E)=k_F\sqrt{1+i\frac{\sqrt{\mathrm{\Delta }^2E^2}}{E_F}\frac{n^2}{M^2}}`$ are the transverse wavenumbers of the electron in the S region and $`k_n(E)=k_F\sqrt{1+\frac{E}{E_F}\frac{n^2}{M^2}}`$ are the transverse wavenumbers of the electron in the S region when $`\mathrm{\Delta }=0`$. It is assumed that the Fermi wavenumber, $`k_F=\sqrt{2mE_F/\mathrm{}^2}`$ is the same in the S and N regions. All the matrices are $`M`$ by $`M`$ dimensional. Finally, $`S_0`$ was calculated using Bessel functions in the wedge part of the normal region, and including evanescent modes. In a different context, the same type of normal billiard was studied by Kaplan and Heller Heller . A secular equation similar to Eq. (4) was derived by Beenakker Carlo\_2\_3  for SNS systems but there instead of $`S_{\mathrm{eff}}(E)`$ the scattering matrix $`S_0(E)`$ of the normal billiard appears. In this sense, the matrix $`S_{\mathrm{eff}}(E)`$ can be regarded as an effective scattering matrix. Note that in Andreev approximationColin-review  $`q_nk_n`$, and one then finds $`S_{\mathrm{eff}}(E)=S_0(E)`$. In contrast the secular equation (4) for Andreev billiards is valid outside Andreev approximation. Using the unitarity of $`S_0(E)`$, one can show that the following equation

$`det(\mathrm{Im}\{\mathrm{e}^{\mathrm{i}\mathrm{arccos}\frac{\mathrm{E}}{\mathrm{\Delta }}}[\mathrm{Q}(\mathrm{E})+\mathrm{K}(\mathrm{E})\mathrm{D}(\mathrm{E})]\times `$
$`[Q(E)+K(E)D^{}(E)]^1\})`$ $`=`$ $`0,`$ (6)
has the same zeros as those of Eq. (4), and is a more suitable form for numerical calculations (the left hand side of Eq. (6) is a real function instead of a complex one).

Figures 2 and 3 show both exact results and an evaluation of the semiclassical expression of $`N(E)`$ given by Eq. (1) for Andreev billiards shown in Fig. 1 with different parameters note\_3 . One can see that the results of the two methods are in good agreement over the entire energy range $`E<\mathrm{\Delta }`$. It is important to note that inclusion of the energy dependence of the phase shift was essential to obtain such a good agreement. A small deviation can be seen only at energies close to the value of $`\mathrm{\Delta }`$ and for $`d0`$.

Both the semiclassical and the exact calculations reveal the presence of an energy gap when $`d=0`$, while no gap appears in case of $`d0`$. The origin of this result can be traced to the existence of a finite upper cut-off $`s_{\mathrm{max}}`$ in the path length distribution $`P(s)`$. From Eq. (2) it is obvious that if the path length of the electron has a maximum value, then the energy spectrum will possess a gap. The condition for determining $`E_{\mathrm{gap}}`$ is $`s_n(E)>s_{\mathrm{max}}`$ for $`n0`$. Expanding the arccos term in Eq. (2) to first order in $`E/\mathrm{\Delta }`$, one finds that the energy gap is given by the following simple equation:

$$\frac{E_{\mathrm{gap}}}{E_\mathrm{T}}=\pi ^2\frac{A}{Ws_{\mathrm{max}}}\frac{1}{1+\xi _0/s_{\mathrm{max}}},$$
(7)
where $`A`$ is the area of the billiard and $`W`$ is the width of the superconductor lead.

As examples, Fig. 4 shows $`P(s)`$ for $`\alpha =80^{},60^{},45^{}`$ along with the corresponding semiclassical density of states $`n(E)`$ given by Eq. (3). From the figure it is seen that the upper cut-off $`s_{\mathrm{max}}`$ of $`P(s)`$ equals to $`2W`$ for $`\alpha =80^{},60^{}`$, and $`s_{\mathrm{max}}=2\sqrt{2}W`$ for $`\alpha =45^{}`$. It is interesting to note that for $`\alpha =45^{}`$ (more generally for $`\alpha =90^{}/k`$ with an integer $`k>0`$) the density of states $`n(E)`$ has a singularity at some energy $`E<\mathrm{\Delta }`$ while for other values of $`\alpha `$ no pronounced singularities exist. In Bohr-Sommerfeld approximation, it can be shown that this singularity is related to the singularity of the path length distribution $`P(s)`$. The classical trajectories of the electron resulting in a singularity for $`\alpha =45^{}`$ are similar to those moving in a lead with length $`d+W`$ and $`\alpha =90^{}`$. The nature of the singularities of the density of states in this rectangular shape of Andreev billiard was studied in Ref. box-disk-paper, . The reason for the disappearance of these singularities for $`\alpha 90^{}/k`$ ($`k=1,2,3,\mathrm{}`$) is consistent with the points made in this reference.

To check the expression (7) we have determined the energy gap from exact calculations for several angles $`\alpha `$. For the billiard of Fig. 1 with $`d=0`$, one can show analytically that the upper cut-off $`s_{\mathrm{max}}`$ is

$$\frac{s_{\mathrm{max}}}{W}=\{\begin{array}{cc}2\frac{\mathrm{sin}k\alpha \mathrm{sin}\left[\left(k+1\right)\alpha \right]}{\mathrm{sin}\alpha \mathrm{cos}\left[\left(2k+1\right)\alpha \right]}\hfill & \text{if }\frac{\pi /2}{k+1}<\alpha \frac{\pi /2}{k+\frac{2}{3}},\hfill \\ 2\frac{\mathrm{sin}k\alpha }{\mathrm{sin}\alpha }\hfill & \text{if }\frac{\pi /2}{k+\frac{2}{3}}<\alpha \frac{\pi /2}{k},\hfill \end{array}$$
(8)
where $`k=1,2,3,\mathrm{}.`$ Using Eqs. (7) and (8) the gap is plotted as a function of the angle $`\alpha `$ in Fig. 5 together with the exact results.

The numerical results (full circles in Fig. 5) agree very well with the predictions of Eq. (7). One can see that decreasing $`\alpha `$ the energy gap in units of Thouless energy increases and tends to a finite value as $`\alpha 0`$. From Eq. (8) and Eq. (2) it can be seen that $`s_{\mathrm{max}}`$ increases with decreasing $`\alpha `$, whereas $`E_{\mathrm{gap}}/\mathrm{\Delta }`$ decreases. The Thouless energy $`E_T`$ also decreases, since the mean level spacing $`\delta `$ becomes smaller for larger area $`A`$ of the normal region. The two effect together result in a finite value of $`E_{\mathrm{gap}}/E_T`$ at $`\alpha =0`$.

In the limit $`\xi _0<<s_{\mathrm{max}}`$ (for example, in the semiclassical limit of large $`M`$), the expression (7) of the gap reduces to

$$\frac{E_{\mathrm{gap}}}{E_\mathrm{T}}=\pi ^2\frac{A}{Ws_{\mathrm{max}}}.$$
(9)
In Fig. 5 the dashed curve is the result from this formula. One can see that for all angles $`\alpha `$ this limiting result for the energy gap is larger than the finite $`M`$ value. Note that the area is $`A=\frac{1}{2}W^2\mathrm{cot}\alpha `$, and therefore, $`E_{\mathrm{gap}}/E_\mathrm{T}`$ is only a function of $`\alpha `$ and independent of $`W`$ when $`\xi _0<<s_{\mathrm{max}}`$. It can also be shown that $`E_{\mathrm{gap}}/E_\mathrm{T}\pi ^2/42.47`$ as $`\alpha 0.`$ Finally, it is worth mentioning that for Andreev billiard of Fig. 1 when $`d=0`$ the energy gap can be much larger for small angle $`\alpha `$ than the value of $`0.6E_T`$ predicted by Melsen et al. Melsen  for the chaotic billiard.

It is interesting to mention that besides the billiard studied in this work (see Fig. 1 for $`d=0`$) there are a number of different shapes of normal dots in which $`P(s)`$ exhibits finite upper cut-off resulting in a sub-gap. Examples for such dots are shown in Fig. 6 (provided $`\alpha +\beta <180^{}`$ in the case of quadrangle).

In conclusion, we have shown that a billiard with a finite upper cut-off in the path length distribution $`P(s)`$ will possess an energy gap in the density of states on the scale of the Thouless energy. By including the energy dependent phase shift of the Andreev reflection, a new expression for the density of states has been given within the frame work of the semiclassical Bohr-Sommerfeld approximation. We have also derived a formula for the energy gap. To check these results we have performed an exact diagonalization of the Bogoliubov-de Gennes equation for different Andreev billiards. The results of the two methods agrees very well both for the integrated density of states (even for energy levels close to the value of $`\mathrm{\Delta }`$) and for the energy gap. Finally we have shown that the energy gap on the scale of the Thouless energy can be much larger than the value $`0.6E_T`$ predicted from random matrix theoryMelsen  for chaotic billiards.

One of us (J. Cs.) gratefully acknowledges very helpful discussions with C. Beenakker. This work was supported by the EU. RTN within the programme “Nanoscale Dynamics, Coherence and Computation”, the Hungarian Science Foundation OTKA TO25866 and TO34832. One of us (Z. K.) would like to thank the Hungarian Academy of Sciences for support as a János Bolyai fellowship.