Proof. Write ${(\mathcal{M}_t)_{t\in [0,\infty )}}=(\Phi (I(t)))_{t\in [0,\infty )}$ . The fact that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is a Mallows process simply follows from applying Proposition 2.1 and the fact that it has independent inversions simply follows from the fact that ${\mathrm{Inv}}_j(\Phi (I(t)))=I_j(t)$ and the assumption on $(I(t))_{t\in [0,\infty )}$ . Similarly, if the coordinates of $(I_j(t))_{t\in [0,\infty )}$ are increasing, then, by the definition of $\Phi$ , $(\mathcal{M}_t)_{t\in [0,\infty )}$ is strongly monotone. Assume now that the processes $(I_j(t))_{t\in [0,\infty )}$ are increasing with increments of size $1$ . To prove that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is regular, it suffices to show that $({\mathrm{Inv}}(\mathcal{M}_t))_{t\in [0,\infty )}$ has increments of size $1$ .

Let $T^{\, j}_k$ by the $k$ -th jumping time of $I_j$ , that is,

\begin{align*} T^{\, j}_k=\inf \big \{t \, : \, [0,\infty )\, :\, I_j(t)\geq k\big \}\,. \end{align*}

Using our assumption on $(I_j(t))_{t\in [0,\infty )}$ , we know that $T^j_1\lt T^j_2\lt \ldots \lt T^j_{j-1}$ . Moreover, the definition of $T^{\, j}_k$ implies that

\begin{align*} \mathbb{P}\big (T^{\, j}_k\leq t\big )=\mathbb{P}\big (I_j(t)\geq k\big )=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\sum _{\ell =k}^{j-1}t^\ell \,, \end{align*}

so $T^{\, j}_k$ is a continuous random variable. Since the coordinate processes $((I_j(t))_{t\in [0,\infty )},j\in [n])$ are independent, it follows that for $j\neq j'$ almost surely $T^{\, j}_k\neq T^{j'}_{k'}$ , which implies that all the values $\{T^{\, j}_k \, : \,\,j\in [n],k\in [j-1]\}$ are almost surely distinct. Using that

\begin{align*} {\mathrm{Inv}}(\mathcal{M}_t)=\big |\big \{1\leq k\lt j\leq n\,:\,T^{\, j}_k\leq t\big \}\big |\,, \end{align*}

it follows that $({\mathrm{Inv}}(\mathcal{M}_t))_{t\in [0,\infty )}$ only has increments of size $1$ .

Proof. We let $\sigma =\Phi (I)$ and $\sigma '=\Phi (I')$ and want to understand the relation between $\sigma$ and $\sigma '$ . Using the characterization of $\Phi$ we gave in Section 2.1, we verify that $\sigma (\,j)=\sigma '(\,j)$ for all $j\gt \ell$ , since $I_j=I'_j$ . Now, at step $\ell$ , we have

\begin{align*} [n]\setminus \{\sigma (\ell +1),\ldots ,\sigma (n)\}=[n]\setminus \{\sigma '(\ell +1),\ldots ,\sigma '(n)\}=\{x_1\lt \ldots \lt x_\ell \}\,. \end{align*}

By definition, we then have $\sigma (\ell )=x_{\ell -I_\ell }$ and $\sigma '(\ell )=x_{\ell -I'_\ell }=x_{\ell -I_\ell -1}$ . From this, it follows that

\begin{align*} [n]\setminus \{\sigma (\ell ),\ldots ,\sigma (n)\}&=([n]\setminus \{\sigma (\ell +1),\ldots ,\sigma (n)\})\setminus \{x_{\ell -I_\ell }\}\\[3pt] &=\{x_1\lt \ldots \lt x_{\ell -I_\ell -2}\lt x_{\ell -I_\ell -1}\lt x_{\ell -I_\ell +1}\lt \ldots \lt x_\ell \} \end{align*}

and

\begin{align*} [n]\setminus \{\sigma '(\ell ),\ldots ,\sigma '(n)\}&=([n]\setminus \{\sigma (\ell +1),\ldots ,\sigma (n)\})\setminus \{x_{\ell -I_\ell -1}\}\\[3pt] &=\{x_1\lt \ldots \lt x_{\ell -I_\ell -2}\lt x_{\ell -I_\ell }\lt x_{\ell -I_\ell +1}\lt \ldots \lt x_\ell \}\,. \end{align*}

Since $I_{\ell -1}=I'_{\ell -1}$ two cases follow. Either $I_{\ell -1}=I'_{\ell -1}=I_\ell$ and then $\sigma (\ell -1)=x_{\ell -I_\ell -1}$ and $\sigma '(\ell -1)=x_{\ell -I_\ell }$ , meaning that $\sigma (\ell -1)=\sigma '(\ell )$ and $\sigma '(\ell -1)=\sigma (\ell )$ ; or $I_{\ell -1}=I'_{\ell -1}\neq I_\ell$ , and then $\sigma (\ell -1)=\sigma '(\ell -1)$ . In this second case, we have that

\begin{align*} [n]\setminus \{\sigma (\ell -1),\ldots ,\sigma (n)\}&=\{x_1\lt \ldots \lt x_{\ell -I_\ell -1}\lt x_{\ell -I_\ell +1}\lt \ldots \lt x_\ell \}\setminus \{\sigma (\ell -1)\} \end{align*}

and that

\begin{align*} [n]\setminus \{\sigma '(\ell -1),\ldots ,\sigma '(n)\}&=\{x_1\lt \ldots \lt x_{\ell -I_\ell -2}\lt x_{\ell -I_\ell }\lt \ldots \lt x_\ell \}\setminus \{\sigma (\ell -1)\} \end{align*}

By applying the same argument as before, depending on the value of $I_{\ell -2}=I'_{\ell -2}$ , we obtain that either $\sigma (\ell -2)=x_{\ell -I_\ell -1}=\sigma '(\ell )$ and $\sigma '(\ell -2)=x_{\ell -I_\ell }=\sigma (\ell )$ , or $\sigma (\ell -2)=\sigma '(\ell -2)\notin \{x_{\ell -I_\ell },x_{\ell -I_\ell -1}\}$ . By repeating this argument, it follows that there exists $i\in [\ell -1]$ such that $\sigma (\ell -i)=\sigma '(\ell )$ , $\sigma '(\ell -i)=\sigma (\ell )$ , and for all $\ell -i\lt j\lt \ell$ , $\sigma (\,j)=\sigma '(\,j)$ . Note that we necessarily have that $i\leq \ell -1$ since, in the case where $i\gt \ell -2$ , then $\sigma (\,j)=\sigma '(\,j)$ for all $\ell -i\lt j\lt \ell$ . Now, using that $\ell -i\leq 1$ , it follows that $\sigma (\,j)=\sigma '(\,j)$ for all $2\leq j\lt \ell$ ; but we also know that this equality holds for all $j\gt \ell$ and then, since $\sigma$ and $\sigma '$ are permutation and since $\sigma (\ell )\neq \sigma '(\ell )$ , it follows that $\sigma (1)=\sigma '(\ell )$ and $\sigma (\ell )=\sigma '(1)$ , hence $i=\ell -1$ . Write now $k=\ell -i$ and note that

\begin{align*} [n]\setminus \{\sigma (k),\ldots ,\sigma (n)\}=[n]\setminus \{\sigma '(k),\ldots ,\sigma '(n)\}\,, \end{align*}

