Suppose we have a chain $$s_1 \rightarrow s_2 \dots \rightarrow s_n,$$ where $$p(s_1 \mid s_i) = p(s_1 = s_i),\ p(s_i = s_{i+1}) = q,$$ and $$p(s_1 = 1) = p(s_1 = -1) = \frac{1}{2}.$$
Prove that:
$P(s_1 \mid s_i)$ is equal to the probability that the number of ‘mismatches’ $(s_j \neq s_{j-1})$ in the chain is even?
When writing this out for $n=3$ it seems to be correct, but I don't understand why this relation is true?
Any hints?