Asymptotic behavior of a Markov process on the set of $\{0,1\}$-polynomials

Question

This question is cross-posted from https://math.stackexchange.com/questions/4711799/asymptotic-behavior-of-a-markov-process-on-the-set-of-0-1-polynomials

I am trying to study the asymptotic behavior of a stochastic process defined on the space of single variable polynomials whose coefficients are either $0$ or $1$.

Letting $\mathbb{B}=\{0,1\}$, I will denote by $\mathbb{B}[x]$ this set of polynomials, and I will denote by $\mathbb{B}[x]_{t}\subset\mathbb{B}[x]$ the subset of such polynomials whose degree is less or equal to $t$. Moreover, given a polynomial $b_t(x)\in \mathbb{B}[x]_{t}$ notice that $xb_t(x)$ and $1+xb_t(x)$ are elements of $\mathbb{B}[x]_{t+1}$: these are the two possible "shifted" version of the polynomial.

Fix two parameters $\kappa,a\in (0,1)$. Define a process $(A_t)_{t=0}^\infty\subset\Delta(\mathbb{B}[x])$ as follows

• $A_0=\delta_0\in\Delta(\mathbb{B}_{0}[x])$. In words $A_0$ is a Dirac on the null polynomial.
• $A_t\in\Delta(\mathbb{B}_{t-1}[x])$ is defined as follows: \begin{align*} A_{t+1}(b_{t})=\begin{cases} A_{t}(b_{t-1})P(b_{t-1})\quad &if\quad b_{t}=1+xb_{t-1}\\ A_{t}(b_{t-1})(1-P(b_{t-1})) \quad &if\quad b_{t}=xb_{t-1}\\ 0\quad & else \end{cases} \end{align*} where, letting $b_{t-1}(\kappa)$ be the evaluation of $b_{t-1}$ at $\kappa$, $P(b_{t-1})=F(\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa))$ where $F:[0,1]\to[0,1]$ is a decreasing function such that $F(x)=1$ for $x$ close to 0, $F(1/2)=1/2$ and $F(x)=1$ for $x$ close to 1.

Hence, transition probabilities are as follows. $b_{t-1}\in\mathbb{B}[x]_{t-1}$ transitions to $1+xb_{t-1}\in\mathbb{B}[x]_{t}$ with probability $P(b_{t-1})=F(\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa))$ or to $xb_{t-1}\in\mathbb{B}[x]_{t}$, with probability $1-P(b_{t-1})$.

This should be a Markov process, where intuitively, the state $b_{t-1}$ is split in the two "shifted" states $1+xb_{t-1}$ and $xb_{t-1}$. Since each distribution is supported in a new set, there is no hope that there is an ergodic distributions. In simulations,though, it appears that, asymptotically $A_t$ concentrates on those polynomials in $\mathbb{B}[x]_{t-1}$ such that the value $\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa)$ is closer to $1/2$.

This is intuitive, given the definition of $P$. While for polynomials such that the value $\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa)$ is very close to $0$, surely or with high probability the mass $A_t(b_{t-1})$ is transfered completely on $1+xb_{t-1}$ (and viceversa for those who have $\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa)$ close to $1$) the polynomials with $\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa)$ close to $1/2$ are those where the mass is split equally. There is a sort of "balance" on this states.

But how can I show this formally?

Any help or reference would be immensely appreciated.

Answer 1

Just a comment really, but too long to fit in a comment box! I think you can simplify the formulation considerably. Let $X_t$ be your $\kappa^{t}a+b_{t-1}(\kappa)(1-\kappa)$. Then you can describe the process $X_t$ as a Markov chain in the following way: $X_1=\kappa a$, and for $t\geq 1$,
\begin{equation*} X_{t+1}=\begin{cases} \kappa X_t &\text{with probability $1-F(X_t)$};\\ \kappa X_t + (1-\kappa) &\text{with probability $F(X_t)$}. \end{cases} \end{equation*} Now $(X_t)_{t\geq 1}$ is a nice Markov process taking values in $[0,1]$, and you can indeed look for a stationary distribution to which $X_t$ converges in distribution as $t\to\infty$. Because of your assumption on $F$, such a stationary distribution will be supported on some sub-interval $[u,v]$ with $0<u<1/2<v<1$ (but it's not the case that it's concentrated on the point $1/2$).