1

In AI book by Norvig and Russell ergodic Markov Chains are defined as follows:

  1. Every state is reachable from every other.
  2. There are no strictly periodic cycles in it.

Can someone explain what is strictly periodic cycle or give any reference?

Evgenii.Balai
  • 299
  • 1
    Two reasons to forget this definition: first, there is no way to distinguish between a "strictly periodic cycle" and a "cycle"; second, aperiodic chains can have cycles, lots of them, only one asks that their lengthes are not all multiples of a same integer $\gt1$. – Did Aug 21 '13 at 11:12
  • So, basically, we can interpret the second condition as "the chain is aperiodic". While it can have cycles, it cannot have strictly periodic cycles, i.e, cycles which only allow to return to the same state after some multiples of an integer >1. Strictly periodic cycle here is some abstract notion coming from a combination of real cycles in the chain, equal to the GCD of all the cycles covering the state. – Evgenii.Balai Aug 22 '13 at 04:16

1 Answers1

1

After some reading on wikipedia I believe what they mean is that for any state $i$ and time $0$, the times $t$ where you can reach $i$ again is not limited to a multiple of any integer greater than $1$. For instance, a random walk is periodic with period $2$ (you cannot come back to where you started after an odd number of moves; it has to be even).

In contrast, say we have a normal 1-D random walk (infinite or finite), but with the single change that if the walker is on square $100$, he can also choose to stand still in addition to moving left or right. Then it's not periodic, since there's a positive probability that he'll be back at the origin at the odd time $201$, even though up until that point it has seemed periodic.

This is more an account of the wikipedia definition than it addresses your concern regarding the word strictly, but I hope it helps you some part along the way.

Arthur
  • 199,419
  • Thank you. So, we can say that a markov chain has a strictly periodic cycle if there is a state i which can be reached again only after a number of steps which is a multiple of some number K>1. Of course just having some cycles is not enough for this condition. For example, if there are two cycles with lengths L1,L2 such that gcd(L1,L2)==1 going over some state S, we can always find some numbers K1 and K2, such that L1K1+L2K2=F for any number F>L1L2 (using extended Euclidean algorithm), which means we can return to the state S after arbitrary number of steps F>L1L2. – Evgenii.Balai Aug 22 '13 at 04:24
  • @iensen Yes, if there are two such "weak" cycles ("Weak" as in you can break out of them, but it's not necessarily very likely), we can alwas find such $K_1$ and $K_2$, provided any state is reachable from any other state, which of course is the other condition for being ergodic. – Arthur Aug 22 '13 at 06:47