Concentration Inequalities for Incomplete U-statistics over Arbitrary Sampling Graphs

2026/07/19 by Zheng Tracy Ke
#math.PR #math.ST #stat.TH

paper · pdf

Abstract

Let X₁, X₂, …, X_n be independent random vectors. For a directed graph G=(V,E) with vertex set V=\1,2,…,n\ and a collection of bivariate kernels \h_e:e∈ E\, we consider U=∑_{e=(i,j)∈ E} h_e(X_i,X_j). This framework generalizes incomplete U-statistics by allowing the random vectors to be non-identically distributed, the kernels to be asymmetric and edge-dependent, and the sampling structure to be specified by an arbitrary graph. We derive several concentration inequalities for U-𝔼U. The main proof strategy exploits edge-coloring results from graph theory and relates the tail behavior of U to the chromatic index of G. This approach is elementary, transparent, and readily adaptable to broader settings, including U-statistics of order m>2 and statistics involving doubly indexed random vectors.

Related

• A concentration result with application to subgraph count
• Concentration for Poisson U-Statistics: Subgraph Counts in Random Geometric Graphs
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• Multivariate concentration of measure type results using exchangeable pairs and size biasing
• Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains