The discrete Gronwall's inequality states that if $x_n$ and and $u_n$ are non-negative sequences such that
$$ x_{n+1}\le a+\sum_{k=0}^n u_k x_k$$ then $$x_n\le a\prod_{k=0}^{n-1} (1+u_k)$$ (It can be shown using a simple induction as in https://math.stackexchange.com/questions/325565/gronwalls-lemma-discrete-version)

For the analysis of a random process, I came with an inequality that is similar to the one above but with a conditional expectation instead of an almost-sure inequality.

More precisely, let $X_n$ and $U_n$ be two discrete time stochastic processes adapted to a filtration $F_n$ such that $X_n>0$, $U_n\in(0,1)$, and $$ E[X_{n+1} | F_n] \le a - \sum_{k=0}^n U_k X_k $$ Let $T$ be a stopping time that is almost surely bounded. I am wondering if the following inequality holds: $$E[X_T]\le a E[\prod_{k=0}^{T-1}(1-U_k)]$$

Is it a known result? I have the impression that the induction used in the deterministic case does not work. If it helps, I can assume that $U_k$ is $F_{k-1}$ measurable for all $k$.


I just realized that the assertion that I was trying to prove is false because of the minus sign. In this case, it is not true even for deterministic sequences.

If I replace the minus with a plus : $$E[X_{n+1}|F_n]\le a+\sum_{k=0}^nU_kX_k$$ then the proof used in https://arxiv.org/pdf/1601.07503v1.pdf can be adapted to show that $$ E\left[\frac{X_T}{\prod_{k=0}^{T-1}(1+U_k)}\right] \le a $$ (the idea of the proof is to set $M_{n+1}=X_{n+1}-E[X_{n+1}|F_n]$ which is a martingale difference sequence. Then following https://arxiv.org/pdf/1601.07503v1.pdf, one obtain Equation (9) of https://arxiv.org/pdf/1601.07503v1.pdf with a $L_n$ that is martingale difference sequence). I will try to provide more details later.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.