proved using (4.33). The proof of (4.77) is straightforward. ∎

######  Proposition 4.13.

Let $\overline{I},\overline{J}\in\mathcal{X}^{k}$. Let $\tau_{1},\tau_{2}>0$.
For all $n\in\mathbb{N}$, on the set

$\displaystyle\mathcal{A}^{\overline{I}}_{\tau_{1}n}\cap\mathcal{A}^{\overline{J}}_{\tau_{2}n}\cap
A^{\mathcal{L}^{\tau_{1}}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)}\Big{)},\mathcal{L}^{\tau_{2}}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{J})\big{)}\Big{)}}_{n}$
$\displaystyle
d^{(k)}\Big{(}\mathcal{L}^{\tau_{1}}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)}\Big{)},\mathcal{L}^{\tau_{2}}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{J})\big{)}\Big{)}\Big{)}$
(4.78) $\displaystyle\leq
2^{k4^{k+3}n}d^{(k)}\big{(}\mathcal{L}^{\tau_{1}}\big{(}\Psi(\overline{I})\big{)},\mathcal{L}^{\tau_{2}}\big{(}\Psi(\overline{J})\big{)}\big{)}+7^{k}k\sup_{|j|\leq
2^{k}\tau_{1}n}\Big{[}\max_{1\leq i\leq
k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]}$
$\displaystyle+7^{k}k\sup_{|j|\leq 2^{k}\tau_{2}n}\Big{[}\max_{1\leq i\leq
k}|J^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{J}^{i+1,q}_{j}|\Big{]}+2^{-n+2}.$

###### Proof.

For $\tau>0$, Lemma 4.11 implies that on the set
$\mathcal{A}^{\overline{I}}_{\tau n}$

$\displaystyle
d^{(k)}_{n}\Big{(}\mathcal{L}^{\tau}\big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)}\big{)},\mathcal{L}^{\tau}\big{(}\Phi^{k}\big{(}\Psi(\overline{I})\big{)}\big{)}\Big{)}\stackrel{{\scriptstyle\eqref{si2}}}{{=}}d^{(k)}_{\tau
n}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)},\Phi^{k}\big{(}\Psi(\overline{I})\big{)}\Big{)}$
(4.79) $\displaystyle\leq 7^{k}k\sup_{|j|\leq 2^{k}\tau n}\Big{[}\max_{1\leq
i\leq k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]},$

and a similar bound holds for $\overline{J}$. From (4.79) and the fact that
$d^{(k)}(\overline{f},\overline{g})\leq
d^{(k)}_{n}(\overline{f},\overline{g})+2^{-n}$ we conclude that on
$\mathcal{A}^{\overline{I}}_{\tau n}$

$\displaystyle
d^{(k)}\Big{(}\mathcal{L}^{\tau}\big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)}\big{)},\mathcal{L}^{\tau}\big{(}\Phi^{k}\big{(}\Psi(\overline{I})\big{)}\big{)}\Big{)}\leq
7^{k}k\sup_{|j|\leq 2^{k}\tau n}\Big{[}\max_{1\leq i\leq
k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]}+2^{-n},$ (4.80)

and a similar bound holds for $\overline{J}$ as well. For
$\tau_{1},\tau_{2}>0$, from Lemma 4.9, on the event
$A^{\mathcal{L}^{\tau_{1}}\big{(}\Psi(\overline{I})\big{)},\mathcal{L}^{\tau_{2}}\big{(}\Psi(\overline{J})\big{)}}_{n}$

$\displaystyle
d^{(k)}\Big{(}\mathcal{L}^{\tau_{1}}\big{(}\Phi^{k}\big{(}\Psi(\overline{I})\big{)}\big{)},\mathcal{L}^{\tau_{2}}\big{(}\Phi^{k}\big{(}\Psi(\overline{J})\big{)}\big{)}\Big{)}\stackrel{{\scriptstyle\eqref{si}}}{{=}}d^{(k)}\Big{(}\Phi^{k}\big{(}\mathcal{L}^{\tau_{1}}\big{(}\Psi(\overline{I})\big{)}\big{)},\Phi^{k}\big{(}\mathcal{L}^{\tau_{2}}\big{(}\Psi(\overline{J})\big{)}\big{)}\Big{)}$
(4.81) $\displaystyle\leq
2^{k4^{k+3}n}d^{(k)}\big{(}\mathcal{L}^{\tau_{1}}\big{(}\Psi(\overline{I})\big{)},\mathcal{L}^{\tau_{2}}\big{(}\Psi(\overline{J})\big{)}\big{)}+2^{-n}.$

From (4.80)–(4.81) we obtain (4.78). ∎

######  Lemma 4.14.

Let $\bm{\rho}=(\rho_{1},...,\rho_{k})\in\mathbb{R}_{+}^{k}$ be a decreasing
vector and let $\overline{I}\sim\nu_{\bm{\rho}}$, then

$\displaystyle\mathbb{P}\Big{(}(\mathcal{A}^{\overline{I}}_{N})^{c}\Big{)}\leq
4k^{2}e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}N}.$ (4.82)

where

$\displaystyle\Delta_{min}=\min_{2\leq i\leq k}\rho_{i-1}-\rho_{i}.$

###### Proof.

We begin with bounding the probability of the following event for $1\leq l\leq
k-2$

$\displaystyle
A^{2^{k-2-l}N}\Big{(}\Psi(I^{k-l-1}),\Psi\big{(}[\mathcal{D}^{(l+1)}(I^{k-l},...,I^{k})]_{m}\big{)}\Big{)}\quad\text{for
$1\leq m\leq l+1$}.$ (4.83)

Recall that
$\mathcal{D}^{(l+1)}(I^{k-l},...,I^{k})\sim\mu_{(\rho_{k-l},...,\rho_{k})}$,
so that for $1\leq m\leq l+1$ $[\mathcal{D}^{(l+1)}(I^{k-l},...,I^{k})]_{m}$
is a sequence of i.i.d. r.v.’s with marginal distribution
$\mathrm{Exp}(\rho_{k-l+m-1})$. To simplify notation let us denote
$\hat{I}^{1}=I^{k-l-1}$ and
$\hat{I}^{2}=[\mathcal{D}^{(l+1)}(I^{k-l},...,I^{k})]_{m}$. The event in
(4.83) equals

$\displaystyle\Big{\\{}$
$\displaystyle\underset{s\leq-2^{k-2-l}N}{\mathrm{argmax\,\,}}\Psi(\hat{I}^{1})(-2^{k-2-l}N)-\Psi(\hat{I}^{1})(s)-[\Psi(\hat{I}^{2})(-2^{k-2-l}N)-\Psi(\hat{I}^{2})(s)]\geq-2^{k-1-l}N\Big{\\}}$
$\displaystyle=\Big{\\{}\underset{s\leq-2^{k-2-l}N}{\mathrm{argmax\,\,}}\Psi(\hat{I}^{1}-\hat{I}^{2})(-2^{k-2-l}N)-\Psi(\hat{I}^{1}-\hat{I}^{2})(s)\geq-2^{k-1-l}N\Big{\\}},$

where we used the linearity of $\Psi$. $\hat{I}^{1}$ is a sequence of i.i.d.
r.v.’s with marginal $\mathrm{Exp}(\rho_{k-l-1})$, the sequence
$\hat{I}^{1}-\hat{I}^{2}$ is i.i.d. with marginal
$\hat{I}^{1}_{0}-\hat{I}^{2}_{0}\sim\mathrm{Exp}(\rho_{k-l-1})-\mathrm{Exp}(\rho_{k-l+m-1})$.
We now use Lemma A.12 with $F=\Psi(\hat{I}^{1}-\hat{I}^{2})$,
$\mathcal{C}_{N}=0$ for all $N\geq 1$ and $\Delta=\rho_{k-l-1}-\rho_{k-l+m-1}$
, which implies that (note that although the supremum in Lemma A.12 is in the
opposite direction, the two r.v. have the same distribution)

$\displaystyle\mathbb{P}\Big{(}\underset{s\leq-2^{k-2-l}N}{\mathrm{argmax\,\,}}\Psi(\hat{I}^{1}-\hat{I}^{2})(-2^{k-2-l}N)-\Psi(\hat{I}^{1}-\hat{I}^{2})(s)<-2^{k-1-l}N\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\underset{s\leq
0}{\mathrm{argmax\,\,}}\,\,\Psi(\hat{I}^{1}-\hat{I}^{2})(0)-\Psi(\hat{I}^{1}-\hat{I}^{2})(s)<-2^{k-2-l}N\Big{)}$
$\displaystyle\leq
4e^{-\frac{(\rho_{k-l+m-1}-\rho_{k-l-1})^{2}2^{k-2-l}}{12\rho_{k-l-1}^{2}}N}\leq
4e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}N},$

where the equality follows from the stationarity of $\hat{I}^{1}-\hat{I}^{2}$
and the that $\mathcal{C}_{N}=0$ for all $N\geq 1$. Using union bound

$\displaystyle\mathbb{P}\Big{(}(A^{\overline{I}})^{c}\Big{)}\leq\sum_{l=1}^{k-2}\sum_{m=1}^{l+1}\Big{[}A^{2^{k-2-l}N}\Big{(}\Psi(I^{k-l-1}),\Psi\big{(}[\mathcal{D}^{(l+1)}(I^{k-l},...,I^{k})]_{m}\big{)}\Big{)}\Big{]}^{c}$
$\displaystyle\leq 4k^{2}e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}N}.$

∎

Recall the event $A_{R}^{\overline{f},\overline{g}}$ in (4.37). The following
result gives an upper bound on the probability of its complement.

######  Lemma 4.15.

Let $\bm{\rho}=(\rho_{1},...,\rho_{k})$ be a decreasing vector in
$\mathbb{R}_{+}^{k}$. Assume $\overline{I}\sim\nu_{\bm{\rho}}$. Define

$\displaystyle\Delta_{min}$ $\displaystyle=\min_{1\leq i\leq
k-1}\rho_{i}-\rho_{i+1}$ $\displaystyle\Delta_{max}$
$\displaystyle=\max_{1\leq i\leq k-1}\rho_{i}-\rho_{i+1}.$

For $\mu\in\mathbb{R}$ and $\tau>0$ let

$\displaystyle\overline{f}^{\tau}$
$\displaystyle\sim\mathcal{L}^{\tau}\big{(}\Psi(\overline{I}-\bm{\mu}^{k})\big{)}.$
(4.84)

Then for $R\in\mathbb{N}$, such that $\tau
R>\big{[}24\Delta_{min}^{-2}\rho_{1}\big{]}\vee\Big{[}\frac{\rho_{1}^{2}48}{\Delta_{min}}\times\frac{7^{k}k}{\rho_{k}}\Big{]}$

$\displaystyle\mathbb{P}\Big{(}\big{(}\bigcap_{\begin{subarray}{c}1\leq j\leq
k-1\\\ 1\leq i\leq
j\end{subarray}}A^{\overline{f}^{\tau},R}_{j,i}\big{)}^{c}\Big{)}\leq$ (4.85)
$\displaystyle
k^{2}\Big{[}2^{4}k^{2}e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau
R}+2^{3k+4}k^{2}(\tau
R+5)e^{-\frac{\Delta_{min}}{\rho_{1}^{2}48}\times\frac{\rho_{k}}{7^{k}k}\tau
R}\Big{]}.$

###### Proof.

We first claim that it is enough to show the result for

$\displaystyle\overline{f}^{\tau}$
$\displaystyle\sim\mathcal{L}^{\tau}\big{(}\Psi(\overline{I})\big{)}$ (4.86)

a translated version of the functions in (4.84), where we simplify
$\overline{f}=\mathcal{L}^{1}\big{(}\Psi(\overline{I})\big{)}$. To see that,
we consider the different sets $A^{\overline{f}^{\tau},R}_{j,i}$ in (4.85). To
see that for any $\tau>0$ the event $A^{\overline{f}^{\tau},R}_{j,i}$ is
invariant under the translation of $\overline{f}^{\tau}$, observe that for
$t\in\mathbb{R}$

$\displaystyle
P_{t}\Bigg{(}\mathcal{L}^{\tau}\big{(}\Psi(I^{j}+\bm{\mu})\big{)},\Phi_{i}^{k-j}\Big{(}\mathcal{L}^{\tau}(\Psi(I^{j+1}+\bm{\mu})),...,\mathcal{L}^{\tau}(\Psi(I^{k}+\bm{\mu}))\Big{)}\Bigg{)}$
$\displaystyle=P_{t}\Big{(}f^{\tau}_{j}-\Psi(\tau\bm{\mu}),\Phi_{i}^{k-j}(f^{\tau}_{j+1}-\Psi(\tau\bm{\mu}),...,f^{\tau}_{k}-\Psi(\tau\bm{\mu}))\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{const2}}}{{=}}P_{t}\big{(}f^{\tau}_{j}-\Psi(\tau\bm{\mu}),\Phi_{i}^{k-j}(f^{\tau}_{j+1},...,f^{\tau}_{k})-\Psi(\tau\bm{\mu})\big{)}$
$\displaystyle=P_{t}\big{(}f^{\tau}_{j},\Phi_{i}^{k-j}(f^{\tau}_{j+1},...,f^{\tau}_{k})\big{)},$

where in the last line we used that $P_{t}(\cdot,\cdot)$ is invariant under
translations. We thus conclude that $A^{\overline{f}^{\tau},R}_{j,i}$ is
invariant under translation of $\overline{f}^{\tau}$. We have proved that it
is enough to show the result for $\overline{f}^{\tau}$ as in (4.86). We
continue with bounding the probability of the complement of the event
$A^{\overline{f}^{\tau},R}_{j,i}$ from (4.37) (the reader may find it helpful
to recall (4.26) and (4.27)) for $1\leq j\leq k-1$ and $1\leq i\leq k-j$ i.e.

$\displaystyle\mathbb{P}\Big{(}P_{-a_{j}^{R}}\big{(}f^{\tau}_{j},\Phi_{i}^{k-j}(f^{\tau}_{j+1},...,f^{\tau}_{k})\big{)}<-2a_{j}^{R}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\underset{s\leq-
a_{j}^{R}}{\mathrm{argmax\,\,}}f^{\tau}_{j}(-a_{j}^{R})-\Phi_{i}^{k-j}(f^{\tau}_{j+1},...,f^{\tau}_{k})(-a_{j}^{R})$
$\displaystyle-[f^{\tau}_{j}(s)-\Phi_{i}^{k-j}(f^{\tau}_{j+1},...,f^{\tau}_{k})(s)]<-2a_{j}^{R})\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\underset{s\leq-\tau
a_{j}^{R}}{\mathrm{argmax\,\,}}f_{j}(-\tau
a_{j}^{R})-\Phi_{i}^{k-j}(f_{j+1},...,f_{k})(-\tau a_{j}^{R})$
$\displaystyle-[f_{j}(s)-\Phi_{i}^{k-j}(f_{j+1},...,f_{k})(s)]<-2\tau
a_{j}^{R})\Big{)}$ $\displaystyle=\mathbb{P}\Big{(}\underset{s\leq
0}{\mathrm{argmax\,\,}}\Phi_{i}^{k-j}(f_{j+1},...,f_{k})(s)-f_{j}(s)<-\tau
a_{j}^{R}\Big{)}$ $\displaystyle=\mathbb{P}\Big{(}\underset{0\leq
s}{\mathrm{argmax\,\,}}f_{j}(s)-\Phi_{i}^{k-j}(f_{j+1},...,f_{k})(s)>\tau
a_{j}^{R}\Big{)}$ (4.87)

where in the last two inequalities we used the invariance of the distribution
of $\overline{f}$ with respect to translation. Next we would like to use Lemma
A.12 to bound (4.2.3). In order to do that, we approximate
$\Phi^{k-j}(f_{j+1},...,f_{k})$ by
$\Psi(\mathcal{D}^{(k-j)}(I^{j+1},...,I^{k}))$ using Lemma 4.11. By Lemma
4.11, on $\mathcal{A}^{\overline{I}}_{n}$, for $1\leq j\leq k-1$ and $1\leq
i\leq k-j$

$\displaystyle
d_{n}\Big{(}\Psi\big{(}[\mathcal{D}^{(k-j)}(I^{j+1},...,I^{k})]_{i}\big{)},\Phi^{k-j}_{i}(f_{j+1},...,f_{k})\Big{)}\leq\mathcal{C}_{n}\quad
n\geq 1,$ (4.88)

where the random variable $\mathcal{C}_{n}$, which is independent from $i,j$,
is given by the right hand side of (4.71) with $l=k$ i.e.

