Skip to main content
formatting
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} Var\operatorname{Var}(X_i) \leq B^2$

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$$$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}. $$

A similar bound (albeit for independent random variables) is given in Corollary 2 in https://epubs.siam.org/doi/abs/10.1137/1134032Pinelis–Utev (1990) (DOI link). I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$$\operatorname{Var}(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$$\operatorname{Var}(X_i)$.

Thank you for your time and consideration.

Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} Var(X_i) \leq B^2$

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}. $$

A similar bound (albeit for independent random variables) is given in Corollary 2 in https://epubs.siam.org/doi/abs/10.1137/1134032. I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$.

Thank you for your time and consideration.

Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}. $$

A similar bound (albeit for independent random variables) is given in Corollary 2 in Pinelis–Utev (1990) (DOI link). I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $\operatorname{Var}(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $\operatorname{Var}(X_i)$.

Thank you for your time and consideration.

As pointed out in the comments, I had missed adding "y" in the bound earlier. So corrected that now.
Source Link
Siam
  • 33
  • 3

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2}\right)}. $$$$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}. $$

A similar bound (albeit for independent random variables) is given in Theorem 7Corollary 2 in https://epubs.siam.org/doi/abs/10.1137/1134032. I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$.

Thank you for your time and consideration.

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2}\right)}. $$

A similar bound (albeit for independent random variables) is given in Theorem 7 in https://epubs.siam.org/doi/abs/10.1137/1134032. I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$.

Thank you for your time and consideration.

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}. $$

A similar bound (albeit for independent random variables) is given in Corollary 2 in https://epubs.siam.org/doi/abs/10.1137/1134032. I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$.

Thank you for your time and consideration.

Source Link
Siam
  • 33
  • 3

Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} Var(X_i) \leq B^2$

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} Var(X_i) \leq B^2. $$ Question 1: Does the following hold? $$ \mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2}\right)}. $$

A similar bound (albeit for independent random variables) is given in Theorem 7 in https://epubs.siam.org/doi/abs/10.1137/1134032. I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $Var(X_i | \mathcal{F}_{i-1})$. As seen from the above, I would rather have the bound in terms of $Var(X_i)$.

Thank you for your time and consideration.