# Proving that given Markov chain is homogeneous. Find state space and transition matrix

Let $$X_i$$ be the results of a consecutive throws of a die. Let $$Z_n=3(X_1^2+\cdots+X_n^2) \bmod 5$$. Show that the sequence $${\{Z_n \mid n\geq1\}}$$ is a homogeneous Markov Chain. Find a state space and a state-trasition matrix.

(Easier version): $$Z_n=X_1^2+\cdots+X_n^2 \mod 5$$.

I know the Markov chain property which is

$$P(X_n=s \mid X_0=x_0,\ldots,X_{n-1}=x_{n-1}) = P(X_n=s\mid X_{n-1} = x_{n-1})$$ and then the Markov chain is homogeneous, when

$$P(X_{n+1}=j\mid X_n=i)=P(X_1=j\mid X_0=i)$$

We know that $$X_1,\ldots,X_n$$ are independent so

$$P(X_n=s \mid X_0=x_0,\ldots,X_{n-1}=x_{n-1})=P(X_n=s)$$ and $$P(X_n=s\mid X_{n-1}=x_{n-1})=P(X_n=s)$$ hence $$P(X_{n+1}=j)=P(X_1=j)$$, but from this point I don't know how to continue.

Any help will be much appreciated.

• First hint: do you know what you need to prove? (I'm slightly worried that you seeem t o be investigating properties of $\{X_n\mid n\geq 1\}$ while the question is about properties of $\{Z_n\mid n\geq 1\}$) – Juho Kokkala Jan 11 at 16:50
• I know that a question is about $Z_n$, but I was trying to focus on more basic problem, so that I could transfer this to more complicated one which is my main problem. But you are right, I don't fully understand my exercise. – MacAbra Jan 11 at 16:54
• So, when you are supposed to show that $Z_1,\ldots,Z_n$ is a Markov chain, you are supposed to show that $P(Z$... (continue the expression)? – Juho Kokkala Jan 11 at 16:57
• $P(Z_4=1|Z_4=0)=P(3(X_1^2+...+X_4^2) \mod 5 =1 | 3(X_1^2+...+X_3^2) \mod 5 =0)=$ (can I use now the fact that $X_i$ are independent?) $=P(3(X_1^2+...+X_4^2) \mod 5 =1)=..$ – MacAbra Jan 11 at 17:20
• It looks like you're on the right track. You might want to begin by characterizing the distribution of $Y_n=3X_n^2 \mod 5.$ A simple tabulation shows that $0$ appears with chance $1/6,$ $2$ appears with chance $1/3,$ and $3$ appears with chance $1/2.$ Thus, $Z_n$ is just the cumulative sum of the $Y_n$ (modulo $5$). – whuber Jan 11 at 17:31

### The state space

The $$Z_n$$ are all numbers modulo $$5.$$ They form the set $$\mathbb{Z}/5\mathbb{Z} = \{0,\pm 1,\pm 2\}.$$ Therefore the state space (which is the set of all possible values any $$Z_n$$ can attain) must be a subset of $$\mathbb{Z}/5\mathbb{Z}.$$

### The transitions

$$Z_n$$ transitions to $$Z_{n+1}$$ by adding $$3X_{n+1}^2$$ to it modulo $$5.$$ Since the numbers modulo $$5$$ are $$0,\pm 1,\pm 2,$$ three easy calculations show that thrice their squares are $$0,-2,2,$$ respectively. We can tabulate the possible transitions by writing the starting state, an arrow, and the terminal state. They are all of the form

$$i\rightarrow i+k \mod 5$$

where $$i$$ ranges over $$\mathbb{Z}/5\mathbb{Z}$$ and $$k$$ ranges over $$\{0,\pm2\},$$ making $$5\times 3 = 15$$ possible transitions.

### The probabilities

Modulo $$5,$$ the faces of a die are $$0,\pm 1, \pm 2,$$ and $$1$$ is repeated (it corresponds to $$1$$ and $$6$$). All six faces are assumed equiprobable, whence each has a $$1/6$$ chance of occurring. Therefore

• On one face of the die (namely $$5 = 0 \mod 5$$), $$3X_{n+1}^2=0.$$ This transition has chance $$1/6.$$

• On three faces of the die (namely $$1,$$ $$4=-1\mod 5,$$ and $$6=1\mod 5$$), $$3X_{n+1}^2 = -2.$$ This transition has chance $$3/6=1/2.$$

• On two faces of the die (namely $$2$$ and $$3=-2\mod 5$$), $$3X_{n+1}^2 = 2.$$ This transition has chance $$2/6=1/3.$$

### The transition matrix

Let's arrange the state space in some meaningful way, such as $$S=(0,1,2,-2,-1)$$ (which are the numbers $$0,1,2,3,4$$ modulo $$5$$ in their usual order). Relative to this sequence, the transition matrix $$\mathbb P$$ has five rows and five columns, each corresponding to $$S,$$ and the entry $$p_{ij}$$ gives the probability of a transition from $$i\in S$$ to $$j\in S.$$ Since we have already worked out the transitions and their probabilities, it remains simply to write $$\mathbb P$$ down. This is easy to do, because addition of $$2$$ modulo $$5$$ rotates $$S$$ in a circular fashion two places to the right, addition of $$-2$$ rotates $$S$$ two places to the left, and addition of $$0$$ leaves it unchanged. Thus, we only need to put $$1/6$$ along the diagonal, $$1/3$$ along the twice-rotated diagonal, and $$1/2$$ along the twice-rotated diagonal in the other direction:

$$\mathbb{P} = \pmatrix{ \frac{1}{6} & 0 & \frac{1}{3} & \frac{1}{2} & 0 \\ 0 & * & 0 & * & * \\ * & 0 & * & 0 & * \\ * & * & 0 & * & 0 \\ 0 &* & * & 0 & * }$$

I have indicated the pattern of non-zero transitions with stars $$*$$ and leave the (easy) exercise of completing it to you.

### Conclusions

The independence of the transitions makes this a Markov chain. It is defined on the set consisting of the starting state (where the sum is zero) together with all states that can be reached from the start.

Because all possible elements of $$\mathbb{Z}/5\mathbb{Z}$$ can be reached with positive probability from the starting state ($$0$$), no smaller state space will suffice.

Because the transitions can be expressed with a matrix whose entries do not depend on $$n,$$ this is a homogeneous chain, by definition.

• I have an additional question. What if instead of $Z_n=3(X_1^2+...+X_n^2) mod 5$ I have $Z_n=2(X_1^2*...*X_n^2) mod 5$? Now if I want to find a proper transitions, I have that $Z_{n+1}=(Z_n * X_{n+1}) mod 5$. Let's say that my state space is $S=\{0,1,2,3,4\}$. I need to substitute all of the numbers on a die to my $Z_{n+1}=(Z_n * X_{n+1}) mod 5$ but in my original question I just took $Z_n=0$. Should I just take $Z_n=1$ this time? Because if I'd take $0$ then $0 mod 5 = 0$ on every side of a die and I guess it won't be a homogeneous Markov chain (not even a Markov chain?). – MacAbra Jan 17 at 19:19
• This time, the transition from $Z_n$ to $Z_{n+1}$ multiplies it by $X_{n+1}^2$ mod $5.$ On a die, this value is either $0$ with probability $1/6$, $1$ with probability $1/2,$ or $-1$ with probability $1/3.$ These are very simple numbers to compute with, making it fast and easy to write down the transition matrix. It will still be a Markov chain and is still homogeneous. Note, however, that the only states that can ever be reached from a starting state $Z_0$ are $0$ and $\pm Z_0.$ – whuber Jan 17 at 20:13