$\displaystyle\mathcal{C}_{n}=16\sum_{i=0}^{k-2}7^{k-2-i}\sup_{|j|\leq
2^{k-1-i}n+2}\Big{[}|I^{k-1-i}_{j}|+\sup_{1\leq q\leq
i+1}|\tilde{I}^{i+1,q}_{j}|\Big{]}$ $\displaystyle\leq 7^{k}k\sup_{|j|\leq
2^{k}n}\Big{[}\max_{1\leq i\leq
k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]}.$ (4.89)

From (4.88), for $n\geq 1$

$\displaystyle
d_{n}\Big{(}\Psi\big{(}I^{j}-[\mathcal{D}^{(k-j)}(I^{j+1},...,I^{k})]_{i}\big{)},f_{j}-\Phi^{k-j}_{i}(f_{j+1},...,f_{k})\Big{)}\leq\mathcal{C}_{n}.$

Next we bound the tail of $\mathcal{C}_{n}$. Notice that by our assumption on
the distribution of $\overline{I}$, the marginal distribution of the sequences
$\\{I^{i}\\}_{i=1}^{k}$ and $\\{\tilde{I}^{i,q}\\}_{1\leq i\leq k-1,1\leq
q\leq i+1}$ is exponential with rates in $\bm{\rho}$ and $\bm{\zeta}$. Using
union bound on all possible r.v.s in (4.89), we obtain the following bound

$\displaystyle\mathbb{P}\big{(}\mathcal{C}_{n}>t\big{)}\leq(2^{k}n)(2k^{2})e^{-7^{-k}k^{-1}\rho_{k}t}\leq
nCe^{-c_{1}t},$ (4.90)

as $(2^{k}n)$ accounts for the length of the block of the supremum while
$(2k^{2})$ bounds the number of different sequences involved in (4.89). For
$M\in\mathbb{N}$ define

$\displaystyle\tilde{\mathcal{A}}_{M}=\bigcap_{i=2}^{\infty}\mathcal{A}^{\overline{I}}_{iM}.$

From Lemma 4.14, for $M\geq\frac{12\rho_{1}}{\Delta_{min}^{2}}$

$\displaystyle\mathbb{P}\Big{(}\big{(}\tilde{\mathcal{A}}_{M}\big{)}^{c}\Big{)}\leq
4k^{2}\sum_{i=2}^{\infty}(e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}}})^{i}\leq
4k^{2}\frac{e^{-2\frac{\Delta_{min}^{2}}{12\rho_{1}}M}}{1-e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}}M}}\leq
8k^{2}e^{-\frac{\Delta_{min}^{2}}{6\rho_{1}}M}.$ (4.91)

We are now ready to use Lemma A.12. First note that $I^{j}$ and
$[\mathcal{D}^{(k-j)}(I^{j+1},...,I^{k})]_{i}$ are independent i.i.d.
sequences of marginals $\mathrm{Exp}(\rho_{j})$ and $\mathrm{Exp}(\rho_{j+i})$
respectively. Set

$\displaystyle
F^{R}_{j}=\begin{cases}f_{j}-\Phi^{k-j}_{i}(f_{j+1},...,f_{k})&\text{on
$\tilde{\mathcal{A}}_{\tau a_{j}^{R}}$}\\\
\Psi\big{(}I^{j}-[\mathcal{D}^{(k-j)}(I^{j+1},...,I^{k})]_{i}\big{)}&\text{on
$\big{(}\tilde{\mathcal{A}}_{\tau a_{j}^{R}}\big{)}^{c}$}.\end{cases}$

$\Delta=\rho_{j}-\rho_{j+i}$, $\rho=\rho_{j+i}$ and apply Lemma A.12 to obtain
for $\Delta_{max}\leq 2(\rho_{k})/5$ and

$\displaystyle\tau a_{j}^{R}>\tau
R>\big{[}24\Delta_{min}^{-2}\rho_{1}\big{]}\vee\Big{[}\frac{\rho_{1}^{2}48}{\Delta_{min}}\times\frac{7^{k}k}{\rho_{k}}\Big{]}$
$\displaystyle\mathbb{P}\Big{(}\underset{0\leq
s}{\mathrm{argmax\,\,}}F^{R}_{j}(s)>\tau a_{j}^{R}\Big{)}$ $\displaystyle\leq
e^{-\frac{(\rho_{j}-\rho_{j+i})^{2}}{12\rho_{j+i}^{2}}\tau
a_{j}^{R}}+\sum_{l=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(l+1)\tau
a_{j}^{R}}\geq\tau
a_{j}^{R}\frac{l(\rho_{j}-\rho_{j+i})}{\rho_{j+i}^{2}48}\Big{)}$
$\displaystyle\leq e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau
a_{j}^{R}}+\sum_{l=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(l+1)\tau
a_{j}^{R}}\geq\tau a_{j}^{R}\frac{l\Delta_{min}}{\rho_{1}^{2}48}\Big{)}$
(4.92) $\displaystyle\leq e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau
R}+4^{k}(\tau R+5)6Ce^{-c_{4}\tau R}$ (4.93)

where

$\displaystyle
c_{4}=\frac{\Delta_{min}}{\rho_{1}^{2}48}\times\frac{\rho_{k}}{7^{k}k}.$
(4.94)

The derivation of (4.93) can be found in the appendix A.4. As the difference
between $F^{j}_{R}$ and $f_{j}-\Phi^{k-j}_{i}(f_{j+1},...,f_{k})$ takes place
on the complement of the event $\tilde{\mathcal{A}}_{\tau a_{j}^{R}}$, from
(4.93),

$\displaystyle\mathbb{P}\Big{(}A^{\overline{f}^{\tau},R}_{j,i}\Big{)}\leq\mathbb{P}\Big{(}\underset{0\leq
s}{\mathrm{argmax\,\,}}f_{j}(s)-\Phi^{k-j}_{i}(f_{j+1},...,f_{k})(s)>\tau
a_{j}\Big{)}$ $\displaystyle\leq
e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau R}+4^{k}(\tau
R+5)6Ce^{-c_{4}\tau R}+\mathbb{P}\Big{(}\big{(}\tilde{\mathcal{A}}_{\tau
a_{j}^{R}}\big{)}^{c}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ub51}}}{{\leq}}e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau
R}+4^{k}(\tau R+5)6Ce^{-c_{4}\tau
R}+8k^{2}e^{-\frac{\Delta_{min}^{2}}{6\rho_{1}}\tau R},$ (4.95)

where we used $R<a_{j}^{R}$. As the number of different pairs of indices
$(i,j)$ in (4.37) is at most $k^{2}$,

$\displaystyle\mathbb{P}\Big{(}\Big{[}\bigcap_{\begin{subarray}{c}1\leq j\leq
k-1\\\ 1\leq i\leq
j\end{subarray}}A^{\overline{f}^{\tau},R}_{j,i}\Big{]}^{c}\Big{)}$
$\displaystyle\leq k^{2}\Big{[}e^{-\frac{\Delta_{min}^{2}}{12\rho_{1}^{2}}\tau
R}+4^{k}(\tau R+5)6Ce^{-c_{4}\tau
R}+8k^{2}e^{-\frac{\Delta_{min}^{2}}{6\rho_{1}}\tau R}\Big{]}.$

Plugging the constant $c_{4}$ from (4.94) and $C=2^{k+1}k^{2}$ in the last
display and rearranging terms we obtain the result. ∎

######  Proposition 4.16.

Let $\overline{t}\in\mathbb{R}^{k}$ be an increasing sequence. For each
$N\in\mathbb{N}$ let $\bm{\rho}^{N}$ be defined through

$\displaystyle\rho^{N}_{i}=1/2-\frac{t_{i}}{4}N^{-1/3}.$

Let $\overline{I}^{N}\sim\nu_{\bm{\rho}^{N}}$. Then there exists a random
variable $X_{\overline{t}}\in\mathcal{S}^{k}$ such that

$\displaystyle
N^{-1/3}\mathcal{L}^{N^{2/3}}\big{(}\Psi(\mathcal{D}^{(k)}(\overline{I}^{N}-\bm{2}^{k}))\big{)}\Rightarrow
X_{\overline{t}},$ (4.96)

where the convergence is with respect to the weak topology on
$\mathcal{S}^{k}$.

###### Proof.

Fix $\epsilon>0$. Let us denote

$\displaystyle Q^{N}$
$\displaystyle=N^{-1/3}\mathcal{L}^{N^{2/3}}\Big{(}\Psi\big{(}\mathcal{D}^{(k)}(\overline{I})\big{)}\Big{)}$
(4.97) $\displaystyle Y^{N}$
$\displaystyle=N^{-1/3}\mathcal{L}^{N^{2/3}}\big{(}\Psi(\overline{I}^{N}-\bm{2}^{k})\big{)}$
$\displaystyle Z^{N}$
$\displaystyle=N^{-1/3}\mathcal{L}^{N^{2/3}}\big{(}\Psi(\mathcal{D}^{(k)}(\overline{I}^{N}-\bm{2}^{k}))\big{)}.$

By Proposition 4.13, on the set
$\mathcal{A}^{\overline{I}^{N_{1}}}_{N_{1}^{2/3}n}\cap\mathcal{A}^{\overline{I}^{N_{2}}}_{N_{2}^{2/3}n}\cap
A^{Q^{N_{1}},Q^{N_{2}}}_{n}$

$\displaystyle d^{(k)}\Big{(}Z^{N_{1}},Z^{N_{2}}\Big{)}$ $\displaystyle\leq
2^{k4^{k+3}n}d^{(k)}\big{(}Y^{N_{1}},Y^{N_{2}}\big{)}$ (4.98)
$\displaystyle+N_{1}^{-1/3}7^{k}k\sup_{|j|\leq
2^{k}N_{1}^{2/3}n}\Big{[}\max_{1\leq i\leq
k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]}$ (4.99)
$\displaystyle+N_{2}^{-1/3}7^{k}k\sup_{|j|\leq
2^{k}N_{2}^{2/3}n}\Big{[}\max_{1\leq i\leq
k}|J^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{J}^{i+1,q}_{j}|\Big{]}+2^{-n+2}.$

For $N\in\mathbb{N}$ let

$\displaystyle B^{N}_{\epsilon}=\Big{\\{}N^{-1/3}7^{k}k\sup_{|j|\leq
2^{k}N^{2/3}n}\Big{[}\max_{1\leq i\leq
k}|I^{i}_{j}|\vee\max_{\begin{subarray}{c}0\leq i\leq k-2\\\ 1\leq q\leq
i+1\end{subarray}}|\tilde{I}^{i+1,q}_{j}|\Big{]}<\frac{\epsilon}{4}\Big{\\}}.$

By Donsker’s invariance principal

$\displaystyle Y^{N}\Rightarrow W^{\overline{t}}$ (4.100)

where
$W^{\overline{t}}=(W^{\overline{t}}_{1},...,W^{\overline{t}}_{k})\in\mathcal{S}^{k}$
is a vector of independent elements where $W^{\overline{t}}_{i}$ is a bi-
infinite Brownian motion with drift $t_{i}$ and diffusivity $2$, conditioned
to vanish at the origin. Without loss of generality, we may assume that the
sequence $\\{Y^{N}\\}_{N\in\mathbb{N}}$ is such that for any
$\delta_{1},\delta_{2}>0$ there exists $N_{0}(\delta_{1},\delta_{2})$ such
that for any $N_{0}<N_{1},N_{2}$

$\displaystyle\mathbb{P}\big{(}d^{(k)}(Y^{N_{1}},Y^{N_{2}})>\delta_{1}\big{)}<\delta_{2}.$
(4.101)

Setting $\delta_{1}=\big{[}2^{k4^{k+3}2+2}\epsilon^{k4^{k+3}+1}\big{]}^{-1}$,
For $\lceil 8+\log_{2}\epsilon^{-1}\rceil\leq n$ and
$N_{1},N_{2}\in\mathbb{N}$, on the event

$\displaystyle\\{d^{(k)}(Y^{N_{1}},Y^{N_{2}})<\delta_{1}\\}\cap
B^{N_{1}}_{\epsilon}\cap
B^{N_{2}}_{\epsilon}\cap\mathcal{A}^{\overline{I}^{N_{1}}}_{N_{1}^{2/3}n}\cap\mathcal{A}^{\overline{I}^{N_{2}}}_{N_{2}^{2/3}n}\cap
A^{Q^{N_{1}},Q^{N_{2}}}_{n}$ (4.102) $\displaystyle
d^{(k)}\Big{(}Z^{N_{1}},Z^{N_{2}}\Big{)}<2^{k4^{k+3}2}\epsilon^{k4^{k+3}}d^{(k)}\Big{(}Y^{N_{1}},Y^{N_{2}}\Big{)}+\frac{3}{4}\epsilon<\frac{\epsilon}{4}+\frac{3}{4}\epsilon=\epsilon.$

Next we bound the probability of the complement of the event in (4.102).
Define

$\displaystyle\tilde{\Delta}_{min}=\min_{1\leq i\leq k-1}t_{i+1}-t_{i}.$

For $N_{0}$ so that $|t_{k}|N_{0}^{-1/3}<1$, $N>N_{0}$ and any $1\leq i\leq
k$, it holds that $1/4<\rho_{i}^{N}<3/4$. It follows that

$\displaystyle\mathbb{P}\Bigg{(}\Big{(}\mathcal{A}^{\overline{I}^{N_{1}}}_{N_{1}^{2/3}n}\cap\mathcal{A}^{\overline{I}^{N_{2}}}_{N_{2}^{2/3}n}\Big{)}^{c}\Bigg{)}\stackrel{{\scriptstyle\eqref{ub58}}}{{\leq}}4k^{2}e^{-\frac{(16)^{-1}\tilde{\Delta}_{min}^{2}N_{1}^{-2/3}}{12\rho_{1}^{2}}N_{1}^{2/3}n}+4k^{2}e^{-\frac{(16)^{-1}\tilde{\Delta}_{min}^{2}N_{2}^{-2/3}}{12\rho_{1}^{2}}N_{2}^{2/3}n}$
(4.103) $\displaystyle\leq
8k^{2}e^{-\frac{\tilde{\Delta}_{min}^{2}}{192(3/4)^{2}}n}$
$\displaystyle\mathbb{P}\Bigg{(}\Big{(}B^{N_{1}}_{\epsilon}\cap
B^{N_{2}}_{\epsilon}\Big{)}^{c}\Bigg{)}\leq
2^{k+2}k^{2}n\Big{[}N_{1}^{2/3}e^{-\frac{1}{4}7^{-k}k^{-1}N_{1}^{1/3}\frac{\epsilon}{4}}+N_{2}^{2/3}e^{-\frac{1}{4}7^{-k}k^{-1}N_{2}^{1/3}\frac{\epsilon}{4}}\Big{]},$
(4.104)

where in the last display we used arguments similar to the ones used in
(4.90). Next

$\displaystyle\mathbb{P}\big{(}(A^{Q^{N_{1}},Q^{N_{2}}}_{n})^{c}\big{)}=\mathbb{P}\Bigg{(}\Big{(}\bigcap_{\begin{subarray}{c}1\leq
j\leq k-1\\\ 1\leq i\leq
j\end{subarray}}A^{Q_{N_{1}},n}_{j,i}\Big{)}^{c}\Bigg{)}+\mathbb{P}\Bigg{(}\Big{(}\bigcap_{\begin{subarray}{c}1\leq
j\leq k-1\\\ 1\leq i\leq
j\end{subarray}}A^{Q_{N_{2}},n}_{j,i}\Big{)}^{c}\Bigg{)}\stackrel{{\scriptstyle\eqref{ub57}}}{{\leq}}$
(4.105) $\displaystyle
k^{2}\Big{[}2^{4}k^{2}e^{-\frac{(16)^{-1}\tilde{\Delta}_{min}^{2}N_{1}^{-2/3}}{12\big{(}\rho_{1}^{N_{1}}\big{)}^{2}}N_{1}^{2/3}n}+2^{3k+4}k^{2}(N_{1}^{2/3}n+5)e^{-\frac{4^{-1}\tilde{\Delta}_{min}N_{1}^{-1/3}}{\big{(}\rho_{1}^{N_{1}}\big{)}^{2}48}\times\frac{\rho_{k}^{N_{1}}}{7^{k}k}N_{1}^{2/3}n}\Big{]}$
$\displaystyle+k^{2}\Big{[}2^{4}k^{2}e^{-\frac{(16)^{-1}\tilde{\Delta}_{min}^{2}N_{2}^{-2/3}}{12\big{(}\rho_{1}^{N_{2}}\big{)}^{2}}N_{2}^{2/3}n}+2^{3k+4}k^{2}(N_{2}^{2/3}n+5)e^{-\frac{4^{-1}\tilde{\Delta}_{min}N_{2}^{-1/3}}{\big{(}\rho_{1}^{N_{2}}\big{)}^{2}48}\times\frac{\rho_{k}^{N_{2}}}{7^{k}k}N_{2}^{2/3}n}\Big{]}$
$\displaystyle\leq
2k^{2}\Big{[}2^{4}k^{2}e^{-\frac{\tilde{\Delta}_{min}^{2}}{192\big{(}3/4\big{)}^{2}}n}$
$\displaystyle+2^{3k+4}k^{2}(N_{1}^{2/3}n+5)e^{-\frac{\tilde{\Delta}_{min}}{\big{(}3/4\big{)}^{2}192}\times\frac{1/4}{7^{k}k}N_{1}^{1/3}n}+2^{3k+4}k^{2}(N_{2}^{2/3}n+5)e^{-\frac{\tilde{\Delta}_{min}}{\big{(}3/4\big{)}^{2}192}\times\frac{1/4}{7^{k}k}N_{2}^{1/3}n}\Big{]}.$

