Renewal process: domination by product measure

Question

Consider a stationary process $(X(i), i\in\mathbb{Z})\in \{0,1 \}^\mathbb{Z}$ with the following structure; runs of 0s alternate with runs of 1s, with the length of all runs independent, and with each run of 0s having geometric distribution with parameter $\alpha$, and each run of 1s having geometric distribution with parameter $\beta$.

Put more straightforwardly, this is just a Markov chain on $\{0,1\}$ with transition matrix $p_{00}=1-p_{01}=\alpha$, $p_{11}=1-p_{10}=\beta$. This chain can be dominated by a process $(Y(i), i\in\mathbb{Z})$ with independent entries, in which each $Y(i)$ is 1 with probability $p$ and 0 with probability $1-p$; we may take $p$ to be $\max(1-\alpha, \beta)$. Here "domination" means we could couple $X$ and $Y$ with $X(i)\leq Y(i)$ for all $i$.

The domination is easy to see -- for example, notice that conditional on any configuration $(X(i), i < k)$, the probability that $X(k)=1$ is no larger than $p$, so the coupling could be built up one site at a time from left to right.

Now alter the process $X$ by changing the distribution of the runs of 1s. Now it is not geometric with parameter $\beta$, but it is stochastically bounded above by the geometric distribution with parameter $\beta$. The distribution of runs of 0s is unchanged.

Is it still true that the process $X$ is dominated by a process $Y$ with independent entries? (excluding the trivial process where every entry is 1).

Loosely, we have reduced the number of 1s in the process, so one might expect the same domination to hold. But notice that the uniform bound on the conditional probability above needn't hold any longer. For example, it could be that the run of 1s never has length exactly 2. Then $\mathbb{P}(X(3)=1|X(0)=0, X(1)=1, X(2)=1)=1$.

Answer 1

Resurrecting this old question because it is something I became interested in recently.

See the answer here: Stochastic process on $\{0,1\}^{\mathbb N}$ domination of product measures, necessary and sufficient conditions

Stochastic domination by product measures on $\{0,1\}^{\mathbb N}$

Let $X,Y$ be stochastic processes on path space $\{0,1\}^{\mathbb N}$ with distributions $\mu_X,\mu_Y$. If $\mu_Y=\pi_p$ the product measure with probability $p$, then, it is sufficient for $\mu_X \preceq \pi_p$ (stochastic domination of measures) that $$\mathbb P(X_n=1\mid A_{n-1})\leq p\tag{1}$$ for $A_{n-1}$ any arbitrary history of the process up to time $n-1$, e.g. $$A_{n-1}=\{X_1=0,X_2=1,X_3=1,\ldots,X_{n-2}=0,X_{n-1}=1\}.$$ This follows since that fact allows us to just construct a step-by-step coupling that unfolds in time.

Stochastic domination of measures does not require that we are allowed to construct our coupling in this step-by-step fashion though! So this condition (1) is only sufficient but not necessary, in general, for $\mu_X \preceq \pi_p$. It is true that the existence of some coupling which preserves their ordering almost surely is equivalent to stochastic domination (that's usually called Strassen's Theorem), but we don't know ahead of time what that coupling looks like.

See the example in the answer linked above for a process where $\pi_p \preceq \mu_X$ but $\mathbb P(X_n=1\mid A_{n-1})< p$. This is the opposite domination to what was discussed above. Here we would expect $p\leq\mathbb P(X_n=1\mid A_{n-1})$ since $\pi_p \preceq \mu_X$, but that is not the case! It is not hard to come up with other examples. Take that example and extend it to all of $\{0,1\}^{\mathbb N}$ in the natural way, where each $(X_{2n-1},X_{2n})$ has the given distribution. Then it does follow that $\pi_p \preceq \mu_X$ if and only if $p\leq\frac12$, and a temporally-sequenced coupling works if we consider consecutive 2-step chunks at a time. I.e. $$(Y_1,Y_2)\preceq(X_1,X_2), (Y_3,Y_4)\preceq(X_3,X_4), \ldots$$ if and only if $p\leq\frac12$. So this temporally-sequence coupling works as desired.

Increasing sets. Stochastic domination $\mu_X\preceq\mu_Y$ is equivalent to $\mu_X(I)\leq\mu_Y(I)$ for any increasing subset $I\subset\Omega$ of the sample path space. An set $I$ is increasing if $\omega\in I$ and $\omega\leq\phi$, then $\phi\in I$. Here we just have the natural partial ordering on $\{0,1\}^{\mathbb N}$ where $\omega\leq\phi$ if and only if $\omega_j\leq\phi_j$ for all $j$. An increasing subset of $\{0,1\}^{\mathbb N}$ can look like $\{\omega_j=1 \text { for } j\in J\}$ with $J$ some subset of $\mathbb N$. Also unions of such events give increasing sets, e.g. $\{\omega_1=1\}\cup\{\omega_2=1\}$ is an increasing subset of the sample path space (as is $\{\omega_1=1\}\cap\{\omega_2=1\}=\{\omega_1=1,\omega_2=1\}$).

