Saddlepoint approximations and nonlinear boundary crossing probabilities of Markov random walks. (English) Zbl 1029.60058

The authors present saddlepoint approximations for Markov random walks \(S_n\) which are used to evaluate the probability that \((j-i)g((S_j -S_i)/(j-i))\) exceeds a threshold value for certain sets of \((i,j)\). The special case \(g(x)=x\) reduces to the usual scan statistic in change-point detection problems, and many generalized likelihood ratio detection schemes are also of this form with suitably chosen \(g\). This boudary crossing probability is used to derive both the asymptotic Gumbel-type distribution of scan statistics and the asymptotic exponential distribution of the waiting time to false alarm in sequential change-point detection. Combinig these saddlepoint approximations with truncation arguments and geometric integration theory also yields asymptotic formulas for other nonlinear boundary crossing probabilities of Markov random walks satisfying certain conditions.


60J05 Discrete-time Markov processes on general state spaces
60F10 Large deviations
60G60 Random fields
60F05 Central limit and other weak theorems
60G40 Stopping times; optimal stopping problems; gambling theory
Full Text: DOI


[1] ARNDT, K. (1980). Asy mptotic properties of the distribution of the supremum of a random walk on a Markov chain. Theory Probab. Appl. 25 309-324. · Zbl 0456.60072
[2] BHATTACHARy A, R. N. and RANGA RAO, R.(1976). Normal Approximations and Asy mptotic Expansions. Wiley, New York.
[3] BOROVKOV, A. A. and ROGOZIN, B. A. (1965). On the multidimensional central limit theorem. Theory Probab. Appl. 10 55-62. · Zbl 0139.35206
[4] CHAN, H. P. and LAI, T. L. (2000). Asy mptotic approximations for error probabilities of sequential or fixed sample size tests in exponential families. Ann. Statist. 28 1638-1669. · Zbl 1105.62367
[5] CHAN, H. P. and LAI, T. L. (2002). Boundary crossing probabilities for scan statistics and their applications to change-point detection. Methodol. Comput. Appl. Probab. · Zbl 1037.60021
[6] DANIELS, H. E. (1954). Saddlepoint approximation in statistics. Ann. Math. Statist. 25 631-650. · Zbl 0058.35404
[7] DE ACOSTA, A. and NEY, P. (1998). Large deviation lower bounds for arbitrary additive functionals of a Markov chain. Ann. Probab. 26 1660-1682. · Zbl 0936.60022
[8] DINWOODIE, I. H. (1993). Identifying a large deviation rate function. Ann. Probab. 21 216-231. · Zbl 0777.60024
[9] FELLER, W. (1971). An Introduction to Probability Theory and Its Applications 2, 2nd ed. Wiley, New York. · Zbl 0219.60003
[10] GRAY, A. (1990). Tubes. Wesley, New York. · Zbl 0692.53001
[11] HIRSCH, M. (1976). Differential Topology. Springer, New York. · Zbl 0356.57001
[12] HÖGLUND, T. (1974). Central limit theorems and statistical inference for finite Markov chains. Z. Wahrsch. Verw. Gebiete 29 123-151. · Zbl 0283.60069
[13] HÖGLUND, T. (1991). The ruin problem for finite Markov chains. Ann. Probab. 19 1298-1310. · Zbl 0744.60083
[14] IGLEHART, D. L. (1972). Extreme values in the GI/G/1 queue. Ann. Math. Statist. 43 627-635. · Zbl 0238.60072
[15] ILTIS, M. (1995). Sharp asy mptotics of large deviations in Rd. J. Theoretical Probab. 8 501-524. · Zbl 0831.60042
[16] ISCOE, I., NEY, P. and NUMMELIN, E. (1985). Large deviations of uniformly recurrent Markov additive processes. Adv. in Appl. Math. 6 373-412. · Zbl 0602.60034
[17] JENSEN, J. L. (1991). Saddlepoint expansions for sums of Markov dependent variables on a continuous state space. Probab. Theory Related Fields 89 181-199. · Zbl 0723.60019
[18] JENSEN, J. L. (1995). Saddlepoint Approximations. Oxford Univ. Press. · Zbl 1274.62008
[19] KARLIN, S., DEMBO, A. and KAWABATA, T. (1990). Statistical composition of high scoring segments from molecular sequences. Ann. Statist. 18 571-581. · Zbl 0711.92013
[20] MEy N, S. P. and TWEEDIE, R. L. (1993). Markov Chains and Stochastic Stability. Springer, New York. · Zbl 0925.60001
[21] NEY, P. and NUMMELIN, E. (1987). Markov additive processes. I. Eigenvalues properties and limit theorems, and II. Large deviations. Ann. Probab. 15 561-609. · Zbl 0625.60027
[22] PITMAN, J. W. (1975). An identity for stopping times of a Markov process. In Studies in Probability and Statistics (E. J. Williams, ed.) 41-57. North-Holland, Amsterdam. · Zbl 0353.60043
[23] SIEGMUND, D. (1988). Approximate tail probabilities for the maxima of some random fields. Ann. Probab. 16 487-501. · Zbl 0646.60032
[24] SIEGMUND, D. and VENTRAKAMAN, E. (1995). Using the generalized likelihood ratio statistics for sequential detection of a change-point. Ann. Statist. 23 255-271. · Zbl 0821.62044
[25] STONE, C. (1965). Local limit theorem for nonlattice multidimensional distribution functions. Ann. Math. Statist. 36 546-551. · Zbl 0135.19204
[26] STANFORD, CALIFORNIA 94305 E-MAIL: lait@stat.stanford.edu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.