A generalization of Sauer's lemma (Q1899068): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0097-3165(95)90001-2 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1981207991 / rank | |||
Normal rank | |||
Revision as of 19:46, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A generalization of Sauer's lemma |
scientific article |
Statements
A generalization of Sauer's lemma (English)
0 references
11 February 1996
0 references
The authors generalize \textit{N. Sauer's} lemma [ibid. 13, 145-147 (1972; Zbl 0248.05005)] to multivalued functions, proving tight bounds on the cardinality of subsets of \(\prod^m_{i= 1} \{0,\dots, N_i\}\) which avoid certain patterns. In addition, the authors give an application of this result, bounding the uniform rate of convergence of empirical estimates of the expectations of a set of random variables to their true expectations.
0 references
Vapnik-Chervonenkis dimension
0 references
multivalued function
0 references
expectation estimate
0 references
