3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ What happens if the exclusion condition is or would be violated? $\endgroup$
    – Mark L. Stone
    Commented Jul 9, 2022 at 17:54
  • $\begingroup$ @MarkL.Stone My guess is that the question is about a walk chosen uniformly at random from all walks satisfying the stated condition. $\endgroup$
    – mathworker21
    Commented Jul 9, 2022 at 19:00
  • 1
    $\begingroup$ exactly, we exclude walks which within them have 5 conseutive steps in each direction, from the sample space. $\endgroup$
    – Sia-TeX
    Commented Jul 9, 2022 at 21:41
  • $\begingroup$ @Sia-TeX If you replace $5$ with $2$, it's trivial. Have you thought about when you replace $5$ with $3$? $\endgroup$
    – mathworker21
    Commented Jul 10, 2022 at 0:55
  • $\begingroup$ In general I am interested, in what happens when we inject some predictability (by imposing some rules) into a random setting. So I chosed 5 just as an example. It can be othre numbers. $\endgroup$
    – Sia-TeX
    Commented Jul 10, 2022 at 19:11

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much for the answer and the sources. In general I am interested, in what happens when we inject some predictability (by imposing some rules) into a random setting. Also assuming there are certain rules, how long it would take for a machin to learn these hidden rules. I have two questions about the elementary approach: 1- How from irreducible +aperiodicity of $Y_n$, we can conclude that $X_m$ and $X_n,$ with $m \neq n$, are nearly independent. 2- For $Y_n$ we should have n=0, 5, 10, ... for it to be a MC, correct? $\endgroup$
    – Sia-TeX
    Commented Jul 10, 2022 at 19:10
  • 1
    $\begingroup$ As I mentioned, the exponential decay of covariances follows, e.g. from pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Theorem 4.9. The sequence $Y_n$ is a Markov chain when $n$ runs through all positive integers. Read about shifts of finite type and the Parry measure in the references [4] [5] above. $\endgroup$
    – Yuval Peres
    Commented Jul 11, 2022 at 0:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .