I have a sequence of random variables $X_1, X_2, \ldots X_N$ such that $|X_i| \leq R \ \forall \ i $, satisfying $$|E[X_n|X_1,X_2,\ldots X_{n-1}]| \leq |X_{n-1}|, $$

Can I construct a sub/super-martingale sequence from this? Intuitively, it makes sense that the random variables are constrained to be not from far the previous one in absolute/distance sense. But can I view this as some sort of martingale or perhaps construct a sequence (or sequences) which satisfy the definition of (sub/super)martingale(s)?

  • 2
    $\begingroup$ How do such sequences arise? $\endgroup$ – Iosif Pinelis Apr 24 '18 at 14:29
  • 3
    $\begingroup$ Suppose $Y_i$ is an estimator for $Y$. Define $X_i = Y_i - Y$. I have an iterative randomized algorithm which estimates $Y_i$ and $i^{th}$ iteration and ensures $$|E[X_n|X_1,X_2,\ldots X_{n-1}]| \leq \alpha |X_{n-1}|, \alpha < 1$$. I want to show that this is some standard stochastic process (like martinagale) and apply concentration tools to show that $X_n$ goes to $0$ with high probability. $\endgroup$ – Enayat Apr 28 '18 at 19:43
  • $\begingroup$ I think this is a good question, but I don't have a good answer to it at this point. $\endgroup$ – Iosif Pinelis Apr 29 '18 at 3:28
  • $\begingroup$ Just a minor comment; it is easy to show that this inequality does not imply a concentration (or convergence for that matter); if you have $X_n$s to be iid mean 0, this inequality is always trivially true... $\endgroup$ – E-A Oct 31 '18 at 23:59

It may actually not be possible. I do not have a proof but trying to use Jensen's inequality is hopeless for example.

If you aim at using Jensen's inequality, you need an even and concave function $f$ increasing on $\mathbb R_+$ to define a supermartingale. Then by Jensen's inequality: $$E[f(X_n)|X_1,\ldots,X_{n-1}]\leq f(E[X_n|X_1,\ldots,X_{n-1}])\leq f(X_{n-1}).$$

To be more precise, since your inequality does not depend on the sign of your random variable, you cannot use anything else than even functions (you don't have an inequality for $X_{n-1}$). Then using a concave and increasing function on $\mathbb R_+$ allows you to use Jensen's inequality in the right order. A convex and decreasing function would lead to a submartingale.

Unfortunately I don't think such functions exist. The issue is in zero. An even function increasing on $\mathbb R_+$ cannot be concave on $\mathbb R$. Indeed if $f$ is even and concave on $\mathbb R_+$ for any $x>0$, $$f(0)=f(-\frac12 x+\frac12 x)\geq \frac12 f(-x)+ \frac12 f(x)=f(x).$$ Hence, if $f$ is monotonous on $\mathbb R_+$, it is non increasing.

| cite | improve this answer | |

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.