I am working on the followign exercise and I would be glad if you could have a look at my solution attempt:
For $n \ge 1$, let $Z_n$ be the RV representing the number of rolls of a fair die until 6 appears $n$ times.
a) Is $(Z_n)_{n \ge 1}$ a Markov chain? Explain your answer.
b) Is $(Z_n)_{n \ge 1}$ stationary? Explain your answer.
c) Compute the entropy rate of $(Z_n)_{n \ge 1}$.
My attempt:
a) $(Z_n)_{n \ge 1}$ is a Markov chain, since we have the relation $Z_{n+1} = Z_n + X_n$ where $X$ is an RV that counts the number of coin tosses required to get the $n$-th 6. Thus Knowledge of $Z_{n+1}$ only depends on knowledge of $Z_n$.
b) The transition matrix $P$ of $(Z_n)_{n \ge 1}$ is given by a $6 \times 6$ matrix where each entry is 1/6. (This is because we assumed that the dice is fair.) The initial distribution is given by the vector $\nu = \begin{bmatrix} 1/6 &1/6 &1/6 &1/6 &1/6 &1/6\end{bmatrix}$. Since $\nu P = \nu$ we know that $(Z_n)_{n \ge 1}$ is stationary.
c) I think that just using the formula for the entropy rate
$$-\sum_{x,y \in \mathcal{X}} \nu(x) \ p(y \mid x) \ \log_2(p(y \mid x))$$
suffices here. I get
$$= -\sum_{i=1}^{36} \frac{1}{36} \ \log_2(1/6) = 2.58.$$
Could you please tell me if I made a mistake?
Best Answer
In the reasoning in a), you need to point out that $X_n$ is independent of $Z_1, \dots, Z_n$.
b) is wrong. The state space of $Z_n$ is the naturals. So a $6 \times 6$ transition matrix makes no sense.
You can note that if the chain is stationary, then $\mathbb{E}[Z_n]$ would be constant. But clearly $\mathbb{E}[Z_n] = n \mathbb{E}[Z_1],$ which grows with $n$, so the chain is not stationary.
c) The approach is as such fine, but the form of the expressions is wrong (this stems from the issue in part b)).
You can make this work by simply noting that since $Z_{n+1} = Z_n + X_n,$ $H(Z_{n+1}|Z_n) = H(X_n|Z_n) = H(X_n),$ so the entropy rate is just the entropy of a geometric random variable with parameter $1/6$.