and that, for all $j\lt k$ , we have $I_j=I'_j$ . These two statement along with the description of $\Phi$ given in Section 2.1 imply that $\sigma (\,j)=\sigma '(\,j)$ for all $j\lt k$ . This shows that, for all $j\notin \{k,\ell \}$ , $\sigma (\,j)=\sigma '(\,j)$ , and that $\sigma (\ell )=\sigma '(k)$ and $\sigma (k)=\sigma '(\ell )$ . This is equivalent to saying that $\sigma '$ is obtained from $\sigma$ by transposing $k$ and $\ell$ , or in other words, that $\sigma '=\sigma \cdot {(k\,\ell )}$ .

Proof. To see that the lemma holds, fix a pair $i\lt j$ and let $I=(I_k)_{k\in [n]}\in \mathcal{E}_n$ be the inversion sequence such that $I_j=j-i-1\lt j-1$ and $I_k=0$ for $k\neq j$ . Further let $I'=(I'_k)_{k\in [n]}\in \mathcal{E}_n$ be such that $I'_k=I_k=0$ for $k\neq j$ and $I'_j=I_j+1=j-i\leq j-1$ . Then $(\Phi (I),\Phi (I'))\in E(\mathcal{H}_n)$ and by observing that the corresponding permutations are given by

and

we see that $\Phi (I')=\Phi (I)\cdot {(i\,j)}$ .

Proof of Theorem 1.2. The first part of the proof addresses the case where $\mathcal{M}$ is smooth; the second part proves the assertions of the theorem for regular $\mathcal{M}$ . Recall from Section 2.1 that for any $I\in \mathcal{E}_n$ and for $\sigma =\Phi (I)$ , the values $\sigma (n),\ldots ,\sigma (1)$ can be recursively constructed by letting

\begin{align*} [n]\setminus \{\sigma (n),\ldots ,\sigma (\,j+1)\}=\{x_1\lt \ldots \lt x_j\} \end{align*}

and by setting $\sigma (\,j)=x_{j-I_j}$ .

For the first part of this proof, assume that $\mathcal{M}={(\mathcal{M}_t)_{t\in [0,\infty )}}$ is a smooth Mallows process. Note that the definition of the expanded hypercube directly implies that $\mathcal{G}_{\mathcal{M}}$ is a subgraph of $\mathcal{H}$ , since every jump of $(\mathcal{M}_t)_{t\in [0,\infty )}$ corresponds to an increment of exactly one of its inversion numbers by $1$ , and by definition every such increment corresponds to an edge of $\mathcal{H}_n$ .

To see that $\langle \mathcal{G}_{\mathcal{M}}\rangle \subset \mathcal{T}$ , simply use that $\mathcal{G}_{\mathcal{M}}$ is a subgraph of $\mathcal{H}_n$ along with Lemma2.3 to find that $\langle \mathcal{G}_{\mathcal{M}}\rangle \subset \langle \mathcal{H}_n\rangle \subset \mathcal{T}$ .

We finally prove that ${\mathcal{T}^a}\subset \langle \mathcal{G}_{\mathcal{M}}\rangle$ . Note first that ${\mathcal{T}^a}=\{\sigma \in {\mathcal{S}_n} \, : \, {\mathrm{Inv}}(\sigma )=1\}$ . Suppose that ${\mathcal{T}^a}\setminus \langle \mathcal{G}_{\mathcal{M}}\rangle \neq \emptyset$ and consider $\tau \in {\mathcal{T}^a}\setminus \langle \mathcal{G}_{\mathcal{M}}\rangle$ . We note that

\begin{align*} \mathbb{P}\big (\mathcal{M}_t=\tau \big )&=\mathbb{P}\big (\mathcal{M}_t=\tau ,\exists u\gt 0 \, : \, \mathcal{M}_{u-}=\mathrm{id},\mathcal{M}_u=\tau \big )\\[3pt] &\leq \mathbb{P}\big (\exists u\gt 0 \, : \, \mathcal{M}_{u-}=\mathrm{id},\mathcal{M}_u=\tau \big )\,. \end{align*}

Since the leftmost probability is strictly positive whenever $t\gt 0$ , it follows that $(\mathrm{id},\tau )\in \mathcal{G}_{\mathcal{M}}$ and so $\tau \in \langle \mathcal{G}_{\mathcal{M}}\rangle$ . Hence, ${\mathcal{T}^a}\subset \langle \mathcal{G}_{\mathcal{M}}\rangle$ .

We now move on to the second part of the proof and prove that if $\mathcal{M}$ is a regular Mallows process, then $\mathcal{G}_{\mathcal{M}}=\mathcal{H}_n$ and $\langle \mathcal{G}_{\mathcal{M}}\rangle =\langle \mathcal{H}_n\rangle =\mathcal{T}$ . We start by proving that $\mathcal{G}_{\mathcal{M}}=\mathcal{H}_n$ . Since we already proved that $\mathcal{G}_{\mathcal{M}}$ is a subgraph of $\mathcal{H}_n$ , it suffices to show that $\mathcal{H}_n$ is a subgraph of $\mathcal{G}_{\mathcal{M}}$ .

Consider $(\sigma ,\sigma ')\in E(\mathcal{H}_n)$ and order $\sigma$ and $\sigma '$ so that ${\mathrm{Inv}}(\sigma ')={\mathrm{Inv}}(\sigma )+1$ ; write $I=(I_1,\ldots ,I_n)=\Phi ^{-1}(\sigma )$ and $I'=(I'_1,\ldots ,I'_n)=\Phi ^{-1}(I')$ . Using the definition of $\mathcal{H}_n$ , we know that there exists $\ell \in [n]$ such that $I'_j=I_j$ for all $j\neq \ell$ and $I'_{\ell }=I_{\ell }+1$ . For $j\in [n]$ , write $(T^{\, j}_k)_{k\in [j-1]}$ for the jumping times of $({\mathrm{Inv}}_j(\mathcal{M}_t))_{t\in [0,\infty )}$ , so

\begin{align*} T^{\, j}_k=\inf \big \{t\in [0,\infty ) \, : \, {\mathrm{Inv}}_j(\mathcal{M}_t)\geq k\big \}\,. \end{align*}

For convenience, set $T^j_0=0$ and $T^{\, j}_k=\infty$ for $k\geq j$ . Note that the processes $((T^{\, j}_k)_{k\in [j-1]})_{j\in [n]}$ are mutually independent (over $j\in [n]$ ) and all have continuous distributions. It follows that the event

\begin{align*} E=\big\{ {\max} \big \{T^j_{I_j} \, : \, j\in [n]\big \}\lt T^{\ell }_{I_{\ell +1}}\lt \min \big \{T^j_{I_j+1} \, : \, j\neq \ell \big \}\big \}\,, \end{align*}

which specifies the ordering of the $I_j$ -th and $(I_j+1)$ -th jumps of the $j$ -th entry of the inversion sequence, occurs with non-zero probability. Under the event $E$ , for any $t\gt 0$ such that

\begin{align*} \max \big \{T^j_{I_j} \, : \, j\in [n]\big \}\lt t\lt T^{\ell }_{I_{\ell +1}}\lt \min \big \{T^j_{I_j+1} \, : \, j\neq \ell \big \}\,, \end{align*}

we have that ${\mathrm{Inv}}_j(\mathcal{M}_t)=I_j$ for all $j\in [n]$ , implying that $\mathcal{M}_t=\Phi (I)=\sigma$ . Then, at time $T^{\ell }_{I_{\ell }+1}$ , the $\ell$ -th inversion number of $(\mathcal{M}_t)_{t\in [0,\infty )}$ jumps to $I_j+1$ , while no other coordinate jumps, which yields that $\mathcal{M}_{T^{\ell }_{I_{\ell }+1}}=\Phi (I')=\sigma '$ . Since there is no jump between $t$ and $T^{\ell }_{I_{\ell }+1}$ , this implies that

\begin{align*} \mathbb{P}(\exists t\in (0,\infty ) \, : \, \mathcal{M}_{t-}=\sigma ,\mathcal{M}_t=\sigma ')\geq \mathbb{P}(E)\gt 0\,. \end{align*}

Hence $(\sigma ,\sigma ')\in E(\mathcal{G}_{\mathcal{M}})$ , as desired.

To prove the last statement of the theorem, that is $\langle \mathcal{G}_M\rangle =\langle \mathcal{H}_n\rangle =\mathcal{T}$ , simply use that $\mathcal{G}_{\mathcal{M}}=\mathcal{H}_n$ along with Lemmas2.3 and 2.4, implying that $\langle \mathcal{H}_n\rangle =\mathcal{T}$ . This concludes the proof of the theorem.

Proof of Theorem 1.3. Fix $k\in \mathbb{N}$ . In the case of a monotone Mallows process $(\mathcal{M}_t)_{t\in [0,\infty )}$ , since ${\mathrm{Inv}}(\mathcal{M}_t)$ is increasing, we have that

\begin{align*} \mathbb{P}(T_k\gt t)=\mathbb{P}({\mathrm{Inv}}(\mathcal{M}_t)\leq k-1)\,. \end{align*}

Using the definition of Mallows permutations, it follows that

\begin{align*} \mathbb{P}(T_k\gt t)=\frac {1}{\prod _{k=1}^n\left (\sum _{\ell =0}^{k-1}t^\ell \right )}\sum _{\ell =0}^{k-1}|\{\sigma \in {\mathcal{S}_n} \, : \, {\mathrm{Inv}}(\sigma )=\ell \}|t^\ell \, \end{align*}

which means that

\begin{align*} \mathbb{P}(nT_k\gt t)=\frac {1}{\prod _{k=1}^n\left (\sum _{\ell =0}^{k-1}\left (\frac {t}{n}\right )^\ell \right )}\sum _{\ell =0}^{k-1}\frac {|\{\sigma \in {\mathcal{S}_n} \, : \, {\mathrm{Inv}}(\sigma )=\ell \}|}{n^\ell }t^\ell \,. \end{align*}

For the denominator, note that, for $n\gt t$ , we have

\begin{align*} \prod _{k=1}^n\left (\sum _{\ell =0}^{k-1}\left (\frac {t}{n}\right )^\ell \right )=\prod _{k=1}^n\left (\frac {1-\left (\frac {t}{n}\right )^k}{1-\frac {t}{n}}\right )=\left (1-\frac {t}{n}\right )^{-n}\prod _{k=1}^n\left (1-\left (\frac {t}{n}\right )^k\right )\,. \end{align*}

Now, as $n$ tends to infinity, the first term converges to $e^t$ and the second term can be written as

\begin{align*} \prod _{k=1}^n\left (1-\left (\frac {t}{n}\right )^k\right )&=\exp \left (\sum _{k=1}^n\log \left (1-\left (\frac {t}{n}\right )^k\right )\right )\,. \end{align*}

Since $(t/n)^k$ is decreasing in $k$ , we can apply a uniform bound over all the logarithmic terms and find that the previous term converges to $1$ . Combining the previous results imply that

\begin{align*} \prod _{k=1}^n\left (\sum _{\ell =0}^{k-1}\left (\frac {t}{n}\right )^\ell \right )\longrightarrow e^t \end{align*}

as $n$ tends to infinity.

Consider now $S^\ell _n=|\{\sigma \in {\mathcal{S}_n} \, : \, {\mathrm{Inv}}(\sigma )=\ell \}|$ . Using the bijection $\Phi$ from Section 2.1, we have that

\begin{align*} S^\ell _n= | \{(I_1,\ldots ,I_n)\in \mathcal{E}_n \, : \, I_1+\ldots +I_n=\ell \} |\,. \end{align*}

By changing the condition that $0\leq I_j\leq j-1$ in the definition of $\mathcal{E}_n$ to $I_j\geq 0$ for an upper bound and to $0\leq I_j\leq \min (1,j-1)$ for a lower bound, we obtain

\begin{align*} S^\ell _n\geq | \{(I_1,\ldots ,I_n) \, : \,I_1+\ldots +I_n=\ell \textrm { and }0\leq I_j\leq \min (1,j-1) \} |=\binom {n-1}{\ell } \end{align*}

and

\begin{align*} S^\ell _n\leq | \{(I_1,\ldots ,I_n) \, : \, I_1+\ldots +I_n=\ell \textrm { and }I_j\geq 0 \} |=\binom {n+\ell -1}{\ell }\,. \end{align*}

It follows that, for any fixed $\ell$ and as $n$ goes to infinity, we have $S^\ell _n/m^\ell \rightarrow 1/\ell !$ . Since $k$ is fixed, this implies that

\begin{align*} \sum _{\ell =0}^{k-1}\frac { | \{\sigma \in {\mathcal{S}_n} \, : \, {\mathrm{Inv}}(\sigma )=\ell \} |}{n^\ell }t^\ell \longrightarrow \sum _{\ell =0}^{k-1}\frac {t^\ell }{\ell !}\,. \end{align*}

Combining the previous results, when $n$ tends to infinity, we have that

\begin{align*} \mathbb{P}\big (nT_k\gt t\big )\longrightarrow e^{-t}\sum _{\ell =0}^{k-1}\frac {t^\ell }{\ell !}=\int _t^\infty \frac {u^{k-1}e^{-u}}{(k-1)!}du\,, \end{align*}

which proves that $nT_k\overset {d}{\rightarrow }\text{GAMMA}(k,1)$ .

We now prove the second part of the theorem, stating that for any $k\in \mathbb{N}$ , the first $k$ inter-jumping times of regular Mallows processes converge to a Poisson point process. Let $t\in [0,\infty )$ and $s\gt 0$ . Also, for any $\sigma \in {\mathcal{S}_n}$ let $I=(I_j)_{j\in [n]}=\Phi ^{-1}(\sigma )$ . Since the process $(\mathcal{M}_t)_{t\in [0,\infty )}$ is regular, it has independent inversions, which implies that

(1) \begin{align} &\hspace {-0.5cm}\mathbb{P}\Big (\mathcal{M}_{\frac {t+s}{n}}=\sigma \,\Big |\,\mathcal{M}_{\frac {t}{n}}=\sigma ,(\mathcal{M}_u)_{0\leq u\lt \frac {t}{n}}\Big ) \nonumber \\[3pt] &=\mathbb{P}\Big (\forall j\in [n],\,{\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=I_j\,\Big |\,\forall j\in [n],\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\nonumber\\[3pt] &=\prod _{j=1}^n\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\,. \end{align}

Note that, whatever the value of $I_j\geq 0$ is, we have that

\begin{align*} &\hspace {-0.5cm}\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\\[3pt] &=1-\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})\gt I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big ) \end{align*}

Moreover, by definition, we have

\begin{align*} &\hspace {-0.5cm}\mathbb{E}\bigg [\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})\gt I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\bigg ]\\[3pt] &=\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})\gt I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j\Big )\\[3pt]&\leq \frac {\mathbb{P}\big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})\gt I_j\big )}{\mathbb{P}\big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j\big )}\,, \end{align*}

