Bounds for the uniform deviation of empirical measures

If X1,...,Xn are independent identically distributed Rd-valued random vectors with probability measure [mu] and empirical probability measure [mu]n, and if is a subset of the Borel sets on Rd, then we show that P{supA[set membership, variant][mu]n(A)-[mu](A)>=[var epsilon]} <= cs(, n2)e-2n[set membership, variant]2, where c is an explicitly given constant, and s(, n) is the maximum over all (x1,...,xn) [set membership, variant] Rdn of the number of different sets in {{x1...,xn}[intersection]AA [set membership, variant]}. The bound strengthens a result due to Vapnik and Chervonenkis.