I ran across this problem in "Elements of Information theory", by Cover and Thomas:
A dog walks on the integers, possibly reversing direction at each step with probability $$p = .1$$ Let $$X_0 = 0$$ The first step is equally likely to be positive or negative. A typical walk might look like this:
$$(X_0, X_1, . . .) = (0, −1, −2, −3, −4, −3, −2, −1, 0, 1, . . .)$$
Every discussion of this problem I've found states that this is a second order Markov process, but I can't see why. It seems to me that for i > 1 each state depends only on the one preceding it, so it should be an order 1 Markov process. What am I missing?