Saddlepoint approximations and nonlinear boundary crossing probabilities of Markov random walks

Saddlepoint approximations are developed for Markov random walks Sn and are used to evaluate the probability that (j.i)g((Sj.Si)/(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. We make use of this boundary crossing probability 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. Combining 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 minorization conditions.