Exact bounds for tail probabilities of martingales with bounded differences

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{Mn \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.

Keywords

• random walks
• maximal inequalities
• probability to visit an interval
• large deviations
• martingale
• super-martingale