From (4.101) with $\delta_{2}<\epsilon/4$ and (4.103)–(4.105), we can choose
$n_{0}(k,\epsilon,\overline{t}),N_{0}(k,\epsilon,\overline{t})>0$ large enough
such that for $n_{0}<n$ and $N_{0}<N_{1},N_{2}$

$\displaystyle\mathbb{P}(\text{the complement of the set in
\eqref{set2}})<\epsilon,$

which in turn implies that for any $\epsilon>0$ there exists
$N_{0}(k,\epsilon,\overline{t})>0$ such that for any $N_{0}<N_{1},N_{2}$

$\displaystyle\mathbb{P}\Bigg{(}d^{(k)}\Big{(}Z^{N_{1}},Z^{N_{2}}\Big{)}>\epsilon\Bigg{)}<\epsilon.$
(4.106)

Let $\mathcal{Z}^{N}$ denote the distribution of $Z^{N}$. Let
$\mathcal{M}(\mathcal{S}^{k})$ denote the set of distributions on the space
$\mathcal{S}^{k}$. Recall the Prohorov metric from (A.27) and that the set
$\mathcal{M}$ is a metric space with respect to the Prohorov metric. It
follows from (4.106) that the sequence
$\\{\mathcal{Z}^{N}\\}_{N\in\mathbb{N}}$ is Cauchy in
$\mathcal{M}(\mathcal{S}^{k})$. As $\mathcal{S}$ is complete and separable so
is $\mathcal{M}(\mathcal{S}^{k})$ (Lemma A.14). We conclude that there exists
$\mathcal{X}\in\mathcal{M}(\mathcal{S}^{k})$ such that

$\displaystyle\mathcal{Z}^{N}\rightarrow\mathcal{X},\quad n\rightarrow\infty.$
(4.107)

Recalling the definition of $Z^{N}$ from (4.97), the display above implies
(4.96). ∎

######  Definition 4.17.

For each $k\in\mathbb{N}$ and an increasing vector
$\overline{t}\in\mathbb{R}^{k}$, we denote by
$\pi^{c}_{\overline{t}}\in\mathcal{M}(\mathcal{S}^{k})$ the distribution of
the r.v. $X_{\overline{t}}$ from (4.96).

Recall the sequences of processes $G^{N}$ from (4.6).

######  Corollary 4.18.

Let $\overline{t}\in\mathbb{R}^{k}$ be an increasing vector, and let us denote
the distribution of $(G^{N}_{t_{1}},...,G^{N}_{t_{k}})$ by
$\bm{G}^{N}_{\overline{t}}$. Then we have the following weak convergence in
$\mathcal{S}^{k}$

$\displaystyle\bm{G}^{N}_{\overline{t}}\Rightarrow\pi^{c}_{\overline{t}}.$

###### Proof.

Recall the vector $\overline{I}^{N}$ from the statement of Proposition 4.16,
associated with the vector $\overline{t}$. From the definition of $G^{N}$ and
Theorem 3.2, it is not hard to verify that

$\displaystyle(G^{N}_{t_{1}},...,G^{N}_{t_{k}})\sim
N^{-1/3}\mathcal{L}^{N^{2/3}}\big{(}\Psi(\mathcal{D}^{(k)}(\overline{I}^{N}-\bm{2}^{k}))\big{)}.$

The result now follows from (4.96). ∎

######  Proposition 4.19.

Let $k\in\mathbb{N}$, and $\overline{t}\in\mathbb{R}^{k}$ be an increasing
vector and let
$W^{\overline{t}}=(W^{\overline{t}}_{1},...,W^{\overline{t}}_{k})\in\mathcal{S}^{k}$
be a vector of independent elements where $W^{\overline{t}}_{i}$ is a bi-
infinite Brownian motion with drift $t_{i}$ and diffusivity $2$, conditioned
to vanish at the origin. Then

$\displaystyle\Phi^{k}(W^{\overline{t}})\sim\pi^{c}_{\overline{t}}.$

###### Proof.

Let $Y^{N}$ and $Z^{N}$ be as in (4.97), and for $N\in\mathbb{N}$ let

$\displaystyle M^{N}=\Phi^{k}\big{(}Y^{N}\big{)}.$

From Lemma 4.11, for $n\in\mathbb{N}$, on the event
$\mathcal{A}^{\overline{I}^{N}}_{n}$ with $l=k$

$\displaystyle
d^{(k)}_{n}\Big{(}Z^{N},M^{N}\Big{)}\stackrel{{\scriptstyle\eqref{si}}}{{=}}d^{(k)}_{n}\Big{(}Z^{N},\mathcal{L}^{N^{2/3}}\Phi^{k}\big{(}N^{-1/3}\Psi(\overline{I}^{N}-\bm{2}^{k})\big{)}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{const2}\&\eqref{si2}}}{{=}}d^{(k)}_{nN^{2/3}}\Big{(}N^{-1/3}\Psi(\mathcal{D}^{(k)}(\overline{I}^{N}-\bm{2}^{k})),N^{-1/3}\Phi^{k}\big{(}\Psi(\overline{I}^{N}-\bm{2}^{k})\big{)}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq11}\&\eqref{const2}}}{{=}}d^{(k)}_{nN^{2/3}}\Big{(}N^{-1/3}\Psi(\mathcal{D}^{(k)}(\overline{I}^{N})),N^{-1/3}\Phi^{k}\big{(}\Psi(\overline{I}^{N})\big{)}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ub35}}}{{\leq}}N^{-1/3}16\sum_{i=0}^{k-2}7^{k-2-i}\sup_{|j|\leq
2^{k-1-i}nN^{2/3}+2}\Big{[}|I^{k-1-i}_{j}|+\sup_{1\leq q\leq
i+1}|\tilde{I}^{i+1,q}_{j}|\Big{]}$

Using bounds similar to the one in (4.90) and (4.82), we conclude that

$\displaystyle d^{(k)}_{n}\Big{(}Z^{N},M^{N}\Big{)}\stackrel{{\scriptstyle
N\rightarrow\infty}}{{\rightarrow}}0\quad\text{in probability}.$

Letting $n\rightarrow\infty$ and using (4.1) we conclude that

$\displaystyle d^{(k)}\Big{(}Z^{N},M^{N}\Big{)}\stackrel{{\scriptstyle
N\rightarrow\infty}}{{\rightarrow}}0\quad\text{in probability}.$ (4.108)

Combining (4.107) and (4.108) implies that

$\displaystyle M^{N}\rightarrow\pi^{c}_{\overline{t}}\quad\text{as
$N\rightarrow\infty$},$ (4.109)

where the convergence is in distribution. We are left to show that

$\displaystyle
M^{N}\rightarrow\Phi^{k}\big{(}W^{\overline{t}}\big{)}\quad\text{as
$N\rightarrow\infty$},$ (4.110)

W.l.o.g. assume (4.100) holds a.s. in $\mathcal{S}^{k}$. Recall the event
$A^{Y^{N},W^{\overline{t}}}_{R}$ from (4.37). From (4.38), it follows that for
$R\in\mathbb{N}$, on $A^{Y^{N},W^{\overline{t}}}_{R}$

$\displaystyle
d^{(k)}\big{(}M^{N},\Phi^{k}\big{(}W^{\overline{t}}\big{)}\big{)}\leq
2^{k4^{k+3}R}d^{(k)}\big{(}Y^{N},W^{\overline{t}}\big{)}+2^{-R}.$

By Donsker’s invariance principle, the first term on the r.h.s. of the display
above goes to $0$ as $N\rightarrow\infty$. It follows that

$\displaystyle\limsup_{N\rightarrow\infty}\mathbb{P}\Big{(}d^{(k)}\big{(}M^{N},\Phi^{k}\big{(}W^{\overline{t}}\big{)}\big{)}>2^{-R}\Big{)}\leq\limsup_{N\rightarrow\infty}\mathbb{P}\Big{(}\big{[}A^{Y^{N},W^{\overline{t}}}_{R}\big{]}^{c}\Big{)}$

which implies that

$\displaystyle
d_{\text{Proh}}\big{(}\Phi^{k}\big{(}W^{\overline{t}}\big{)},\pi^{c}_{\overline{t}}\big{)}\leq
2^{-R}\vee\limsup_{N\rightarrow\infty}\mathbb{P}\Big{(}\big{[}A^{Y^{N},W^{\overline{t}}}_{R}\big{]}^{c}\Big{)}.$
(4.111)

From Remark 4.5 and (4.85) it follows that

$\displaystyle\limsup_{R\rightarrow\infty}\limsup_{N\rightarrow\infty}\mathbb{P}\Big{(}\big{[}A^{Y^{N},W^{\overline{t}}}_{R}\big{]}^{c}\Big{)}=0.$
(4.112)

Sending $R\rightarrow\infty$ in (4.111) and using (4.112) and (4.109), implies
(4.110). ∎

###  4.3 Putting everything together

(a)

(b)

Figure 4.1: Illustration of a typical realization of the Stationary Horizon.
Figure 1(a)) A typical realization of the Stationary Horizon on a compact
rectangle on the $x-\mu$ plane. The different colours in the picture represent
different constant values (three in total in this picture) of the process
along the $\mu$ axis. Figure 1(b)) A finer depiction of the jump points of
$G$. Recall the process $G^{x_{0}}$ from (1.6). For $i\in\\{1,2\\}$, on the
interval $[\mu_{i},\mu_{i+1})$, $G^{x_{0}}$ attains the value
$G^{x_{0}}_{\mu_{i}}\in C\big{(}[-x_{0},x_{0}]\big{)}$. Typically a change at
$\mu_{2}$ will consist of a (random) compact interval around the origin (on
the $x$-axis) where there is no change (solid purple curve), possible change
around the interval (solid curve in new colour), where $G$ will take
larger\smaller values (on the $x$-axis). To facilitate the comparison between
old and new values of $G$, we keep the old values in dashed lines and in the
same colour as when they were solid. The dynamics of the SH can therefore be
described by a ”sticky” line ensemble, branching away as we zoom away from the
origin or vary $\mu$.

In this subsection we combine the different results obtained in the previous
subsections to prove Theorem 1.1 and Theorem 1.2.

###### Proof of Theorem 1.1.

The result will follow from Lemma A.17 once we verify all the conditions in
its statement for the sequence $\\{G^{N}\\}_{N\in\mathbb{N}}$. Condition 1
holds from Lemma 4.2. Condition 2 holds from Corollary 4.18 with
$p_{\overline{t}}=\pi_{\overline{t}}^{c}$ for any $k\in\mathbb{N}$ and
$\overline{t}=(t_{1},...,t_{k})$. Finally Condition 3 follows from Proposition
4.3. ∎

###### Proof of Theorem 1.2.

Part 1. This follows from the fact that the prelimiting random walk
$\Psi\big{(}I^{1/2-\frac{\mu}{4}N^{-1/3}}\big{)}$, under diffusive scaling,
converges to a Brownian motion with drift $\mu$. Part 2 is implied by
Definition 4.17, Proposition 4.16 and Proposition 4.19. Part 3. From (4.6), it
is not hard to verify that i) considering the parameter $N$ to take values in
$\mathbb{R}$, we still have that $G^{N}\rightarrow G$, where $G$ is the
stationary horizon. ii) For $c>0$ we have

$\displaystyle G^{N}_{\mu}(x)=cG^{c^{3}N}_{c\mu}(c^{-2}x).$ (4.113)

Sending $N\rightarrow\infty$ on both sides of (4.113) we obtain the result.
Part 4 follows from Lemma 4.2 and Lemma A.16. Part 5. Let $x_{0},\mu_{0}>0$.
Recall the processes $G^{x_{0},N}\in
D\big{(}\mathbb{R},C([-x_{0},x_{0}])\big{)}$ defined in (4.21). Clearly,

$\displaystyle G^{x_{0},N}\Rightarrow G^{x_{0}}\qquad N\rightarrow\infty,$
(4.114)

where convergence is in $D\big{(}\mathbb{R},C([-x_{0},x_{0}])\big{)}$ equipped
with a metric similar to the one in (A.28) only with

$\displaystyle d(f,g)=\sup_{x\in[-x_{0},x_{0}]}|f(x)-g(x)|\qquad f,g\in
C\big{(}[-x_{0},x_{0}]\big{)}.$

Let

$\displaystyle\mathcal{B}^{M,\mu_{0},x_{0}}=\\{\text{the process $G^{x_{0}}$
has no less then $M$ epochs in $[-\mu_{0},\mu_{0}]$}\\}.$

Recall the event $\mathcal{B}^{M,N,\mu_{0},x_{0}}$ from (4.22), on which the
number of epochs of $G^{x_{0},N}$ is at least $M$. Without loss of generality,
we may assume that the convergence in (4.114) is an almost sure one. This
implies that

$\displaystyle\mathbb{P}\big{(}\mathcal{B}^{M,\mu_{0},x_{0}}\setminus\,\mathcal{B}^{M,N,2\mu_{0},x_{0}}\big{)}\rightarrow
0,$

or that

$\displaystyle\mathbb{P}\big{(}\mathcal{B}^{M,\mu_{0},x_{0}}\big{)}\leq\mathbb{P}\big{(}\mathcal{B}^{M,N,2\mu_{0},x_{0}}\big{)}+\epsilon_{N},$
(4.115)

where $\epsilon_{N}\rightarrow 0$. Indeed, if the process $G^{x_{0}}$ has at
least $M$ epochs in $[-\mu_{0},\mu_{0}]$, then for $N>N_{0}$ for some random
$N_{0}$, the process $G^{x_{0},N}$ must have at least $M$ epochs in the
interval $[-2\mu_{0},2\mu_{0}]$. Using the bound (4.23) in (4.115) and sending
$N$ to infinity gives

$\displaystyle\mathbb{P}\big{(}\mathcal{B}^{M,\mu_{0},x_{0}}\big{)}\leq
2^{22}\frac{x_{0}\mu_{0}}{M-2}\qquad M\geq 3,$

which is essentially (1.7). In particular, with probability 1, the process
$G^{x_{0}}$ has finitely many epochs on any compact interval. Part 6. Let
$x_{1}\leq x_{2}$ and $\mu_{1}\leq\mu_{2}$. Using (3.1) and (3.3) in (4.6)
implies that for large enough $N$

$\displaystyle G^{N}_{\mu_{2}}(x_{2})-G^{N}_{\mu_{2}}(x_{1})\geq
G^{N}_{\mu_{1}}(x_{2})-G^{N}_{\mu_{1}}(x_{1}).$

This implies (1.8). ∎

##  Appendix A Appendix

###  A.1 Queues

The following is a known result in queueing theory.

######  Lemma A.1.

Fix $0<\rho_{-}<\rho_{+}$. Let $\mathbf{a}\sim\nu^{\rho_{-}}$ and
$\mathbf{s}\sim\nu^{\rho_{+}}$. Then

$\displaystyle J_{0}:=S_{oj}(\mathbf{s},\mathbf{a})_{0}=w_{0}+s_{0},$

where $w_{0}$ and $s_{0}$ are independent and

$\displaystyle w_{0}\sim\mathrm{BerExp}(\rho_{+}-\rho_{-},\rho_{+})$
$\displaystyle s_{0}\sim\mathrm{Exp}(\rho_{+}).$

and therefore

$\displaystyle J_{0}\sim\mathrm{Exp}(\rho_{+}-\rho_{-}).$

The following lemma is a deterministic result from [17, Lemma 4.4].

######  Lemma A.2.

Let $\overline{I}\in\mathcal{Y}^{3}$. Then

