One-Sided and Two-Sided Hoeffding Confidence Bounds

From Tail Probabilities to Confidence Limits

Hoeffding’s inequality controls how far a sample average of bounded independent observations can deviate from its mean. A confidence bound uses that deviation statement in reverse: choose a tolerated failure probability, solve for the corresponding deviation radius, and report a limit that covers the unknown mean with at least the desired probability. The direction of the tail matters. An upper limit for the mean is obtained from the lower tail of the sample average, and a lower limit is obtained from its upper tail.

Assume \(X_1,\ldots,X_n\) are independent observations, each taking values in the same known interval \([a,b]\), where \(a<b\), and with common mean \(\mu=E[X_i]\). Write \(\bar X_n=n^{-1}\sum_{i=1}^n X_i\). For this setting, Hoeffding’s inequality gives, for every \(t>0\),

A confidence statement is a repeated-sampling guarantee: the data, and hence the reported bound, vary from sample to sample, while \(\mu\) is fixed. The guarantee says how often the reported bound covers that fixed mean under the assumptions above.

Inverting a One-Sided Tail

Let \(0<\delta<1\) be the allowed failure probability. To make the right side of either Hoeffding tail inequality equal to \(\delta\), solve for \(t\):

The upper confidence limit comes from the event that the sample average falls too far below the mean. If \(\mu>\bar X_n+r_n(\delta)\), then \(\bar X_n-\mu<-r_n(\delta)\). Hoeffding’s lower-tail inequality therefore bounds the probability that this upper limit misses.

Proof. The event \(\{\mu>U_\delta\}\) is exactly \(\{\bar X_n-\mu<-r_n(\delta)\}\), which is contained in \(\{\bar X_n-\mu\leq-r_n(\delta)\}\). Thus

Consequently \(P(\mu\leq U_\delta)\geq1-\delta\). Similarly, \(\{\mu<L_\delta\}=\{\bar X_n-\mu>r_n(\delta)\}\), which is contained in \(\{\bar X_n-\mu\geq r_n(\delta)\}\). The upper-tail inequality gives \(P(\mu<L_\delta)\leq\delta\), hence \(P(\mu\geq L_\delta)\geq1-\delta\). \(\square\)

Because \(\mu\in[a,b]\), the limits may be tightened without reducing coverage: use \(\min\{b,U_\delta\}\) as the upper limit and \(\max\{a,L_\delta\}\) as the lower limit. The untrimmed formulas are often simpler to work with, and either form gives the stated one-sided guarantee.

Two-Sided Coverage and the Radius Cost

A two-sided interval must control both ways the sample mean can differ from \(\mu\). The event that the interval \([\bar X_n-r,\bar X_n+r]\) misses \(\mu\) is contained in the union of the upper-tail and lower-tail deviation events. The union bound adds their failure probabilities.

Proof. If \(|\bar X_n-\mu|>r\), then either \(\bar X_n-\mu>r\) or \(\bar X_n-\mu<-r\). Applying the two Hoeffding bounds and the union bound,

Set \(r=r_{n,2}(\delta)\). Then the right side is \(2\exp[-\log(2/\delta)]=\delta\). Therefore the probability that \(\mu\) lies in the interval is at least \(1-\delta\). \(\square\)

For the same nominal confidence level \(1-\delta\), the two-sided radius is larger than the one-sided radius:

The increase comes from protecting against two tails rather than one. It is not a change in the boundedness assumption or the sample size. As \(\delta\) becomes small, the ratio approaches 1, but for any \(0<\delta<1\) it is strictly greater than 1.

Different Error Allocations for Asymmetric Limits

The two sides do not have to receive equal failure probabilities. Suppose an upper bound is required to fail with probability at most \(\delta_U\), and a lower bound with probability at most \(\delta_L\). Applying the one-sided result separately and then using the union bound gives simultaneous coverage of at least \(1-\delta_U-\delta_L\). The resulting interval can therefore have different distances from \(\bar X_n\) on its two sides.

Common Pitfall: Using the One-Sided Radius Twice

A frequent error is to calculate a radius using \(\log(1/\delta)\), then claim that the interval extending that distance in both directions has coverage \(1-\delta\). That radius makes each tail probability at most \(\delta\), so the union bound only guarantees total failure probability at most \(2\delta\). For a two-sided failure budget of \(\delta\), assign at most \(\delta/2\) to each tail; equivalently, use the radius involving \(\log(2/\delta)\).

The radius also depends on the known range width \(b-a\) and on \(n\): it grows linearly with the range width and decreases at the rate \(1/\sqrt n\). A confidence level alone does not determine a numerical bound. The observations’ range, sample size, and observed average are all needed.