Let $\{ Z_n \mid n = 0,1,..\}$ be a non-negative super-martingale and assume that it is of bounded difference i.e $\exists ~c_i >0$ s.t $\vert Z_{i+1} - Z_i \vert \leq c_i$. Then we know (Azuma-Hoeffding) that $\mathbb{P} \left [ Z_n - Z_0 \geq t \right ] $ is exponentially suppressed for any $t>0$,

• Under what conditions are either or both of the following probabilities also exponentially suppressed ?
  • $\mathbb{P} \left [ \min_{i=0,\ldots,n} Z_i \geq t \right ] $
  • $\mathbb{P} \left [ \frac{1}{n+1} \sum_{i=0,\ldots,n} Z_i \geq t \right ] $

The above question might be reminiscent of what happens in the ``Kolmogorov's sub-martingale inequality" which says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative sub-martingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

Though I don't know if there is any direct connection between this and my question.

Let $\{ Z_n \mid n = 0,1,..\}$ be a non-negative super-martingale and assume that it is of bounded difference i.e $\exists ~c_i >0$ s.t $\vert Z_{i+1} - Z_i \vert \leq c_i$. Then we know (Azuma-Hoeffding) that $\mathbb{P} \left [ Z_n - Z_0 \geq t \right ] $ is exponentially suppressed for any $t>0$,

• Under what conditions are either or both of the following probabilities also low or even exponentially suppressed ?
  • $\mathbb{P} \left [ \min_{i=0,\ldots,n} Z_i \geq t \right ] $
  • $\mathbb{P} \left [ \frac{1}{n+1} \sum_{i=0,\ldots,n} Z_i \geq t \right ] $

The above question might be reminiscent of what happens in the ``Kolmogorov's sub-martingale inequality" which says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative sub-martingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

Though I don't know if there is any direct connection between this and my question.

The ``Kolmogorov's sub-martingale inequality" says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative sub-martingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

• I would like to know if there are more refined versions of this.

• Like is there a version of this for bounded difference super-martingales with the ``max" replaced by "min"?

• Is there a version of this for bounded difference super-martingales with the ``max" replaced by say the average, $(1/m) \sum_{n=1}^m Z_n$ ?

Let $\{ Z_n \mid n = 0,1,..\}$ be a non-negative super-martingale and assume that it is of bounded difference i.e $\exists ~c_i >0$ s.t $\vert Z_{i+1} - Z_i \vert \leq c_i$. Then we know (Azuma-Hoeffding) that $\mathbb{P} \left [ Z_n - Z_0 \geq t \right ] $ is exponentially suppressed for any $t>0$,

• Under what conditions are either or both of the following probabilities also exponentially suppressed ?
  • $\mathbb{P} \left [ \min_{i=0,\ldots,n} Z_i \geq t \right ] $
  • $\mathbb{P} \left [ \frac{1}{n+1} \sum_{i=0,\ldots,n} Z_i \geq t \right ] $

The above question might be reminiscent of what happens in the ``Kolmogorov's sub-martingale inequality" which says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative sub-martingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

Though I don't know if there is any direct connection between this and my question.

The ``Kolmogorov's submartingale inequality" says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative submartingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

• I would like to know if there are more refined versions of this.

• Like is there a version of this for bounded difference super-martingales with the ``max" replaced by "min"?

The ``Kolmogorov's sub-martingale inequality" says the following : that if $\{ Z_n \mid n = 1,..\}$ is a non-negative sub-martingale then for any $a >0$ and $m \in \mathbb{Z}^+ $we have, $\mathbb{P} [ \max_{n=1,..m} Z_n > a ] \leq \frac{\mathbb{E} [Z_m ]}{a}$

• I would like to know if there are more refined versions of this.

• Like is there a version of this for bounded difference super-martingales with the ``max" replaced by "min"?

• Is there a version of this for bounded difference super-martingales with the ``max" replaced by say the average, $(1/m) \sum_{n=1}^m Z_n$ ?