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?
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$$