Exact bounds for tail probabilities of martingales with bounded differences

Abstract

We consider random walks, say W_n = {0, M₁, . . ., M_n} of length n starting at 0 and based on a martingale sequence M_k = X₁ + ··· + X_k with differences X_m. Assuming |X_k| \leq 1 we solve the isoperimetric problem

B_n(x) = supP\{W_n 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} M_k   \geq x\} \leq B_n(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
B_n(x) = supP{M_n  \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.