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

Question

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.

Answer 1

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.