$\displaystyle D^{(3)}(\overline{I})=D^{(3)}(\sigma_{1}\overline{I}).$ (A.1)

The following lemma extends this result.

######  Lemma A.3.

Fix $n\geq 3$. Let $\overline{I}\in\mathcal{Y}^{n}$, then for $1\leq i\leq
n-2$

$\displaystyle D^{(n)}(\overline{I})=D^{(n)}(\sigma_{i}\overline{I})$ (A.2)

###### Proof.

First note that as $1\leq i\leq n-2$ and $\overline{I}\in\mathcal{Y}^{n}$, it
follows that $[\Gamma(\sigma_{i}\overline{I})]_{j}>[\Gamma(\overline{I})]_{n}$
for every $1\leq j<n$ so that the right hand side of (A.2) is well defined. By
definition

$\displaystyle
D^{(n)}(I^{1},...,I^{n})=D^{(i)}\Bigg{(}I^{1},...,I^{i-1},D\Big{(}I^{i},D\big{(}I^{i+1},D^{(n-(i+2)+1)}(I^{i+2},...,I^{n})\big{)}\Big{)}\Bigg{)}$
(A.3)

From (A.1)

$\displaystyle
D\Big{(}I^{i},D\big{(}I^{i+1},D^{(n-(i+2)+1)}(I^{i+2},...,I^{n})\big{)}\Big{)}$
(A.4)
$\displaystyle=D\Big{(}D(I^{i},I^{i+1}),D\big{(}R(I^{i},I^{i+1}),D^{(n-(i+2)+1)}(I^{i+2},...,I^{n})\big{)}\Big{)}$

Plugging (A.4) in (A.3)

$\displaystyle D^{(n)}(I^{1},...,I^{n})$
$\displaystyle=D^{(i)}\Bigg{(}I^{1},...,I^{i-1},D\Big{(}D(I^{i},I^{i+1}),D\big{(}R(I^{i},I^{i+1}),D^{(n-(i+2))}(I^{i+2},...,I^{n})\big{)}\Big{)}\Bigg{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{qi}}}{{=}}D^{(n)}(I^{1},...,I^{i-1},D(I^{i+1},I^{i}),R(I^{i+1},I^{i}),I^{i+2},...,I^{n})=D^{(n)}(\sigma_{i}\overline{I}).$

∎

######  Lemma A.4 ([17, Lemma B.2]).

Let $\rho_{1}>\rho_{2}>0$. Let $I^{1}$ and $I^{2}$ be two independent i.i.d.
sequences with $I^{i}_{0}\sim\rm{Exp}(\rho_{i})$.

  1. (i)

For each $k\in\mathbb{Z}$ the random variables

$\displaystyle\\{D(I^{1},I^{2})_{i}\\}_{i\leq
k},\\{R(I^{1},I^{2})_{i}\\}_{i\leq k},S_{oj}(I^{1},I^{2})_{k}$

are mutually independent with marginals

$\displaystyle D(I^{1},I^{2})_{0}\sim\text{Exp}(\rho_{2})\quad
R(I^{1},I^{2})_{0}\sim\text{Exp}(\rho_{1})\quad
S_{oj}(I^{1},I^{2})_{0}\sim\text{Exp}\big{(}\rho_{1}-\rho_{2}\big{)}$

  2. (ii)

$D(I^{1},I^{2})$ and $R(I^{1},I^{2})$ are independent.

######  Lemma A.5.

Let $\mathbf{s},\mathbf{a}\in\mathcal{X}$ and define
$S_{oj}(\mathbf{s},\mathbf{a})=\\{J_{i}\\}_{i\in\mathbb{Z}}$. For every
integers $m\leq n$

$\displaystyle\sum_{i=m}^{n}(J_{i-1}-a_{i})^{-}=\Big{(}\inf_{m\leq i\leq
n-1}J_{m-1}+\sum_{j=m}^{i-1}(s_{j}-a_{j})+a_{i}\Big{)}^{-}$ (A.5)

###### Proof.

This follows from [2, Lemma A.1.]. ∎

#### Comparing stationary queues to empty ones

Here we show that the output of a stationary queue can be controlled by that
of a queue starting with zero waiting time. This tool is an important
ingredient in the proof of Lemma 3.3.

Let $m\in\mathbb{Z}$. Define
$D_{m}:\mathcal{X}\times\mathcal{X}\rightarrow(\mathcal{X})^{[m,\infty)}$ as
the restriction of the queueing map on $[m,\infty)$ i.e.

$\displaystyle D_{m}(I^{1},I^{2})_{i}=D(I^{1},I^{2})_{i}\quad for\quad m\leq
i<\infty.$

Recall (3.7)–(3.8) and note that

$\displaystyle
S^{m,i}(D(I^{1},I^{2}))=S^{m,i}(I^{1})+\psi^{m}(S_{oj}(I^{1},I^{2})_{m-1},I^{1},I^{2})_{i}$
(A.6) $\displaystyle\leq S^{m,i}(I^{1})+\psi^{m}(0,I^{1},I^{2})_{i}\leq
S^{m,i}(I^{1})+\sup_{m\leq j\leq i}[S^{m,i}(I^{2}-I^{1})]^{+}+\sup_{m\leq
j\leq i}|I^{2}_{j}|.$

Next define the map
$D_{m,0}:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}^{[m,\infty)}$ in
the following way. First define the sequence

$\displaystyle J^{\prime}_{m-1}$ $\displaystyle=0$ $\displaystyle
J^{\prime}_{i}$ $\displaystyle=(a_{i}-J^{\prime}_{i-1})^{-}+s_{i}\quad i\geq
m,$

and then define

$\displaystyle
D_{m,0}(\mathbf{s},\mathbf{a})_{i}=(J^{\prime}_{i-1}-a_{i})^{-}+s_{i}\quad
i\geq m.$ (A.7)

The map $D_{m,0}$ can also be obtained by setting its input prior to time $m$
to zero. That is,

$\displaystyle
D_{m,0}(\mathbf{s},\mathbf{a})=D_{m}(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$

where

$\displaystyle\mathbf{a}^{\prime}_{i}=\begin{cases}\mathbf{a}_{i}&i\geq m\\\
0&i<m.\end{cases}$

and where $\mathbf{s}^{\prime}$ is defined similarly.

######  Lemma A.6.

For every $m\in\mathbb{Z}$ the following holds

  1. 1.

$\displaystyle D(\mathbf{s},\mathbf{a})_{i}\leq
D_{m,0}(\mathbf{s},\mathbf{a})_{i}\quad i\geq m$

  2. 2.

The map $S^{m,i}\big{(}D_{m,0}(\cdot,\cdot)\big{)}$ is increasing in both
variables, i.e.

$\displaystyle S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{1},\mathbf{a}^{1})\big{)}\leq
S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{2},\mathbf{a}^{2})\big{)}$

whenever

$\displaystyle(\mathbf{s}^{1},\mathbf{a}^{1})\leq(\mathbf{s}^{2},\mathbf{a}^{2}).$

###### Proof.

The proof of 1. follows by induction on $i\geq m$. Let
$J_{m-1}=S_{oj}(\mathbf{s},\mathbf{a})_{m-1}$ and construct $J_{i}$ via the
map

$\displaystyle J_{i}=(a_{i}-J_{i-1})^{-}+s_{i}\quad i\geq m.$

Using induction on $i$ we see that

$\displaystyle J^{\prime}_{i}\leq J_{i}\quad\text{for all }i\geq m.$

This implies that

$\displaystyle
D(\mathbf{s},\mathbf{a})_{i}=(J_{i}-a_{i})^{-}+s_{i}\leq(J^{\prime}_{i}-a_{i})^{-}+s_{i}\leq
D_{m,0}(\mathbf{s},\mathbf{a})_{i}\quad i\geq m.$

Moving on to the proof of 2, let $\mathbf{s}^{\prime}\geq 0$

$\displaystyle
S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{1}+\mathbf{s}^{\prime},\mathbf{a}^{1})\big{)}-S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{1},\mathbf{a}^{1})\big{)}$
(A.8)
$\displaystyle=S^{m,i}(\mathbf{s}^{\prime})+\psi(0,\mathbf{s}^{1}+\mathbf{s}^{\prime},\mathbf{a}^{1})_{i}-\psi(0,\mathbf{s}^{1},\mathbf{a}^{1})_{i}.$

As

$\displaystyle\psi(0,\mathbf{s}^{1}+\mathbf{s}^{\prime},\mathbf{a}^{1})_{i}-\psi(0,\mathbf{s}^{1},\mathbf{a}^{1})_{i}\geq-S^{m,i}(\mathbf{s}^{\prime}),$

it follows that the left hand side of (A.8) is non negative which shows that
$S^{m,i}\big{(}D_{m,0}(\cdot,\cdot)\big{)}$ is increasing in its first
element. Similarly for $\mathbf{a}^{\prime}\geq 0$, clearly,

$\displaystyle
S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{1},\mathbf{a}^{1}+\mathbf{a}^{\prime})\big{)}-S^{m,i}\big{(}D_{m,0}(\mathbf{s}^{1},\mathbf{a}^{1})\big{)}$
$\displaystyle=\psi(0,\mathbf{s}^{1},\mathbf{a}^{1}+\mathbf{a}^{\prime})-\psi(0,\mathbf{s}^{1},\mathbf{a}^{1})\geq
0,$

so $S^{m,i}\big{(}D_{m,0}(\cdot,\cdot)\big{)}$ is increasing in its second
element as well, thus proving the claim. ∎

The map $D_{m,0}$ can be generalized to a map on $k$ variables in the
following way. Let $k\geq 2$ and let $I^{1},..,I^{k}$ be sequences. Define
another set of sequences $\hat{I}^{1},...,\hat{I}^{k}$ by

$\displaystyle\hat{I}^{i}_{l}=\begin{cases}I^{i}_{l}&l\geq m\quad\quad
i\in\\{1,..,k\\}\\\ 0&l<m.\end{cases}$

Define the map $D^{(k)}_{m,0}$ through

$\displaystyle[D^{(k)}_{m,0}(I^{1},...,I^{k})]_{i}=D^{(k)}(\hat{I}^{1},...,\hat{I}^{k})_{i}\quad\text{for
$i\geq m$}.$

Analogous to Lemma A.6 we have the following.

######  Lemma A.7.

For every $m\in\mathbb{Z}$ the following holds

  1. 1.

$\displaystyle D^{(k)}(I^{1},...,I^{k})_{i}\leq
D^{(k)}_{m,0}(I^{1},...,I^{k})_{i}\quad i\geq m$ (A.9)

  2. 2.

The map $S^{m,i}\big{(}D_{m,0}(\cdot,\cdot)\big{)}$ is increasing in all its
variables, i.e.

$\displaystyle S^{m,i}\big{(}D_{m,0}(I^{1},...,I^{k})\big{)}\leq
S^{m,i}\big{(}D_{m,0}(T^{1},...,T^{k})\big{)}$ (A.10)

whenever

$\displaystyle(I^{1},...,I^{k})\leq(T^{1},...,T^{k}).$

###### Proof.

The proof of 1 follows by induction on $k$. The base case is $k=2$ was proven
in Lemma A.6. Assume the claim holds for $k-1$ . Then for $i\geq m$

$\displaystyle
D^{(k)}(I^{1},...,I^{k})_{i}=D\big{(}I^{1},D^{(k-1)}(I^{2},...,I^{k})\big{)}_{i}\leq
D\big{(}I^{1},D^{(k-1)}_{m,0}(I^{2},...,I^{k})\big{)}_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{od}}}{{\leq}}D_{m,0}\big{(}I^{1},D^{(k-1)}_{m,0}(I^{2},...,I^{k})\big{)}_{i}=D^{(k)}_{m,0}(I^{1},...,I^{k})_{i},$

where in the first inequality we used that the map $D(\cdot,\cdot)$ is
increasing in its second element. We have thus proven 1. Similarly,

$\displaystyle
S^{m,i}\big{(}D^{(k)}_{m,0}(I^{1},...,I^{k})\big{)}=S^{m,i}\Big{(}D_{m,0}\big{(}I^{1},D^{(k-1)}_{m,0}(I^{2},...,I^{k})\big{)}\Big{)}$
$\displaystyle\leq S^{m,i}(I^{1})+\inf_{m\leq j\leq
i}\Big{(}S^{m,j-1}(I^{1})-S^{m,j}(D^{(k-1)}_{m,0}(I^{2},...,I^{k}))\Big{)}^{-}$
$\displaystyle\leq S^{m,i}(I^{1})+\inf_{m\leq j\leq
i}\Big{(}S^{m,j-1}(I^{1})-S^{m,j}(D^{(k-1)}_{m,0}(T^{2},...,T^{k}))\Big{)}^{-}$
$\displaystyle=S^{m,i}\Big{(}D_{m,0}\big{(}I^{1},D^{(k-1)}_{m,0}(T^{2},...,T^{k})\big{)}\Big{)}\stackrel{{\scriptstyle\eqref{od2}}}{{\leq}}S^{m,i}\Big{(}D_{m,0}\big{(}T^{1},D^{(k-1)}_{m,0}(T^{2},...,T^{k})\big{)}\Big{)}$
$\displaystyle=S^{m,i}\big{(}D^{(k)}_{m,0}(T^{1},...,T^{k})\big{)},$

where in the second inequality we used the induction hypothesis, thus proving
2. ∎

Next we obtain a simple bound on the queueing map in terms of its input. For
integers $m\leq n$ define the function $\Phi_{m,n}:\mathbb{R}^{\llbracket
m,\infty\rrbracket}\rightarrow\mathbb{R}_{+}$ through

$\displaystyle\Phi_{m,n}(I)=\big{[}\sup_{m\leq i\leq n}S^{m,i}(I)\big{]}^{+}.$
(A.11)

Define $\mathcal{M}_{m,n}:\mathcal{X}\rightarrow\mathbb{R}$ through

$\displaystyle\mathcal{M}_{m,n}(I)=\max_{m\leq i\leq n}|I_{i}|$ (A.12)

######  Lemma A.8.

Let $m,n\in\mathbb{Z}$ such that $m\leq n$ and let $I^{0}\in\mathcal{X}$. Then

$\displaystyle\Phi_{m,n}(D^{(k)}_{m,0}(I^{1},...,I^{k})-I^{0})\leq\sum_{l=1}^{k}\big{[}\Phi_{m,n}(I^{l}-I^{l-1})\big{]}+\sum_{l=2}^{k}\mathcal{M}_{m,n}\Big{(}\sum_{i=l}^{k}I^{i}\Big{)}.$
(A.13)

###### Proof.

The proof follows by induction on $k$. The base case is $k=2$. Indeed, from
(A.6)

$\displaystyle\Phi_{m,n}(D_{m,0}(I^{1},I^{2})-I^{0})$
$\displaystyle=\big{[}\sup_{m\leq i\leq
n}S^{m,i}(I^{1}-I^{0})+\psi^{m}(0,I^{1},I^{2})_{i}\big{]}^{+}$ (A.14)
$\displaystyle\leq\Phi_{m,n}(I^{1}-I^{0})+\Phi_{m,n}(I^{2}-I^{1})+\mathcal{M}_{m,n}(I^{2}).$

Assume the hypothesis holds for $k-1\geq 2$, then

$\displaystyle\Phi_{m,n}(D^{(k)}_{m,0}(I^{1},...,I^{k})-I^{0})=\Phi_{m,n}(D^{(k-1)}_{m,0}(I^{1},...,D_{m,0}(I^{k-1},I^{k}))-I^{0})$
(A.15)
$\displaystyle\leq\sum_{l=1}^{k-2}\big{[}\Phi_{m,n}(I^{l}-I^{l-1})\big{]}+\sum_{l=2}^{k-2}\mathcal{M}_{m,n}\Big{(}\sum_{i=l}^{k-2}I^{i}\Big{)}+\Phi_{m,n}(D_{m,0}(I^{k-1},I^{k})-I^{k-2})$
$\displaystyle+\mathcal{M}_{m,n}\big{(}D_{m,0}(I^{k-1},I^{k})\big{)}.$

Note that by the base case $k=2$ in (A.14)

$\displaystyle\Phi_{m,n}(D_{m,0}(I^{k-1},I^{k})-I^{k-2})$ (A.16)
$\displaystyle\leq\Phi_{m,n}(I^{k-1}-I^{k-2})+\Phi_{m,n}(I^{k}-I^{k-1})+\mathcal{M}_{m,n}(I^{k}),$

and that

