Text

theses

In this thesis, we study the probability of a small deviation from the mean of a sum of independent or semi-independent random variables. In contrast with the rich history of large deviation inequalities, small deviations have only recently gained attention, and we make contributions to several problems on this topic. Perhaps the most significant result in this field was an inequality proved by Feige. Let X1, . . . , Xn be nonnegative independent random variables, with E[Xi] ≤ 1 ∀i, and let X = ni=1 Xi. Then for any n, Pr[X < E[X] + 1] ≥ α > 0, for some α ≥ 1/13. This bound was later improved to 1/8 by He, Zhang, and Zhang. Building off their work, we improve the bound to approximately .14. The conjectured true bound is 1/e ≃ .368, so there is still (possibly) quite a gap left to fill. We also consider whether or not such small deviation inequalities hold for k-wise independent random variables. We show that for some classes of random variables, 4- wise independence is sufficient for a constant lower bound of α = 1/6, which we show to be tight. Furthermore, we present counterexamples showing that 3-wise independence is insufficient for a positive constant lower bound. For sums of Bernoulli random variables, we can let α = 1/e. We also show that k-wise independence can bring us arbitrarily close to that bound for large enough k.

ETD_7260

Ph.D.

Includes bibliographical references

by Brian Garnett

doi:10.7282/T3R213JD

ETD doctoral

The author owns the copyright to this work.