4.3 FMCI
Once a DFA and the corresponding matrices P and Q have been built, it is easy to get a FMCI allowing to compute the p-values we are looking for.
Let us consider
where Yj is the sequence of vertexes, Nj is the number of pattern occurrences in the sequence Y1...Yj (or X = X1...Xj as it is the same), where f is the final (absorbing state) and where a ∈ ℕ is the observed number of occurrences Nobs if the pattern is over-represented and Nobs + 1 if it is under-represented.
The transition matrix of the Markov chain Z is then given by:
where for all size L blocks i, j we have
with ΣQ, the column vector resulting from the sum of Q.
By plugin the structure of R and v in the corollaries 2 and 3 we get the following recurrences:
Proposition 6. For all n ≥ 1 and 1 ≤ i ≤ k we have
where for x = u or v we have ∀j ≥ 0 the following size L block decomposition:  and we have the recurrence relations:
with u0 = (1...1)' and v0 = v.