$\displaystyle\mathcal{M}_{m,n}\big{(}D_{m,0}(I^{k-1},I^{k})\big{)}=\max_{m\leq
i\leq n}|D_{m,0}(I^{k-1},I^{k})_{i}|\leq\max_{m\leq i\leq
n}|I^{k}_{i}+I^{k-1}_{i}|=\mathcal{M}_{m,n}\big{(}I^{k}+I^{k-1}\big{)}.$
(A.17)

Plugging (A.16) and (A.17) in (A.15), we obtain the result. ∎

###  A.2 Results on Random walks

######  Lemma A.9.

Let $\Delta,\rho>0$ and let $\\{X_{i}\\}_{i\in\mathbb{Z}}$ be i.i.d. r.v.s
such that $X_{0}\sim\mathrm{Exp}(\rho+\Delta,\rho)$. Assume that
$\sqrt{\Delta^{2}+4m^{-1}}<\rho$, then

$\displaystyle\mathbb{P}(\inf_{0\leq j\leq
m}S^{0,j}(X)<-t)\leq\Big{(}1+\frac{m^{-1}}{(\rho-\sqrt{\Delta^{2}+4m^{-1}})\rho}\Big{)}^{m}e^{-\frac{\sqrt{\Delta^{2}+4m^{-1}}-\Delta}{2}t}.$

###### Proof.

Let $\phi_{\rho}(\theta)$ be the moment generating function of the exponential
distribution with intensity $\rho>0$. Using Doob’s inequality

$\displaystyle\mathbb{P}(\inf_{0\leq j\leq
m}S^{0,j}(X)<-t)=\mathbb{P}(\sup_{0\leq j\leq
m}-S^{0,j}(X)>t)\leq\big{[}\phi_{\rho+\Delta}(-\theta)\phi_{\rho}(\theta)\big{]}^{m}e^{-\theta
t}.$ (A.18)

Compute

$\displaystyle\phi_{\rho+\Delta}(-\theta)\phi_{\rho}(\theta)=\frac{(\rho+\Delta)\rho}{(\rho+\Delta+\theta)(\rho-\theta)}=1+\frac{\theta^{2}+\theta\Delta}{(\rho+\Delta+\theta)(\rho-\theta)}.$
(A.19)

Setting $\theta_{0}=\frac{-\Delta+\sqrt{\Delta^{2}+4m^{-1}}}{2}>0$ such that
$\theta_{0}^{2}+\theta_{0}\Delta=m^{-1}$, plugging (A.19) in (A.18)

$\displaystyle\mathbb{P}(\inf_{0\leq j\leq
m}S^{0,j}(X)<-t)\leq\Big{(}1+\frac{m^{-1}}{(\rho-\theta)\rho}\Big{)}^{m}e^{-\frac{\sqrt{\Delta^{2}+4m^{-1}}-\Delta}{2}t}$
$\displaystyle\leq\Big{(}1+\frac{m^{-1}}{(\rho-\sqrt{\Delta^{2}+4m^{-1}})\rho}\Big{)}^{m}e^{-\frac{\sqrt{\Delta^{2}+4m^{-1}}-\Delta}{2}t},$

which is the required result. ∎

######  Lemma A.10.

Let $X=\\{X_{i}\\}_{i=1}^{\infty}$ be i.i.d. r.v’s such that
$X_{1}\sim\textrm{Exp}(\rho+\Delta)-\textrm{Exp}(\rho)$. Then

$\displaystyle\mathbb{P}\Big{(}S^{0,m}(X)>t\Big{)}\leq\Big{(}1-\frac{\Delta^{2}}{4(\rho+\Delta/2)^{2}}\Big{)}^{m}e^{-\Delta
t/2}\leq e^{-\frac{\Delta^{2}m}{4(\rho+\frac{\Delta}{2})^{2}}-\Delta t/2}.$
(A.20)

In particular, for $\Delta=\mu N^{-1/3}$ and $m=xN^{2/3}$ where $x>0$, and for
large enough $N$,

$\displaystyle\mathbb{P}\Big{(}S^{0,m}(X)>tN^{1/3}\Big{)}\leq
e^{-\frac{\mu}{4}\big{(}\frac{\mu x}{\rho^{2}}+t\big{)}}$ (A.21)

###### Proof.

Using Chernoff’s bound with $\theta=\Delta/2$ gives

$\displaystyle\mathbb{P}\Big{(}S^{0,m}(X)>t\Big{)}\leq[\phi_{\rho+\Delta}(\theta)\phi_{\rho}(-\theta)]^{m}e^{-\theta
t}\leq\Big{(}1-\frac{\Delta^{2}}{4(\rho+\Delta/2)^{2}}\Big{)}^{m}e^{-\Delta
t/2}$ $\displaystyle\leq
e^{-\frac{\Delta^{2}m}{4(\rho+\frac{\Delta}{2})^{2}}-\Delta t/2},$

proving (A.20). Plugging $\Delta$ and $m$ in (A.20) and sending
$N\rightarrow\infty$ gives (A.21). ∎

######  Lemma A.11.

Let $X=\\{X_{i}\\}_{i=1}^{\infty}$ be i.i.d. r.v’s such that
$X_{1}\sim\textrm{Exp}(\rho+\Delta)-\textrm{Exp}(\rho)$. Then for $t>0$ and
any $m\in\mathbb{N}$

$\displaystyle\mathbb{P}\Big{(}\sup_{1\leq j\leq m}S^{1,j}(X)>t\Big{)}\leq
e^{-\Delta t}.$ (A.22)

###### Proof.

For $\theta=\Delta$, $\mathbb{E}(e^{\theta X_{1}})=1$ which implies that
$\\{e^{\theta S^{0,j}}\\}_{j\geq 1}$ is a martingale. Using Doob’s inequality

$\displaystyle\mathbb{P}\Big{(}\sup_{0\leq j\leq
m}S^{0,j}(X)>t\Big{)}=\mathbb{P}\Big{(}\sup_{0\leq j\leq m}e^{\Delta
S^{0,j}(X)}>e^{\Delta t}\Big{)}\leq e^{-\Delta t}.$

∎

######  Lemma A.12.

Let $X=\\{X_{i}\\}_{i=1}^{\infty}$ be i.i.d. r.v’s such that
$X_{1}\sim\textrm{Exp}(\rho+\Delta)-\textrm{Exp}(\rho)$. Let $F$ be a random
element in $\mathcal{S}$ such that

$\displaystyle d_{N}(F,\Psi(X))\leq\mathcal{C}_{N}\quad\forall N\geq 1$

where $\\{\mathcal{C}_{i}\\}_{i=1}^{\infty}$ is a sequence of positive random
variables. Then for $\Delta\leq\frac{2\rho}{5}$ and $M\in\mathbb{N}$ such that
$M>24\Delta^{-2}\rho^{2}$

$\displaystyle\mathbb{P}\Big{(}\sup_{M<t}F(t)>0\Big{)}\leq
4e^{-\frac{\Delta^{2}M}{12\rho^{2}}}+\sum_{k=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(k+1)M}\geq
M\frac{k\Delta}{\rho^{2}48}\Big{)}.$ (A.23)

###### Proof.

For $M\in\mathbb{N}$, denote

$\displaystyle\hat{M}=\Delta\rho^{-2}6^{-1}M,$ (A.24)

and let

$\displaystyle A_{k}$
$\displaystyle=\Big{\\{}\Psi(X)(kM)\leq-\frac{k\hat{M}}{2},\sup_{kM<s\leq(k+1)M}\Psi(X)(s)-\Psi(X)(kM)<\frac{k\hat{M}}{4}\Big{\\}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{sum}}}{{=}}\Big{\\{}S^{1,kM}(X)\leq-\frac{k\hat{M}}{2},\sup_{kM<i\leq(k+1)M}S^{kM,i}(X)<\frac{k\hat{M}}{4}\Big{\\}}$
(A.25) $\displaystyle B_{k}$
$\displaystyle=\Big{\\{}\mathcal{C}_{(k+1)M}<\frac{k\hat{M}}{8}\Big{\\}},$

where in the second equality we used the fact that linear interpolation
attains its maxima on the interpolated points. It is not hard to see that

$\displaystyle A_{k}\cap
B_{k}\subseteq\Big{\\{}\sup_{kM<s\leq(k+1)M}F(s)<0\Big{\\}}$

which implies that

$\displaystyle\mathbb{P}\Big{(}\sup_{M<s}F(s)<0\Big{)}\geq\mathbb{P}\Big{(}\bigcap_{k\geq
1}A_{k}\cap B_{k}\Big{)}.$

It follows that

$\displaystyle\mathbb{P}\Big{(}\sup_{M<s}F(s)\geq
0\Big{)}\leq\sum_{k=1}^{\infty}\Big{[}\mathbb{P}\Big{(}A_{k}^{c}\Big{)}+\mathbb{P}\Big{(}B_{k}^{c}\Big{)}\Big{]}\leq\sum_{k=1}^{\infty}\Big{[}C^{1}_{k}+C^{2}_{k}+\mathbb{P}\Big{(}B_{k}^{c}\Big{)}\Big{]}.$

For $\Delta\leq(\sqrt{\frac{3}{2}}-1)2\rho$

$\displaystyle C^{1}_{k}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq12}}}{{=}}\mathbb{P}\big{(}S^{0,kM}>-\frac{k\hat{M}}{2}\big{)}\stackrel{{\scriptstyle\ref{lem:rw}}}{{\leq}}e^{-\frac{\Delta^{2}kM}{6\rho^{2}}+\Delta
k\hat{M}/4}=e^{-\frac{3\Delta k\hat{M}}{4}}$ $\displaystyle C^{2}_{k}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq12}}}{{=}}\mathbb{P}\Big{(}\sup_{kM<i\leq(k+1)M}S^{kM,i}(X)>\frac{k\hat{M}}{4}\Big{)}\stackrel{{\scriptstyle\ref{lem:rw2}}}{{\leq}}e^{-\frac{\Delta
k\hat{M}}{4}},$

where in the second equality of the first line we used (A.24). It follows that
for $\hat{M}>4\Delta^{-1}$

$\displaystyle\mathbb{P}\Big{(}\sup_{M<s}F(s)\geq
0\Big{)}\leq\sum_{k=1}^{\infty}2e^{-\frac{\Delta
k\hat{M}}{4}}+\mathbb{P}\Big{(}B_{k}^{c}\Big{)}\leq\sum_{k=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(k+1)M}\geq\frac{k\hat{M}}{8}\Big{)}+4e^{-\frac{\Delta\hat{M}}{4}}.$

The bound in (A.23) follows from substituting $\hat{M}\mapsto M\rho^{-2}\Delta
6^{-1}$ in the last display for $M>24\Delta^{-2}\rho^{2}$. ∎

###  A.3 Topological results

Recall the space $\mathcal{S}$ from Subsection 4.1.

######  Lemma A.13.

The metric space $(d,\mathcal{S})$ is complete and separable.

###### Proof.

To see that $\mathcal{S}$ is separable, let $\\{f^{n}_{i}\\}_{i=1}^{\infty}$
be a dense set in $C[-n,n]$, then $\bigcup_{i,n\geq 1}f^{n}_{i}$ is dense in
$\mathcal{S}$, showing that $\mathcal{S}$ is separable. Next we show that
$\mathcal{S}$ is complete. Let $\\{f_{i}\\}$ be a Cauchy sequence in
$\mathcal{S}$, and let $f^{n}_{i}=f_{i}|_{[-n,n]}$ be the restriction of
$f_{i}$ on the interval $[-n,n]$. As $C([-n,n])$ is complete, for any $n\geq
1$ $\exists g^{n}\in C([-n,n],\mathbb{R})$ such that

$\displaystyle d_{n}(f^{n}_{i},g^{n})\rightarrow 0\qquad\text{ as
}i\rightarrow\infty$ (A.26)

Define

$\displaystyle g(x):=g^{\lceil|x|\rceil}(x)\qquad x\in\mathbb{R},$

and note that $g\in\mathcal{S}$. It follows that for every $n$

$\displaystyle
d(f_{i},g)\leq\sum_{j=1}^{n}2^{-j}\frac{d_{j}(f_{i},g)}{1+d_{j}(f_{i},g)}+2^{-n+1},$

which along with (A.26) implies the completeness. ∎

From here until the end of the section, we assume $\mathcal{S}$ is a complete
separable space equipped with a metric $d$. Let us denote by
$\mathcal{M}(\mathcal{S})$ the set of probability measures on the Borel sigma
algebra generated by the metric on $\mathcal{S}$. Recall the Prohorov metric
$d_{\text{Proh}}:\mathcal{M}\times\mathcal{M}\rightarrow\mathbb{R}_{+}$ given
by

$\displaystyle
d_{\text{Proh}}(\mu,\nu)=\inf\big{\\{}\epsilon>0:\mu(A)\leq\nu(A^{\epsilon})+\epsilon\text{
and }\nu(A)\leq\mu(A^{\epsilon})+\epsilon\big{\\}}.$ (A.27)

The following holds

######  Lemma A.14.

[10][Theorem 6.8] Weak convergence in $\mathcal{M}(\mathcal{S})$ is equivalent
to convergence with respect to $d_{\text{Proh}}$, $\mathcal{M}(\mathcal{S})$
is a complete and separable metric space.

We recall the space $D(\mathbb{R},\mathcal{S})$ of rcll functions defined on
$\mathbb{R}$ and taking values in $\mathcal{S}$. We follow closely
[16][Chapter 3, Sections 5-9]. We note that in [16] the authors considered the
space $D([0,\infty),E)$, where $E$ is a complete separable metric space.
However, going over the relevant proofs in [16][Chapter 3] one concludes that
the extension to the real line i.e. $D(\mathbb{R},\mathcal{S})$ is
straightforward (See for example [18], where it was done for
$D(\mathbb{R},\mathbb{R})$). Nevertheless, as we use a slightly different
space than the one studied in [16] we define the metric on
$D(\mathbb{R},\mathcal{S})$ rather than just refer to [16].

Let $D(\mathbb{R},\mathcal{S})$ be the space of functions defined on
$\mathbb{R}$, that are right continuous with left limits in $\mathcal{S}$. Let
$\Lambda^{\prime}$ be the set of strictly increasing functions $\lambda$
mapping $\mathbb{R}$ to itself. Let $\Lambda$ be the set of Lipschitz
continuous functions $\lambda\in\Lambda^{\prime}$

$\displaystyle\gamma(\lambda)=\sup_{s<t}|\log\frac{\lambda(s)-\lambda(t)}{s-t}|<\infty.$

For $x,y\in D(\mathbb{R},\mathcal{S})$, define

$\displaystyle
r(x,y)=\inf_{\lambda\in\Lambda}\big{[}\gamma(\lambda)\vee\int_{0}^{\infty}e^{-u}r(x,y,\lambda,u)\big{]},$
(A.28)

where

$\displaystyle r(x,y,\lambda,u)=\sup_{0\leq t}d\big{(}x(t\wedge
u),y(\lambda(t)\wedge u)\big{)}\vee\sup_{0\geq t}d\big{(}x(t\vee
u),y(\lambda(t)\vee u)\big{)}.$

Since $\mathcal{S}$ is complete and separable, the space
$(D(\mathbb{R},\mathcal{S}),r)$ is also a complete and separable space (see
[16][Theorem 5.6]). We recall the modulus of continuity
$\omega:D(\mathbb{R},\mathcal{S})\times\mathbb{R}_{+}\times\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$
associated with the space $D(\mathbb{R},\mathcal{S})$. For $X\in
D(\mathbb{R},\mathcal{S})$ define

$\displaystyle\theta_{X}[a,b)=\sup_{s,t\in[a,b)}d\big{(}X(t),X(s)\big{)},$
(A.29)

and

$\displaystyle\omega(X,t,\delta)=\inf\\{\max_{1\leq i\leq
n}\theta_{X}[t_{i-1},t_{i})$ $\displaystyle:\exists n\geq
1,-t=t_{0}<t_{1}<...<t_{n}=t$ (A.30) $\displaystyle\text{such that
$t_{i}-t_{i-1}>\delta$ for all $i\leq n$}\\}.$

The following are a well known tightness criteria

######  Theorem A.15.

[16][Corollary 7.4]Let $\\{X^{N}\\}_{N\in\mathbb{N}}$ be a sequence of r.v.s
in $D\big{(}\mathbb{R},\mathcal{S}\big{)}$. Then $\\{X^{N}\\}$ is relatively
compact if and only if the following conditions hold:

  1. 1.

For every $\epsilon>0$ and $t$ rational there exists a compact set
$A_{t,\epsilon}$ such that