If you work with these increasing sets, you'll quickly find that it isn't sufficient for stochastic domination to only consider conditional probabilities like (1) above. Test this out with the example in the answer linked above. It's a good exercise to try and come up with a different example too, and try to extend it to all of $\{0,1\}^{\mathbb N}$.

Coupling by run length

Now, to a construction in the question for processes $X,Y$. Let $N_0^X,N_1^X,N_0^Y,N_1^Y$ be random variables that govern the lengths of the runs of 0's and 1's for the two processes. And let's just consider $\{N_0^X(j)\}_{j\in\mathbb N}$ to be i.i.d., and likewise for the other run lengths. Let's just assume they both start in state 0 and alternate between state 0 and state 1 and stay in each state according to their run length distributions. Then $X$ will have $N_0^X(1)$ zeros, then $N_1^X(1)$ ones, then $N_0^X(2)$ zeros, etc. And similarly for $Y$.

Now assume that $N_0^X\succeq N_0^Y$ and $N_1^X\preceq N_1^Y$ so that $X$ tends to have longer runs of zeros and shorter runs of ones, relative to $Y$. We don't get that $Y$ dominates $X$ here in the normal step-by-step, forward-in-time coupling though!

Although it is true that $X$ will always have fewer ones that $Y$, the zeros and ones can get out of sync so that $X$ will still have a one where $Y$ has a zero. But, we can construct stochastically ordered summation processes $S^X=(\sum_{j=1}^n X_j)_{n\in\mathbb N}$ and likewise $S^Y$ to get $S^X\preceq S^Y$ via temporally sequenced coupling of $X$ and $Y$. This can be seen by just coupling their run lengths forward in time: $(N_j^X(n),N_j^Y(n))$ for $j=0,1$ and $n=1,2,\ldots$. that $X$ always has fewer ones at any given fixed end time follows.

As a simple example, let $N_0^X,N_1^X$ both be uniform on $\{1,2\}$, and let $N_0^Y$ also be uniform on $\{1,2\}$ but let $Y$ always have deterministically a run of length two timesteps for state 1. When coupled in the natural way, they always have the same run-lengths of zeros, but $X$ will sometimes have a single one with $Y$ always having two ones. Here are two example sample paths which are coupled via run-lengths: $$\begin{aligned} X&=(0,1,0,1,\ldots)\\ Y&=(0,1,1,0,\ldots).\\ \end{aligned}$$ Clearly $X$ is not below $Y$ in the desired step-by-step, forward-in-time way, but if we summed these processes, we would get $S^X\leq S^Y$.

This example is interesting, since the natural time-forward coupling via run lengths does not order the processes, but that doesn't prove $\mu_X\not\preceq\mu_Y$. We would need further work to investigate that. For example, consider increasing set $I=\{\omega_4=1\}$. We have that $$\mu_X(I)=\mathbb P(N_0^X=1)^2\mathbb P(N_1^X=1)+\mathbb P(N_0^X=2)\mathbb P(N_1^X=2)=\frac38$$ and $$\mu_Y(I)=\mathbb P(N_0^Y=2)\mathbb P(N_1^Y=2)=\mathbb P(N_0^Y=2)=\frac12.$$ Hence, $\mu_X(I)<\mu_Y(I)$ as desired but $X_4>Y_4$ is possible with the time-forward coupling as illustrated above.

This example shows that $\mu_X\not\preceq\mu_Y$ can occur even if we have stochastic domination of the run lengths for processes $X,Y$. Truncate the above example processes to 4 timesteps and list out all possible 4-step paths for $X$ and $Y$. Draw the ordered graph where $\omega\leq\phi$ if and only if $\omega_j\leq\phi_j$ for $j=1,2,3,4$. There are 5 possible paths, and the ordered graph has a "M" shape. One increasing subset consists of the single path $(0,1,0,1)$. Clearly $X$ places positive probability here and $Y$ places zero probability. So although the run lengths have the desired dominations, we get $\mu_X\not\preceq\mu_Y$.

Stochastic domination for Markov chains is very nice with all kinds of established theory. Without the Markov property, things quickly become much more complicated.

We did answer the main question here though, by showing that $\mu_X\prec \pi_p$ is not the same as $\mathbb P(X_n=1\mid A_{n-1})\leq p$ for arbitrary histories $A_{n-1}$.