Summary: The distribution of \(X_{n}(\Lambda )\), the number of occurrences of a specified pattern \(\Lambda \) of length \(\ell \) in a sequence of multi-state trials \(\{X_i\}^n_{i=1}\), is of vital importance in statistical inference and applied probability. In [Adv. Appl. Probab. 41, No. 1, 292–308 (2009; Zbl 1166.60008)], the first two authors introduced a finite Markov chain embedding (FMCI) approximation for the left-hand tail probability \(\mathbb P\{X_{n}(\Lambda )=k\}\). They show that, for fixed \(k\), the ratio between the exact and approximate probabilities tend to one as \(n\to \infty \) 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 \(\mathbb P\{X_{n}(\Lambda )\geq n/\ell - x\}\), and large deviation probabilities of the form \(\mathbb P\{X_{n}(\Lambda )\geq \mathbb EX_{n}(\Lambda )+nx\}\). Theoretical and numerical results show that the proposed approximations perform very well.