Let \(X_ j,j\geq 1\), be i.i.d. random variables with distribution F, \(S_ n=X_ 1+...+X_ n\) (random walk), \(\tau_ a=\min \{n:\) \(S_ n>a\}\) (first passage time). Let F be a non-lattice probability distribution with mean \(\mu >0\) (positive drift) and variance \(\sigma^ 2<\infty.\)
Theorem 1. Let \(n_ 0(u,a)=[a\mu^{-1}+u\sigma \mu^{- 3/2}a^{{1/2}}]\), where \([\cdot]\) denotes the greatest integer; then \[ P(\tau_ a=n_ 0(u,a))\sim \exp \{-u^ 2/2\}\sigma^{- 1}\mu^{3/2}(2\pi a)^{-1/2}=:\phi (u;\mu,\sigma,a), \]
\[ P(\tau_ a=n_ 0(u,a);S_{\tau_ a}-a\leq x)\sim (\int^{x}_{0}P(S_{\tau_ 0}>y)dy)(ES_{\tau_ 0})^{-1}\phi (u;\mu,\sigma,a) \] as \(a\to \infty\). These relations are valid uniformly for x bounded away from 0 and u in any compact subset of \({\mathbb{R}}\). Theorems of the same type are proved for vector-valued walks (values of \(X_ j\) belong to the additive group \(G=\oplus^{p}_{i=1}G_ i\) where either \(G_ i={\mathbb{Z}}\) or \(G_ i={\mathbb{R}})\) and Markov random walks.
Suppose now that F has a finite moment-generating function in some open interval J, \(0\in J\). The distribution F is then imbedded in the exponential family \(\{F_{\theta}:\) \(\theta\in J\}\) where \(F_{\theta}(dx)=\exp \{\theta x-\psi (\theta)\}F_ 0(dx)\), \(F_ 0=F\), \(\phi (\theta)=\log \int_{{\mathbb{R}}}\exp \{\theta x\}F_ 0(dx)\). Let \(\mu_{\theta}\) and \(\sigma^ 2_{\theta}\) be the mean and variance of \(F_{\theta}\), respectively. For non-lattice distributions \(F_ 0\) asymptotic evaluations (a\(\to \infty)\) are given for \(P_ 0(\tau_ a\leq a\mu^{-1}_{\theta})\) if \(\theta >0\), \(\theta\in J\), \(\psi (\theta)>0\), and for \(P_ 0(a\mu_{\theta}^{-1}<\tau_ a<\infty)\) if \(\theta\) is in the interior of J, \(\mu_{\theta}>0\), \(\psi(\theta)<0\). These results may be interpreted as a large deviation theorem for the time of first passage to a linear boundary.
The same is done for random walks with increments depending on the state of a finite Markov chain. Let \(S_ n\) be random walk with \(\mu >0\), \(Z_ n=S_ n+\xi_ n\) (perturbed random walk), and \(T_ a=\min \{n\geq m(a):\) \(Z_ n>a\}\), where \(\xi_ n\) is independent of \({\mathcal F}(X_{n+1}\), \(X_{n+2},...)\) and m(a) is an integer, \(\overline{\lim}_{n\to \infty}\) \(m(a)/a<\mu^{-1}\). Under some further conditions a full analogue of Th. 1 is proved for \(T_ a\) and \(S_{T_ a}\)-a (Theorem 7). Th. 7 may be used to derive large-deviation results for first passage times to curved boundaries. As an example of applications in sequential analysis the type II error probabilities for the repeated generalized likelihood ratio procedure for testing a simple hypothesis against all alternatives in a one-dimensional exponential family are calculated. The characteristic feature of the work is that no factorization identities are used.