 |
|
|
| | | | | |
|
|
|
|
|
Exponential inequalities for self-normalized processes with applications
|
Victor H de la Peņa, Columbia University
Guodong Pang, Columbia University
|
Abstract
We prove the following exponential inequality for a pair of random variables $(A,B)$ with $B >0$ satisfying the textit{canonical assumption}, $E[exp(lambda A - frac{lambda^2}{2} B^2)] leq 1$ for $lambda in RR$,
begin{equation*}
Pleft( frac{|A|}{sqrt{ frac{2q-1}{q} left(B^2+ (E[|A|^p])^{2/p} right) }} geq x right) leq left(frac{q}{2q-1} right)^{frac{q}{2q-1}} x^{-frac{q}{2q-1}} e^{-x^2/2}
end{equation*}
for $x>0$,
where $1/p+ 1/q =1$ and $pgeq1$. Applying this inequality, we obtain exponential bounds for the tail probabilities for self-normalized martingale difference sequences. We propose a method of hypothesis testing for the $L^p$-norm $(p geq 1)$ of $A$ (in particular, martingales) and some stopping times. We apply this inequality to the stochastic TSP in $[0,1]^d$ ($dgeq 2$), connected to the CLT.
|
Full text: PDF
Pages: 372-381
Published on: September 8, 2009
|
Bibliography
-
B. Bercu and A. Touati.
Exponential inequalities for self-normalized martingales with applications.
Ann. Appl. Probab. (2008), 18, 1848--1869.
MR2462551
-
N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus.
The random link approximation for the Euclidean Traveling Salesman Problem.
Journal de Physique I. (1997), 7, 117--136.
-
V.H. de la Pe~{n}a.
A general class of exponential inequalities for martingales and ratios.
Ann. Probab. (1999), 27, 537--564.
MR1681153 (2000c:60020)
-
V.H. de la Pe~{n}a, M.J. Klass and T.L. Lai.
Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws.
Ann. Probab.. (2004), Vol. 32, No.3A, 1902--1933.
MR2073181 (2005g:60035)
-
V.H. de la Pe~{n}a, M.J. Klass and T.L. Lai.
Pseudo-maximization and self-normalized processes.
Probability Surveys . (2007), Vol. 4,172--192.
MR2368950 (2009b:60061)
-
V.H. de la Pe~{n}a, T.L. Lai and Q.M. Shao.
Self-Normalized Processes: Limit Theory and Statistical Applications.
Springer. (2009).
MR2488094
-
V. Egorov.
On the Growth Rate of Moments of Random Sums.
{em Preprint. } (1998).
-
E. Gin{'e}, F. G{"o}tze and D. Mason.
When is the Student $t$-statistic asymptotically standard normal?
Ann. Probab. (1997), 25, 1514--1531.
MR1457629 (98j:60033)
-
B. Efron.
Student's $t$-test under symmetry conditions.
J. Amer. Statist. Assoc. (1969), 64, 1278--1302.
MR1121940 (92h:60127)
-
B.F. Logan, C.L. Mallows, S.O. Rice and L.A. Shepp.
Limit Distributions of Self-Normalized Sums.
Ann. Probab. (1973), 1, 788--809.
MR0362449 (50 #14890)
-
W.T. Rhee and M. Talagrand.
Martingale inequalities and NP-complete problems.
Mathematics of Operations Research. (1987), 12, 177--181.
MR0882849 (88j:68071)
-
W.T. Rhee and M. Talagrand.
Martingale inequalities, interpolation and NP-complete problems.
Mathematics of Operations Research. (1989a), 13, 91--96.
MR0984560 (89m:60104)
-
W.T. Rhee and M. Talagrand.
A sharp deviation inequality for the stochastic Traveling Salesman Problem.
Ann. Probab. (1989b), 17, 1--8.
MR0972767 (89m:60065)
-
J.M. Steele.
Complete convergence of short paths and Karp's algorithm for the TSP.
Mathematics of Operations Research. (1981), 6, 374--378.
MR0629637 (82i:90040)
-
J.M. Steele.
Probability Theory and Combinatorial Optimization. CBMS-NSF regional conference series in applied mathematics. (1997).
MR1422018 (99d:60002)
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context