Consider a simple random walk $$\mathcal{X}\_t= \sum\_{n<t} X\_n,$$ where $P(X\_n=1)= P(X\_n=-1)= 1/2.$


If I put an extra condition that excludes cases with more than 5 consecutive +1, or -1 in the sum:


For every $n$, between 1 and t-4:


$$|X\_n+ X\_{n+1}+ X\_{n+2}+ X\_{n+3}+ X\_{n+4}|< 5.$$


Can I still expect that $\mathcal{X}\_t \ll \sqrt{t}$ almost surley?


If yes, how can we prove this?



Simple random walk with an extra condition
Let $Y\_n=(X\_n,X\_{n+1},X\_{n+2},X\_{n+3},X\_{n+4})$. The sequence $\{Y\_n\}$ is an aperiodic irreducible Markov chain on 30 states (vectors of $\pm 1$ that are not all $1$ or all $-1$). Its distribution is known as the Parry measure on a shift of finite type, See [4] or [5]. For the aperiodicity, it is important that the constraint is on sums of five-tuples and not on pairs. One could easily reduce the number of states to 16, since looking at 4-tuples also yields a Markov chain, but that takes a moments' thought and is not important, so let's stay with 30 states.


The invariance of the constraint to flipping the sign of all the variables implies that the unique stationary distribution $\pi$ is even:
$$\pi(x\_1,\ldots,x\_5)=\pi(-x\_1,\ldots,-x\_5)$$
This is not really necessary, but we note that the Markov chain $\{Y\_n\}$ is reversible, since the constraint is stable to flipping the direction of time.


The partial sums $$S\_t= \sum\_{n<t} X\_n$$ (note the change of notation)
form a mean zero additive functional in this Markov chain, so one fancy way to conclude and obtain a central limit theorem is to use the Kipnis-Varadhan Theorem [1], see [2] for a friendly exposition.


A more elementary approach is to observe that any finite irreducible aperiodic Markov chain exhibits
exponential decay of correlations (see e.g. [3]) so $|E(X\_m X\_{m+k})| \le C\alpha^k$
for some $\alpha<1$ and $C<\infty$.
Therefore
$$ES\_t^2\le 2\sum\_{m<t} \sum\_{k\ge 0} |E(X\_m X\_{m+k})| \le 2Ct/(1-\alpha)=C't.$$
Thus
$$E|S\_t| \le \sqrt{C't} \,.$$


[1] Kipnis, C., Varadhan, S. R. S. (1986) Central limit theorem for additive functionals of reversible markov processes. Commun. Math. Phys. 104 1-19.


[2] [https://www.math.arizona.edu/~sethuram/588/lecture8.pdf](https://www.math.arizona.edu/%7Esethuram/588/lecture8.pdf) Theorem 3.1


[3] <https://www.yuval-peres-books.com/markov-chains-and-mixing-times/> <https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf> Theorem 4.9


[4] <https://dmg.tuwien.ac.at/aofa15/slides/Marcovici_AofA.pdf> Slides 12-33


[5] <https://personalpages.manchester.ac.uk/staff/Charles.Walkden/ergodic-theory/lecture15.pdf> Section 15.5


