Appendix A
We give here the expression of the covariance matrix C introduced in section "distribution of N = (N0, N1)". The sequence Y (of length n) is generated by an homogeneous, stationary and ergodic order m Markov model of parameter π and stationary distribution μ. We want to compute the covariance of the vector N of random frequencies of size m and m + 1 words.
For any word w (of size hw), we introduce the following notation for hw ≤ i ≤ n
I i  ( w ) = I { w   e n d  i n  p o s i t i o n  i }   = I { Y i − h w  + 1  i  = w }         ( 45 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaacqWGjbqsdaWgaaWcbaGaemyAaKgabeaakiabcIcaOiabdEha3jabcMcaPiabg2da9mrr1ngBPrwtHrhAYaqehuuDJXwAKbstHrhAGq1DVbacfaGae8hIWN0aaSbaaSqaaiabcUha7jabdEha3jabbccaGGqaaiab+vgaLjab+5gaUjab+rgaKjab+bcaGiab+LgaPjab+5gaUjab+bcaGiab+bhaWjab+9gaVjab+nhaZjab+LgaPjab+rha0jab+LgaPjab+9gaVjab+5gaUjab+bcaGiabdMgaPjabc2ha9bqabaGccqGH9aqpcqWFicFsdaWgaaWcbaGaei4EaSNaemywaK1aa0baaWqaaiabdMgaPjabgkHiTiabdIgaOnaaBaaabaGaem4DaChabeaacqGHRaWkcqaIXaqmaeaacqWGPbqAaaWccqGH9aqpcqWG3bWDcqGG9bqFaeqaaOGaaCzcaiaaxMaacqGGOaakcqaI0aancqaI1aqncqGGPaqkaaa@7BBF@
where Yij MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGzbqwdaqhaaWcbaGaemyAaKgabaGaemOAaOgaaaaa@30CC@ = Yi ... Yj for all i ≤ j. If hw ≥ m, we denote by
p ( w ) = μ ( w 1 m  ) Π ( w 1 m  , w m + 1   ) ... Π ( w h w  − m  h − 1   , w h  )       ( 46 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGWbaCcqGGOaakcqWG3bWDcqGGPaqkcqGH9aqpiiGacqWF8oqBcqGGOaakcqWG3bWDdaqhaaWcbaGaeGymaedabaGaemyBa0gaaOGaeiykaKIaeuiOdaLaeiikaGIaem4DaC3aa0baaSqaaiabigdaXaqaaiabd2gaTbaakiabcYcaSiabdEha3naaBaaaleaacqWGTbqBcqGHRaWkcqaIXaqmaeqaaOGaeiykaKIaeiOla4IaeiOla4IaeiOla4IaeuiOdaLaeiikaGIaem4DaC3aa0baaSqaaiabdIgaOnaaBaaameaacqWG3bWDaeqaaSGaeyOeI0IaemyBa0gabaGaemiAaGMaeyOeI0IaeGymaedaaOGaeiilaWIaem4DaC3aaSbaaSqaaiabdIgaObqabaGccqGGPaqkcaWLjaGaaCzcaiabcIcaOiabisda0iabiAda2iabcMcaPaaa@5F8B@
the probability to see one occurrence of w at a given position in the sequence. At last, if we consider another word v (of size hv = m) and if hw = m, we denote by
Π δ  ( v , w ) = ∑ x ∈ A δ    p ( v x w )         ( 47 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaacqqHGoaudaWgaaWcbaacciGae8hTdqgabeaakiabcIcaOiabdAha2jabcYcaSiabdEha3jabcMcaPiabg2da9maaqafabaGaemiCaaNaeiikaGIaemODayNaemiEaGNaem4DaCNaeiykaKcaleaacqWG4baEcqGHiiIZimaacqGFaeFqdaahaaadbeqaaiab=r7aKbaaaSqab0GaeyyeIuoakiaaxMaacaWLjaGaeiikaGIaeGinaqJaeG4naCJaeiykaKcaaa@556F@
the probability to see occurrences of v and w separated by a gap of length δ.
For any words v an w (to simplify, we suppose that hv ≥ hw) then, for all δ ∈ ℤ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaatuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab=rsiAbaa@3772@ and
max(hv, hw - δ) ≤ i ≤ min(n, n - δ) we have
E MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaatuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab=ri8fbaa@388C@ [Ii (v) Ii+δ (w)] = Dδ (v, w)     (48)
which do not depend on i.
It is therefore easy to show that
E [ N ( v ) N ( w ) ] = ∑ i = h v   n  ∑ δ = h w  − i  n − i   D δ  ( v , w )             ( 49  )     = ∑ δ = h w  − n  n − h v    N δ  D δ  ( v , w )     ( 50  )     = M ( v , w ) + O ( v , m )   ( 51  )        MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeGabaa9fuaabmqadiaaaeaatuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab=ri8fjabcUfaBHqabiab+5eaojabcIcaOiabdAha2jabcMcaPiab+5eaojabcIcaOiabdEha3jabcMcaPiabc2faDjabg2da9maaqahabaWaaabCaeaacqWGebardaWgaaWcbaacciGae0hTdqgabeaakiabcIcaOiabdAha2jabcYcaSiabdEha3jabcMcaPaWcbaGae0hTdqMaeyypa0JaemiAaG2aaSbaaWqaaiabdEha3bqabaWccqGHsislcqWGPbqAaeaacqWGUbGBcqGHsislcqWGPbqAa0GaeyyeIuoaaSqaaiabdMgaPjabg2da9iabdIgaOnaaBaaameaacqWG2bGDaeqaaaWcbaGaemOBa4ganiabggHiLdGccaWLjaGaaCzcaaqaamaabmaabaGaeGinaqJaeGyoaKdacaGLOaGaayzkaaaabaGaeyypa0ZaaabCaeaacqWGobGtdaWgaaWcbaGae0hTdqgabeaakiabdseaenaaBaaaleaacqqF0oazaeqaaOGaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKcaleaacqqF0oazcqGH9aqpcqWGObaAdaWgaaadbaGaem4DaChabeaaliabgkHiTiabd6gaUbqaaiabd6gaUjabgkHiTiabdIgaOnaaBaaameaacqWG2bGDaeqaaaqdcqGHris5aaGcbaWaaeWaaeaacqaI1aqncqaIWaamaiaawIcacaGLPaaaaeaacqGH9aqpcqGFnbqtcqGGOaakcqWG2bGDcqGGSaalcqWG3bWDcqGGPaqkcqGHRaWkcqGFpbWtcqGGOaakcqWG2bGDcqGGSaalcqWGTbqBcqGGPaqkaeaadaqadaqaaiabiwda1iabigdaXaGaayjkaiaawMcaaaaaaaa@9BD3@
where the main part (2n - hv - hw + 2 terms) is given by
M ( v , w ) = ∑ δ = h v   n − h w    N − δ   D − δ     ( v , w ) + ∑ δ = h w   n − h v    N δ  D δ    ( v , w )       ( 52 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFnbqtcqGGOaakcqWG2bGDcqGGSaalcqWG3bWDcqGGPaqkcqGH9aqpdaaeWbqaaiabd6eaonaaBaaaleaacqGHsisliiGacqGF0oazaeqaaOGaemiraq0aaSbaaSqaaiabgkHiTiab+r7aKbqabaaabaGae4hTdqMaeyypa0JaemiAaG2aaSbaaWqaaiabdAha2bqabaaaleaacqWGUbGBcqGHsislcqWGObaAdaWgaaadbaGaem4DaChabeaaa0GaeyyeIuoakiabcIcaOiabdAha2jabcYcaSiabdEha3jabcMcaPiabgUcaRmaaqahabaGaemOta40aaSbaaSqaaiab+r7aKbqabaGccqWGebardaWgaaWcbaGae4hTdqgabeaaaeaacqGF0oazcqGH9aqpcqWGObaAdaWgaaadbaGaem4DaChabeaaaSqaaiabd6gaUjabgkHiTiabdIgaOnaaBaaameaacqWG2bGDaeqaaaqdcqGHris5aOGaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKIaaCzcaiaaxMaacqGGOaakcqaI1aqncqaIYaGmcqGGPaqkaaa@6D1F@
and the overlapping part (hv + hw - 1 terms) by
O ( v , w ) = ∑ δ = − h v  + 1  h w  − 1   N δ  D δ  ( v , w )         ( 53 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFpbWtcqGGOaakcqWG2bGDcqGGSaalcqWG3bWDcqGGPaqkcqGH9aqpdaaeWbqaaiabd6eaonaaBaaaleaaiiGacqGF0oazaeqaaOGaemiraq0aaSbaaSqaaiab+r7aKbqabaGccqGGOaakcqWG2bGDcqGGSaalcqWG3bWDcqGGPaqkaSqaaiab+r7aKjabg2da9iabgkHiTiabdIgaOnaaBaaameaacqWG2bGDaeqaaSGaey4kaSIaeGymaedabaGaemiAaG2aaSbaaWqaaiabdEha3bqabaWccqGHsislcqaIXaqma0GaeyyeIuoakiaaxMaacaWLjaGaeiikaGIaeGynauJaeG4mamJaeiykaKcaaa@5444@
and with
N δ  = { n − h w  + 1 + δ   δ ∈ [ h w  − n , h w  − h v  [    n − h v  + 1   δ ∈ [ h w  − h v  , 0 ]    n − h v  + 1 − δ   δ ∈ ] 0 , n − h v  ]             ( 54 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGobGtdaWgaaWcbaacciGae8hTdqgabeaakiabg2da9maaceqabaqbaeaabmGaaaqaaiabd6gaUjabgkHiTiabdIgaOnaaBaaaleaacqWG3bWDaeqaaOGaey4kaSIaeGymaeJaey4kaSIae8hTdqgabaGae8hTdqMaeyicI4Saei4waSLaemiAaG2aaSbaaSqaaiabdEha3bqabaGccqGHsislcqWGUbGBcqGGSaalcqWGObaAdaWgaaWcbaGaem4DaChabeaakiabgkHiTiabdIgaOnaaBaaaleaacqWG2bGDaeqaaOGaei4waSfabaGaemOBa4MaeyOeI0IaemiAaG2aaSbaaSqaaiabdAha2bqabaGccqGHRaWkcqaIXaqmaeaacqWF0oazcqGHiiIZcqGGBbWwcqWGObaAdaWgaaWcbaGaem4DaChabeaakiabgkHiTiabdIgaOnaaBaaaleaacqWG2bGDaeqaaOGaeiilaWIaeGimaaJaeiyxa0fabaGaemOBa4MaeyOeI0IaemiAaG2aaSbaaSqaaiabdAha2bqabaGccqGHRaWkcqaIXaqmcqGHsislcqWF0oazaeaacqWF0oazcqGHiiIZcqGGDbqxcqaIWaamcqGGSaalcqWGUbGBcqGHsislcqWGObaAdaWgaaWcbaGaemODayhabeaakiabc2faDbaaaiaawUhaaiaaxMaacaWLjaGaeiikaGIaeGynauJaeGinaqJaeiykaKcaaa@7F57@
As we have
C(v, w) = M (v, w) + O (v, w) - E (v) E (w)     (55)
the problem is hence to compute M and O for all pairs of size m or m + 1 words. In order to simplify, we will just treat here the case of a pair of size m words (other cases can be derived from this special case).
For the main part we obtain
M ( v , w ) = ∑ δ = m  n − m   N − δ   μ ( w ) Π δ − m + 1   ( w , v )      + ∑ δ = m  n − m   N δ  μ ( v ) Π δ − m + 1   ( v , w )             ( 56 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaafaqadeGabaaabaacbeGae8xta0KaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKIaeyypa0ZaaabCaeaacqWGobGtdaWgaaWcbaGaeyOeI0ccciGae4hTdqgabeaakiab+X7aTjabcIcaOiabdEha3jabcMcaPiabfc6aqnaaBaaaleaacqGF0oazcqGHsislcqWGTbqBcqGHRaWkcqaIXaqmaeqaaOGaeiikaGIaem4DaCNaeiilaWIaemODayNaeiykaKcaleaacqGF0oazcqGH9aqpcqWGTbqBaeaacqWGUbGBcqGHsislcqWGTbqBa0GaeyyeIuoaaOqaaiabgUcaRmaaqahabaGaemOta40aaSbaaSqaaiab+r7aKbqabaGccqGF8oqBcqGGOaakcqWG2bGDcqGGPaqkcqqHGoaudaWgaaWcbaGae4hTdqMaeyOeI0IaemyBa0Maey4kaSIaeGymaedabeaakiabcIcaOiabdAha2jabcYcaSiabdEha3jabcMcaPaWcbaGae4hTdqMaeyypa0JaemyBa0gabaGaemOBa4MaeyOeI0IaemyBa0ganiabggHiLdaaaOGaaCzcaiaaxMaacqGGOaakcqaI1aqncqaI2aGncqGGPaqkaaa@78C7@
(2n - 2m + 2 terms). As Pk (v, w) quickly converges toward μ(w) when k grows (convergence speed is given by λk where λ is the magnitude of the second eigenvalue of the transition matrix Π). So there exists a rank r ≥ m such as
M ( v , w ) ≃ μ ( v ) μ ( w ) ∑ δ = r  n − m   ( N − δ   + N δ  )     + ∑ δ = m  r − 1   N − δ   μ ( w ) Π δ − m + 1     ( w , v )   + ∑ δ = m  r − 1   N δ  μ ( v ) Π δ − m + 1     ( v , w )       ( 57 )     MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqGabeqaaW8abaacbeGae8xta0KaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKIaeS4qISdcciGae4hVd0MaeiikaGIaemODayNaeiykaKIae4hVd0MaeiikaGIaem4DaCNaeiykaKYaaabCaeaacqGGOaakcqWGobGtdaWgaaWcbaGaeyOeI0Iae4hTdqgabeaakiabgUcaRiabd6eaonaaBaaaleaacqGF0oazaeqaaOGaeiykaKcaleaacqGF0oazcqGH9aqpcqWGYbGCaeaacqWGUbGBcqGHsislcqWGTbqBa0GaeyyeIuoaaOqaaiaaxMaacqGHRaWkdaaeWbqaaiabd6eaonaaBaaaleaacqGHsislcqGF0oazaeqaaOGae4hVd0MaeiikaGIaem4DaCNaeiykaKIaeuiOda1aaSbaaSqaaiab+r7aKjabgkHiTiabd2gaTjabgUcaRiabigdaXaqabaaabaGae4hTdqMaeyypa0JaemyBa0gabaGaemOCaiNaeyOeI0IaeGymaedaniabggHiLdGccqGGOaakcqWG3bWDcqGGSaalcqWG2bGDcqGGPaqkaeaacaWLjaGaey4kaSYaaabCaeaacqWGobGtdaWgaaWcbaGae4hTdqgabeaakiab+X7aTjabcIcaOiabdAha2jabcMcaPiabfc6aqnaaBaaaleaacqGF0oazcqGHsislcqWGTbqBcqGHRaWkcqaIXaqmaeqaaaqaaiab+r7aKjabg2da9iabd2gaTbqaaiabdkhaYjabgkHiTiabigdaXaqdcqGHris5aOGaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKIaaCzcaiaaxMaacqGGOaakcqaI1aqncqaI3aWncqGGPaqkaaaa@981D@
which has only 2r - 2m + 1 terms.
And for the overlapping part we get
O ( v , w ) = N 0  × μ ( v ) × I { v = w }     + ∑ δ = 1  m − 1   N − δ     × p ( w v m − δ + 1  m  ) × I { v 1 m − δ   = w 1 + δ  m   }      + ∑ δ = 1  m − 1   N δ  × p ( v w m − δ + 1  m  )   × I { v 1 + δ  m  = w 1 m − δ    }          ( 58 )     MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqGabeqaaaNabaacbeGae83ta8KaeiikaGIaemODayNaeiilaWIaem4DaCNaeiykaKIaeyypa0JaemOta40aaSbaaSqaaiabicdaWaqabaGccqGHxdaTiiGacqGF8oqBcqGGOaakcqWG2bGDcqGGPaqkcqGHxdaTtuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab9Hi8jnaaBaaaleaacqGG7bWEcqWG2bGDcqGH9aqpcqWG3bWDcqGG9bqFaeqaaaGcbaGaaCzcaiabgUcaRmaaqahabaGaemOta40aaSbaaSqaaiabgkHiTiab+r7aKbqabaaabaGae4hTdqMaeyypa0JaeGymaedabaGaemyBa0MaeyOeI0IaeGymaedaniabggHiLdGccqGHxdaTcqWGWbaCcqGGOaakcqWG3bWDcqWG2bGDdaqhaaWcbaGaemyBa0MaeyOeI0Iae4hTdqMaey4kaSIaeGymaedabaGaemyBa0gaaOGaeiykaKIaey41aqRae0hIWN0aaSbaaSqaamaacmqabaGaemODay3aa0baaWqaaiabigdaXaqaaiabd2gaTjabgkHiTiabes7aKbaaliabg2da9iabdEha3naaDaaameaacqaIXaqmcqGHRaWkcqGF0oazaeaacqWGTbqBaaaaliaawUhacaGL9baaaeqaaaGcbaGaaCzcaiabgUcaRmaaqahabaGaemOta40aaSbaaSqaaiab+r7aKbqabaGccqGHxdaTcqWGWbaCcqGGOaakcqWG2bGDcqWG3bWDdaqhaaWcbaGaemyBa0MaeyOeI0Iae4hTdqMaey4kaSIaeGymaedabaGaemyBa0gaaOGaeiykaKcaleaacqGF0oazcqGH9aqpcqaIXaqmaeaacqWGTbqBcqGHsislcqaIXaqma0GaeyyeIuoakiabgEna0kab9Hi8jnaaBaaaleaadaGadeqaaiabdAha2naaDaaameaacqaIXaqmcqGHRaWkcqGF0oazaeaacqWGTbqBaaWccqGH9aqpcqWG3bWDdaqhaaadbaGaeGymaedabaGaemyBa0MaeyOeI0Iae4hTdqgaaaWccaGL7bGaayzFaaaabeaakiaaxMaacaWLjaGaeiikaGIaeGynauJaeGioaGJaeiykaKcaaaa@BCF0@
which has 2m + 1 terms.
So the overall complexity for the computation of one term of C is hence O(r) where the value of r is directly connected to the magnitude λ of the second eigenvalue of the transition matrix.
In the particular case of an order one Markov model (m = 1), we give here the complete expressions of M and O.
For all a, b, c, d ∈ A MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFaeFqaaa@3821@, we have
M ( a , b ) ≃ ( n − r + 1 ) ( n − r ) μ ( a ) μ ( b )   + ∑ δ = 1  r − 1   ( n − δ ) ( μ ( b ) Π δ  ( b , a ) + μ ( a ) Π δ  ( a , b )  )        ( 59 )       MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqaabeqaaGqabiab=1eanjabcIcaOiabdggaHjabcYcaSiabdkgaIjabcMcaPiabloKi7iabcIcaOiabd6gaUjabgkHiTiabdkhaYjabgUcaRiabigdaXiabcMcaPiabcIcaOiabd6gaUjabgkHiTiabdkhaYjabcMcaPGGaciab+X7aTjabcIcaOiabdggaHjabcMcaPiab+X7aTjabcIcaOiabdkgaIjabcMcaPaqaaiabgUcaRmaaqahabaGaeiikaGIaemOBa4MaeyOeI0Iae4hTdqMaeiykaKYaaeWaaeaacqGF8oqBcqGGOaakcqWGIbGycqGGPaqkcqqHGoaudaahaaWcbeqaaiab+r7aKbaakiabcIcaOiabdkgaIjabcYcaSiabdggaHjabcMcaPiabgUcaRiab+X7aTjabcIcaOiabdggaHjabcMcaPiabfc6aqnaaCaaaleqabaGae4hTdqgaaOGaeiikaGIaemyyaeMaeiilaWIaemOyaiMaeiykaKcacaGLOaGaayzkaaGaaCzcaiaaxMaacqGGOaakcqaI1aqncqaI5aqocqGGPaqkaSqaaiab+r7aKjabg2da9iabigdaXaqaaiabdkhaYjabgkHiTiabigdaXaqdcqGHris5aaaaaa@7BAA@
O (a, b) = nμ(a) I MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaatuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab=Hi8jbaa@3894@{a = b}     (60)
M ( a b , c )  Π ( a , b )   ≃ ( n − r ) ( n − r − 1 ) μ ( a ) μ ( c )   + ∑ δ = 1  r − 1   ( n − δ − 1 ) ( μ ( c ) Π δ  ( c , a ) + μ ( a ) Π δ  ( b , c )  )        ( 61 )       MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqaabeqaamaalaaabaacbeGae8xta0KaeiikaGIaemyyaeMaemOyaiMaeiilaWIaem4yamMaeiykaKcabaGaeuiOdaLaeiikaGIaemyyaeMaeiilaWIaemOyaiMaeiykaKcaaiabloKi7iabcIcaOiabd6gaUjabgkHiTiabdkhaYjabcMcaPiabcIcaOiabd6gaUjabgkHiTiabdkhaYjabgkHiTiabigdaXiabcMcaPGGaciab+X7aTjabcIcaOiabdggaHjabcMcaPiab+X7aTjabcIcaOiabdogaJjabcMcaPaqaaiabgUcaRmaaqahabaGaeiikaGIaemOBa4MaeyOeI0Iae4hTdqMaeyOeI0IaeGymaeJaeiykaKYaaeWaaeaacqGF8oqBcqGGOaakcqWGJbWycqGGPaqkcqqHGoaudaahaaWcbeqaaiab+r7aKbaakiabcIcaOiabdogaJjabcYcaSiabdggaHjabcMcaPiabgUcaRiab+X7aTjabcIcaOiabdggaHjabcMcaPiabfc6aqnaaCaaaleqabaGae4hTdqgaaOGaeiikaGIaemOyaiMaeiilaWIaem4yamMaeiykaKcacaGLOaGaayzkaaGaaCzcaiaaxMaacqGGOaakcqaI2aGncqaIXaqmcqGGPaqkaSqaaiab+r7aKjabg2da9iabigdaXaqaaiabdkhaYjabgkHiTiabigdaXaqdcqGHris5aaaaaa@8595@
O ( a b , c )  Π ( a , b )   = ( n − 1 ) μ ( a ) ( I { a = c }   + I { b = c }   )       ( 62 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaWcaaqaaGqabiab=9eapjabcIcaOiabdggaHjabdkgaIjabcYcaSiabdogaJjabcMcaPaqaaiabfc6aqjabcIcaOiabdggaHjabcYcaSiabdkgaIjabcMcaPaaacqGH9aqpcqGGOaakcqWGUbGBcqGHsislcqaIXaqmcqGGPaqkiiGacqGF8oqBcqGGOaakcqWGHbqycqGGPaqkcqGGOaaktuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGabaiab9Hi8jnaaBaaaleaacqGG7bWEcqWGHbqycqGH9aqpcqWGJbWycqGG9bqFaeqaaOGaey4kaSIae0hIWN0aaSbaaSqaaiabcUha7jabdkgaIjabg2da9iabdogaJjabc2ha9bqabaGccqGGPaqkcaWLjaGaaCzcaiabcIcaOiabiAda2iabikdaYiabcMcaPaaa@690B@
M ( a b , c d )  Π ( a , b ) Π ( c , d )   ≃ ( n − r − 1 ) ( n − r − 2 ) μ ( a ) μ ( c )   + ∑ δ = 1  r − 1   ( n − δ − 2 ) ( μ ( c ) Π δ  ( d , a ) + μ ( a ) Π δ  ( b , c )  )        ( 63 )       MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqaabeqaamaalaaabaacbeGae8xta0KaeiikaGIaemyyaeMaemOyaiMaeiilaWIaem4yamMaemizaqMaeiykaKcabaGaeuiOdaLaeiikaGIaemyyaeMaeiilaWIaemOyaiMaeiykaKIaeuiOdaLaeiikaGIaem4yamMaeiilaWIaemizaqMaeiykaKcaaiabloKi7iabcIcaOiabd6gaUjabgkHiTiabdkhaYjabgkHiTiabigdaXiabcMcaPiabcIcaOiabd6gaUjabgkHiTiabdkhaYjabgkHiTiabikdaYiabcMcaPGGaciab+X7aTjabcIcaOiabdggaHjabcMcaPiab+X7aTjabcIcaOiabdogaJjabcMcaPaqaaiabgUcaRmaaqahabaGaeiikaGIaemOBa4MaeyOeI0Iae4hTdqMaeyOeI0IaeGOmaiJaeiykaKYaaeWaaeaacqGF8oqBcqGGOaakcqWGJbWycqGGPaqkcqqHGoaudaahaaWcbeqaaiab+r7aKbaakiabcIcaOiabdsgaKjabcYcaSiabdggaHjabcMcaPiabgUcaRiab+X7aTjabcIcaOiabdggaHjabcMcaPiabfc6aqnaaCaaaleqabaGae4hTdqgaaOGaeiikaGIaemOyaiMaeiilaWIaem4yamMaeiykaKcacaGLOaGaayzkaaGaaCzcaiaaxMaacqGGOaakcqaI2aGncqaIZaWmcqGGPaqkaSqaaiab+r7aKjabg2da9iabigdaXaqaaiabdkhaYjabgkHiTiabigdaXaqdcqGHris5aaaaaa@8F7D@
O ( a b , c d )  Π ( a , b )   = ( n − 1 ) μ ( a ) I { a b = c d }     + ( n − 2 ) Π ( c , d ) ( μ ( c ) I { a = d }   + μ ( a ) I { b = c }    )        ( 64 )     MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakqaabeqaamaalaaabaacbeGae83ta8KaeiikaGIaemyyaeMaemOyaiMaeiilaWIaem4yamMaemizaqMaeiykaKcabaGaeuiOdaLaeiikaGIaemyyaeMaeiilaWIaemOyaiMaeiykaKcaaiabg2da9iabcIcaOiabd6gaUjabgkHiTiabigdaXiabcMcaPGGaciab+X7aTjabcIcaOiabdggaHjabcMcaPmrr1ngBPrwtHrhAYaqeguuDJXwAKbstHrhAGq1DVbaceaGae0hIWN0aaSbaaSqaaiabcUha7jabdggaHjabdkgaIjabg2da9iabdogaJjabdsgaKjabc2ha9bqabaaakeaacqGHRaWkcqGGOaakcqWGUbGBcqGHsislcqaIYaGmcqGGPaqkcqqHGoaucqGGOaakcqWGJbWycqGGSaalcqWGKbazcqGGPaqkdaqadaqaaiab+X7aTjabcIcaOiabdogaJjabcMcaPiab9Hi8jnaaBaaaleaacqGG7bWEcqWGHbqycqGH9aqpcqWGKbazcqGG9bqFaeqaaOGaey4kaSIae4hVd0MaeiikaGIaemyyaeMaeiykaKIae0hIWN0aaSbaaSqaaiabcUha7jabdkgaIjabg2da9iabdogaJjabc2ha9bqabaaakiaawIcacaGLPaaacaWLjaGaaCzcaiabcIcaOiabiAda2iabisda0iabcMcaPaaaaa@8BDE@
With the example given in section "validation" we get for the expectation
E0t MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFfbqrdaqhaaWcbaGaeGimaadabaGaemiDaqhaaaaa@3051@ = [4615.4 5384.6]     (65)
and
E1t MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFfbqrdaqhaaWcbaGaeGymaedabaGaemiDaqhaaaaa@3053@ = [1384.5 3230.4 3230.4 2153.6]     (66)
The magnitude of the second eigenvalue of Π is λ = 0.3, then rank r = 19 give a relative error < 10 -10 and we get for the covariance
C 0 , 0   = [ 1338.28   − 1338.28    − 1338.28   1338.28      ]        ( 67 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFdbWqdaWgaaWcbaGaeGimaaJaeiilaWIaeGimaadabeaakiabg2da9maadmaabaqbaeqabiGaaaqaaiabigdaXiabiodaZiabiodaZiabiIda4iabc6caUiabikdaYiabiIda4aqaaiabgkHiTiabigdaXiabiodaZiabiodaZiabiIda4iabc6caUiabikdaYiabiIda4aqaaiabgkHiTiabigdaXiabiodaZiabiodaZiabiIda4iabc6caUiabikdaYiabiIda4aqaaiabigdaXiabiodaZiabiodaZiabiIda4iabc6caUiabikdaYiabiIda4aaaaiaawUfacaGLDbaacaWLjaGaaCzcaiabcIcaOiabiAda2iabiEda3iabcMcaPaaa@5529@
C 1 , 0   = [ 1146.9   191.2   191.2   − 1529.2    − 1146.9   − 191.2   − 191.2   1529.2      ]        ( 68 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFdbWqdaWgaaWcbaGaeGymaeJaeiilaWIaeGimaadabeaakiabg2da9maadmaabaqbaeqabiabaaaabaGaeGymaeJaeGymaeJaeGinaqJaeGOnayJaeiOla4IaeGyoaKdabaGaeGymaeJaeGyoaKJaeGymaeJaeiOla4IaeGOmaidabaGaeGymaeJaeGyoaKJaeGymaeJaeiOla4IaeGOmaidabaGaeyOeI0IaeGymaeJaeGynauJaeGOmaiJaeGyoaKJaeiOla4IaeGOmaidabaGaeyOeI0IaeGymaeJaeGymaeJaeGinaqJaeGOnayJaeiOla4IaeGyoaKdabaGaeyOeI0IaeGymaeJaeGyoaKJaeGymaeJaeiOla4IaeGOmaidabaGaeyOeI0IaeGymaeJaeGyoaKJaeGymaeJaeiOla4IaeGOmaidabaGaeGymaeJaeGynauJaeGOmaiJaeGyoaKJaeiOla4IaeGOmaidaaaGaay5waiaaw2faaiaaxMaacaWLjaGaeiikaGIaeGOnayJaeGioaGJaeiykaKcaaa@6605@
and
C 1 , 1   = [ 1536.8   − 390.0   − 390.0   − 756.9    − 390.0   581.2   581.0   − 772.2    − 390.0   581.0   581.2   − 772.2    − 756.9   − 772.2   − 772.2   2301.4      ]        ( 69 )   MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaaieqacqWFdbWqdaWgaaWcbaGaeGymaeJaeiilaWIaeGymaedabeaakiabg2da9maadmaabaqbaeqabqabaaaaaeaacqaIXaqmcqaI1aqncqaIZaWmcqaI2aGncqGGUaGlcqaI4aaoaeaacqGHsislcqaIZaWmcqaI5aqocqaIWaamcqGGUaGlcqaIWaamaeaacqGHsislcqaIZaWmcqaI5aqocqaIWaamcqGGUaGlcqaIWaamaeaacqGHsislcqaI3aWncqaI1aqncqaI2aGncqGGUaGlcqaI5aqoaeaacqGHsislcqaIZaWmcqaI5aqocqaIWaamcqGGUaGlcqaIWaamaeaacqaI1aqncqaI4aaocqaIXaqmcqGGUaGlcqaIYaGmaeaacqaI1aqncqaI4aaocqaIXaqmcqGGUaGlcqaIWaamaeaacqGHsislcqaI3aWncqaI3aWncqaIYaGmcqGGUaGlcqaIYaGmaeaacqGHsislcqaIZaWmcqaI5aqocqaIWaamcqGGUaGlcqaIWaamaeaacqaI1aqncqaI4aaocqaIXaqmcqGGUaGlcqaIWaamaeaacqaI1aqncqaI4aaocqaIXaqmcqGGUaGlcqaIYaGmaeaacqGHsislcqaI3aWncqaI3aWncqaIYaGmcqGGUaGlcqaIYaGmaeaacqGHsislcqaI3aWncqaI1aqncqaI2aGncqGGUaGlcqaI5aqoaeaacqGHsislcqaI3aWncqaI3aWncqaIYaGmcqGGUaGlcqaIYaGmaeaacqGHsislcqaI3aWncqaI3aWncqaIYaGmcqGGUaGlcqaIYaGmaeaacqaIYaGmcqaIZaWmcqaIWaamcqaIXaqmcqGGUaGlcqaI0aanaaaacaGLBbGaayzxaaGaaCzcaiaaxMaacqGGOaakcqaI2aGncqaI5aqocqGGPaqkaaa@8FB3@