Approximating the extreme right-hand tail probability for the distribution of the number of patterns in a sequence of multi-state trials

The distribution of X n ( Λ ) , the number of occurrences of a specified pattern Λ of length ℓ in a sequence of multi-state trials { X i } i = 1 n , is of vital importance in statistical inference and applied probability. Fu and Johnson [2009. Approximate probabilities for runs and patterns in i.i.d. and Markov dependent multi-state trials. Advances in Applied Probability 41(1), 292–308] introduced a finite Markov chain imbedding (FMCI) approximation for the left-hand tail probability P { X n ( Λ ) = k } . They show that, for fixed k, the ratio between the exact and approximate probabilities tend to one as n → ∞ and also show that the FMCI approximation can perform much better than normal or Poisson approximations. However, if k is a function of n, and right-hand tail probabilities are of interest, then the normal and Poisson approximations perform extremely poorly. The performance of the FMCI approximation also degrades in this region. In this paper we examine approximations for extreme right-hand tail probabilities, such as P { X n ( Λ ) ≥ n / ℓ − x } , and large deviation probabilities of the form P { X n ( Λ ) ≥ E X n ( Λ ) + nx } . Theoretical and numerical results show that the proposed approximations perform very well.