Notion of convergence of random variables
Uniform convergence in probability is a form of convergence in probability in statistical asymptotic theory and probability theory. It means that, under certain conditions, the "empirical frequencies" of all events in a certain event-family converge to their "theoretical probabilities". Uniform convergence in probability has applications to statistics as well as machine learning as part of statistical learning theory.
The law of large numbers says that, for each "single" event formula_1, its empirical frequency in a sequence of independent trials converges (with high probability) to its theoretical probability. In many application however, the need arises to judge simultaneously the probabilities of events of an entire class formula_2 from one and the same sample. Moreover it, is required that the relative frequency of the events converge to the probability uniformly over the entire class of events formula_2 The Uniform Convergence Theorem gives a sufficient condition for this convergence to hold. Roughly, if the event-family is sufficiently simple (its VC dimension is sufficiently small) then uniform convergence holds.
 ;templatestyles src="Template:TOC limit/styles.css" / ;
Definitions.
For a class of predicates formula_4 defined on a set formula_5 and a set of samples formula_6, where formula_7, the "empirical frequency" of formula_8 on formula_9 is
 formula_10
The "theoretical probability" of formula_8 is defined as formula_12
The Uniform Convergence Theorem states, roughly, that if formula_4 is "simple" and we draw samples independently (with replacement) from formula_5 according to any distribution formula_15, then with high probability, the empirical frequency will be close to its expected value, which is the theoretical probability.
Here "simple" means that the Vapnik–Chervonenkis dimension of the class formula_4 is small relative to the size of the sample. In other words, a sufficiently simple collection of functions behaves roughly the same on a small random sample as it does on the distribution as a whole.
The Uniform Convergence Theorem was first proved by Vapnik and Chervonenkis using the concept of growth function.
Uniform convergence theorem.
The statement of the uniform convergence theorem is as follows:
If formula_4 is a set of formula_18-valued functions defined on a set formula_5 and formula_15 is a probability distribution on formula_5 then for formula_22 and formula_23 a positive integer, we have:
 formula_24
The maximum is guaranteed to exist since there is only a finite set of values that probability under a random permutation can take.
Reduction to a finite class.
Lemma: Basing on the previous lemma,
 formula_25.
Proof:
Let us define formula_26 and formula_27 which is at most formula_28. This means there are functions formula_29 such that for any formula_30 between formula_31 and formula_32 with formula_33 for formula_34
We see that formula_35 iff for some formula_36 in formula_4 satisfies,
formula_38. 
Hence if we define formula_39 if formula_40 and formula_41 otherwise.
For formula_42 and formula_43, we have that formula_35 iff for some formula_45 in formula_46 satisfies formula_47. By union bound we get
 formula_48
formula_49
Since, the distribution over the permutations formula_50 is uniform for each formula_51, so formula_52 equals formula_53, with equal probability.
Thus,
 formula_54
where the probability on the right is over formula_55 and both the possibilities are equally likely. By Hoeffding's inequality, this is at most formula_56.
Finally, combining all the three parts of the proof we get the Uniform Convergence Theorem.
References.
 ;templatestyles src="Reflist/styles.css" / ;