Что является доказательством этой нестандартной версии неравенства Азумы?

В Приложении B « Повышение и дифференциальная конфиденциальность » Дворка и др. Авторы приводят следующий результат без доказательств и называют его неравенством Азумы:

Пусть - действительные случайные величины, такие что для каждого ,$C_1, \dots, C_k$$i \in [k]$

1. $\Pr[|C_i| \leq \alpha] = 1$ и
2. для каждого $(c_1, \dots, c_{i - 1}) \in \text{Supp}(C_1, \dots, C_{i - 1})$ мы имеем $\text{E}[C_i \mid C_1 = c_1, \dots, C_{i - 1} = c_{i - 1}] \leq \beta$ .

Тогда для каждого $z > 0$ имеем $\Pr[\sum_{i = 1}^k C_i > k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$ ,

У меня проблемы с доказательством. Стандартная версия неравенства Азумы говорит:

Предположим, что $\{X_0, X_1, \dots, X_k\}$ является мартингалом, а $|X_i - X_{i - 1}| \leq \gamma_i$ почти наверняка. Тогда для всех $t > 0$ имеем $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$ .

Чтобы доказать версию неравенства Азумы, изложенную Дворком и др., Я решил, что нам нужно взять $X_0 = 0$ и $X_i = X_{i - 1} + C_i - \text{E}[C_i \mid C_1, C_2, \dots, C_{i - 1}]$ . Таким образом, я думаю, что $\{X_0, \dots, X_k\}$ - мартингейл. Но все, что мы можем сказать, это то, что $|X_i - X_{i - 1}| \leq 2\alpha$ почти наверняка, верно? Этот фактор в два раза вызывает проблемы, потому что это означает, что после замены мы просто обнаруживаем, что $\Pr[\sum_{i = 1}^k C_i > k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$ , что слабее, чем заключение, сформулированное Dwork et al.

Есть ли простой трюк, который я пропускаю? Является ли заявление Dwork et al. не хватает в два раза?

Я не могу найти ссылку, поэтому я просто набросал доказательство здесь.

Теорема. Пусть - реальные случайные величины. Пусть являются константами. Предположим, что для всех и всех в поддержке , у нас есть$X_1, \cdots, X_n$$a_1, \cdots, a_n, b_1, \cdots, b_n$$i \in \{1,\cdots,n\}$$(x_1,\cdots,x_{i-1})$$(X_1, \cdots, X_{i-1})$

1. $\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$ и
2. $\mathbb{P}[X_i \in [a_i,b_i]]=1$ .

Тогда для всех ,$t\geq0$

$$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right] \leq \exp\left(\frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right).$$

Доказательство. Определить . Мы утверждаем, что Для всех и у нас есть По предположению, и для всех в поддержку$Y_i = \sum_{j=1}^i X_j$

$$\forall i \in \{1,\cdots,n\}~\forall \lambda \geq 0 ~~~~~ \mathbb{E}\left[e^{\lambda Y_i}\right] \leq e^{\frac18 \lambda^2 \sum_{j=1}^i (b_j-a_j)^2}.\tag*{(*)}$$ $i$$\lambda$ $$\mathbb{E}\left[e^{\lambda Y_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{\lambda X_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot \mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}\right]\right].$$ $\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$$\mathbb{P}[X_i \in [a_i,b_i]] =1$$y_{i-1}$$Y_{i-1}$, (Обратите внимание, что .) Таким образом, по лемме Хеффдинга , для всех в поддержку и всех . Так , мы имеем, для всех , Теперь индукция дает иск (*) выше.$Y_{i-1}=X_1+\cdots+X_{i-1}$ $$\mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}=y_{i-1}\right] \leq e^{\lambda\mu(y_{i-1})+\frac18 \lambda^2(b_i-a_i)^2}$$ $y_{i-1}$$Y_{i-1}$$\lambda \in \mathbb{R}$$\mu(y_{i-1})\leq 0$$\lambda \geq 0$ $$\mathbb{E}\left[e^{\lambda Y_i}\right] \leq \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{0+\frac18 \lambda^2(b_i-a_i)^2}\right].$$

Теперь мы применяем неравенство Маркова к и используем наше утверждение (*). Для всех , Наконец, установите чтобы минимизировать выражение правой руки и получить результат. $e^{\lambda Y_n}$$t, \lambda > 0$

$$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right]=\mathbb{P}[Y_n \geq t] = \mathbb{P}\left[e^{\lambda Y_n} \geq e^{\lambda t}\right] \leq \frac{\mathbb{E}\left[e^{\lambda Y_n}\right]}{e^{\lambda t}} \leq \frac{e^{\frac18 \lambda^2 \sum_{i=1}^n (b_i-a_i)^2}}{e^{\lambda t}}.$$ $\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$$\tag*{$\blacksquare$}$

Как я упоминал в своем комментарии, ключевое отличие между этим и «обычным» утверждением о неравенстве заключается в том , что вместо требуется . Первый обеспечивает большую гибкость, и в некоторых случаях это экономит коэффициент 2.$X_i \in [a_i,b_i]$$X_i \in [-a,a]$

Обратите внимание, что случайные величины в доказательстве являются супермартингалом. Вы можете получить обычную версию неравенства взяв мартингейл , установив и (где ) с последующим применением вышеуказанного результата.$Y_i$$Y_1, \cdots, Y_n$$X_i=Y_i-Y_{i-1}$$[a_i,b_i]=[-c_i,c_i]$$\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$