Hoeffding-Serfling inequality for U-statistics without replacement (Q6046195)

Let \(X_1,\ldots,X_n\) denote a sample of size \(n\) drawn without replacement from a finite population \(\mathcal{X}\) of size \(N\), and let \(U\) denote the corresponding U-statistic of order \(r\leq N-1\) with kernel \(g\). That is, \[ U=\frac{1}{n^{(r)}}\sum_{(i_1,\ldots,i_r)}g(X_{i_1},\ldots,X_{i_r})\,, \] where \(n^{(r)}=n(n-1)\cdots(n-r+1)\) is the falling factorial, and the sum is taken over all \(r\)-tuples of distinct positive integers up to \(n\). The authors establish a concentration inequality for \(U\). Denoting \[ \mu=\frac{1}{N^{(r)}}\sum_{(i_1,\ldots,i_r)}g(X_{i_1},\ldots,X_{i_r})\,, \] with this sum taken over all \(r\)-tuples of distinct elements of \(\mathcal{X}\), and assuming that \(a\leq g(x_{i_1},\ldots,x_{i_r})\leq b\) for all \(x_{i_1},\ldots,x_{i_r}\), the main result of the present paper is that, for all \(\varepsilon>0\), \[ P(U-\mu\geq\varepsilon)\leq\exp\left\{-\frac{2(n-r+1)\varepsilon^2}{r^2\left(1-\frac{n-r+1}{N-r+1}\right)\left(1+\frac{1}{n-r+1}\right)(b-a)^2}\right\}\,. \] A simulation study is used to investigate the quality of this bound numerically.