Non-Markovian jumping process conjecture for the birth Mallows process

Proof for every $n\ge4$. Write

$$[j]_t=1+t+\cdots+t^{j-1}, \qquad Z_n(t)=\prod_{j=2}^n[j]_t, \qquad N=\binom n2.$$

By the source's independent inversion-coordinate construction, the birth Mallows process corresponds bijectively to independent unit-birth processes $B_j(t)$ with

$$\Pr(B_j(t)=r)=\frac{t^r}{[j]_t}, \qquad 0\le r<j.$$

Let $H_{23}$ be the history in which the first two global jumps occur in coordinates $2,3$, and $H_{32}$ the reverse history. Both have positive probability and end at the identical state

$$(B_2,B_3,B_4,\ldots,B_n)=(1,1,0,\ldots,0).$$

If $T$ denotes the second jump time, independence gives the unnormalized history-time densities

$$f_{23}(t) = \frac{t}{[2]_t} \frac{[3]'_t}{[3]_t^2} \prod_{j=4}^n\frac1{[j]_t},$$ $$f_{32}(t) = \frac{t}{[3]_t} \frac1{[2]_t^2} \prod_{j=4}^n\frac1{[j]_t} = \frac{t}{(1+t)Z_n(t)} =:w(t).$$

Their ratio is

$$R(t) = \frac{f_{23}(t)}{f_{32}(t)} = \frac{(1+t)(1+2t)}{1+t+t^2} = 2+\phi(t), \qquad \phi(t)=\frac{t-1}{1+t+t^2}.$$

Palindromicity of $Z_n$ gives

$$\frac{w(1/t)}{t^2}=t^{N-3}w(t), \qquad \phi(1/t)=-t\phi(t).$$

Therefore

$$\int_0^\infty w(t)(R(t)-2)\,dt = \int_0^1 w(t)\phi(t)(1-t^{N-2})\,dt <0.$$

Consequently the normalization ratio

$$c_n=\frac{\int f_{23}}{\int f_{32}}$$

satisfies $1<c_n<2$. Moreover $R$ is strictly increasing on $(0,1)$, and $R(t)\ge2$ for $t\ge1$. Hence $R(t)-c_n$ changes sign exactly once, from negative to positive. The two conditional time distributions therefore satisfy strict stochastic ordering:

$$T\mid H_{23}>_{\mathrm{st}}T\mid H_{32}. \tag{1}$$

Now consider the future embedded-chain event

$$E= \{ \text{the second jump in coordinate }3 \text{ precedes the first jump in coordinate }4 \}.$$

Jumps in all other coordinates can be ignored. The two competing birth rates are

$$a(t)=q_{3,1}(t)=\frac{t+2}{1+t+t^2}, \qquad b(t)=q_{4,0}(t) =\frac{3t^2+2t+1}{(1+t)(1+t^2)}.$$

A direct calculation yields

$$\left(\frac{a(t)}{b(t)}\right)' = -\frac{ 4t^6+6t^5+15t^4+32t^3+30t^2+18t+3 }{ (t^2+t+1)^2(3t^2+2t+1)^2 } <0.$$

Thus $h(t)=a(t)/(a(t)+b(t))$ is strictly decreasing. If $\tau_t$ is the first ring of these two clocks after time $t$, then

$$Q(t):=\Pr(E\mid T=t,B(T)=(1,1,0,\ldots,0)) =\mathbb E[h(\tau_t)].$$

For $t<s$, splitting at $s$ gives

$$Q(t) = \int_t^s h(u)(a(u)+b(u)) e^{-\int_t^u(a+b)} \,du + e^{-\int_t^s(a+b)}Q(s).$$

Since $h(u)>h(s)>Q(s)$ for $t<u<s$, this identity implies $Q(t)>Q(s)$. Thus $Q$ is strictly decreasing.

Applying this to the strict stochastic ordering (1),

$$\boxed{\displaystyle \Pr(E\mid H_{23}) < \Pr(E\mid H_{32}). }$$

The two histories reach the same state at the same jump index, yet yield different conditional probabilities for a future event determined entirely by the jumping chain. This contradicts the Markov property. Therefore the jumping process is not a Markov chain for every $n\ge4$.

Source: Benoît Corsini, Continuous-time Mallows processes, Conjecture 3, §4.2, https://arxiv.org/abs/2205.04967.