OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 31J / a / Solution

A function has the bounded-differences property with constants

L_{1}, \dots, L_{n}

when replacing only coordinate

i

changes its value by at most

L_{i}

. The Bounded differences inequality states that, for independent inputs,

P (F - E F \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i} L _{i}^{2}}),

and the analogous lower-tail bound also holds.

Solved by gpt-5.6-sol high.

 Ancestors (11)