×

Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures. (English) Zbl 1326.60032

Summary: Let \(\{X_1,\dots , X_n\}\) be a collection of binary-valued random variables and let \(f : \{0, 1\}^n \to \mathbb{R}\) be a Lipschitz function. Under a negative dependence hypothesis known as the strong Rayleigh condition, we show that \(f-\mathbb{E}f\) satisfies a concentration inequality. The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; some familiar examples from these classes are generalized negative binomials and spanning tree measures. For instance, any Lipschitz-1 function of the edges of a uniform spanning tree on a vertex set \(V\) (e.g. the number of leaves) satisfies the Gaussian concentration inequality \[ \mathbb{P}(f-\mathbb{E}f\geq a)\leq \exp\bigg(-\frac{a^2}{8|V|}\bigg). \] We also prove a continuous version for concentration of Lipschitz functionals of a determinantal point process.

MSC:

60F10 Large deviations
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)

References:

[1] DOI: 10.1088/0305-4470/23/14/025 · doi:10.1088/0305-4470/23/14/025
[2] Ecole de Probabilites de Saint Flour VI, 1976 pp 187– (1977)
[3] Random Measures (1986)
[4] Comm. Math. Phys. 242 pp 277– (2003) · Zbl 1031.60084 · doi:10.1007/s00220-003-0945-y
[5] Zeros of Gaussian Analytic Functions and Determinantal Point Processes (2009) · Zbl 1190.60038
[6] DOI: 10.1214/aop/1176996452 · Zbl 0313.60037 · doi:10.1214/aop/1176996452
[7] DOI: 10.1214/154957806000000078 · Zbl 1189.60101 · doi:10.1214/154957806000000078
[8] DOI: 10.1080/01621459.1963.10500830 · doi:10.1080/01621459.1963.10500830
[9] DOI: 10.1090/S0094-9000-09-00754-6 · doi:10.1090/S0094-9000-09-00754-6
[10] DOI: 10.1214/09-AAP620 · Zbl 1197.60047 · doi:10.1214/09-AAP620
[11] Probability: Theory and Examples (2004)
[12] DOI: 10.1002/(SICI)1098-2418(199809)13:2&lt;99::AID-RSA1&gt;3.0.CO;2-M · Zbl 0964.60503 · doi:10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M
[13] DOI: 10.1063/1.1704292 · Zbl 0127.39304 · doi:10.1063/1.1704292
[14] DOI: 10.1214/aoms/1177729330 · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[15] DOI: 10.1214/aop/1176989121 · Zbl 0785.60007 · doi:10.1214/aop/1176989121
[16] J. Amer. Math. Soc. 22 pp 521– (2009)
[17] The Probabilistic Method (2008)
[18] DOI: 10.1090/S0273-0979-2010-01321-5 · Zbl 1207.32006 · doi:10.1090/S0273-0979-2010-01321-5
[19] Introduction to the Theory of Matroids (1971)
[20] DOI: 10.4213/rm321 · doi:10.4213/rm321
[21] DOI: 10.1007/BF02392515 · Zbl 1099.60037 · doi:10.1007/BF02392515
[22] DOI: 10.1063/1.533200 · Zbl 1052.62518 · doi:10.1063/1.533200
[23] DOI: 10.1137/S0097539793250767 · Zbl 0867.05063 · doi:10.1137/S0097539793250767
[24] Siemons, Surveys in Combinatorics pp 148– (1989)
[25] IHES 98 pp 167– (2003) · Zbl 1055.60003 · doi:10.1007/s10240-003-0016-0
[26] DOI: 10.2140/pjm.1959.9.1141 · Zbl 0092.34503 · doi:10.2140/pjm.1959.9.1141
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.