$\displaystyle\liminf_{N\rightarrow\infty}\mathbb{P}\Big{(}X^{N}(t)\in
A_{t,\epsilon}^{\epsilon}\Big{)}\geq 1-\epsilon.$ (A.31)

  2. 2.

For every $\epsilon>0$ and $T>0$

$\displaystyle\lim_{\delta\rightarrow
0}\limsup_{N\rightarrow\infty}\mathbb{P}\Big{(}\omega(X^{N},T,\delta)>\epsilon\Big{)}=0.$
(A.32)

######  Lemma A.16.

Suppose $\\{X^{N}\\}_{N\in\mathbb{N}}$ is a sequence of r.v.s in
$D(\mathbb{R},\mathcal{S})$. Let $t\in\mathbb{R}$. Assume that for every
$0<\epsilon<1$ there exists $0<\delta<1$ and
$N_{1}(\epsilon,\delta,t),C(\epsilon)>0$ such that for $N>N_{1}$

$\displaystyle\mathbb{P}\Big{(}\sup_{u,v\in(t-\delta,t+\delta]}d(X^{N}_{u},X^{N}_{v})>\epsilon\Big{)}<C\delta.$
(A.33)

Suppose further that

$\displaystyle X^{N}\Rightarrow X,$ (A.34)

for some $X\in D(\mathbb{R},\mathcal{S})$.Then $X$ is stochastically
continuous at $t$, i.e.

$\displaystyle\mathbb{P}(\Delta X_{t})=0.$

###### Proof.

From (A.34), w.l.o.g., we may assume that the convergence in (A.34) is an a.s.
one. It then follows that for every $\delta>0$ there exists a sequence
$\\{\lambda_{N}\\}_{N\geq 1}\subseteq\Lambda$ and $N_{0}(\delta,\epsilon)>0$
such that for $N>N_{0}$ (see [16][p.117])

$\displaystyle\mathbb{P}\Big{(}\lambda_{N}(t-\delta,t+\delta]\subseteq[t-2\delta,t+2\delta],\sup_{u\in(t-\delta,t+\delta]}d(X_{u},X^{N}_{\lambda_{N}(u)})<\frac{\epsilon}{4}\Big{)}>1-\epsilon/2.$
(A.35)

By the triangle inequality

$\displaystyle\Big{\\{}\sup_{u,v\in(t-\delta,t+\delta]}d(X_{u},X_{v})>\epsilon\Big{\\}}$
(A.36)
$\displaystyle\subseteq\Big{\\{}2\sup_{u\in(t-\delta,t+\delta]}d(X_{u},X^{N}_{\lambda_{N}(u)})>\epsilon/2\Big{\\}}\cap\Big{\\{}\sup_{u,v\in(t-\delta,t+\delta]}d(X^{N}_{\lambda_{N}(u)},X^{N}_{\lambda_{N}(v)})>\epsilon/2\Big{\\}}.$

It follows from (A.35) and (A.36) that for $N$ large enough

$\displaystyle\mathbb{P}\Big{(}\sup_{u,v\in(t-\delta,t+\delta]}d(X_{u},X_{v})>\epsilon\Big{)}$
$\displaystyle\leq\frac{\epsilon}{2}+\mathbb{P}\Big{(}\sup_{u,v\in(t-2\delta,t+2\delta]}d(X^{N}_{u},X^{N}_{v})>\epsilon/2\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ub68}}}{{<}}\frac{\epsilon}{2}+2C\delta.$

Setting $\delta=\frac{\epsilon}{4C}$

$\displaystyle\mathbb{P}\Big{(}\sup_{u,v\in(t-\delta,t+\delta]}d(X_{u},X_{v})>\epsilon\Big{)}<\epsilon,$

which implies the result as $\epsilon$ is arbitrary small. ∎

######  Lemma A.17.

Let $\\{X^{N}\\}_{N\in\mathbb{N}}$ be a sequence of r.v.s in
$D\big{(}\mathbb{R},\mathcal{S}\big{)}$. Let $T\subseteq\mathbb{R}$ be dense.
Suppose that

  1. 1.

For every $t\in T$ and $0<\epsilon<1$, there exists $0<\delta<1$ and
$N_{1}(\epsilon,\delta),C(\epsilon)>0$ such that for $N>N_{1}$

$\displaystyle\mathbb{P}\Big{(}\sup_{u,v\in(t-\delta,t+\delta]}d(X^{N}_{u},X^{N}_{v})>\epsilon\Big{)}<C\delta.$

  2. 2.

For $k\in\mathbb{N}$ and any $t_{1},...,t_{k}\in T$

$\displaystyle(X^{N}_{t_{1}},...,X^{N}_{t_{k}})\Rightarrow
p_{t_{1},...,t_{k}},$

for some $p_{t_{1},...,t_{k}}\in\mathcal{M}(\mathcal{S}^{k})$.

  3. 3.

$\\{X^{N}\\}_{N\in\mathbb{N}}$ satisfy (A.32).

Then there exists a unique process $X\in D(\mathbb{R},\mathcal{S})$ with
finite dimensional distributions $p_{\cdot}$, such that

$\displaystyle X^{N}\Rightarrow X.$ (A.37)

###### Proof.

From Condition 2, for every $t\in T$ the sequence of distributions
$\\{X^{N}_{t}\\}$ is convergent. As $\mathcal{S}$ is complete and separable,
this sequence is also tight, which implies that (A.31) in Theorem A.15 holds
for $\\{X^{N}_{t}\\}$ which implies that Condition 1 holds for $\\{X^{N}\\}$
(see [16][Theorem 2.2, Chapter 3]). Now suppose Condition 3 holds. As
$\\{X^{N}\\}$ satisfies both Conditions 1 and 2 of Theorem A.15, the sequence
$\\{X^{N}\\}_{N\in\mathbb{N}}$ is sequentially compact. We can therefore find
a subsequence $\\{N_{m}\\}_{m\in\mathbb{N}}$ such that $X^{N_{m}}\Rightarrow
X$ as $m$ goes to infinity for some $X\in D(\mathbb{R},\mathcal{S})$. Take
$T^{\prime}\subseteq T$ countable. Next we claim that for $t_{1},...,t_{k}\in
T^{\prime}$

$\displaystyle(X^{N_{m}}_{t_{1}},...,X^{N_{m}}_{t_{k}})\Rightarrow(X_{t_{1}},...,X_{t_{k}})\quad\text{as
$m\rightarrow\infty$}.$ (A.38)

In order to show (A.38) we will invoke the Continuous Mapping Theorem, for
which application we will need to show that $X$ is stochastically continuous.
But this follows from Condition 1 and Lemma A.16. We continue showing(A.38) by
considering the family of projections
$\pi_{t_{1},...,t_{k}}:D(\mathbb{R},\mathcal{S})\rightarrow\mathcal{S}^{k}$
for any $k\in\mathbb{N}$ and $(t_{1},...,t_{k})\in\mathbb{R}^{k}$, given by
$\pi_{t_{1},...,t_{k}}Y=(Y_{t_{1}},...,Y_{t_{k}})$ for any $Y\in
D(\mathbb{R},\mathcal{S})$. The mapping $\pi_{t_{1},...,t_{k}}$ is continuous
at functions in $D(\mathbb{R},\mathcal{S})$ that are continuous at the points
$t_{1},...,t_{k}$. From the stochastic continuity of $X$ we conclude that with
probability one, $\pi_{t_{1},...,t_{k}}$ is continuous at $X$ for every
$k\in\mathbb{N}$ and $t_{1},...,t_{k}\in T^{\prime}$. Fix $k\in\mathbb{N}$ and
$t_{1},...,t_{k}\in T^{\prime}$. From the continuous mapping theorem we
conclude that the following distributional limit holds

$\displaystyle\lim_{m\rightarrow\infty}\pi_{t_{1},...,t_{k}}X^{N_{m}}=\pi_{t_{1},...,t_{k}}X.$

We have thus proven A.38. From Condition 2 we conclude that if $X^{1}$ and
$X^{2}$ are two sub-sequential limits of $X^{N}$ then

$\displaystyle\pi_{t_{1},...,t_{k}}X^{1}\sim\pi_{t_{1},...,t_{k}}X^{2}\quad\forall
t_{1},...,t_{k}\in T^{\prime}.$ (A.39)

As the set $\mathcal{S}$ is separable, by [16][Proposition 7.1] the sigma
algebra $\mathfrak{S}$ generated by $D(\mathbb{R},\mathcal{S})$ equals the
sigma algebra $\sigma(\pi_{t}:t\in T^{\prime})$ i.e.

$\displaystyle\mathfrak{S}=\sigma(\pi_{t}:t\in T^{\prime}).$ (A.40)

From (A.40) and (A.39) it follows that

$\displaystyle X^{1}\sim X^{2},$

which implies (A.37). ∎

###  A.4 Proofs of some computations appearing in the text

###### proof of (4.93):.

From (4.2.3)

$\displaystyle\sum_{l=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(l+1)\tau
a_{j}^{R}}\geq\tau
a_{j}^{R}\frac{l\Delta_{min}}{\rho_{1}^{2}48}\Big{)}=\sum_{l=1}^{\infty}(l+1)\tau
a_{j}^{R}Ce^{-c\cdot c_{2}l},$

where we used (4.90) and where $c_{2}=\frac{\tau
a_{j}^{R}\Delta_{min}}{\rho_{1}^{2}48}$. Let

$\displaystyle c_{3}=c_{2}\cdot c=\frac{\tau
a_{j}^{R}\Delta_{min}}{\rho_{1}^{2}48}\times\frac{\rho_{k}}{7^{k}k}.$ (A.41)

Compute

$\displaystyle\sum_{l=1}^{\infty}(l+1)e^{-c_{3}l}\leq
2\sum_{l=1}^{\infty}le^{-c_{3}l}\leq
2e^{-c_{3}}+2\int_{1}^{\infty}xe^{-c_{3}x}dx$
$\displaystyle=2e^{-c_{3}}+2[-xc_{3}^{-1}e^{-c_{3}x}|_{1}^{\infty}+\int_{1}^{\infty}c_{3}^{-1}e^{-c_{3}x}dx]$
$\displaystyle=2e^{-c_{3}}[1+c_{3}^{-1}+c_{3}^{-2}].$

From (A.41), for
$a_{j}^{R}>R\geq\Big{[}\frac{\Delta_{min}}{\rho_{1}^{2}48}\times\frac{\rho_{k}}{7^{k}k}\Big{]}^{-1}$,
the last line in the above display is bounded by $6e^{-c_{3}}$ so that

$\displaystyle\sum_{l=1}^{\infty}\mathbb{P}\Big{(}\mathcal{C}_{(l+1)\tau
a_{j}^{R}}\geq\tau a_{j}^{R}\frac{l\Delta_{min}}{\rho_{1}^{2}48}\Big{)}$
$\displaystyle\leq\tau a_{j}^{R}6Ce^{-c_{4}\tau
R}\stackrel{{\scriptstyle\eqref{ub50}}}{{\leq}}4^{k}(\tau R+5)6Ce^{-c_{4}\tau
R}$

where

$\displaystyle
c_{4}=\frac{\Delta_{min}}{\rho_{1}^{2}48}\times\frac{\rho_{k}}{7^{k}k}.$

∎

###### Proof.

[Proof of (3.28)]

$\displaystyle=2\int_{0}^{\infty}2^{-M}e^{-2^{-M}t}(1-e^{-2^{-M}t})\Big{(}4e^{-\frac{1}{32}(2x_{0}+1)^{-1/2}{N^{-1/3}N^{1/3}t}+1}+4(2x_{0}^{N}+1)e^{-N^{1/3}t/32}\Big{)}dt$
$\displaystyle=8e\frac{2^{-M}}{2^{-M}+\tfrac{1}{32}(2x_{0}+1)^{-1/2}}+8\cdot
2^{-M}(2x_{0}^{N}+1)\frac{1}{2^{-M}+\tfrac{1}{32}N^{1/3}}$
$\displaystyle-\Big{[}8e\frac{2^{-M}}{2^{-M+1}+\tfrac{1}{32}(2x_{0}+1)^{-1/2}}+8\cdot
2^{-M}(2x_{0}^{N}+1)\frac{1}{2^{-M+1}+\tfrac{1}{32}N^{1/3}}\Big{]}$
$\displaystyle=8e\frac{2^{-2M}}{(2^{-M}+\tfrac{1}{32}(2x_{0}+1)^{-1/2})(2^{-M+1}+\tfrac{1}{32}(2x_{0}+1)^{-1/2})}$
$\displaystyle+8(2x_{0}^{N}+1)\frac{2^{-2M}}{(2^{-M}+\tfrac{1}{32}N^{1/3})(2^{-M+1}+\tfrac{1}{32}N^{1/3})}$
$\displaystyle\leq
2^{5}(32)^{2}(2x_{0}+1)2^{-2M}+2^{3}(32)^{2}(2x_{0}+1)2^{-2M}\leq
2^{17}x_{0}2^{-2M}+2^{15}x_{0}2^{-2M}\leq 2^{18}x_{0}2^{-2M}$

∎

###### Proof of (4.16).

From [2, Lemma 5.8]

$\displaystyle\mathbb{P}(\text{the event in \eqref{eq15}})\leq
1-\frac{\beta}{\alpha}+\int\Big{[}\frac{\alpha}{\alpha+\theta}\frac{\beta}{\beta-\theta}\Big{]}^{2nN^{2/3}}e^{-\theta
w}\frac{(\alpha-\beta)\beta}{\alpha}e^{-(\alpha-\beta)w}dw.$ (A.42)

For $N>|\mu-\delta|^{3}$

$\displaystyle
1-\frac{\beta}{\alpha}\leq\frac{\frac{\delta}{4}N^{-1/3}}{1/2-\frac{\mu-\delta}{4}N^{-1/3}}\leq\delta
N^{-1/3}.$ (A.43)

Setting
$\alpha=1/2-\frac{\mu-\delta}{4}N^{-1/3},\beta=1/2-\frac{\mu}{4}N^{-1/3}$ and
$\theta=N^{-1/3}$

$\displaystyle\Big{[}\frac{\alpha}{\alpha+\theta}\frac{\beta}{\beta-\theta}\Big{]}^{2nN^{2/3}}=\Big{[}1+\frac{\theta^{2}+\theta(\alpha-\beta)}{\alpha\beta+\theta(\beta-\alpha)-\theta^{2}}\Big{]}^{2nN^{2/3}}$
(A.44)

For $N\geq 2(4+\delta+|\mu|)^{3}\geq 2(5+|\mu|)^{3}$

$\displaystyle(\alpha\beta)+[\theta(\beta-\alpha)-\theta^{2}]\geq(1/4-\mu/4N^{-1/3})-[(1+\delta/4)N^{-1/3}]>1/8$
(A.45)

Using (A.45) in (A.44) to obtain

$\displaystyle\Big{[}\frac{\alpha}{\alpha+\theta}\frac{\beta}{\beta-\theta}\Big{]}^{2nN^{2/3}}\leq\big{[}1+8(1+\delta/4)N^{-2/3}\big{]}^{2nN^{2/3}}\leq
e^{2n(8+2\delta)}\leq e^{10n}.$ (A.46)

Finally

$\displaystyle\int e^{-\theta
w}\frac{(\alpha-\beta)\beta}{\alpha}e^{-(\alpha-\beta)w}dw\leq\frac{\delta}{4}N^{-1/3}\int
e^{-(\alpha-\beta+\theta)w}dw\leq\frac{\delta}{4(1+\delta/4)}.$ (A.47)

Plugging (A.43), (A.46) and (A.47) in (A.42) we see that for $N\geq
2(5+|\mu|)^{3}$

$\displaystyle\eqref{ub74}\leq\delta
N^{-1/3}+e^{2n(8+2\delta)}\frac{\delta}{4(1+\delta/4)}\leq\delta(1+e^{10n}).$

∎

