Entropy rate of a dog looking for a bone

Question

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?

Answer 1

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)$

Answer 2

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.