This Continuous-Space Discrete-Time Markov Chain

markov chainsmarkov-processprobability distributionsstochastic-processes

So, I was doing my Sunday tinkering and I came across this continuous-space, discrete-time Markov Chain:

  1. $X_0 \in (0,1)$, $k \in (0,1)$

  2. Update rule:

  • With probability $p$, $X_{t+1} = k+(1-k)X_t$

  • With probability $1-p$, $X_{t+1} = X_t(1-k)$

I'm interested in learning what this Markov chain is and what its steady-state distribution is, from simulation – I'm fairly convinced its a Beta distribution, as always, proof is preferable!

Best Answer

I mostly understand what's going on when $k \ge \frac12$.

For a nice special case, let $k = \frac23$ and $p = \frac12$. Then our update rule is that $X_{t+1}$ first multiplies $X_t$ by $\frac13$, and then flips a coin to decide whether to add $\frac23$ or not. If we write $X_t$ as $0.x_1x_2x_3x_4\dots$ in ternary, then $X_{t+1}$ is equally likely to be either $0.0x_1x_2x_3x_4\dots$ or $0.2x_1x_2x_3x_4\dots$ in ternary.

As a result, the limiting distribution is to choose a random number in $[0,1]$ via its ternary representation, putting a $0$ or $2$ in each ternary digit with equal probability. This has a name: it's the Cantor distribution. The Cantor distribution is, informally, a uniform distribution on the Cantor set. It is a singular distribution, not even a little discrete (every point has probability $0$) nor even a little continuous (its support has measure $0$).

If we keep $p$ the same, but vary $p$, then as long as $p$ is not either $0$ or $1$, we get a different distribution on the Cantor set, with similar properties.

For other values of $k$ such that $k>\frac12$, we get something similar happening on a Cantor set with different proportions. The update rule of the Markov chain guarantees that $X_1 \in [0,1-k] \cup [k,1]$. Therefore $X_2 \in [0,(1-k)^2] \cup [k(1-k),1-k] \cup [k,k+(1-k)^2] \cup [k+k(1-k),1]$. For $X_t$, we get a similar support of $2^t$ intervals of total length $(2(1-k))^t$.

Looking at $k =\frac12$ is trickier, but the answer turns out to be similar. In this case, $X_{t+1}$ is $\frac12 + \frac12X_t$ with probability $p$ and $\frac12X_t$ otherwise. Written in binary, we shift $X_t$ over and put $1$ (with probability $p$) or $0$ (with probability $1-p$) in the first position. This leads to a random real number whose binary digits are chosen from a Bernoulli distribution, and people have thought about this a lot; see, for example, this question on MSE.

If $p = \frac12$, then this is just the uniform distribution. If $p \ne \frac12$, it is once again purely singular. Suppose, for example, $p = \frac23$. Then we expect that around $\frac23$ of the first $t$ binary digits of $X_t$ are $1$, and around $\frac13$ are $0$, and in the limiting distribution, we expect that this is almost true for almost all $t$. Let $X$ have that limiting distribution. Then with probability $1$, there is a number $N$ such that for all $t \ge N$, at least $0.66t$ of the first $t$ binary digits are $1$. But the set of real numbers in $[0,1]$ with this property has measure $0$.

When $k<\frac12$, the intervals $[0,1-k]$ and $[k,1]$ overlap, and the description becomes messy. I do not know what's going on here and I don't know if it's still purely singular. I'm pretty sure that it's not a Beta distribution, because when I looked at a special case, there were no parameters of the Beta distribution that led to the PDF being a fixed point of the update rule.

Related Question