## References

  * [1] J. Baik, P.A. Deift, and K. Johansson.  On the distribution of the length of the longest increasing subsequence of random permutations.  J. Amer. Math. Soc., 12:1119–1178, 1999.
  * [2] M. Balázs, O. Busani, and T. Seppäläinen.  Local stationarity of exponential last passage percolation.  Probab. Theory Relat. Fields, 180:113–162, 2021.
  * [3] Márton Balázs, Ofer Busani, and Timo Seppäläinen.  Non-existence of bi-infinite geodesics in the exponential corner growth model.  Forum Math. Sigma, 8:Paper No. e46, 34, 2020.
  * [4] Y. Baryshnikov.  GUEs and queues.  Probab. Theory Relat. Fields, 119:256–274, 2001.
  * [5] Riddhipratim Basu, Shirshendu Ganguly, and Alan Hammond.  Fractal geometry of $\rm Airy_{2}$ processes coupled via the Airy sheet.  Ann. Probab., 49(1):485–505, 2021.
  * [6] Riddhipratim Basu, Christopher Hoffman, and Allan Sly.  Nonexistence of bigeodesics in integrable models of last passage percolation.  2018\.  arXiv:1811.04908.
  * [7] Riddhipratim Basu, Sourav Sarkar, and Allan Sly.  Coalescence of geodesics in exactly solvable models of last passage percolation.  J. Math. Phys., 60(9):093301, 22, 2019.
  * [8] Erik Bates, Shirshendu Ganguly, and Alan Hammond.  Hausdorff dimensions for shared endpoints of disjoint geodesics in the directed landscape.  Electron. J. Probab., 27:–, 2022.
  * [9] Philippe Biane, Philippe Bougerol, and Neil O’Connell.  Littelmann paths and Brownian paths.  Duke Math. J., 130(1):127–167, 2005.
  * [10] P. Billingsley.  Convergence of Probability Measures.  Wiley ed., New York, 1968.
  * [11] P.J. Burke.  The output of a queuing system.  Operations Res., 4:699–704, 1956.
  * [12] Ofer Busani and Patrik Ferrari.  Universality of the geodesic tree in last passage percolation.  Ann. Probab., to appear - 2020.
  * [13] Duncan Dauvergne.  Last passage isometries for the directed landscape.  arXiv preprint arXiv:2106.07566, 2021.
  * [14] Duncan Dauvergne, Janosch Ortmann, and Bálint Virág.  The directed landscape.  arXiv preprint arXiv:1812.00309, 2018.
  * [15] Duncan Dauvergne and Bálint Virág.  The scaling limit of the longest increasing subsequence.  arXiv preprint arXiv:2104.08210, 2021.
  * [16] Stewart N. Ethier and Thomas G. Kurtz.  Markov processes.  Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986.  Characterization and convergence.
  * [17] W. Fan and T. Seppäläinen.  Joint distribution of Busemann functions in the exactly solvable corner growth model.  Prob. Math. Phys., 1:55–100, 2018.
  * [18] D. Ferger and D. Vogel.  Weak convergence of the empirical process and the rescaled empirical distribution function in the Skorokhod product space.  Teor. Veroyatn. Primen., 54(4):750–770, 2009.
  * [19] Shirshendu Ganguly and Milind Hegde.  Local and global comparisons of the airy difference profile to brownian local time.  2021\.
  * [20] Nicos Georgiou, Firas Rassoul-Agha, and Timo Seppäläinen.  Geodesics and the competition interface for the corner growth model.  Probab. Theory Related Fields, 169(1-2):223–255, 2017.
  * [21] Nicos Georgiou, Firas Rassoul-Agha, and Timo Seppäläinen.  Stationary cocycles and Busemann functions for the corner growth model.  Probab. Theory Related Fields, 169(1-2):177–222, 2017.
  * [22] Peter W. Glynn and Ward Whitt.  Departures from many queues in series.  Ann. Appl. Probab., 1(4):546–572, 1991.
  * [23] Janko Gravner, Craig A. Tracy, and Harold Widom.  Limit theorems for height fluctuations in a class of discrete space and time growth models.  J. Statist. Phys., 102(5-6):1085–1132, 2001.
  * [24] Christopher Hoffman.  Geodesics in first passage percolation.  Ann. Appl. Probab., 18(5):1944–1969, 2008.
  * [25] C. Douglas Howard and Charles M. Newman.  Euclidean models of first-passage percolation.  Probab. Theory Related Fields, 108(2):153–170, 1997.
  * [26] C. Douglas Howard and Charles M. Newman.  Geodesics and spanning trees for Euclidean first-passage percolation.  Ann. Probab., 29(2):577–623, 2001.
  * [27] Christopher Janjigian, Firas Rassoul-Agha, and Timo Seppäläinen.  Geometry of geodesics through busemann measures in directed last-passage percolation.  arXiv preprint arXiv:1908.09040, 2019.
  * [28] Cristina Licea and Charles M. Newman.  Geodesics in two-dimensional first-passage percolation.  Ann. Probab., 24(1):399–410, 1996.
  * [29] Konstantin Matetski, Jeremy Quastel, and Daniel Remenik.  The KPZ fixed point.  Acta Math., 227(1):115–203, 2021.
  * [30] Charles M. Newman.  A surface view of first-passage percolation.  In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), pages 1017–1023. Birkhäuser, Basel, 1995.
  * [31] Neil O’Connell.  A path-transformation for random walks and the Robinson-Schensted correspondence.  Trans. Amer. Math. Soc., 355(9):3669–3697, 2003.
  * [32] Neil O’Connell and Marc Yor.  A representation for non-colliding random walks.  Electron. Comm. Probab., 7:1–12, 2002.
  * [33] Leandro P. R. Pimentel.  Duality between coalescence times and exit points in last-passage percolation models.  Ann. Probab., 44(5):3187–3206, 2016.
  * [34] Leandro P. R. Pimentel.  Local behaviour of airy processes.  J. Stat. Phys., 173(6):1614–1638, 2018.
  * [35] Leandro P. R. Pimentel.  Ergodicity of the KPZ fixed point.  ALEA Lat. Am. J. Probab. Math. Stat., 18(1):963–983, 2021.
  * [36] M. Prähofer and H. Spohn.  Scale invariance of the PNG droplet and the Airy process.  J. Stat. Phys., 108:1071–1106, 2002.
  * [37] Mustazee Rahman and Balint Virag.  Infinite geodesics, competition interfaces and the second class particle in the scaling limit.  arXiv preprint arXiv:2112.06849, 2021.
  * [38] Firas Rassoul-Agha.  Busemann functions, geodesics, and the competition interface for directed last-passage percolation.  In Random growth models, volume 75 of Proc. Sympos. Appl. Math., pages 95–132. Amer. Math. Soc., Providence, RI, 2018.
  * [39] H. Rost.  Non-equilibrium behavior of a many particle system: density profile and local equilibrium.  Z. Wahrsch. Verw. Gebiete, 58:41–53, 1981.
  * [40] Timo Seppäläinen.  Variational formulas, busemann functions, and fluctuation exponents for the corner growth model with exponential weights.  arXiv preprint arXiv:1709.05771, 2017.
  * [41] Timo Seppäläinen and Xiao Shen.  Coalescence estimates for the corner growth model with exponential weights.  Electron. J. Probab., 25:Paper No. 85, 31, 2020.
  * [42] Timo Seppäläinen and Evan Sorensen.  Busemann process and semi-infinite geodesics in brownian last-passage percolation.  arXiv preprint arXiv:2103.01172, 2021.
  * [43] Timo Seppäläinen and Evan Sorensen.  Global structure of semi-infinite geodesics and competition interfaces in brownian last-passage percolation.  arXiv preprint arXiv:2112.10729, 2021.
  * [44] W. Szczotka and F. P. Kelly.  Asymptotic stationarity of queues in series and the heavy traffic approximation.  Ann. Probab., 18(3):1232–1248, 1990.


# Counting symmetric and non-symmetric peaks in a set partition

Walaa Asakly and Noor Kezil
Department of Mathmatics, Braude collage, Karmial, Israel
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

The aim of this paper is to derive explicit formulas for two distinct values.
The first is the total number of symmetric peaks in a set partition of $[n]$
with exactly $k$ blocks, and the second one is the total number of non-
symmetric peaks in a set partition of $[n]$ with exactly $k$ blocks. We
represent these results in two ways. First by using the theory of generating
functions, and the second by using combinatorial tools.

Keywords: Symmetric peaks, Non-symmetric peaks, Set partitions and Generating
functions.

##  1 Introduction

A partition $\Pi$ of set $[n]=\\{1,2,\cdots,n\\}$ of size $k$ (a partition of
$[n]$ with exactly $k$ blocks) is a collection
$\\{B_{1},B_{2},\ldots,B_{k}\\}$ that satisfies: $\emptyset\neq
B_{i}\subseteq[n]$ for all $i$, $B_{i}\bigcap B_{j}=\emptyset$ for $i\neq j$
and $\bigcup_{i=1}^{k}B_{i}=[n]$. The elements $B_{i}$ are called blocks, we
use the assumption that blocks are listed in an increasing order of their
minimal elements, that is, $\min B_{1}<\min B_{2}<\cdots<\min B_{k}$. We
denote the set of all partitions of $[n]$ with exactly $k$ blocks by
$P_{n,k}$, and $|P_{n,k}|=S_{n,k}$, which are known as the Stirling numbers of
the second kind, see [13]. A partition $\Pi$ can be written as
$\pi_{1}\pi_{2}\cdots\pi_{n}$, where $i\in B_{\pi_{i}}$ for all $i$, this form
is called the canonical sequential form. For example,
$\Pi=\\{\\{12\\},\\{3\\}\\}$ is a partition of $[3]$, the canonical sequential
form is $\pi=112$. Then we can see that any partition $\Pi$ of set $[n]$ with
exactly $k$ blocks can be represented as a word of length $n$ over alphabet
$[k]$ (a word $\omega$ of length $n$ over alphabet $[k]$ is an element of
$[k]^{n}$, see [3]) of the form $1(1)^{*}2(2)^{*}\cdots,k(k)^{*}$, where
$(m)^{*}$ is a word over alphabet $[m]$. These words are called restricted
growth functions. For extra properties about set partitions see [8].

The study of occurrence patterns in combinatorial structures is popular. For
example, Kitaev [4] researched patterns in permutations and words. For more
examples of patterns in various combinatorial structures, refer to [5], [6],
[9] and [12]. Let $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in[k]^{n}$, a pattern
$\pi_{i}\pi_{i+1}\pi_{i+2}$ where, $1\leq i\leq n-2$, that satisfies
$\pi_{i}<\pi_{i+1}>\pi_{i+2}$ is called a peak at $i$. For instance, if
$\pi=1322141251$ is a word of $[5]^{10}$, it has $3$ peaks, which are, $132$,
$141$ and $251$. Mansour and Shattuck [10] determined the number of peaks in
all words of length $n$ over alphabet $[k]$, and derived the number of peaks
over $P_{n,k}$. We say that $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in[k]^{n}$
contains a symmetric peak, if exists $1\leq i\leq n-2$ such that
$\pi_{i}\pi_{i+1}\pi_{i+2}$ is a peak, and $\pi_{i}=\pi_{i+2}$, and we say
that $\pi$ contains a non-symmetric peak, if exists $1\leq i\leq n-2$ such
that $\pi_{i}\pi_{i+1}\pi_{i+2}$ is a peak and $\pi_{i}\neq\pi_{i+2}$. In the
case of the example $\pi=1322141251$, there is one symmetric peak, denoted as
$141$, and two non-symmetric peaks, namely $132$ and $251$. Asakly [1]
determined the number of symmetric and non-symmetric peaks in all words of
length $n$ over alphabet $[k]$. More recently, other researchers have studied
symmetric and non-symmetric peaks in different combinatorial structures. For
additional information refer to [2] and [14]. In this paper, we aim to
determine the total number of symmetric and non-symmetric peaks over
$P_{n,k}$. Mansour, Shattuck and H.F. Yan [11] found the total number of
occurrences of the subword pattern $121$ (a symmetric peak) in all the
partitions of $[n]$ with exactly $k$ blocks. Additionally, they found the
number of occurrences of the subword patterns $231$ and $321$ (non-symmetric
peaks) in all the partitions of $[n]$ with exactly $k$ blocks. We will provide
another proofs that give the same results through two different ways. First
one by using the theory of generating functions and the results that Asakly
[1] obtained, and the second one by using combinatorial tools.

###  1.1 Counting symmetric peaks

####  1.1.1 The ordinary generating function for the number of partitions with
exactly $k$ blocks according to the number of symmetric peaks

We denote the number of symmetric peaks in partition $\pi$ to be ${\rm
sp}(\pi)$. Let $SP_{k}(x,q)$ be the ordinary generating function for the
number of partitions of $[n]$ with exactly $k$ blocks according to the number
of symmetric peaks, that is

$SP_{k}(x,q)=\sum_{n\geq k}x^{n}\sum_{\pi\in P_{n,k}}q^{{\rm sp}(\pi)}.$

###### Theorem 1

The generating function for the number of partitions of $[n]$ with exactly $k$
blocks, according to the number of symmetric peaks, is given by

$SP_{k}(x,q)=x^{k}(xq+1-x)^{k-1}\prod_{j=1}^{k}\left(W_{j}(x,q)\right).$

Where,

$W_{j}(x,q)=\frac{x(q-1)+(1-x(q-1))W_{j-1}(x,q)}{1-x(1-q)(1-(j-1)x)-xW_{j-1}(x,q)(x(j-1)+q(1-x(j-1)))}.$

##### Proof

In this context we want to use the canonical sequential form of a partition
$\pi$ of $[n]$ with exactly $k$ blocks. Any partition $\pi$ of $[n]$ with
exactly $k$ blocks, can be decomposed as, $\pi=\pi^{\prime}k\omega$, where
$\pi^{\prime}$ is a partition of $[n_{1}]$ with exactly $k-1$ blocks and
$\omega$ is a word of length $n_{2}$ over alphabet $[k]$, satisfying
$n_{1}+1+n_{2}=n$. The word $\omega$ is either empty, starts with a letter
equal to the last letter in $\pi^{\prime}$, or starts with a letter different
to the last letter of $\pi^{\prime}$. Let $W_{k}(x,q)$ be the generating
function for the number of words $\omega$ of length $n$ over alphabet $[k]$,
according to the statistic of symmetric peaks. By Asakly’s result see [1], we
have

$W_{k}(x,q)=\frac{x(q-1)+(1-x(q-1))W_{k-1}(x,q)}{1-x(1-q)(1-(k-1)x)-xW_{k-1}(x,q)(x(k-1)+q(1-x(k-1)))}.$

The corresponding generating functions for the aforementioned cases are,

$xSP_{k-1}(x,q),$ $x^{2}qSP_{k-1}(x,q)W_{k}(x,q),$
$xSP_{k-1}(W_{k}(x,q)-xW_{k}(x,q)-1).$

These lead to

$SP_{k}(x,q)=xSP_{k-1}(1+xqW_{k}(x,q)+(W_{k}(x,q)-xW_{k}(x,q)-1)),$

with initial conditions, $SP_{0}(x,q)=1$ and $SP_{1}(x,q)=\frac{x}{1-x}$. By
induction, we obtain the required result. $\Box$

Note that, by substituting $q=1$ in Theorem 1, we obtain
$SP(x,1)=x^{k}\prod_{j=1}^{k}W_{j}(x,1)=x^{k}\prod_{j=1}^{k}\frac{1}{1-jx}$
which is the generating function for the number of partitions of $[n]$ with
$k$ blocks.
We aim to prove that the total number of the symmetric peaks over all
partitions of $[n]$ with exactly $k$ blocks is

$(k-1)S_{n-1,k}+\sum_{j=2}^{k}\binom{j}{2}\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}.$

We need to perform as follows:
$\bullet$ Firstly, differentiate the generating function $SP(x,y,q)$ with
respect to the variable $q$.
$\bullet$ Secondly, substitute $q=1$ in $\frac{\partial}{\partial q}SP(x,q)$
$\bullet$ Finally, find the coefficients of $x^{n}$ in
$\frac{\partial}{\partial q}SP_{k}(x,q)\mid_{q=1}$ to obtain the total number
of symmetric peaks over all $P_{n,k}$.

###### Lemma 2

The partial derivative $\frac{\partial}{\partial q}SP(x,q)\mid_{q=1}$ is given
by

$\frac{\partial}{\partial
q}SP(x,q)\mid_{q=1}=(k-1)xSP_{k}(x,1)+SP_{k}(x,1)\sum_{m\geq
1}^{k}\frac{x^{3}\binom{m}{2}}{(1-mx)}.$ (1)

##### Proof

We need to differentiate the generating function $SP(x,q)$ with respect to the
variable $q$ and then evaluate the result at $q=1$:

$\displaystyle\frac{\partial}{\partial q}SP(x,q)\mid_{q=1}$
$\displaystyle=x^{k+1}(k-1)(xq+1-x)^{k-2}\prod_{j=1}^{k}W_{j}(x,q)\mid_{q=1}$
$\displaystyle+x^{k}(xq+1-x)^{k-1}\left(\sum_{m=1}^{k}\frac{\partial}{\partial
q}W_{m}(x,q)\prod_{j=1,j\neq m}^{k}W_{j}(x,q)\right)\mid_{q=1}$
$\displaystyle=x^{k+1}(k-1)\prod_{j=1}^{k}W_{j}(x,1)+x^{k}\left(\sum_{m=1}^{k}\frac{\frac{\partial}{\partial
q}W_{m}(x,q)}{W_{m}(x,q)}\prod_{j=1}^{k}W_{j}(x,q)\right)\mid_{q=1},$

