5,321
edits
No edit summary |
|||
Line 193: | Line 193: | ||
where <math>F \circ S = \{(f(z_1),...,f(z_n)) \mid f \in F\}</math><br> | where <math>F \circ S = \{(f(z_1),...,f(z_n)) \mid f \in F\}</math><br> | ||
;Notes | ;Notes | ||
===Concentration Bounds=== | |||
====Hoeffding's inequality==== | |||
Let <math>X_1,...,X_n</math> be bounded in (a,b)<br> | |||
Then <math>P(|\bar{X}-E[\bar{X}]| \geq t) \leq 2exp(-\frac{2nt^2}{(b-a)^2})</math> |