Abstract:
 Let $X_{n}\left ( \wedge \right )$ be the number of nonoverlapping occurrences of a simple pattern $\wedge $ in a sequence of independent and identically distributed [i.i.d.] multistate trials. For fixed $k$, the exact tail probability $\mathbb{P}\left \{ X_{n}\left ( \wedge \right )< k \right \}$ is diffcult to compute and tends to 0 exponentially as $n \to \infty $. In this paper, we use the
finite Markov chain imbedding technique and standard matrix theory results to obtain an approximation for this tail probability. The result is extended to compound patterns, Markov dependent multistate trials and overlapping occurrences of $\wedge $. Numerical comparisons with the normal approximation are provided. Results indicate that the proposed approximations perform very well and do significantly better than the normal approximation in many cases.
