Suppose I start flipping independent fair coins $c_1,c_2,\dots$. I want to look at "windows" of length $n$, e.g., $(c_1,\dots,c_n)$ would be the first window, $(c_2,\dots,c_{n+1})$ would be the second window, etc. Let $X_i$ be the number of Heads I see in the window $(c_{1+i},\dots,c_{n+i})$. Thus $X_0 \sim \text{Bin}(n,\frac{1}{2})$.
Ultimately I would like to find the expected time for $X_i$ to exceed a particular value. I would like to do this by viewing $(X_i)$ as a random walk. (Or is there a better way to compute this?)
My first thought was that each time we "shift the window" we discard a coin and add a coin. With probability $1/2$ the coin we add shows the same thing as the coin discarded, i.e., $P(X_{i+1}=X_i)=1/2$. With probability $1/2$ they show different things. Half of that time we discard a Head and add a Tail, so $P(X_{i+1}=X_i-1)=1/4$, and half of that time we discard a Tail and add a Head, so $P(X_{i+1}=X_i+1)=1/4$. However, this is not totally correct. If $(X_i)$ did follow the transition probabilities above, then it would be possible for $(X_i)$ to go negative, yet we know the number of heads in each window is always nonnegative. (Also, that walk could exceed $n$, but the number of heads in each window is always less than or equal to $n$).
My next thought is perhaps $(X_i)$ is the random walk described above, but conditioned to remain in $\{0,1,2,\dots,n\}$. How would I prove or disprove this?
The random walk view can lead to outcomes that are not possible in the coin flip view. For example, with $n=2$, the walk might give $X_1 = 0$, $X_2=1$, $X_3=1$, $X_4=1$, $X_5=2$.
With the coin flipping method, the first window must be $(0, 0, 0)$, then the second third and fourth are $(0, 0, 1)$, $(0, 1, 0)$, and $(1, 0, 0)$. There is now window consistent with both these and $X_5 = 2$.
Basically the process isn't Markovian over the state space you've given.