Exact bounds for tail probabilities of martingales with bounded differences
Articles
Dainius Dzindzalieta
Institute of Mathematics and Informatics
Published 2009-12-20
https://doi.org/10.15388/LMR.2009.73
PDF

Keywords

random walks
maximal inequalities
probability to visit an interval
large deviations
martingale
super-martingale
bounds for tail probabilities

How to Cite

Dzindzalieta, D. (2009) “Exact bounds for tail probabilities of martingales with bounded differences”, Lietuvos matematikos rinkinys, 50(proc. LMS), pp. 412–415. doi:10.15388/LMR.2009.73.

Abstract

We consider random walks, say Wn = {0, M1, . . ., Mn} of length n starting at 0 and based on a martingale sequence Mk = X1 + ··· + Xk with differences Xm. Assuming |Xk| \leq 1 we solve the isoperimetric problem

Bn(x) = supP\{Wn visits an interval [x,∞)\},  (1)

where sup is taken over all possible Wn. We describe random walks which maximize the probability in (1). We also extend the results to super-martingales.For martingales our results can be interpreted as a maximal
inequalities
P\{max 1\leq k\leq n Mk   \geq x\} \leq Bn(x).
The maximal inequality is optimal since the equality is achieved by martingales related to the maximizing random walks. To prove the result we introduce a general principle – maximal inequalities for (natural classes of) martingales are equivalent to (seemingly weaker) inequalities for tail probabilities, in our case
Bn(x) = supP{M\geq  x}.
Our methods are similar in spirit to a method used in [1], where a solution of an isoperimetric problem (1), for integer x is provided and to the method used in [4], where the isoperimetric problem of type (1) for conditionally symmetric bounded martingales was solved for all x ∈ R.

PDF

Downloads

Download data is not yet available.