Entropy rate of a dog looking for a bone My question is about Entropy rate of a dog looking for a bone. According to this problem, A dog walks on the integers, possibly reversing direction at each step with probability $p = 0.1$ . Let $X_{0} = 0.$  The first step is equally likely to be positive or negative. A typical walk might look like this:
\begin{equation}
 (X_{0},X_{1}, . . .) = (0,−1,−2,−3,−4,−3,−2,−1, 0, 1, . . .).
\end{equation}
Now I want to find $H(X_{1},X_{2}, . . . , X_{n}).$
Here in the solution it has been said that, since $H(X_{0})=0$ and $H(X_{1}|X_{0})=0$, so for $i>0$:
\begin{equation}
 H(X_{i}|X_{i-1},X_{i-2}) = H(.1,.9)
\end{equation}
Where does $H(.1,.9)$ come from?
And also for computing entropy rate of this browsing dog, the solution is like this:
\begin{equation}
 H(X_{0},X_{1}, . . .)/(n+1) = (1+(n-1)H(.1,.9))/(n+1)
\end{equation}
What is $(n+1)$ here?
 A: Given $X_{i-2}$ and $X_{i-1}$, we know what direction the dog is "currently" walking and where it is. The information gained by measuring $X_i$ is just "whether or not the dog changed direction", which is the result of a coin flip with probability $0.1$. So $H(X_i \mid X_{i-1}, X_{i-2}) = H(0.1, 0.9)$.
The $n+1$ comes from averaging the joint entropy over $n+1$ random variables $X_0, X_1, \dots, X_n$.
Just to work it out: the joint entropy $H(X_0, X_1, X_2, \dots, X_n)$ is, by the chain rule
$$H(X_0, X_2, \dots, X_n) = \displaystyle\sum_{i = 0}^n H(X_i \mid X_0, X_1, X_2, \dots, X_{i-1})$$
$X_i$ is conditionally independent of $X_{i-3}, X_{i-4}, \dots,$ given $X_{i-1}, X_{i-2}$ because the only relevant things are (1) the past state, $X_{i-1}$, and (2) the direction of travel, determined by $X_{i-2}$. 
$$H(X_0, X_2, \dots, X_n) = H(X_0) + H(X_1 \mid X_0) + \displaystyle\sum_{i = 2}^n H(X_i \mid X_{i-1}, X_{i-2})$$
$H(X_0) = 0$ because it's fixed. $H(X_1 \mid X_0) = 1$ for an unbiased coin flip. $H(X_i \mid X_{i-1}, X_{i-2}) = H(0.1, 0.9)$.
$$H(X_0, X_2, \dots, X_n) = 1 + (n-1)H(0.1, 0.9)$$
$$H(X_0, X_2, \dots, X_n)/(n+1) = (1 + (n-1)H(0.1, 0.9))/(n+1)$$
Entropy rate: $\lim_{n\to\infty}H(X_0, X_2, \dots, X_n)/(n+1) = H(0.1, 0.9)$
A: Another way of looking this is there is a correspondence between such dog walks and sequences of the form:
$$(Bern(0.5), Bern(0.1), …, Bern(0.1))$$
for independent Bernoulli’s where there are n-1 Bern(0.1). The first variable encodes the direction of the first step, the next encodes whether the dog turns at a given step. Entropy is preserved under bijective mappings and the entropy of a sequence of independent variables is just the sum of the entropies of each variable, giving the same result as the above answer.