and by the definition of $(\mathcal{M}_t)_{t\in [0,\infty )}$ , it follows that

\begin{align*} \frac {\mathbb{P}\big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})\gt I_j\big )}{\mathbb{P}\big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j\big )}=\frac {1-\frac {t}{n}}{\left (\frac {t}{n}\right )^{I_j}-\left (\frac {t}{n}\right )^j}\cdot \frac {\left (\frac {t+s}{n}\right )^{I_j+1}-\left (\frac {t+s}{n}\right )^j}{1-\frac {t+s}{n}}\underset {n\rightarrow \infty }{\longrightarrow }0\,. \end{align*}

The previous results imply that

(2) \begin{align} \mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\longrightarrow 1 \end{align}

in probability, as $n$ goes to infinity. Now, recall that, by assumption, for any $j\in [n]$ , the process $({\mathrm{Inv}}_j(\mathcal{M}_t))_{t\in [0,\infty )}$ is increasing. This implies that, for $I_j=0$ , we have

(3) \begin{align} &\hspace {-0.5cm}\mathbb{P}\Big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t+s}{n}}\big)=0\,\Big |\,{\mathrm{Inv}}_j \big(\mathcal{M}_{\frac {t}{n}}\big)=0,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big ) \nonumber \\[3pt] &=\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=0\,\Big |\,{\mathrm{Inv}}_j \big(\mathcal{M}_{\frac {t}{n}}\big)=0\Big )\notag \\[3pt] &=\frac {\mathbb{P}\big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t+s}{n}}\big)=0\big )}{\mathbb{P}\big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=0\big )}\notag \\[3pt] &=\frac {1-\frac {t+s}{n}}{1-\left (\frac {t+s}{n}\right )^j}\cdot \frac {1-\left (\frac {t}{n}\right )^j}{1-\frac {t}{n}}\,.\end{align}

