Consider the sequence $\{X_i\}_{i=1}^{\infty}$. We have that marginally $\mathbb{P}(X_i = 1) = 1/2$, $\mathbb{P}(X_i = -1) = 1/2$. The sequence is Markov such that $\mathbb{P}(X_{i} = X_{i-1}) = 1-p$ and $\mathbb{P}(X_{i} = -X_{i-1}) = p$.
When $p = 1/2$, the sequence is i.i.d, and we can prove the weak law: $$ \frac{1}{n}\sum_{i=0}^{n}X_i = \frac{S_n}{n} \rightarrow 0\;\;\text{(in probability)} $$ simply via the Markov inequality. For $0<p<1$, we can prove a strong law by noting that the sequence is generated by an aperiodic, irreducible Markov chain with stationary distribution [1/2, 1/2]. It should thus be possible to prove a weak law for general $0<p<1$. But, if we follow the same method as in the case of $p=1/2$, we have:
$$ \mathbb{P}\left(\left(\frac{S_n}{n} - 0\right)^2 > \epsilon^2\right) \leq \frac{\mathbb{E}[S_n^2]}{n^2\epsilon^2}. $$ For $p=1/2$, $\mathbb{E}[S_n^2] = n$, completing the proof. But in general:
$$ \mathbb{E}[S_n^2] = n + 2\sum_{j=1}^n\sum_{i>j}^n \mathbb{E}[X_iX_j]. $$
Is it possible to show that this second term grows slower than $n^2$? If not, what am I missing?