Speaker : Professor James Fu (University of Manitoba) Finite Markov Chain Imbedding Approximation 2012-12-03 (Mon) 14:10 - Seminar Room 617, Institute of Mathematics (NTU Campus) Let $X_{n}\left ( \wedge \right )$ be the number of non-overlapping occurrences of a simple pattern $\wedge$ in a sequence of independent and identically distributed [i.i.d.] multi-state 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 multi-state 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.