Return to Question

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read in Dubhashi-Panconesi book that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\big(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\big) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read in Dubhashi-Panconesi book that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\left(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\right) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\big(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\big) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read in Dubhashi-Panconesi book that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\big(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\big) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

Let $(X_i)$ be a martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\big(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\big) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a martingale with respect to the conditional probability.

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\big(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\big) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.