Applications of size biased couplings for concentration of measures

Subhankar Ghosh (University of Southern California)
Larry Goldstein (University of Southern California)

Abstract


Let $Y$ be a nonnegative random variable with mean $\mu$ and finite positive variance $\sigma^2$, and let $Y^s$, defined on the same space as $Y$, have the $Y$ size biased distribution, that is, the distribution characterized by $$ E[Yf(Y)]=\mu E f(Y^s) \quad \mbox{for all functions $f$ for which these expectations exist.} $$ Under a variety of conditions on the coupling of $Y$ and $Y^s$, including combinations of boundedness and monotonicity, concentration of measure inequalities such as $$ P\left(\frac{Y-\mu}{\sigma}\ge t\right)\le \exp\left(-\frac{t^2}{2(A+Bt)}\right) \quad \mbox{for all $t \ge 0$} $$ are shown to hold for some explicit $A$ and $B$ in \cite{cnm}. Such concentration of measure results are applied to a number of new examples: the number of relatively ordered subsequences of a random permutation, sliding window statistics including the number of $m$-runs in a sequence of coin tosses, the number of local maxima of a random function on a lattice, the number of urns containing exactly one ball in an urn allocation model, and the volume covered by the union of $n$ balls placed uniformly over a volume $n$ subset of $\mathbb{R}^d$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 70-83

Publication Date: January 23, 2011

DOI: 10.1214/ECP.v16-1605

References

  1. P. Baldi, Y. Rinott and C. Stein, A normal approximations for the number of local maxima of a random function on a graph, Probability, Statistics and Mathematics, Papers in Honor of Samuel Karlin, T. W. Anderson, K.B. Athreya and D. L. Iglehart eds. (1989), Academic Press, 59-81.
  2. D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), no. 2, 294-313. MR1161056
  3. S. Chatterjee, Stein's method for concentration inequalities, Probab. Theory Related Fields 138 (2007), no. 1-2, 305-321. MR2288072
  4. S. Chatterjee, A new method of normal approximation, Ann. Probab. 36 (2008), no. 4, 1584-1610. MR2435859
  5. L.H.Y. Chen, L. Goldstein and Q.M. Shao. Normal Approximation by Stein's Method.(2010). Springer, New York.
  6. G. Englund, A remainder term estimate for the normal approximation in classical occupancy, Ann. Probab. 9 (1981), no. 4, 684-692. MR0624696
  7. Feller, W.(1966). An Introduction to Probability and its Applications, volume II. Wiley.
  8. S. Ghosh and L. Goldstein. Concentration of measures via size biased couplings, (2009). To appear in Probab. Th. Rel. Fields.
  9. L. Goldstein, Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing, J. Appl. Probab. 42 (2005), no. 3, 661-683. MR2157512
  10. L. Goldstein and M. D. Penrose, Normal approximation for coverage models over binomial point processes, Ann. Appl. Probab. 20 (2010), no. 2, 696-721. MR2650046
  11. L. Goldstein and Y. Rinott, Multivariate normal approximations by Stein's method and size bias couplings, J. Appl. Probab. 33 (1996), no. 1, 1-17. MR1371949
  12. P. Hall. Introduction to the theory of coverage processes, (1988). John Wiley, New York.
  13. V.F. Kolchin, B.A. Sevast'yanov and V.P. Chistyakov. Random Allocations, (1978). Winston, Washington D.C.
  14. M. Ledoux. The concentration of measure phenomenon, (2001). Amer. Math. Soc., Providence, RI.
  15. H. Luk. Stein's Method for the Gamma Distribution and Related Statistical Applications, Ph.D Thesis, (1994). Department of Mathematics, University of Southern California, USA.
  16. H. Midzuno, On the sampling system with probability proportionate to sum of sizes, Ann. Inst. Statist. Math., Tokyo 3 (1952), 99-107. MR0050840
  17. P. A. P. Moran, The random volume of interpenetrating spheres in space, J. Appl. Probab. 10 (1973), 483-490. MR0353412
  18. M. Penrose. Random geometric graphs, (2003). Oxford University Press, Oxford.
  19. M. D. Penrose, Normal approximation for isolated balls in an urn allocation model, Electron. J. Probab. 14 (2009), no. 74, 2156-2181. MR2550296
  20. M. D. Penrose and J. E. Yukich, Central limit theorems for some graphs in computational geometry, Ann. Appl. Probab. 11 (2001), no. 4, 1005-1041. MR1878288
  21. M. P. Quine and J. Robinson, A Berry-Esseen bound for an occupancy problem, Ann. Probab. 10 (1982), no. 3, 663-671. MR0659536
  22. M. Raic, CLT-related large deviation bounds based on Stein's method, Adv. in Appl. Probab. 39 (2007), no. 3, 731-752. MR2357379
  23. G. Reinert and A. Roellin, Multivariate normal approximation with Stein's method of exchangeable pairs under a general linearity condition, Ann. Probab. 37 (2009), no. 6, 2150-2173. MR2573554
  24. C. Stein. Approximate Computation of Expectations, (1986). Institute of Mathematical Statistics, Hayward, CA.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.