1. МЕТОД МАРТИНГЕЙЛА. 1.1. Нерівність Азуми-Хеффдінга. Концентраційні нерівності є нерівності, які обмежують ймовірності відхилень випадкової величини від її середнього або медіани.

Концентраційні нерівності мають справу з відхиленнями функцій незалежних випадкових величин від їх очікування. В останнє десятиліття були представлені нові інструменти, що дозволяють встановити прості та потужні нерівності.

Про це говорить нерівність Чебишева ймовірність падіння X більш ніж на k стандартних відхилень від свого середнього (в будь-якому напрямку) становить не більше 1/k2 1 / k 2 . Сила нерівності Чебишева полягає в тому, що вона широко застосовна – вона вимагає лише, щоб X мав кінцеве середнє значення та дисперсію.

Простий приклад нерівності Азуми для підкидання монети Наприклад, якщо ми встановлюємо t пропорційним до n, тоді це говорить нам про те, що хоча максимально можливе значення Xn лінійно масштабується з n, ймовірність того, що сума масштабується лінійно з n, експоненціально швидко зменшується з n. наближається до 0, коли n прямує до нескінченності.

Існує приказка про ймовірність, яка говорить, що за кожною граничною теоремою лежить ймовірнісна нерівність (тобто, обмеження ймовірності виникнення небажаної події). Оскільки велика частина теорії ймовірностей стосується доведення граничних теорем, люди розробили дивовижну кількість нерівностей.

Нерівності є математичні вирази, у яких обидві сторони не рівні. У нерівності, на відміну від рівнянь, ми порівнюємо дві величини. Знак рівності між ними замінюється знаком менше (або менше або дорівнює), більше (або більше або дорівнює) або не дорівнює знаку.