Разности мартингала и неравенство Хёффдинга

Требуется упаковать рюкзак с максимальной выгодой. Предположим, у вас есть $n$ предметов, причём $i$-й предмет имеет объём $V_{i}$ и ценность $W_{i}$, где $V_{1}, V_{2}, \ldots , V_{n}, W_{1}, W_{2}, \ldots , W_{n}$ — независимые неотрицательные случайные величины с конечными средними, и $W_{i} \leq M$ для всех $i$ и некоторого фиксированного $M$. Ваш рюкзак имеет объём $c$, и вы хотите максимизировать суммарную ценность предметов, упакованных в него. То есть вы хотите найти вектор $z_{1}, z_{2}, \ldots , z_{n}$ из 0 и 1 такой, что $\sum_{1}^{n} z_{i} V_{i} \leq c$, максимизирующий $\sum_{1}^{n} z_{i} W_{i}$. Пусть $Z$ — максимально возможная ценность содержимого рюкзака, и покажите, что $\mathbb {P}\left(|Z-\mathbb {E}\left[Z\right]| \geq x\right) \leq 2 \exp \left\{ -x^{2} /\left(2 n M^{2}\right)\right\}$ при $x > 0$.

Даны $n$ вершин $v_{1}, v_{2}, \ldots , v_{n}$; для каждого $1 \leq i < j \leq n$ мы проводим ребро между $v_{i}$ и $v_{j}$ с вероятностью $p$; различные пары соединяются независимо друг от друга. Мы называем $v_{i}$ и $v_{j}$ соседями, если они соединены ребром. Хроматическое число $\chi$ получившегося графа — это минимальное число карандашей различных цветов, необходимых для того, чтобы каждая вершина могла быть окрашена иначе, чем каждый из её соседей. Покажите, что $\mathbb {P}\left(|\chi -\mathbb {E}\left[\chi \right]| \geq x\right) \leq 2 \exp \left\{ -\frac{1}{2} x^{2} / n\right\}$ при $x > 0$.

Пусть $(M, \mathcal{F})$ — мартингал с $M_{0} = 0$, с разностями $D_{r} = M_{r}-M_{r-1}$. Процесс, задаваемый формулой $Q_{n} = \sum_{r = 1}^{n} D_{r}^{2}$, называется опциональной квадратической вариацией $M$, тогда как $V_{n} = \sum_{r = 1}^{n} \mathbb {E}\left[D_{r}^{2} \mid \mathcal{F}_{r-1}\right]$ называется предсказуемой квадратической вариацией $M$. Покажите, что $X_{n} = M_{n}^{2}-Q_{n}$ и $Y_{n} = M_{n}^{2}-V_{n}$ задают мартингалы относительно $\mathcal{F}$.