I have a question regarding Markov chains obtained by random indep. iterations.

We should consider a Markov chain $\{X_{n}\}^{\infty}_{n=0}$ obtained by random indep. iterations with the functions $f_{1}(x)=x^{2}+17$, $f_{2}(x)=x^{2}-17$ and $f_{3}(x)=0$ where the functions are chosen with equal prob. in each iteration step.

If we suppose $X_{0}=0$. How would I show that $\{X_{n}\}^{\infty}_{n=0}$ has a unique stationary prob. distribution?

The confusing part for me is the third function. If that function would be left out I would get $X_{n+1}=X_{n}^{2}+\xi_{n+1}$, where $\xi_{n+1}=\pm17$ with prob. $1/2$. But how do I see this process with the third function in mind?

  • $\begingroup$ The Markov dynamics would rather correspond to the recursion $$X_{n+1}=A_{n+1}X_n^2+B_{n+1}$$ with $(A_n,B_n)$ i.i.d. uniformly distributed on $$\{(1,17),(1,-17),(0,0)\}$$ $\endgroup$ – Did Feb 9 '18 at 17:11
  • $\begingroup$ I see that making sense, thank you. Now, how should I proceed to find the stationary probability distribution? I have tried to search for examples, as my course book doesn't provide any (or theory on that matter either). $\endgroup$ – Femman Feb 9 '18 at 19:01
  • $\begingroup$ The usual approach. Some care is needed to get the correct state space, though. $\endgroup$ – Did Feb 9 '18 at 19:55

The states of the Markov chain are $0$ and every iterated image of $0$ by $f_1$ and $f_2$. With the exception of $f_1(f_1(0))=f_1(f_2(0))=17^2+17$ and of $f_2(f_1(0))=f_2(f_2(0))=17^2-17$, it seems that all these images are different.

Thus, the state space of the Markov chain has roughly the structure of a binary tree rooted at $0$, with the exception that the vertices of the second generation are identified two by two. For every $n\geqslant2$, the $2^{n-1}$ vertices of the $n$th generation represent the $n$th iterates of $f_1$ and $f_2$ applied to $0$.

To describe this "almost tree" more precisely, let us label its vertices as $0$, $1'$, $2'$, $1$, $2$, $11$, $21$, $12$, $22$, and so on, thus $0$ points to $1'$ and $2'$, $1'$ and $2'$ point to $1$ and $2$, and, for every nonempty $\{1,2\}$-word $x$, the vertex $x$ points to $1x$ and $2x$.

By symmetry, the stationary distribution of the Markov chain puts the same weight, say $w_n$, on every vertex of the $n$th generation. Recall that the sizes of the successive generation, starting at and including the root, are $1$, $2$, $2$, $4$, $8$, $16$, ..., thus, the usual one-step stationarity yields $$w_0=\frac13\left(w_0+2w_1+\sum_{n=2}^\infty2^{n-1}w_n\right)=\frac13$$ Likewise, $$w_1=\frac13w_0=\frac19\qquad w_2=\frac13(2w_1)=\frac2{27}$$ and, for every $n\geqslant3$, $$w_n=\frac13w_{n-1}=\frac2{3^{n+1}}$$ As a sanity check, note that the total mass of the stationary distribution is indeed $$w_0+2w_1+\sum_{n=2}^\infty2^{n-1}w_n=\frac13+2\frac19+\sum_{n=2}^\infty2^{n-1}\frac2{3^{n+1}}=1$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.