this leads to,

$\frac{\partial}{\partial
q}SP(x,q)\mid_{q=1}=x^{k+1}(k-1)\prod_{j=1}^{k}W_{j}(x,1)+x^{k}\left(\sum_{m=1}^{k}\frac{\frac{\partial}{\partial
q}W_{m}(x,1)}{W_{m}(x,1)}\prod_{j=1}^{k}W_{j}(x,1)\right),$ (2)

using the facts that,

$SP(x,1)=x^{k}\prod_{j=1}^{k}W_{j}(x,1)=x^{k}\prod_{j=1}^{k}\frac{1}{1-jx},$
(3)

and

$\frac{\partial}{\partial
q}W_{k}(x,q)\mid_{q=1}=\frac{x^{3}\binom{k}{2}}{(1-kx)^{2}},$ (4)

(see Asakly [1] for more details), together in (2), we get the required.
$\Box$

###### Corollary 3

The total number of symmetric peaks in all partitions of $[n]$ with exactly
$k$ blocks is given by

$(k-1)S_{n-1,k}+\sum_{j=2}^{k}\binom{j}{2}\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}.$

##### Proof

In order to enumerate the total number of all partitions of $[n]$ with exactly
$k$ blocks according to the symmetric peaks, we need to find the coefficients
of $x^{n}$ in (1). Due to the fact,

$SP(x,1)=\frac{x^{k}}{\prod_{j=1}^{k}(1-jx)}=\sum_{r\geq k}S_{r,k}x^{r}.$ (5)

we get the required result. $\Box$

####  1.1.2 Combinatorial proof

In this subsection, we want to show a combinatorial proof for Corollary (3).
For that, we need the following definitions. Consider any set partition
$\pi=\pi_{1}\pi_{2}\dots\pi_{n}$ represented by its canonical sequence. We say
that $\pi$ contains a rise (descent) at $i$ if
$\pi_{i}<\pi_{i+1}(\pi_{i}>\pi_{i+1})$. For instance, $\pi=1121324323\in
P_{10,4}$, we have $4$ rises at $i=2,4,6,9$ and we have $4$ descents at
$i=3,5,7,8$. Consider any set partition $\pi$, we say that $\pi_{i}$ is a
record if $\pi_{i}>\pi_{j}$ for $j<i$, and $i$ is called the index of the
record $\pi_{i}$ (see [7]).

##### Proof

Let us divide the proof into two distinct parts. In the first part, our focus
is on symmetric peaks $\pi_{\ell}\pi_{\ell+1}\pi_{\ell+2}$, where
$\pi_{\ell+1}$ is a record. In the second part, our attention will turn to a
symmetric peak, where $\pi_{\ell+1}$ is not a record. Let
$\pi=\pi_{1}\pi_{2}\dots\pi_{n-1}$ be a canonical sequential form for $\Pi\in
P_{n-1,k}$. Choose any record $\pi_{\ell+1}$ in $\Pi\in P_{n-1,k}$, where
$1\leq\ell\leq n-1$, and denote $a=\pi_{\ell}$. It is obvious that we have a
rise at $\ell$. Add $\ell+2$ to block $a$ and increase by one any member in
their block that is greater or equal to $\ell+2$. As a result, we get the
canonical sequential form
$\pi^{\prime}=\pi_{1}\pi_{2}\cdots\pi_{\ell}\pi_{\ell+1}a\pi_{\ell+2}\cdots\pi_{n-1}$,
where $\pi_{\ell+1}a\pi_{\ell+2}$ forms a symmetric peak. With $k-1$ options
for choosing a record, we have a total of $(k-1)S_{n-1,k}$ symmetric peaks.

Considering $i$ and $j$, where $3\leq i\leq n-k$ and $2\leq j\leq k$, the
total number of symmetric peaks at $\ell$ where $\pi_{\ell+1}$ is not a record
can be determined by summing the optional partitions in $P_{n,k}$ that can be
decomposed as $\pi=\pi^{\prime\prime}j\alpha\beta$ for each $i$ and $j$. Here,
$\pi^{\prime\prime}$ is a partition with $j-1$ blocks, $\alpha$ is a word of
length $i$ over alphabet $[j]$ whose last three letters forming a symmetric
peak, and $\beta$ may be an empty word. There are ${j\choose
2}j^{i-3}S_{n-i,k}$ members of $P_{n,k}$ with this form. This is because there
are $j^{i-3}$ choices for the first $i-3$ letters of $\alpha$, ${j\choose 2}$
for the final three letters in $\alpha$ (representing a symmetric peak), and
$S_{n-i,k}$ choices for the remaining letters $\pi=\pi^{\prime\prime}j\beta$,
ensuring that they form a partition of an $(n-i)$-set into $k$ blocks. $\Box$

###  1.2 Counting non-symmetric peaks

####  1.2.1 The ordinary generating function for the number of partitions with
exactly $k$ blocks according to the number of non-symmetric peaks

We denote the number of non-symmetric peaks in partition $\pi$ to be ${\rm
nsp}(\pi)$. Let $NSP_{k}(x,q)$ be the ordinary generating function for the
number of partitions of $[n]$ with exactly $k$ blocks according to the number
of non-symmetric peaks, that is

$NSP_{k}(x,q)=\sum_{n\geq k}x^{n}\sum_{\pi\in P_{n,k}}q^{{\rm nsp}(\pi)}.$

###### Theorem 4

The generating function for the number of partitions of $[n]$ with exactly $k$
blocks according to the number of non-symmetric peaks is given by

$NSP_{k}(x,q)=x^{k}\prod_{i=1}^{k}\widetilde{W}_{i}(x,q)\prod_{j=3}^{k}\left((j-2)xq+1-(j-2)x\right).$

Where,

$\widetilde{W}_{j}(x,q)=\frac{x(q-1)+(1-x(q-1))\widetilde{W}_{j-1}(x,q)}{1-x(1-q)(1-2x)-x\widetilde{W}_{j-1}(x,q)(2x+q(1-2x))}.$

##### Proof

Let $\pi$ be any partition of $[n]$ with exactly $k$ blocks, it can be
decomposed as, $\pi=\pi^{\prime}k\omega$, where $\pi^{\prime}$ is a partition
of $[n_{1}]$ with exactly $k-1$ blocks and $\omega$ is a word of length
$n_{2}$ over alphabet $[k]$ satisfying $n_{1}+1+n_{2}=n$. The word $\omega$ is
either empty, starts with a letter different from the last letter in
$\pi^{\prime}$, or starts with a letter equal to the last letter of
$\pi^{\prime}$. Let

$\widetilde{W}_{k}(x,q)=\frac{x(q-1)+(1-x(q-1))\widetilde{W}_{k-1}(x,q)}{1-x(1-q)(1-2x)-x\widetilde{W}_{k-1}(x,q)(2x+q(1-2x))},$

be the generating function for the number of words $\omega$ of length $n$ over
alphabet $[k]$ according to the statistic non-symmetric peaks (see [1]). Then
the corresponding generating functions for the above cases respectively are,

$xNSP_{k-1}(x,q),$ $x^{2}(j-2)qNSP_{k-1}(x,q)\widetilde{W}_{k}(x,q),$
$xNSP_{k-1}(\widetilde{W}_{k}(x,q)-x(j-2)\widetilde{W}_{k}(x,q)-1).$

Which leads,

$NSP_{k}(x,q)=xNSP_{k-1}(1+x(j-2)q\widetilde{W}_{k}(x,q)+(\widetilde{W}_{k}(x,q)-x(j-2)\widetilde{W}_{k}(x,q)-1)),$

with initial conditions, $NSP_{0}(x,q)=1$, $NSP_{1}(x,q)=\frac{x}{1-x}$ and
$NSP_{2}(x,q)=\frac{x^{2}}{(1-x)(1-2x)}$. By induction we obtain the required
result. $\Box$

By substituting $q=1$ in Theorem 4, we obtain
$NSP(x,1)=x^{k}\prod_{j=1}^{k}W_{j}(x,1)=x^{k}\prod_{j=1}^{k}\frac{1}{1-jx}$
which is the generating function for the number of partitions of $[n]$ with
$k$ blocks.
Now, we aim to prove that the total number of the non-symmetric peaks over all
partitions of $[n]$ with exactly $k$ blocks is

$\binom{k-1}{2}S_{n-1,k}+2\sum_{j=3}^{k}\binom{j}{3}\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}.$

For that we repeat the same steps in Lemma 2.

###### Lemma 5

The partial derivative $\frac{\partial}{\partial q}NSP(x,q)\mid_{q=1}$ is
given by

$\frac{\partial}{\partial
q}NSP(x,q)\mid_{q=1}=\binom{k-1}{2}xNSP_{k}(x,1)+NSP_{k}(x,1)\sum_{m=3}^{k}\frac{2x^{3}\binom{m}{3}}{(1-mx)}.$
(6)

##### Proof

By differentiating the generating function $NSP(x,q)$ with respect to the
variable $q$ and then evaluate the result in $q=1$ we obtain,

$\displaystyle\frac{\partial}{\partial q}NSP(x,q)\mid_{q=1}$
$\displaystyle=\left(x^{k}\sum_{m=1}^{k}\frac{\partial}{\partial
q}\widetilde{W}_{m}(x,q)\prod_{i=1,i\neq
m}^{k}\widetilde{W}_{i}(x,q)\prod_{j=3}^{k}((j-2)xq+1-(j-2)x)\right)\mid_{q=1}$
$\displaystyle+\left(x^{k}\prod_{i=1}^{k}{\widetilde{W}_{i}(x,q)}\sum_{m=3}^{k}(m-2)x\prod_{j=3,j\neq
m}^{k}((j-2)xq+1-(j-2)x)\right)\mid_{q=1}$
$\displaystyle=x^{k}\sum_{m=1}^{k}\frac{\partial}{\partial
q}\widetilde{W}_{m}(x,q)\mid_{q=1}\prod_{i=1,i\neq
m}^{k}\widetilde{W}_{i}(x,1)+x^{k}\prod_{i=1}^{k}{\widetilde{W}_{i}(x,1)}\sum_{m=3}^{k}(m-2)x$
$\displaystyle=x^{k}\sum_{m=1}^{k}\frac{\frac{\partial}{\partial
q}\widetilde{W}_{m}(x,q)\mid_{q=1}}{\widetilde{W}_{m}(x,1)}\prod_{i=1}^{k}\widetilde{W}_{i}(x,1)+x\frac{(k-1)(k-2)}{2}x^{k}\prod_{i=1}^{k}{\widetilde{W}_{i}(x,1)}.$

According to Asakly [1], $\frac{\partial}{\partial
q}\widetilde{W}_{k}(x,q)\mid_{q=1}=\frac{2x^{3}\binom{k}{3}}{(1-kx)^{2}}$ and
the facts $\widetilde{W}_{k}(x,q)\mid_{q=1}=\frac{1}{1-kx}$ and
$NSP(x,1)=x^{k}\prod_{i=1}^{k}{\widetilde{W}_{i}(x,1)}$ leads to the required
result. $\Box$

###### Corollary 6

The total number of non-symmetric peaks in all partitions of $[n]$ with
exactly $k$ blocks is given by

$\binom{k-1}{2}S_{n-1,k}+2\sum_{j=3}^{k}\binom{j}{3}\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}.$

##### Proof

By finding the coefficients of $x$ in $\frac{\partial}{\partial
q}NSP(x,q)\mid_{q=1}$ we get the result. $\Box$

####  1.2.2 Combinatorial proof

In this subsection, we want to present a combinatorial proof for Corollary
(6).

##### Proof

Let us focus on non-symmetric peaks $\pi_{\ell}\pi_{\ell+1}\pi_{\ell+2}$,
where $\pi_{\ell+1}$ is a record. Consider $\pi=\pi_{1}\pi_{2}\dots\pi_{n-1}$
as a canonical sequential form for $\Pi\in P_{n-1,k}$. Choose any record
$\pi_{\ell+1}$ in $\Pi\in P_{n-1,k}$, where $1\leq\ell\leq n-1$. It is obvious
that we have a rise at $\ell$. Add $\ell+2$ to any block $a$, where
$a<\pi_{\ell+1}$ and $a\neq\pi_{\ell}$, by increasing any member in their
block that is greater or equal to $\ell+2$ by one. As a result, we obtain the
canonical sequential form
$\pi^{\prime}=\pi_{1}\pi_{2}\cdots\pi_{\ell}\pi_{\ell+1}a\pi_{\ell+2}\cdots\pi_{n-1}$,
where $\pi_{\ell+1}a\pi_{\ell+2}$ forms a non-symmetric peak. For each chosen
record $\pi_{\ell+1}$, there are $\pi_{\ell+1}-2$ possible choices for the
block $a$. The sum of these choices, considering all optional records from $3$
to $k$ (excluding $1$ and $2$ since they don’t form non-symmetric peaks),
gives $\frac{(k-1)(k-2)}{2}$ possibilities. As a result, this leads to
$\binom{k-1}{2}S_{n-1,k}$ non-symmetric peaks.

Turning our focus to non-symmetric peaks $\pi_{\ell}\pi_{\ell+1}\pi_{\ell+2}$,
where $\pi_{\ell+1}$ is not record. Considering $i$ and $j$, where $3\leq
i\leq n-k$ and $2\leq j\leq k$, the total number of non-symmetric peaks at
$\ell$ where $\pi_{\ell+1}$ is not a record can be determined by summing the
optional partitions in $P_{n,k}$ that can be decomposed as
$\pi=\pi^{\prime\prime}j\alpha\beta$ for each $i$ and $j$. Here,
$\pi^{\prime\prime}$ is a partition with $j-1$ blocks, $\alpha$ is a word of
length $i$ over alphabet $[j]$ whose last three letters forming a non-
symmetric peak, and $\beta$ may be an empty word. There are $2{j\choose
3}j^{i-3}S_{n-i,k}$ members of $P_{n,k}$ with this form. This is because there
are $j^{i-3}$ choices for the first $i-3$ letters of $\alpha$, $2{j\choose 3}$
for the final three letters in $\alpha$ (representing a non-symmetric peak),
and $S_{n-i,k}$ choices for the remaining letters
$\pi=\pi^{\prime\prime}j\beta$, ensuring that they form a partition of an
$(n-i)$-set into $k$ blocks. $\Box$

## References

  * [1] W. Asakly Enumerating symmetric and non-symmetric peaks in words, OJAC 10 (2018), Article 2.
  * [2] R. Flórez and J. L. Ramírez, Enumerating symmetric and asymmetric peaks in Dyck paths, Disc. Math.. 343 (2020),No 112118.
  * [3] S. Heubach and T. Mansour, Combinatorics of compositions and words, CRC Press, Boca Raton, FL, 2010.
  * [4] S. Kitaev. Patterns in Permutations and Words. Springer, USA, 2011.
  * [5] M. Klazar. Counting pattern-free set partitions. I. A generalization of Stirling numbers of the second kind. European J. Combin., 21(3):367– 378, 2000.
  * [6] M. Klazar. Counting pattern-free set partitions. II. Noncrossing and other hypergraphs.Electron. J. Combin., 7:Research Paper 34, 2000.
  * [7] A. Knopfmacher, T. Mansour and S. Wagner, Records in set partitions, Electron. J. Combin. 17 (2010), no.1, Paper 109, 14 pp.
  * [8] T. Mansour, Combinatorics of Set Partitions, CRC Press, Boca Raton, FL, 2013.
  * [9] T. Mansour and A.O. Munagi. Enumeration of partitions by rises, levels and descents. In Permutation Patterns, St. Andrews 2007, volume 376, pages 221–232. Cambridge University Press, Cambridge, 2007.
  * [10] T. Mansour and M. Shattuck, Counting peaks and valleys in a partition of a set, J. Integer Seq.13 (2010) Art. 10.6.8.
  * [11] T. Mansour and M. Shattuck and S. H. F. Yan, Counting subwords in a partition of a set, Electron. J. Combin. 17(2010), article #R191.
  * [12] M. Shattuck, Recounting the number of rises, levels and descentes in finite set partitions, Integers 10:2 (2010) 179-185.
  * [13] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, UK, 1996\.
  * [14] Y. Sun, W. Shi and D. Zhao, Symmetric and asymmetric peaks or valleys in (partial) dyckpaths, Enumer. Comb. Appl. 2 (2022), article #S2R24.