1
$\begingroup$

I am looking for a concentration inequality for supremum of a moving average. I think that a situation I assume below occurs naturally, and there exists a concentration inequality for that. However, I could not find one.

Let $X_0, X_1, \cdots$ to be a martingale difference sequence with respect to $Y_0, Y_1, \cdots$ such that $X_n \in [a_n, b_n]$. By "moving average", I mean \begin{align} S_M = \sum_{m=0}^{M} \omega^{M-m} X_m, \end{align} where $\omega \in (0, 1)$. I am looking for a concentration inequality that bounds \begin{align} \mathbb{P} \left[ \max_{0 \leq n \leq N} S_n \geq t \right]. \end{align}

My first attempt was as follows: note that \begin{align} S_M = \omega^M \sum_{m=0}^{M} \omega^{-m} X_m := \omega^M S'_M. \end{align} Now, $\omega^{-m} X_m$ is also a martingale difference sequence with respect to $Y_0, Y_1, \cdots$ such that $\omega^{-n} X_n \in [\omega^{-n} a_n, \omega^{-n} b_n]$. Therefore, by Hoeffding's inequality for supremum (P363 of [1]), \begin{align} \mathbb{P} \left[ \max_{0 \leq n \leq N} S'_n \geq t \right] \leq \exp \left( - \frac{2 t^2}{\sum_{n=0}^N \omega^{-2n} (b_i - a_i)^2} \right). \end{align} Since $0 < \omega < 1$, \begin{align} \mathbb{P} \left[ \max_{0 \leq n \leq N} \omega^n S'_n \geq t \right] \leq \mathbb{P} \left[ \max_{0 \leq n \leq N} S'_n \geq t \right] \leq \exp \left( - \frac{2 t^2}{\sum_{n=0}^N \omega^{-2n} (b_i - a_i)^2} \right). \end{align}

However, unfortunately, the bound above is very loose. Indeed, when $\omega$ is close to $0$, the bound is very close to $0$, and has almost no meaning. This is because I ignored $\omega^n$ at the last line. Do you have any idea to avoid it? Or do you have another idea?

[1] Prediction, Learning, and Games: http://www.ii.uni.wroc.pl/~lukstafi/pmwiki/uploads/AGT/Prediction_Learning_and_Games.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.