Q:

Finding the period in a Markov Chains related situation.

Let there be two vases with total 4 balls in them. At every step a ball is chosen with a uniform probability to every ball, and is put in the other vase. Let us consider the number of balls in vase $a$ as the possible states. What is the period of the chain? 
What I did is: There are five state that I will denote as $s_0,s_1,s_2,s_3,s_4$, $s_i$=$i$ balls in vase a. I can go from $s_i$ to $s_{i+1}$ or $s_{i-1}$(if $i\ne 0$). I can't however go from $s_{i}$ to $s_{i+k}$ or $s_{i-k}$ if $k>1$. The shortest orbit number of steps from one state to itself is 2. Therefore, I have to check if there are orbits with odd number of steps. I don't know how to show that. Another thing: I have to take gcd of the all the orbits lengths, but is there another condition required for this gcd to actually be the period? Like, a connection between any pair of states? I would appreciate your help.  

A:

If you draw the graphical representation of this Markov chain, you get $s_0 \leftrightarrow s_1 \leftrightarrow s_2 \leftrightarrow s_3 \leftrightarrow s_4$. This is a bipartite graph, since there is no possible transition within $s_0, s_2, s_4$ or $s_1, s_3$ (including e.g. $s_1 \rightarrow s_1$).
Consequently, the period of the chain is 2.

