Simple random walk with an extra condition 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?
 A: 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 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