We will now combine (2) and (3) with (1) to obtain the convergence of the sequence of the first jumping times of $(\mathcal{M}_t)_{t\in [0,\infty )}$ . Fix $k\geq 0$ . For any $\sigma \in {\mathcal{S}_n}$ such that ${\mathrm{Inv}}(\sigma )\leq k$ , by separating according to whether $I_j=0$ or $I_j\gt 0$ , (1) and (3) tell us that

\begin{align*} &\hspace {-0.5cm}\mathbb{P}\Big (\mathcal{M}_{\frac {t+s}{n}}=\sigma \,\Big |\,\mathcal{M}_{\frac {t}{n}}=\sigma ,(\mathcal{M}_u)_{0\leq u\lt \frac {t}{n}}\Big )\\[3pt] &=\prod _{j\, : \,I_j\gt 0}\mathbb{P}\Big ({\mathrm{Inv}}_j(\mathcal{M}_{\frac {t+s}{n}})=I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )\\[3pt] &\hspace {0.5cm}\times \prod _{j\, : \,I_j=0}\frac {1-\frac {t+s}{n}}{1-\left (\frac {t+s}{n}\right )^j}\cdot \frac {1-\left (\frac {t}{n}\right )^j}{1-\frac {t}{n}}\,. \end{align*}

Note that $|\{j\, : \,I_j\gt 0\}|\leq {\mathrm{Inv}}(\sigma )\leq k$ . Combining this fact with the result of (2) and the assumption that the different inversion numbers are independent processes, it follows that

\begin{align*} \prod _{j\, : \,I_j\gt 0}\frac {\mathbb{P}\Big ({\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t+s}{n}}\big)=I_j\,\Big |\,{\mathrm{Inv}}_j\big(\mathcal{M}_{\frac {t}{n}}\big)=I_j,\big ({\mathrm{Inv}}_j(\mathcal{M}_u)\big )_{0\leq u\lt \frac {t}{n}}\Big )}{\frac {1-\frac {t+s}{n}}{1-\left (\frac {t+s}{n}\right )^j}\cdot \frac {1-\left (\frac {t}{n}\right )^j}{1-\frac {t}{n}}}=1+o_{\mathbb{P}}(1)\,. \end{align*}

This means that the previous result is

\begin{align*} \mathbb{P}\Big (\mathcal{M}_{\frac {t+s}{n}}=\sigma \,\Big |\,\mathcal{M}_{\frac {t}{n}}=\sigma ,(\mathcal{M}_u)_{u\lt \frac {t}{n}}\Big )&=\big (1+o_{\mathbb{P}}(1)\big )\prod _{j=1}^n\frac {1-\frac {t+s}{n}}{1-\left (\frac {t+s}{n}\right )^j}\cdot \frac {1-\left (\frac {t}{n}\right )^j}{1-\frac {t}{n}} \end{align*}

as $n\rightarrow \infty$ , where for any fixed $k\in \mathbb{N}$ the $o_{\mathbb{P}}(1)$ term is uniform over all permutations with ${\mathrm{Inv}}(\sigma )\leq k$ . Using the convergence result stated in the previous case, we know that

\begin{align*} \prod _{j=1}^n\frac {1-\left (\frac {t}{n}\right )^j}{1-\left (\frac {t+s}{n}\right )^j}\longrightarrow 1\,, \end{align*}

from which it follows that, for any $k\in \mathbb{N}$ , uniformly over permutations $\sigma$ with ${\mathrm{Inv}}(\sigma )\leq k$ ,

\begin{align*} \mathbb{P}\Big (\mathcal{M}_{\frac {t+s}{n}}=\sigma \,\Big |\,\mathcal{M}_{\frac {t}{n}}=\sigma ,(\mathcal{M}_u)_{u\lt \frac {t}{n}}\Big )&=\big (1+o_{\mathbb{P}}(1)\big )\left (\frac {1-\frac {t+s}{n}}{1-\frac {t}{n}}\right )^n=\big (1+o_{\mathbb{P}}(1)\big )e^{-s}\,. \end{align*}

This exactly corresponds to saying that the first inter jumping times of the process are asymptotically distributed as independent $\text{EXPONENTIAL}(1)$ random variables, proving the desired result.

Proof. First, note that, when $k=j-1$

\begin{align*} p_j(t,j-1)=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\left [j\sum _{\ell =0}^{j-2}(\ell +1)t^\ell -j\sum _{\ell =-1}^{j-2}(\ell +1)t^\ell \right ]=0\,, \end{align*}

which supports the fact that $B_j(t)\leq j-1$ . Now, before proving the result, we verify that $p_j$ is non-negative, a necessary assumption for this birth process to be well-defined. For $0\leq k\leq j-2$ and $t\in [0,\infty )$ , we have

\begin{align*} &(k+1)\sum _{\ell =0}^{j-2}(\ell +1)t^\ell -j\sum _{\ell =j-k-2}^{j-2}(\ell -j+k+2)t^\ell \\[3pt] &\hspace {0.5cm}=(k+1)\sum _{\ell =0}^{j-k-3}(\ell +1)t^\ell +\sum _{\ell =j-k-2}^{j-2}[(k+1)(\ell +1)-j(\ell -j+k+2)]t^\ell \,. \end{align*}

The first sum is non-negative, and by re-organizing the terms inside the second sum, we have

\begin{align*} (k+1)(\ell +1)-j(\ell -j+k+2)&=k+1-j(k+2-j)-\ell (\,j-k-1)\,. \end{align*}

Since $j-k-1\geq 1\gt 0$ , the previous equation is decreasing in $\ell$ . Using that $\ell \leq j-2$ , it follows that

\begin{align*} (k+1)(\ell +1)-j(\ell -j+k+2)&\geq (k+1)(\,j-2+1)-j(\,j-2-j+k+2)\\[3pt] &=j-k-1\gt 0\,, \end{align*}

proving that $p_j(t,k)\geq 0$ .

We now want to prove that $B_j(t)$ has the desired distribution. To do so, we prove by induction on $k$ that

\begin{align*} \mathbb{P}(B_j(t)=k)=\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }\,. \end{align*}

For $k=0$ , using that

\begin{align*} \mathbb{P}\big (B_j(t+h)=0\,\big |\,B_j(t)=0\big )=1-hp_j(t,0)+o(h)\,, \end{align*}

we have that

\begin{align*} \frac {\partial }{\partial t} (\mathbb{P} (B_j(t)=0 ) )=-p_j(t,0)\mathbb{P} (B_j(t)=0 )\,. \end{align*}

We solve this equation using that $\mathbb{P}(B_j(0)=0)=1$ and that

\begin{align*} p_j(t,0)=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\sum _{\ell =0}^{j-2}(\ell +1)t^\ell =\frac {\partial }{\partial t}\left (\log \left (\sum _{\ell =0}^{j-1}t^\ell \right )\right )\,, \end{align*}

to obtain

\begin{align*} \mathbb{P} (B_j(t)=0 )=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\,. \end{align*}

Assume now that for some $0\leq k\leq j-2$ , we have

\begin{align*} \mathbb{P}(B_j(t)=k)=\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }\,. \end{align*}

Then, the forward equation tells us that

\begin{align*} \mathbb{P} (B_j(t+h)=k+1 )&=\sum _{\ell =0}^{k+1}\mathbb{P} (B_j(t+h)=k+1\, |\,B_j(t)=\ell )\mathbb{P} (B_j(t)=\ell )\\[3pt] &= [1-hp_j(t,k+1) ]\mathbb{P} (B_j(t)=k+1 )+hp_j(t,k)\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }+o(h)\,, \end{align*}

from which it follows that

(4) \begin{align} \frac {\partial }{\partial t} (\mathbb{P} (B_j(t)=k+1 ) )=-p_j(t,k+1)\mathbb{P} (B_j(t)=k+1 )+p_j(t,k)\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }\,. \end{align}

Consider the target function for $\mathbb{P}(B_j(t)=k+1)$ :

(5) \begin{align} f(t)=\frac {t^{k+1}}{\sum _{\ell =0}^{j-1}t^\ell }\,. \end{align}

Note that

(6) \begin{align} -p_j(t,k+1) \, f(t)+p_j(t,k)\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }&=\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }[p_j(t,k)-tp_j(t,k+1)]\,, \end{align}

from which, using the definition of $p_j$ , we obtain

\begin{align*} p_j(t,k)-tp_j(t,k+1)&=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\left [(k+1)\sum _{\ell =0}^{j-2}(\ell +1)t^\ell -j\sum _{\ell =j-k-2}^{j-2}(\ell -j+k+2)t^\ell \right ]\\[3pt] &\hspace {0.5cm}-\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\left [(k+2)\sum _{\ell =0}^{j-2}(\ell +1)t^{\ell +1}-j\sum _{\ell =j-k-3}^{j-2}(\ell -j+k+3)t^{\ell +1}\right ]\,. \end{align*}

Using that

\begin{align*} (k+1)\sum _{\ell =0}^{j-2}(\ell +1)t^\ell -(k+2)\sum _{\ell =0}^{j-2}(\ell +1)t^{\ell +1}&=-(k+2)(\,j-1)t^{j-1}+\sum _{\ell =0}^{j-2}(k-\ell +1)t^\ell \,, \end{align*}

and that

\begin{align*} -j\sum _{\ell =j-k-2}^{j-2}(\ell -j+k+2)t^\ell +j\sum _{\ell =j-k-3}^{j-2}(\ell -j+k+3)t^{\ell +1}=j(k+1)t^{j-1}\,, \end{align*}

we obtain

\begin{align*} p_j(t,k)-tp_j(t,k+1)&=\frac {1}{\sum _{\ell =0}^{j-1}t^\ell }\sum _{\ell =0}^{j-1}(k-\ell +1)t^\ell \,. \end{align*}

Plug the previous formula into (6) and use the definition of $f$ from (5) to obtain that

\begin{align*} -p_j(t,k+1)\, f(t)+p_j(t,k)\frac {t^k}{\sum _{\ell =0}^{j-1}t^\ell }&=\frac {t^k}{\left (\sum _{\ell =0}^{j-1}t^\ell \right )^2}\left [\sum _{\ell =0}^{j-1}(k+1-\ell )t^\ell \right ] = \,f'(t)\,. \end{align*}

Note now that this last equation is the same as (4) where the probability $\mathbb{P}(B_j(t)=k+1)$ is replaced by $f(t)$ . Using that $f(0)=\mathbb{P}(B_j(0)=k+1)=0$ , it follows that $\mathbb{P}(B_j(t)=k+1)=f(t)$ , which completes the inductive step. This concludes the proof of the lemma.

Proof. By the definition of $B_1,\ldots ,B_n$ from Lemma3.1, we know that $(B(t))_{t\in [,\infty )}$ is a cadlag process of $\mathcal{E}_n$ satisfying all conditions of Proposition2.2. This implies that $(\mathcal{M}^B_t)_{t\in [0,\infty )}$ is a regular Mallows process. To see that it is also a Markov process, recall that $\Phi$ is a bijection, meaning that

\begin{align*} \big \{\mathcal{M}^B_t=\sigma \big \}=\big \{B(t)=\Phi ^{-1}(\sigma )\big \}=\big \{(B_1(t),\ldots ,B_n(t))=\Phi ^{-1}(\sigma )\big \}\,. \end{align*}

Now, since all the processes $(B_1(t))_{t\in [0,\infty )},\ldots ,(B_n(t))_{t\in [0,\infty )}$ are time-inhomogeneous birth processes, in particular they are Markov processes. This implies that, for any $t_1\lt \ldots \lt t_k\lt t$ and $\sigma _1,\ldots ,\sigma _k,\sigma \in {\mathcal{S}_n}$ , we have

\begin{align*} &\hspace {-0.5cm}\mathbb{P}\big (\mathcal{M}^B_t=\sigma \,\big |\,\mathcal{M}^B_{t_1}=\sigma _1,\ldots ,\mathcal{M}^B_{t_k}=\sigma _k\big )\\[3pt] &=\mathbb{P}\big (B(t)=\Phi ^{-1}(\sigma )\,\big |\,B(t_1)=\Phi ^{-1}(\sigma _1),\ldots ,B(t_k)=\Phi ^{-1}(\sigma _k)\big )\\[3pt] &=\prod _{j=1}^n\mathbb{P}\big (B_j(t)=\Phi ^{-1}(\sigma )_j\,\big |\,B_j(t_1)=\Phi ^{-1}(\sigma _1)_j,\ldots ,B_j(t_k)=\Phi ^{-1}(\sigma _k)_j\big )\,, \end{align*}

where the second inequality follows from the independence of the different coordinates of the processes $(B(t))_{t\in [0,\infty )}$ . But then, using that these are Markov processes, we obtain

\begin{align*} \mathbb{P}\big (\mathcal{M}^B_t=\sigma \,\big |\,\mathcal{M}^B_{t_1}=\sigma _1,\ldots ,\mathcal{M}^B_{t_k}=\sigma _k\big )&=\prod _{j=1}^n\mathbb{P}\big (B_j(t)=\Phi ^{-1}(\sigma )_j\,\big |\,B_j(t_k)=\Phi ^{-1}(\sigma _k)_j\big )\\[3pt] &=\mathbb{P}\big (\mathcal{M}^B_t=\sigma \,\big |\,\mathcal{M}^B_{t_k}=\sigma _k\big )\,, \end{align*}

which exactly corresponds to the fact that $(\mathcal{M}^B_t)_{t\in [0,\infty )}$ is a Markov process.

Proof. Start by fixing $t\in [0,\infty )$ and let $T=\inf \{s \, : \, \mathcal{M}_s\neq \mathcal{M}_t\}$ be the first jumping time after $t$ . Let $I=(I_j)_{j\in [n]}\in \mathcal{E}_n$ and $\sigma =\Phi (I)$ be as defined in Section 2.1 and such that ${\mathrm{Inv}}(\sigma )\lt \binom {n}{2}$ or equivalently there exists $j$ such that $I_j\lt j-1$ . Finally, let $T^{(\,j)}=\inf \{s \, : \, B_j(s)\gt B_j(t)\}$ be the next jumping time of $B_j$ , as defined in Lemma3.1. Note that $T=\min \{T^{(1)},\ldots ,T^{(n)}\}$ . We now want to characterize the distribution of $(T^{(1)},\ldots ,T^{(n)})$ .

Since $(\mathcal{M}_t)_{t\in [0,\infty )}$ has independent inversions, $T^{(1)},\ldots ,T^{(n)}$ are independent of each other and it suffices to characterize their distribution individually. Fix $j\in [n]$ . Using the rate of $B_j$ , we observe that

\begin{align*} &{\mathbb{P}}\big (B_j(t+s+h)=I_j\,\big |\,B_j(t)=I_j\big )\\[3pt] &\hspace {0.5cm}={\mathbb{P}}\big (B_j(t+s+h)=I_j\,\big |\,B_j(t+s)=I_j\big ){\mathbb{P}}\big (B_j(t+s)=I_j\,\big |\,B_j(t)=I_j\big )\\[3pt] &\hspace {0.5cm}=(1-hp_j(t,I_j)=o(h)){\mathbb{P}}\big (B_j(t+s)=I_j\,\big |\,B_j(t)=I_j\big ) \end{align*}

which means that

\begin{align*} \frac {\partial }{\partial s}{\mathbb{P}}\big (B_j(t+s)=I_j\,\big |\,B_j(t)=I_j\big )=-p_j(t,I_j){\mathbb{P}}\big (B_j(t+s)=I_j\,\big |\,B_j(t)=I_j\big )\,. \end{align*}

By solving this equation and using that ${\mathbb{P}}(B_j(t)=I_j\mid B_j(t)=I_j)=1$ , we obtain

\begin{align*} {\mathbb{P}}\big(B_j(t+s)=I_j\,\big|\,B_j(t)=I_j\big)=\exp \left (-\int _t^{t+s}p_j(u,I_j)du\right )\,. \end{align*}

Finally, observe that $\{T^{(\,j)}\gt t+s\mid B_j(t)=I_j\}=\{B_j(t+s)=I_j\mid B_j(t)=I_j\}$ so that the probability density function of $T^{(\,j)}$ conditionally given that $B_j(t)=I_j$ is

\begin{align*} \frac {\partial }{\partial s}{\mathbb{P}}\big (T^{(\,j)}\gt t+s\,\big |\,B_j(t)=I_j\big )=p_j(t+s,I_j)e^{-\int _t^{t+s}p_j(u,I_j)du}\,. \end{align*}

This provides us the distribution of the vector $(T^{(1)},\ldots ,T^{(n)})$ . Note that this formula remains true when $I_j=j-1$ since, in that case $p_j(u,I_j)=0$ .

Use the previous formula to obtain the joint distribution of the next jump and the time of the jump as

\begin{align*} &{\mathbb{P}}\big (T=T^{(J)},T\leq t+r\,\big |\,\mathcal{M}_t=\sigma \big )\\[3pt] &\hspace {0.5cm}={\mathbb{E}}\big [{\mathbb{P}}\big (T=T^{(J)},T^{(J)}\leq t+r\,\big |\,T^{(J)},\mathcal{M}_t=\sigma \big )\big ]\\[3pt] &\hspace {0.5cm}=\int _0^r\prod _{j\neq J}{\mathbb{P}}\big (T^{(\,j)}\gt t+s\,\big |\,B_j(t)=I_j\big )p_J(t+s,I_J)e^{-\int _t^{t+s}p_J(u,I_J)du}ds\\[3pt] &\hspace {0.5cm}=\int _0^rp_J(t+s,I_J)e^{-\int _t^{t+s}P(u,\sigma )du}ds\,. \end{align*}

Note that $\{T=T^{(J)}\mid \mathcal{M}_t=\sigma \}=\{\mathcal{M}_T=\sigma ^{(J)}\mid \mathcal{M}_t=\sigma \}$ where $\sigma ^{(J)}$ is obtain by increasing the $J$ -th inversion number of $\sigma$ by $1$ . Thus, the previous formula can be re-written as

(8) \begin{align} {\mathbb{P}}\big (\mathcal{M}_T=\sigma ^{(J)},T\leq t'\,\big |\,\mathcal{M}_t=\sigma \big )&=\int _t^{t'}p_J(s,I_J)e^{-\int _t^sP(u,\sigma )du}ds\,. \end{align}

We conclude the proof by using this formula to show the desired result.

In order to prove the formula of the proposition, we prove by induction on $m$ that

\begin{align*} &{\mathbb{P}}({M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m,T_m\leq t)\\[3pt] &\hspace {0.5cm}=\int _{0=u_0\lt u_1\lt \ldots \lt u_m\lt t}\prod _{k=1}^m\left (p_{j_k}(u_k,{\mathrm{Inv}}_{j_k}(\sigma _{k-1}) )e^{-\int _{u_{k-1}}^{u_k}P(u,\sigma _{k-1})du}\right )du_1\cdots du_m\,. \end{align*}

For $m=1$ , this directly follows from (8) as

\begin{align*} {\mathbb{P}}(M_0=\sigma _0,M_1=\sigma _1,T_1\leq t)&={\mathbb{P}}\big (\mathcal{M}_{T_1}=\sigma _1,T_1\leq t\,\big |\,\mathcal{M}_0=\sigma _0\big )\\[3pt] &=\int _0^t p_{j_1}(u_1,{\mathrm{Inv}}_{j_1}(\sigma _0))e^{-\int _0^{u_1}P(u,\sigma )du}du_1\,. \end{align*}

Now, assuming this holds for some $m\geq 1$ , we have that

\begin{align*} &{\mathbb{P}}({M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m,{M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t)\\[3pt] &\hspace {0.5cm}={\mathbb{E}}\big [{\mathbb{P}}\big ({M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t\,\big |\,T_m,{M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m\big )\big]\\[3pt] &\hspace {0.5cm}=\int _0^t\big [{\mathbb{P}}\big ({M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t\,\big |\,T_m=s,{M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m\big )\\[3pt] &\hspace {1cm}\times \frac {\partial }{\partial t}{\mathbb{P}}({M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m,T_m\leq t)\big |_{t=s}\big ]ds\,. \end{align*}

On one hand, by the induction hypothesis, we have that

\begin{align*} &\frac {\partial }{\partial t}{\mathbb{P}}({M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m,T_m\leq t)\big |_{t=s}\\[3pt] &\hspace {0.5cm}=\int _{0=u_0\lt u_1\lt \ldots \lt u_{m-1}\lt u_m=s}\prod _{k=1}^m\left (p_{j_k}(u_k,{\mathrm{Inv}}_{j_k}(\sigma _{k-1}))e^{-\int _{u_{k-1}}^{u_k}P(u,\sigma _{k-1})du}\right )du_1\cdots du_{m-1}\,. \end{align*}

On the other hand, by the Markov property and thanks to (8), we obtain

\begin{align*} &{\mathbb{P}}\big ({M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t\,\big |\,T_m=s,{M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m\big )\\[3pt] &\hspace {0.5cm}={\mathbb{P}}\big ({M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t\,\big |\,\mathcal{M}_s=\sigma _m\big )\\[3pt] &\hspace {0.5cm}=\int _s^tp_{j_{m+1}}(u_{m+1},{\mathrm{Inv}}_{j_{m+1}}(\sigma _m))e^{-\int _s^{u_{m+1}}P(u,\sigma _m)du}du_{m+1}\,. \end{align*}

Thus, the three previous equations combined lead to

\begin{align*} &{\mathbb{P}}({M}_0=\sigma _0,{M}_1=\sigma _1,\ldots ,{M}_m=\sigma _m,{M}_{m+1}=\sigma _{m+1},T_{m+1}\leq t)\\[3pt] &\hspace {0.5cm}=\int _{0=u_0\lt u_1\lt \ldots \lt u_{m+1}\lt t}\prod _{k=1}^{m+1}\left (p_{j_k}(u_k,{\mathrm{Inv}}_{j_k}(\sigma _{k-1}))e^{-\int _{u_{k-1}}^{u_k}P(u,\sigma _{k-1})du}\right )du_1\cdots du_mdu_{m+1}\,. \end{align*}

This proves that the induction hypothesis holds and the statement of the proposition follows by taking the limit as $t$ goes to infinity.

Proof of Theorem 1.1. Thanks to Proposition3.2, we know that there exists a cadlag Markov process which is a regular Mallows process. Conversely, using $\Phi$ as defined in Section 2.1, regular Mallows processes are fully characterized by their corresponds inversion sequence processes $({\mathrm{Inv}}_j(\mathcal{M}_t))_{t\in [0,\infty )},({\mathrm{Inv}}_2(\mathcal{M}_t))_{t\in [0,\infty )},\ldots ,({\mathrm{Inv}}_n(\mathcal{M}_t))_{t\in [0,\infty )}$ . Since regular Mallows processes have the independent inversion property, these processes are independent jump processes. Moreover, using that a regular Mallows process is by definition smooth, we know that these processes will only jump by increments of $1$ . This means that each $({\mathrm{Inv}}_j(\mathcal{M}_t))_{t\in [0,\infty )}$ for $j\in [n]$ is a time-inhomogeneous birth process, for which properties of time-homogenous birth process apply by adapting the formulas to incorporate the time parameter (see [Reference Grimmett and Stirzaker24, Section 6.8] for the properties of time-homogeneous birth processes, which extend to time-inhomogenous birth processes). In particular, for any $j\in [n]$ , since the time-inhomogenous birth process $({\mathrm{Inv}}_j(\mathcal{M}_t))_{t\in [0,\infty )}$ has a continuous distribution, it is fully characterized by its infinitesimal generator

\begin{align*} g_j(t,k)=\lim _{h\downarrow 0}\frac {1-\mathbb{P}\big ({\mathrm{Inv}}_j(\mathcal{M}_{t+h})=k\,\big |\,{\mathrm{Inv}}_j(\mathcal{M}_t)=k\big )}{h}\,, \end{align*}

just like in the case of time-homogeneous processes. Furthermore, these incremental generators $g_j$ have to satisfy the forward equation

\begin{align*} \frac {\partial }{\partial t} (\mathbb{P} ({\mathrm{Inv}}_j(\mathcal{M}_t)=k+1 ) )=g_j(t,k)\mathbb{P} ({\mathrm{Inv}}_j(\mathcal{M}_t)=k )-g_j(t,k+1)\mathbb{P} ({\mathrm{Inv}}_j(\mathcal{M}_t)=k+1 )\,. \end{align*}

Since the previous equation is the same as (4) with $p_j$ replaced by $g_j$ , it follows that $g_j=p_j$ for all $j\in [n]$ . This proves the uniqueness of such process.

Proof. We start by observing that ${\mathrm{Inv}}({M}_i)=i$ and that $(X_t)_{t\in [0,\infty )}$ only increases, so that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is monotone. Moreover, since $({M}_k)_{0\leq k\leq N}$ evolves on $\mathcal{H}_n$ and $(X_t)_{t\in [0,\infty )}$ is cadlag and only has jumps of size $1$ , it also follows that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is cadlag and smooth (while not necessarily being a Mallows process yet). We can also check that $({M}_k)_{0\leq k\leq N}$ is the discrete jumping process corresponding to $(\mathcal{M}_t)_{t\in [0,\infty )}$ and so $(\mathcal{M}_t)_{t\in [0,\infty )}$ has the discrete Markov property. We now prove that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is itself a Markov process.

Fix $t\lt t'$ and $\sigma ,\sigma '\in {\mathcal{S}_n}$ with $i={\mathrm{Inv}}(\sigma )$ and $i'={\mathrm{Inv}}(\sigma ')$ . We first observe that

\begin{align*} \{\mathcal{M}_t=\sigma \}= \{X_t=i,{M}_i=\sigma \} \end{align*}

and that the same formula holds for $t'$ , $\sigma '$ , and $i'$ . Moreover, $\{\mathcal{M}_t=\sigma ,(\mathcal{M}_s)_{s\lt t}\}$ is a function of $\{X_t=i,(X_s)_{s\lt t}\}$ and $\{{M}_i=\sigma ,({M}_k)_{0\leq k\leq i}\}$ . Combining the previous two arguments, we see that

\begin{align*} &{\mathbb{P}}\big (\mathcal{M}_{t'}=\sigma '\,\big |\,\mathcal{M}_t=\sigma ,(\mathcal{M}_s)_{s\lt t}\big )\\[3pt] &\hspace {0.5cm}={\mathbb{P}}\big ({M}_{i'}=\sigma '\,\big |\,{M}_i=\sigma ,({M}_k)_{0\leq k\lt i}\big ){\mathbb{P}}\big (X_{t'}=i'\,\big |\,X_t=i,(X_s)_{s\lt t}\big )\\[3pt] &\hspace {0.5cm}={\mathbb{P}}\big ({M}_{i'}=\sigma '\,\big |\,{M}_i=\sigma \big ){\mathbb{P}}\big (X_{t'}=i'\,\big |\,X_t=i\big )\\[3pt] &\hspace {0.5cm}={\mathbb{P}}\big (\mathcal{M}_{t'}=\sigma '\,\big |\,\mathcal{M}_t=\sigma \big )\,, \end{align*}

thus proving that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is a Markov process.

We now conclude the proof by showing that $\mathcal{M}_t$ is $\pi _{n,t}$ -distributed. Using again that $\{\mathcal{M}_t=\sigma \}=\{X_t={\mathrm{Inv}}(\sigma ),{M}_{{\mathrm{Inv}}(\sigma )}=\sigma \}$ , and by independence of $({M}_k)_{0\leq k\leq N}$ and $(X_t)_{t\in [0,\infty )}$ , we see that

\begin{align*} {\mathbb{P}}(\mathcal{M}_t=\sigma )={\mathbb{P}}(X_t={\mathrm{Inv}}(\sigma )){\mathbb{P}}({M}_{{\mathrm{Inv}}(\sigma )}=\sigma)\,. \end{align*}

But now, using the given distribution of $(X_t)_{t\in [0,\infty )}$ and $({M}_k)_{0\leq k\leq N}$ , we obtain

\begin{align*} {\mathbb{P}}(\mathcal{M}_t=\sigma )=\frac {|L_{{\mathrm{Inv}}(\sigma )}|t^{{\mathrm{Inv}}(\sigma )}}{Z_{n,t}}\cdot \frac {1}{|L_{{\mathrm{Inv}}(\sigma )}|}=\frac {t^{{\mathrm{Inv}}(\sigma )}}{Z_{n,t}}\,. \end{align*}

This is exactly the Mallows distribution, which concludes the proof that $(\mathcal{M}_t)_{t\in [0,\infty )}$ is a smooth doubly Markovian Mallows process.

Proof of Theorem 1.5. Using Lemma3.4, it suffices to show the existence of $({M}_k)_{0\leq k\leq N}$ and $(X_t)_{t\in [0,\infty )}$ as stated. The existence of $({M}_k)_{0\leq k\leq N}$ is proven in [Reference Acan and Pittel1, Theorem 2.3], so we now show that we can define $(X_t)_{t\in [0,\infty )}$ as desired.

Define the time-inhomogeneous birth process $(X_t)_{t\in [0,\infty )}$ with infinitesimal rates given by

\begin{align*} {\mathbb{P}}(X_{t+h}=k+\ell \mid X_t=k)&=\left \{\begin{array}{ll} 1-hr_k(t)+o(h) &\quad \text{if }\ell =0 \\[3pt] hr_k(t)+o(h) &\quad \text{if }\ell =1 \\[3pt] o(h) &\quad \textrm {otherwise}\,, \end{array}\right . \end{align*}

where

\begin{align*} r_k(t)=-\frac {Z_{n,t}}{|L_k|t^k}\frac {d}{dt}\left (\sum _{j=0}^k\frac {|L_j|t^{\, j}}{Z_{n,t}}\right )=-\frac {1}{{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k)}\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k) \end{align*}

and $\sigma _{n,t}$ is $\pi _{n,t}$ -distributed. We prove that $(X_t)_{t\in [0,\infty )}$ has the desired distribution by proving by induction on $k$ that

\begin{align*} {\mathbb{P}}(X_t=k)=\frac {|L_k|t^k}{Z_{n,t}}={\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k)\,. \end{align*}

We also note that all rate functions $r_k$ are positive, since $t\mapsto {\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k)$ is decreasing. For $k=0$ , we use the rate function $r_0$ to see that

\begin{align*} {\mathbb{P}}(X_{t+h}=0)={\mathbb{P}}(X_{t+h}=0,X_t=0)=(1-hr_0(t)+o(h)){\mathbb{P}}(X_t=0)\,. \end{align*}

This implies that

\begin{align*} \frac {d}{dt}{\mathbb{P}}(X_t=0)=-r_0(t){\mathbb{P}}(X_t=0)=\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=0) \end{align*}

which proves the induction hypothesis for $k=0$ since ${\mathbb{P}}(X_0=0)={\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,0})=0)=1$ . Assume now that

\begin{align*} {\mathbb{P}}(X_t=k)=\frac {|L_k|t^k}{Z_{n,t}}={\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k)\,. \end{align*}

for some $k\lt N$ and use the forward equation to see that

\begin{align*} {\mathbb{P}}(X_{t+h}=k+1)&=\sum _{\ell =0}^{k+1}{\mathbb{P}}(X_{t+h}=k\mid X_t=\ell ){\mathbb{P}}(X_t=\ell )\\[3pt] &=(1-hr_{k+1}(t)){\mathbb{P}}(X_t=k+1)+hr_k(t){\mathbb{P}}(X_t=k)+o(h)\,, \end{align*}

which leads to

\begin{align*} \frac {d}{dt}{\mathbb{P}}(X_t=k+1)=r_k(t){\mathbb{P}}(X_t=k)-r_{k+1}(t){\mathbb{P}}(X_t=k+1)\,. \end{align*}

Now, using the induction hypothesis on ${\mathbb{P}}(X_t=k)$ and the definition of $r_k$ and $r_{k+1}$ , we obtain

\begin{align*} \frac {d}{dt}{\mathbb{P}}(X_t=k+1)=\frac {{\mathbb{P}}(X_t=k+1)}{{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k+1)}\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k+1)-\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k)\,. \end{align*}

We observe that the function $t\mapsto {\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k+1)$ satisfies the same equation, that is

\begin{align*} \frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k+1)=\frac {{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k+1)}{{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})=k+1)}\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k+1)-\frac {d}{dt}{\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,t})\leq k)\,, \end{align*}

and furthermore that ${\mathbb{P}}(X_0=k+1)={\mathbb{P}}({\mathrm{Inv}}(\sigma _{n,0})=k+1)=0$ . By uniqueness of the dimension of the solutions to a differential equation of the first order, this proves the induction hypothesis. The theorem thus follows from defining such $({M}_k)_{0\leq k\leq N}$ and $(X_t)_{t\in [0,\infty )}$ independently and by applying Lemma3.4.

Proof. First of all, consider $\phi (t)=\frac {\log (1-u(1-t^{\, j}))}{\log t}$ . Then, we have

\begin{align*} \phi '(t)&=\frac {1}{(\log t)^2}\left [\frac {jut^{\, j-1}}{1-u(1-t^{\, j})}\log t-\frac {1}{t}\log \big(1-u \big(1-t^{\, j} \big)\big)\right ]\\[3pt] &=\frac {1}{t(\log t)^2}\left [\frac {ut^{\, j}}{1-u(1-t^{\, j})}\log (t^{\, j})-\log \big(1-u \big(1-t^{\, j} \big)\big)\right ]\,. \end{align*}

Now, by the concavity of $\log$ , we know that

\begin{align*} \lambda \log \frac {1}{x}+(1-\lambda )\log \frac {1}{y}\geq \log \left (\frac {1}{\lambda x+(1-\lambda )y}\right )\,. \end{align*}

Apply this formula with $\lambda =\frac {ut^{\, j}}{1-u(1-t^{\, j})}$ , $x=\frac {1}{t^{\, j}}$ and $y=1$ to obtain

\begin{align*} \frac {ut^{\, j}}{1-u(1-t^{\, j})}\log (t^{\, j})\geq \log \left (\frac {1}{\frac {u}{1-u(1-t^{\, j})}+\frac {1-u}{1-u(1-t^{\, j})}}\right )=\log \big(1-u \big(1-t^{\, j} \big)\big)\,, \end{align*}

which proves that $\phi '(t)\geq 0$ . This proves that $f_j(\cdot; \,u)$ is increasing on $(0,1)$ and on $(1,\infty )$ . To conclude the proof of the first claim of the lemma, note that $\phi$ can continuously be extended to $0$ and $1$ and corresponds to the previous definition, thus $f_j(\cdot; \,u)$ is cadlag.

For the second part of the lemma, first note that the statement holds for $t=0$ and $t=1$ . Then, for $t\gt 0$ with $t\neq 1$ , and for all $0\leq k\leq j-1$ , we have

\begin{align*} \mathbb{P}\Big (\,f_j(t; \, U)=k\Big )&=\mathbb{P}\left (k\leq \frac {\log (1-U(1-t^{\, j}))}{\log t}\lt k+1\right )\\[3pt] &=\mathbb{P}\left (\frac {t^k-1}{t^{\, j}-1}\leq U\lt \frac {t^{k+1}-1}{t^{\, j}-1}\right )\\[3pt] &=\frac {t^k(t-1)}{t^{\, j}-1}\,, \end{align*}

which is the desired formula. This concludes the proof of the proposition.