Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes
Formelles, 91190, Gif-sur-Yvette France https://orcid.org/0000-0002-7261-9342
Isa Vialard [500]Theory of computation Complexity theory and logic [300]Theory
of computation Logic and verification [300]Theory of computation Proof theory
[300]Theory of computation Program reasoning

# Ordinal measures of the set of finite multisets

Isa Vialard

###### Abstract

Well-partial orders, and the ordinal invariants used to measure them, are
relevant in set theory, program verification, proof theory and many other
areas of computer science and mathematics. In this article we focus on one of
the most common data structure in programming, the finite multiset of some
wpo. There are two natural orders one can define on the set of finite
multisets $M(X)$ of a partial order $X$: the multiset embedding and the
multiset ordering, for which $M(X)$ remains a wpo when $X$ is. Though the
maximal order type of these orders is already known, the other ordinal
invariants remain mostly unknown. Our main contributions are expressions to
compute compositionally the width of the multiset embedding and the height of
the multiset ordering. Furthermore, we provide a new ordinal invariant useful
for characterizing the width of the multiset ordering.

###### keywords:

Well-partial order, finite multisets, termination, program verification

## Introduction

Measuring partial orders intervene in many domains, from set theory to proof
theory, including infinitary combinatorics, program verification, rewriting
theory, proof automation and many more.

There are intuitive notions of measure for a partial order when it is finite:
its cardinal obviously, but also its height (the length of a maximal chain) or
its width (the length of a maximal antichain). Similar notions exist for
infinite partial orders, as long as they are _well partial orders_ (wpo),
i.e., well-founded partial orders with no infinite antichains [10, 12]. Two
such notions are the _height_ , which is the order type of a maximal chain,
and the _maximal order type_ (m.o.t.), which is the order type of a maximal
linearisation, a notion introduced by De Jongh and Parikh in order to measure
hierarchies of functions [6]. These are transfinite measures, hence we call
them _ordinal invariants_. Kříž and Thomas introduced equivalent
characterizations for m.o.t. and height, which naturally led to the definition
of a third ordinal invariant, _width_ [11]. Less studied than its
counterparts, the width of a wpo relates to its antichains, even though it
cannot be defined as the order type of a maximal antichain. While exploring
techniques for program termination, Blass and Gurevich developed these
characterizations into a game-theoretical point of view which gives useful
intuitions [4].

Ordinal invariants have proven helpful to establish program termination or to
analyze well-structured transition systems (wsts) [5], i.e., transition
systems whose set of configurations is a wpo and whose transitions respect
this ordering. The study of wsts through controlled bad sequences [9], and
sometimes controlled antichains [14], shows obvious connections between the
complexity of verification problems on wsts and the m.o.t. and width of the
underlying wpo.

Computing ordinal invariants compositionally is paramount, as most wpos one
might want to measure are built from classical operations on simpler wpos
whose invariants are known. De Jongh and Parikh computed the m.o.t. of the
disjoint sum and the cartesian product of wpos [6]. Schmidt then computed the
m.o.t. of word embedding and homeomorphic tree embedding on a wpo [13].
Abraham and Bonnet pursued this line of study by computing the height of
cartesian product, but also the width of disjoint sum and lexicographic
product [1]. For a complete survey of these results, see [8], where Džamonja
et al. computed the ordinal invariants of the lexicographic product, but also
the height of the multiset word and tree embeddings.

Finite multisets: In this article, we study the ordinal invariants of the set
of finite multisets. Multisets are one of computer science’s most common data
structures, especially in rewriting theory. Informally, a finite multiset over
a set $X$ is a finite subset of $X$ where an element can appear finitely many
times. One can see the set of finite multisets on a wpo as the set of finite
words quotiented by the equivalence relation “equality up to some
permutation”. It comes down to describing a multiset as a word where the order
of terms is irrelevant. A finite multiset can be represented by a function
from $X$ to $\mathbb{N}$ with finite support, which associates each element
with its multiplicity.

Two orderings are classically defined on the finite multisets of any ordered
set. The first one is the _multiset ordering_. The intuition behind this
ordering is that, from a multiset $m$, one can build a smaller multiset by
removing an element $x$ from $m$, and replacing it with an arbitrary number of
elements smaller than $x$. The multiset ordering often appears in rewriting
theory and automation of termination proofs [7].

A perhaps more natural, but less known, ordering on the set of finite
multisets is the _multiset embedding_ , or term ordering as it is called in
[15]. It was presented by Aschenbrenner and Pong as a natural extension of the
embedding order over finite words [3].

Some invariants of these two orderings have already been measured: Van der
Meeren, Rathjen, and Weiermann [15] built on [17] to compute the m.o.t. of the
set of finite multisets on a wpo $X$ ordered with the multiset ordering, and
provided a new proof for the expression of the m.o.t of the multiset embedding
computed in [18]. Džamonja et al. [8] proved that the height of the multiset
embedding is equal to the height of the set of finite words ordered with word
embedding. It is noteworthy that these three results give expressions that are
functional in the m.o.t. and height of $X$. However, the height of invariants
of the multiset ordering still needs to be determined, and the width remains
unstudied for both orderings.

Our contributions: In this article, we provide functional expressions for the
width of the multiset embedding (Theorem 2.1) and the height of the multiset
ordering (Theorem 3.1).

We further show that the width of the multiset ordering is not functional in
any of the three ordinal invariants (Example 3.3). Nonetheless, we get around
this issue by introducing a fourth ordinal invariant, the _maximal safe order
type_ (Definition 3.10), in which the width is functional (Theorem 3.13).

Table 1 sums up this article’s contributions (in the gray cases) amidst the
current state of the art.

Table 1: Ordinal invariants of $M^{\diamond}(X)$ and $M^{r}(X)$. Invariants | $M^{\diamond}(X)$ | $M^{r}(X)$
---|---|---
M.o.t. $\bm{o}$ | ${\omega}^{\widehat{\bm{o}(X)}}$ | ${\omega}^{\bm{o}(X)}$
Height $\bm{h}$ | $\bm{h}^{*}(X)$ | ${\omega}^{\bm{h}(X)}$
Width $\bm{w}$ | ${\omega}^{\widehat{\bm{o}(X)}-1}$ | ${\omega}^{\operatorname{\underline{\mathbb{o}}}(X)}$

##  1 Definitions and state of the art

###  1.1 Width, height and maximal order type

We suppose that the reader is familiar with ordinal arithmetic. Otherwise, the
notions used in this article can be found in the appendix.

A sequence $x_{1},\dots,x_{n},\dots$ on a partial order is _good_ when there
exist $i<j$ such that $x_{i}\leq x_{j}$, otherwise it is a _bad_ sequence. A
sequence is an _antichain_ when all its elements are pairwise incomparable
(i.e. $x_{i}\perp x_{j}$ for any $i<j$).

A _well partial order (wpo)_ is a partial order that has no infinite bad
sequences. Equivalently, a wpo is a partial order that is both well-founded
(i.e. no infinite strictly decreasing sequences) and has no infinite
antichains (i.e. sequences of pairwise incomparable elements).

Let $X$ be a wpo. We define ${\textit{Bad}}(X)$, ${\textit{Dec}}(X)$ and
${\textit{Ant}}(X)$ as the trees of bad sequences, strictly decreasing
sequences, and antichains of $X$, respectively, ordered by inverse prefix
order (a sequence is smaller than its prefixes) The finiteness of bad
sequences, strictly decreasing sequences and antichains in a wpo implies that
these trees are well-founded. Therefore, one can define a notion of rank: a
sequence has rank $0$ when it cannot be extended; otherwise its rank is the
smallest ordinal strictly larger than the ranks of smaller sequences (by
inverse prefix order).

The _maximal order type_ (or m.o.t.) of $X$, denoted with $\bm{o}(X)$, is
defined as the rank of the empty sequence in ${\textit{Bad}}(X)$. Similarly,
the _height_ $\bm{h}(X)$ and the _width_ $\bm{w}(X)$ of $X$ are defined as the
ranks of the empty sequence in ${\textit{Dec}}(X)$ and ${\textit{Ant}}(X)$,
respectively. Together, $\bm{o}(X)$, $\bm{h}(X)$ and $\bm{w}(X)$ are called
the _ordinal invariants_ of $X$.

Since the rank of the empty sequence is the smallest ordinal strictly larger
than the ranks of the sequences of length $1$, these definitions can be
reformulated inductively through the following _residual equations_ :

$\displaystyle\bm{o}(X)$ $\displaystyle=\sup_{x\in X}\left(\bm{o}(X_{\not\geq
x})+1\right)$ (Res-o) $\displaystyle\bm{h}(X)$ $\displaystyle=\sup_{x\in
X}\left(\bm{h}(X_{<x})+1\right)$ (Res-h) $\displaystyle\bm{w}(X)$
$\displaystyle=\sup_{x\in X}\left(\bm{w}(X_{\perp x})+1\right)$ (Res-w)

$X_{*x}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\;y\in X\;:\;y*x\;\\}$ for
$*\in\\{\;\not\geq,<,\perp\;\\}$ is what is called a residual of $X$.

Since ${\textit{Dec}}(X)$ and ${\textit{Ant}}(X)$ are embedded in
${\textit{Bad}}(X)$, we know $\bm{h}(X)\leq\bm{o}(X)$ and
$\bm{w}(X)\leq\bm{o}(X)$. Kříž and Thomas found that the m.o.t can also be
bounded by the width and the height [11]:

######  Theorem 1.1 (Height-Width Theorem).

For any wpo $A$,

  * •

$\bm{o}(A)\leq\bm{h}(A)\otimes\bm{w}(A)$.

  * •

Furthermore, if $\bm{o}(A)$ is multiplicatively indecomposable (see Appendix)
and $\bm{h}(A)<\bm{o}(A)$ (resp. $\bm{w}(A)<\bm{o}(A)$) then
$\bm{w}(A)=\bm{o}(A)$ (resp. $\bm{h}(A)=\bm{o}(A)$).

###  1.2 Ordinal invariants of basic data structures

In computer science, sums and products of wpos are the most basic data
structures one can find. Their ordinal invariants are easy to compute
compositionally, with the notable exception of the width of the cartesian
product which is not functional [16]. In this article, these structures will
often be used as examples, or appear in proofs.

######  Lemma 1.2 (Disjoint sum [6, 1, 8]).

Let $P,Q$ be two wpos. The _disjoint sum_ $P\sqcup Q$ is the disjoint union of
$P$ and $Q$ ordered such that for all $p\in P,q\in Q$, $p\perp q$. It is a wpo
and:

  * •

$o(P\sqcup Q)=\bm{o}(P)\oplus\bm{o}(Q)$,

  * •

$w(P\sqcup Q)=\bm{w}(P)\oplus\bm{w}(Q)$.

  * •

$h(P\sqcup Q)=\max(\bm{h}(P),\bm{h}(Q))$.

######  Lemma 1.3 (Lexicographic sum [8]).

Let $P,Q$ be two wpos. The _lexicographic sum_ $P+Q$ is the disjoint union of
$P$ and $Q$ ordered such that for all $p\in P,q\in Q$, $p\leq q$. Ti is a wpo
and:

  * •

$\bm{o}(P+Q)=\bm{o}(P)+\bm{o}(Q)$,

  * •

$\bm{w}(P+Q)=\max(\bm{w}(P),\bm{w}(Q))$,

  * •

$\bm{h}(P+Q)=\bm{h}(P)+\bm{h}(Q)$.

######  Lemma 1.4 (Cartesian product [6]).

Let $P,Q$ be two wpos. The _cartesian product_ $P\times Q$, where elements are
compared component-wise, is a wpo and:

  * •

$\bm{o}(P\times Q)=\bm{o}(P)\otimes\bm{o}(Q)$,

  * •

$\bm{h}(P\times
Q)=\sup\\{\;\alpha\oplus\beta+1\;:\;\alpha<\bm{h}(P),\beta<\bm{h}(Q)\;\\}$.

######  Lemma 1.5 (Lexicographic product [8]).

Let $P,Q$ be two wpos. The _lexicographic product_ of $P$ along $Q$, written
$P\cdot Q$, has the same support as $P\times Q$, and but is ordered
differently:

$(p,q)\leq_{P\cdot Q}(p^{\prime},q^{\prime})\quad\text{ iff }\quad
q<_{Q}q^{\prime}\text{ , or }q=q^{\prime}\text{ and }p\leq_{P}p^{\prime}\;.$

It is a wpo, and:

  * •

$\bm{o}(P\cdot Q)=\bm{o}(P)\cdot\bm{o}(Q)$,

  * •

$\bm{w}(P\cdot Q)=\bm{w}(P)\odot\bm{w}(Q)$.

See the appendix for definitions of the natural sum $\oplus$ and product
$\otimes$, as well as for the lesser-known Hessenberg-based product $\odot$.

###  1.3 Comparing wpos

A widely-used and intuitive relation between wpos is the _reflection_
relation. A mapping between wpos $f\colon(A,\leq_{A})\rightarrow(B,\leq_{B})$
is a _reflection_ if $f(x)\leq_{B}f(y)$ implies $x\leq_{A}y$, i.e. it is a
morphism from $(A,\not\leq_{A})$ to $(B,\not\leq_{B})$ When there is a
reflection from $A$ to $B$, we note $A{\hookrightarrow}B$.

However, in this article, we prefer to use the stronger notions of
augmentations and substructures.

######  Definition 1.6 (Substructure, augmentation).

A wpo $(A,\leq_{A})$ is a _substructure_ of a wpo $(B,\leq_{B})$ whenever
$A\subseteq B$ and $\leq_{A}$ is the restriction of $\leq_{B}$ to $A$. This
relation is written $A\leq_{\text{st}}B$. Similarly $(A,\leq_{A})$ is an
_augmentation_ of $(B,\leq_{B})$ whenever $A=B$ and
${\leq_{B}}\subseteq{\leq_{A}}$. We write this relation $A\geq_{\text{aug}}B$.

Obviously, $A\leq_{\text{st}}B$ or $A\geq_{\text{aug}}B$ imply
$A{\hookrightarrow}B$.

We denote with $A\equiv B$ that $(A,\leq_{A})$ is isomorphic to
$(B,\leq_{B})$.

We often abuse these notations and write $A\leq_{\text{st}}B$ (resp.
$B\leq_{\text{aug}}A$) to mean that $A$ is isomorphic to a substructure (resp.
an augmentation) of $B$.

######  Example 1.7.

It is well-known that the height and the m.o.t. of a wpo $X$ are reached by
the order type of a maximal chain and a maximal linearisation of $X$,
respectively. Therefore $\bm{h}(X)\leq_{\text{st}}X$ and
$\bm{o}(X)\geq_{\text{aug}}X$.

In this article, when we consider a subset $Y$ of a wpo $X$, it is understood
that $Y\leq_{\text{st}}X$, i.e. $Y$ is ordered with $\leq_{X}$ restricted to
the subset.

These notions allow us to compare the ordinal invariants of wpos.

######  Lemma 1.8.

Let $A$ and $B$ be wpos.

If $A\leq_{\text{st}}B$ then $\bm{i}(A)\leq\bm{i}(B)$ for
$\bm{i}\in\\{\;\bm{o},\bm{h},\bm{w}\;\\}$.

If $A\geq_{\text{aug}}B$ then $\bm{o}(A)\leq\bm{o}(B)$ and
$\bm{w}(A)\leq\bm{w}(B)$. However $\bm{h}(A)\geq\bm{h}(B)$.

The substructure and augmentation relations are monotonous through most
operations on wpos.

###  1.4 Orderings on the set of finite multiset

We note $\langle x_{1},\dots,x_{n}\rangle$ the finite multiset that contains
the elements $x_{1},\dots,x_{n}$. The symbols $\cup,\cap$ and $\setminus$
denote the union, the intersection and the subtraction, respectively. For any
$n\in\mathbb{N}$, $m\times n$ means the union of $n$ copy of $m$. For
instance, let $m=\langle 1,1,1,2,2,3\rangle$ and $m^{\prime}=\langle
1,1,2,4\rangle$. Then $m\cup m^{\prime}=\langle 1,1,1,1,1,2,2,2,3,4\rangle$,
and $m\cap m^{\prime}=\langle 1,1,2\rangle$. Furthermore, $m\setminus(m\cap
m^{\prime})=\langle 1,2,3\rangle$, and $m^{\prime}\times 2=\langle
1,1,1,1,2,2,4,4\rangle$

We denote with $|m|$ the number of elements of a multiset $m$.

There are two main orderings classically defined on the set of finite
multisets $M(X)$ of a partial order $X$:

######  Definition 1.9 (multiset embedding).

$M^{\diamond}(X)=(M(X),\leq_{\diamond})$ is ordered with the _multiset
embedding_ , also known as the term ordering:

$m\leq_{\diamond}m^{\prime}$ iff there exists $f:m\rightarrow m^{\prime}$
injective such that for any $x\in m$, $x\leq f(x)$.

######  Definition 1.10 (Multiset ordering).

$M^{r}(X)=(M(X),\leq_{r})$ is ordered with the _multiset ordering_ :

$m\leq_{r}m^{\prime}\iff m=m^{\prime}\text{ or }\forall x\in m\setminus(m\cap
m^{\prime}),\exists y\in m^{\prime}\setminus(m\cap m^{\prime}),x<y\;.$

The multiset ordering and the multiset embedding are both augmentations of the
word embedding on $X^{*}$. Therefore, according to Higman’s lemma [10],
$M^{\diamond}(X)$ and $M^{r}(X)$ are wpos when $X$ is.

The main differences between these two ordering are that the multiset
embedding gives a lot of importance to the size of a multiset (for any
multisets $m,m^{\prime}$, $m\leq_{\diamond}m^{\prime}$ implies
$|m|\leq|m^{\prime}|$), whereas with the multiset ordering one element can
dominate many. For instance, $\langle 1\rangle\geq_{r}\langle 0\rangle\cdot
100$ in $M^{r}(\mathbb{N})$. This is why for any wpo $X$,
$M^{\diamond}(X)\leq_{\text{aug}}M^{r}(X)$, as was observed by Aschenbrenner
and Pong [3].

Note that if $X$ is a linear ordering, then $M^{r}(X)$ remains linear, while
$M^{\diamond}(X)$ does not.

Nonetheless, $\leq_{\diamond}$ and $\leq_{r}$ behave similarly on simple data
structures, as we will see with the following _transformation lemmas_ :

######  Lemma 1.11 (Disjoint sum transformation).

For any wpos $A$ and $B$, $M^{*}(A\sqcup B)\equiv M^{*}(A)\times M^{*}(B)$ for
$*\in\\{\diamond,r\\}$.

######  Lemma 1.12 (Direct sum transformation, multiset ordering).

For any wpos $A$ and $B$, $M^{r}(A+B)\equiv M^{r}(A)\cdot M^{r}(B)$

######  Lemma 1.13 (Direct sum transformation, multiset embedding).

For any wpos $A$ and $B$,
$M^{\diamond}(A+B)\leq_{\text{aug}}M^{\diamond}(A)\cdot M^{\diamond}(B)$

######  Proof 1.14.

For all $m\in M^{\diamond}(A+B)$, $m=m_{A}\cup m_{B}$ for some $m_{A}\in
M^{\diamond}(A)$, $m_{B}\in M^{\diamond}(B)$. Let $m=m_{A}\cup
m_{B},m^{\prime}=m^{\prime}_{A}\cup m^{\prime}_{B}$ such that
$m\leq_{M^{\diamond}(A+B)}m^{\prime}$. By definition there exists an injective
function $f:m\rightarrow m^{\prime}$ such that $x\leq_{A+B}f(x)$ for any $x\in
m$. Then $f(m_{B})\subseteq m^{\prime}_{B}$ hence
$m_{B}\leq_{M^{\diamond}(B)}m^{\prime}_{B}$. If
$m_{B}<_{M^{\diamond}(B)}m^{\prime}_{B}$ then
$(m_{A},m_{B})<_{M^{\diamond}(A)\cdot
M^{\diamond}(B)}(m^{\prime}_{A},m^{\prime}_{B})$. Otherwise
$m_{B}=m^{\prime}_{B}$. Then $f(m_{A})\subseteq m^{\prime}_{A}$, hence
$m_{A}\leq_{M^{\diamond}(A)}m^{\prime}(A)$. Thus
$(m_{A},m_{B})\leq_{M^{\diamond}(A)\cdot
M^{\diamond}(B)}(m^{\prime}_{A},m^{\prime}_{B})$.

The augmentation and substructure relations are monotone with respect to the
multiset ordering and multiset embedding:

######  Lemma 1.15.

Let $A,B$ be two wpos. Then $A\leq_{\text{st}}B$ implies
$M^{\diamond}(A)\leq_{\text{st}}M^{\diamond}(B)$ and
$M^{r}(A)\leq_{\text{st}}M^{r}(B)$. Moreover, $A\geq_{\text{aug}}B$ implies
that $M^{\diamond}(A)\geq_{\text{aug}}M^{\diamond}(B)$ and
$M^{r}(A)\geq_{\text{aug}}M^{r}(B)$

###  1.5 Ordinal invariants of the set of finite multisets

Van der Meeren, Rathjen and Weiermann computed the m.o.t. of $M^{\diamond}(X)$
and $M^{r}(X)$.

######  Theorem 1.16 (M.o.t. of the multiset embedding [15, 18]).

Let $X$ be a wpo.

Then $\bm{o}(M^{\diamond}(X))={\omega}^{\widehat{\bm{o}(X)}}$, where
$\widehat{\alpha}\stackrel{{\scriptstyle\text{def}}}{{=}}{\omega}^{\alpha^{\prime}_{1}}+\dots+{\omega}^{\alpha^{\prime}_{n}}$
for all $\alpha={\omega}^{\alpha_{1}}+\dots+{\omega}^{\alpha_{n}}$, with
$\alpha_{i}^{\prime}$ is $\alpha_{i}+1$ when $\alpha_{i}$ is the sum of an
$\epsilon$-number and a finite ordinal, otherwise
$\alpha_{i}^{\prime}=\alpha_{i}$.

######  Theorem 1.17 (M.o.t. of the multiset ordering [15, 17]).

Let $X$ be a wpo.

Then $\bm{o}(M^{r}(X))={\omega}^{\bm{o}(X)}$.

Observe that ${\omega}^{\bm{o}(X)}\leq{\omega}^{\widehat{\bm{o}(X)}}$, as one
would expect since $M^{r}(X)\geq_{\text{aug}}M^{\diamond}(X)$. Furthermore, we
should have $\bm{w}(M^{r}(X))\leq\bm{w}(M^{\diamond}(X))$, while
$\bm{h}(M^{r}(X))\geq\bm{h}(M^{\diamond}(X))$. Unfortunately, only the height
of $M^{\diamond}(X)$ is known for now.

######  Theorem 1.18 (Height of the multiset embedding [8]).

Let $X$ be a wpo.

Then $\bm{h}(M^{\diamond}(X))=\bm{h}^{*}(X)$, where

$\bm{h}^{*}(A)\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{cases}\bm{h}(A)&\text{
if }\bm{h}(A)\text{ is infinite and indecomposable, }\\\
\bm{h}(A)\cdot{\omega}&\text{ otherwise.}\end{cases}$

###  1.6 A tool to compute the width: Quasi-incomparable subsets

Of all three ordinal invariants, the width is the less studied, since it has
been introduced more recently. It is also the hardest invariant to study:
unlike the m.o.t. and the height that are reached by the order types of the
maximal linearisation and the maximal chain of a wpo, respectively, the width
is not embodied by a sort of "maximal antichain".

A powerful tool for analysing the width of a wpo is the notion of _quasi-
incomparable_ subsets of a wpo, which was first used in [16] for the cartesian
product of several ordinals.

For any partial order $X$, we denote with $x\perp y$ when two elements $x,y\in
X$ are incomparable. This notation can be extended to subsets $Y,Z$ of $X$: we
denote with $Y\perp Z$ when for every $y\in Y,z\in Z$, $y\perp z$.

######  Definition 1.19.

Let $A$ be a wpo, and $A_{1},\dots,A_{n}$ be $n$ subsets of $A$. Then
$(A_{i})_{i\leq n}$ is a _quasi-incomparable_ family of subsets of $A$ iff for
any $i<n$, for any finite $Y\subseteq A_{1}\cup\dots\cup A_{i}$, there exists
$A_{i+1}^{\prime}\subseteq A_{i+1}$ such that $A_{i+1}^{\prime}\perp Y$ and
$A_{i+1}^{\prime}\equiv A_{i+1}$.

This definition is slightly more restrictive than the one in [16], which only
required that $\bm{w}(A_{i+1}^{\prime})=\bm{w}(A_{i+1})$.

The idea behind these quasi-incomparable subsets is that sometimes one can
slice a wpo $A$ into simpler subsets $A_{1},\dots,A_{n}$ whose width is known,
such that ${\textit{Ant}}(A_{n})+\dots+{\textit{Ant}}(A_{1})$ is embedded in
${\textit{Ant}}(A)$. Intuitively, it means that one can combine antichains of
$A_{1},\dots,A_{n}$ into one antichain of $A$.

This entails a practical relation between the widths of $A$ and its subsets:

######  Lemma 1.20.

Let $(A_{i})_{i\leq n}$ be a quasi-incomparable family of subsets of $A$. Then
$\bm{w}(A)\geq\bm{w}(A_{n})+\dots+\bm{w}(A_{1})$.

Lemma 1.20 will prove very useful soon, in the proofs of Lemmas 2.4 and 3.6.

##  2 Width of the multiset embedding

In this section we compute the width of $M^{\diamond}(X)$ for any wpo $X$,
which happens to be functional in the width of $X$:

######  Theorem 2.1 (Width of the multiset embedding).

For any wpo $X$, $\bm{w}(M^{\diamond}(X))={\omega}^{\widehat{\bm{o}(X)}-1}$.

(See Theorem 1.16 for a definition of $\widehat{\alpha}$.)

We already know that, in some cases, the width of the multiset embedding
reaches its m.o.t.

######  Lemma 2.2 ([8]).

If $\bm{o}(X)$ is infinite indecomposable,
$\bm{w}(M^{\diamond}(X))=\bm{o}(M^{\diamond}(X))$.

######  Proof 2.3.

According to Theorem 1.16,
$\bm{o}(M^{\diamond}(X))={\omega}^{\widehat{\bm{o}(X)}}$, which is
multiplicatively indecomposable when $\bm{o}(X)$ is indecomposable.
Furthermore, when $\bm{o}(X)>1$,
$\bm{o}(M^{\diamond}(X))>\bm{h}^{*}(X)=\bm{h}(M^{\diamond}(X))$ according to
Theorem 1.18. Hence $\bm{w}(M^{\diamond}(X))=\bm{o}(M^{\diamond}(X))$
according to Theorem 1.1.

We focus for now on the set of finite multisets on an ordinal. Let us treat
first the case of successor ordinals.

######  Lemma 2.4.

For any successor ordinal $\alpha=\beta+1$,
$\bm{w}(M^{\diamond}(\alpha))\geq\bm{w}(M^{\diamond}(\beta))\cdot{\omega}$.

######  Proof 2.5.

We write $M^{\diamond}_{>k}(X)$ for the substructure of $M^{\diamond}(X)$
where multisets have strictly more than $k$ elements. According to Equation
Res-w,

$\bm{w}(M^{\diamond}(\alpha))=\sup\;\\{\bm{w}(M^{\diamond}(\alpha)_{\perp
m})+1\;|\;m\in M^{\diamond}(\alpha)\\}\;.$

Let us compute $\bm{w}(M^{\diamond}(\alpha)_{\perp m_{n}})$ with
$m_{n}=\langle\beta\rangle\times n$ for any $n\in\mathbb{N}$. Let
$M_{k}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\;\langle\beta\rangle\times(n-k)\cup
m\;:\;m\in M^{\diamond}_{>k}(\beta)\;\\}$ for $k\in[1,n]$ be a family of
subsets of $M^{\diamond}(\alpha)$. These subsets are relevant because, for any
$k\in[1,n]$, $M_{k}\equiv M^{\diamond}(\beta)$, and for all $m\in\M_{k}$,
$m\perp m_{n}$ since $|m|>|m_{n}|$. Moreover, $(M_{k})_{k\in[1,n]}$ is a
quasi-incomparable family of subsets of $M^{\diamond}(\alpha)_{\perp m_{n}}$:
for any $i<n$, for any finite $Y\subset M_{1}\cup\dots\cup M_{i}$, let
$s(Y)=max\\{|m|,m\in Y\\}$. Observe that $M_{i+1}$ contains $M_{i+1}\cap
M^{\diamond}_{>s(Y)}(\beta)$ which is incomparable to $Y$, and isomorphic to
$M_{i+1}$, which is also isomorphic to $M^{\diamond}(\beta)$ .

Therefore, according to Lemma 1.20, $\bm{w}(M^{\diamond}(\alpha)_{\perp
m_{n}})\geq\bm{w}(M^{\diamond}(\beta))\cdot n$. Hence Equation Res-w entails:

$\displaystyle w(M^{\diamond}(\alpha))$
$\displaystyle\geq\sup\\{\bm{w}(M^{\diamond}(\alpha)_{\perp
m_{n}})+1\;|\;n\in\mathbb{N}\\}$
$\displaystyle\geq\bm{w}(M^{\diamond}(\beta))\cdot{\omega}\;.$

######  Lemma 2.6.

For any infinite ordinal $\alpha$,
$\bm{w}(M^{\diamond}(\alpha))=\bm{o}(M^{\diamond}(\alpha))$.

######  Proof 2.7.

We already know that
$\bm{w}(M^{\diamond}(\alpha))\leq\bm{o}(M^{\diamond}(\alpha))$. We prove the
lower bound by induction on $\alpha$:

  * •

If $\alpha$ is infinite indecomposable, see Lemma 2.2.

  * •

If $\alpha=\beta+1$ , then according to Lemma 2.4,

$\displaystyle\bm{w}(M^{\diamond}(\alpha))$
$\displaystyle\geq\bm{w}(M^{\diamond}(\beta))\cdot{\omega}$
$\displaystyle\overset{IH}{=}\bm{o}(M^{\diamond}(\beta))\cdot{\omega}$
$\displaystyle={\omega}^{\widehat{\beta}+1}={\omega}^{\widehat{\beta+1}}=\bm{o}(M^{\diamond}(\alpha))\text{
according to<EMAIL_ADDRESS>
  * •

If $\alpha=\beta+{\omega}^{\rho}$ with $\beta,{\omega}^{\rho}<\alpha$ and
$\rho>0$, then according to the transformation lemma 1.13,
$M^{\diamond}(\alpha)\geq_{\text{aug}}M^{\diamond}(\beta)\cdot
M^{\diamond}({\omega}^{\rho})$. Hence according to Lemma 1.5,

$\displaystyle\bm{w}(M^{\diamond}(\alpha))$
$\displaystyle\geq\bm{w}(M^{\diamond}(\beta))\odot\bm{w}(M^{\diamond}({\omega}^{\rho}))$
$\displaystyle\overset{IH}{=}\bm{o}(M^{\diamond}(\beta))\odot\bm{o}(M^{\diamond}({\omega}^{\rho}))$
$\displaystyle={\omega}^{\widehat{\beta}}\odot{\omega}^{\widehat{{\omega}^{\rho}}}={\omega}^{\widehat{\alpha}}$
$\displaystyle=\bm{o}(M^{\diamond}(\alpha))\;.$

We can now prove that Lemma 2.2 generalizes to any infinite $X$.

######  Lemma 2.8.

$\bm{w}(M^{\diamond}(X))=\bm{o}(M^{\diamond}(X))$ if $\bm{o}(X)$ is infinite.

######  Proof 2.9.

Let $\alpha=\bm{o}(X)$. Then $X\leq_{\text{aug}}\alpha$, hence
$M^{\diamond}(X)\leq_{\text{aug}}M^{\diamond}(\alpha)$. Thus

$\bm{w}(M^{\diamond}(\alpha))\leq\bm{w}(M^{\diamond}(X))\leq\bm{o}(M^{\diamond}(X))\;,$

and $\bm{o}(M^{\diamond}(X))=\bm{o}(M^{\diamond}(\alpha))$ since
$\bm{o}(M^{\diamond}(X))$ only depends on $\bm{o}(X)=\alpha$. According to
Lemma 2.6, $\bm{w}(M^{\diamond}(\alpha))=\bm{o}(M^{\diamond}(\alpha))$, hence
$\bm{w}(M^{\diamond}(X))=\bm{o}(M^{\diamond}(X))$.

We can also compute the width of $M^{\diamond}(X)$ when $X$ is a finite wpo:

For any $k<{\omega}$, we define $\Gamma_{k}$ as the disjoint union of $k$
singleton wpos:

$\Gamma_{k}\stackrel{{\scriptstyle\text{def}}}{{=}}\overbrace{1\sqcup\dots\sqcup
1}^{k}\;.$

######  Lemma 2.10.

If $\bm{o}(X)$ is finite, then
$\bm{w}(M^{\diamond}(X))={\omega}^{\bm{o}(X)-1}$.

######  Proof 2.11.

Let $k=\bm{o}(X)$. Then $\Gamma_{k}\leq_{\text{aug}}X\leq_{\text{aug}}k$,
hence
$\bm{w}(M^{\diamond}(\Gamma_{k}))\geq\bm{w}(M^{\diamond}(X))\geq\bm{w}(M^{\diamond}(k))$.

Since $M^{\diamond}(\Gamma_{1})={\omega}$, the transformation lemma 1.11 tells
us that $M^{\diamond}(\Gamma_{k})$ is isomorphic to the cartesian product
${\omega}\times\dots\times{\omega}$ $k$ times. In general, we do not know how
to compute the width of a cartesian product, but in this special case we know
that $\bm{w}(M^{\diamond}(\Gamma_{k}))={\omega}^{k-1}$ [16].

Furthermore, according to Lemma 2.4 applied $(k-1)$ times,
$\bm{w}(M^{\diamond}(k))\geq\bm{w}(M^{\diamond}(1))\cdot{\omega}^{k-1}={\omega}^{k-1}$.
Therefore $\bm{w}(M^{\diamond}(X))={\omega}^{k-1}={\omega}^{\bm{o}(X)-1}$.

We can now prove this section’s main result: See 2.1

######  Proof 2.12.

If $\bm{o}(X)$ is finite, then $\widehat{\bm{o}(X)}=\bm{o}(X)$. On the other
hand, if $\bm{o}(X)$ is infinite, then $\widehat{\bm{o}(X)}$ is infinite too,
hence $\widehat{\bm{o}(X)}-1=\widehat{\bm{o}(X)}$. Hence
$\bm{w}(M^{\diamond}(X))={\omega}^{\widehat{\bm{o}(X)-1}}$ follows from Lemmas
2.10 and 2.8.

##  3 Height and width of the multiset ordering

The m.o.t. is the only invariant we know how to compute compositionally for
the multiset ordering. See 1.17

Since the multiset ordering of a linear ordering remains linear, we can deduce
that for any ordinal $\alpha$, $M^{r}(\alpha)\equiv{\omega}^{\alpha}$.

For the height of $M^{r}(X)$, we have a result similar to Theorem 1.17.

######  Theorem 3.1 (Height of the multiset ordering).

Let $X$ be a wpo.

Then $\bm{h}(M^{r}(X))={\omega}^{\bm{h}(X)}$.

######  Proof 3.2.

Remember that $X\geq_{\text{st}}\bm{h}(X)$, and thus
$M^{r}(X)\geq_{\text{st}}M^{r}(\bm{h}(X))\equiv{\omega}^{\bm{h}(X)}$.
Therefore $\bm{h}(M^{r}(X))\geq{\omega}^{\bm{h}(X)}$.

We prove the upper bound by induction on $\bm{h}(X)$. If $\bm{h}(X)=0$ then
$X=\emptyset$ and $M^{r}(X)$ only contains the empty multiset, so
$\bm{h}(M^{r}(X))=1={\omega}^{0}$.

For any multiset $m\in M^{r}(X)$, we write $X_{<m}$ for $(\cap_{x\in
m}X_{\not\geq x})\cap(\cup_{x\in m}X_{<x})$. Observe that $X_{<m}$ is a subset
of $X$ such that $\bm{h}(X_{m})<\bm{h}(X)$. Now suppose $X$ is not empty and
$m$ is any multiset on $X$:

$\displaystyle M^{r}(X)_{<m}$
$\displaystyle=\bigcup_{m_{1}+m_{2}=m,m_{1}\neq\emptyset}\\{\;m^{\prime}+m_{2}\;:\;m^{\prime}\in
M^{r}(X_{<m_{1}})\;\\}$ $\displaystyle\equiv\bigcup_{m_{1}\subseteq
m,m_{1}\neq\emptyset}M^{r}(X_{<m_{1}})\;.$

Since $\bm{h}(X_{m_{1}})<\bm{h}(X)$, by induction hypothesis
$\bm{h}(M^{r}(X_{<m_{1}}))\leq{\omega}^{\bm{h}(X_{<m_{1}})}<{\omega}^{\bm{h}(X)}$.
Moreover, ${\omega}^{\bm{h}(X)}$ is indecomposable. Hence:

$\bm{h}(M^{r}(X)_{<m})\leq\bigoplus_{m_{1}+m_{2}=m,m_{1}\neq\emptyset}\bm{h}(M^{r}(\cup_{x\in
m_{1}}X_{<x}))<{\omega}^{\bm{h}(X)}\;.$

Therefore $\bm{h}(M^{r}(X))\leq{\omega}^{\bm{h}(X)}$ according to Equation
Res-h.

Unfortunately, the width of the multiset ordering is harder to compute, as
$\bm{w}(M^{r}(X))$ is not functional in the ordinal invariants of $X$. The
following example exhibits two wpos $X_{1}$ and $X_{2}$, with identical
invariants, such that $\bm{w}(M^{r}(X_{1}))\neq\bm{w}(M^{r}(X_{2}))$.

######  Example 3.3.

Let $H=\Sigma_{n<{\omega}}\Gamma_{n}$. An interesting property of $H$ is that
$\bm{w}(H)=\bm{h}(H)=\bm{o}(H)={\omega}$. Observe that
$\bm{w}(M^{r}(H))\leq\bm{o}(M^{r}(H))={\omega}^{{\omega}}$ and that
$\bm{w}(M^{r}(H))\geq\bm{w}(M^{r}(\Gamma_{n}))={\omega}^{n-1}$ for all
$0<n<{\omega}$. Hence $\bm{w}(M^{r}(H))={{\omega}^{{\omega}}}$.

Consider $X_{1}=H+H$ and $X_{2}=H+{\omega}$, two wpos with the same ordinal
invariants: $\bm{o}(X_{i})=\bm{h}(X_{i})={\omega}\cdot 2$ and
$\bm{w}(X_{i})={\omega}$ for $i\in\\{\;1,2\;\\}$. According to Lemma 1.12,
$\bm{w}(M^{r}(X_{1}))=\bm{w}(M^{r}(H))\odot\bm{w}(M^{r}(H))={{\omega}^{{\omega}}}\odot{{\omega}^{{\omega}}}={\omega}^{{\omega}\cdot
2}$ and
$\bm{w}(M^{r}(X_{1}))=\bm{w}(M^{r}(H))\odot\bm{w}(M^{r}({\omega}))={{\omega}^{{\omega}}}\odot
1={{\omega}^{{\omega}}}$.

We will get around this non-functionality issue by introducing a new invariant
in which the width of the multiset ordering is functional. But first we will
show upper and lower bounds on width.

######  Lemma 3.4.

Let $X$ be a wpo. Then

$\bm{w}(M^{r}(X))\leq\sup_{x\in X,n<{\omega}}\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\otimes n+1$

######  Proof 3.5.

Let us define the notation $\underline{\perp}$: For any multisets
$m,m^{\prime}\in M^{r}(X)$, $m\underline{\perp}m^{\prime}$ iff $m\cap
m^{\prime}=\emptyset$ and $m\perp m^{\prime}$.

In other words, $m\underline{\perp}m^{\prime}$ iff $m$ and $m^{\prime}$ are
disjoint and there exists $x\in m$ such that for all $y^{\prime}\in
m^{\prime}$, $x\not\geq y^{\prime}$, and there exists $x^{\prime}\in
m^{\prime}$ such that for all $y\in m$, $x^{\prime}\not\geq y$. In particular
$x^{\prime}\not\geq x$. Hence $m\underline{\perp}m^{\prime}$ implies there
exists $x\in m$ such that $\langle x\rangle\underline{\perp}m^{\prime}$, which
is equivalent to $\langle x\rangle\perp m^{\prime}$. Now:

$\displaystyle M^{r}(X)_{\perp m}$
$\displaystyle\geq_{\text{aug}}\bigsqcup_{m_{1}+m_{2}=m,m_{1}\neq\emptyset}\\{\;m^{\prime}+m_{2}\;:\;m^{\prime}\in
M^{r}(X),m^{\prime}\underline{\perp}m_{1}\;\\}$
$\displaystyle\equiv\bigsqcup_{m_{1}\subseteq
m,m_{1}\neq\emptyset}M^{r}(X)_{\underline{\perp}m_{1}}$
$\displaystyle\leq_{\text{st}}\geq_{\text{aug}}\bigsqcup_{m_{1}\subseteq
m,m_{1}\neq\emptyset}\;\bigsqcup_{x\in m_{1}}M^{r}(X)_{\perp\langle x\rangle}$

Hence according to Lemma 1.2,

$M^{r}(X)_{\perp m}\leq\bigoplus_{m_{1}\subseteq
m,m_{1}\neq\emptyset}\;\bigoplus_{x\in m_{1}}\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\;.$

Let $x\in m$ such that $\bm{w}(M^{r}(X)_{\perp\langle x\rangle})$ is maximal.
Then $\bm{w}(M^{r}(X)_{\perp m})\leq\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\otimes n$ for some $n<{\omega}$. Hence according to Equation Res-w,

$\bm{w}(M^{r}(X))=\sup_{m\in M^{r}(X)}\bm{w}(M^{r}(X)_{\perp
m})+1\leq\sup_{x\in X,n<{\omega}}\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\otimes n+1\;.$

Here is a similar lower bound:

######  Lemma 3.6.

Let $X$ be a wpo. Then

$\bm{w}(M^{r}(X))\geq\sup_{x\in X,n<{\omega}}\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\cdot n+1$

######  Proof 3.7.

This proof follows the same structure as the proof of Lemma 2.4: We study the
residual of $M^{r}(X)$ which contains every element incomparable to some
multiset of the form $\langle x\rangle\times n$, and slice this residual into
a family of quasi-incomparable subsets.

According to Equation Res-w,

$\displaystyle w(M^{r}(X))$ $\displaystyle=\sup_{m\in
M^{r}(X)}\bm{w}(M^{r}(X)_{\perp m})+1$ $\displaystyle\geq\sup_{x\in
X,n<{\omega}}\bm{w}(M^{r}(X)_{\perp\langle x\rangle\times n})+1\;.$

Let us compute a lower bound for $\bm{w}(M^{r}(X)_{\perp\langle x\rangle\times
n})$ for any $x\in X$ and $n<{\omega}$. For all $k\in[1,n]$, let
$M_{k}=\\{\;\langle x\rangle\times(n-k)\cup m\;:\;m\in M^{r}(X)_{\perp\langle
x\rangle}\;\\}$. Observe that $M_{k}\equiv M^{r}(X)_{\perp\langle x\rangle}$
for any $k\in[1,n]$, and for all $m\in M_{k}$, $m\perp\langle x\rangle\times
n$. We claim that $(M_{k})_{k\in[1,n]}$ is a quasi-incomparable family of
subsets of $M^{r}(X)_{\perp(\langle x\rangle\times n)}$: Let $i<n$ and $Y$ a
finite subset of $M_{1}\cup\dots\cup M_{i}$. We define $m_{Y}$ and
$M^{\prime}_{i+1}$ as

$\displaystyle m_{y}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{j\leq
i}\;\bigcup_{m\in(M_{j}\cap Y)}(m\setminus(\langle x\rangle\times(n-j)))\;,$
$\displaystyle M^{\prime}_{i+1}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\;\langle
x\rangle\times(n-i-1)\cup m_{Y}\cup m\;:\;m\in M^{r}(X)_{\perp\langle
x\rangle}\;\\}\;.$

Observe that $M^{\prime}_{i+1}$ is a subset of and isomorphic to $M_{i+1}$,
and $Y\perp M^{\prime}_{i+1}$.

Therefore according to Lemma 1.20, $\bm{w}(M^{r}(X)_{\perp(\langle
x\rangle\times n)})\geq\bm{w}(M^{r}(X)_{\perp\langle x\rangle})\cdot n$.

The bounds provided by Lemmas 3.4 and 3.6 actually match. Furthermore, they
can be reformulated in such a way that the residual on $M^{r}(X)$ boils down
to a residual on $X$:

######  Theorem 3.8.

For any non-linear wpo $X$,

$\bm{w}(M^{r}(X))=\sup\\{\;\bm{w}(M^{r}(X_{\not\geq x}))\cdot{\omega}\;:\;x\in
X,X_{\perp x}\neq\emptyset\;\\}\;.$ (W)

######  Proof 3.9.

For any ordinal $\alpha$, $\sup_{n<{\omega}}(\alpha\cdot
n+1)=\sup_{n<{\omega}}(\alpha\otimes n+1)=\alpha\cdot{\omega}$. Hence
according to Lemmas 3.6 and 3.4,

$\bm{w}(M^{r}(X))=\sup_{x\in X}(\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})\cdot{\omega})\;.$

Let $x\in X$. If $X_{\perp x}=\emptyset$, then $M^{r}(X)_{\perp\langle
x\rangle}=\emptyset$. Otherwise let $y\in X_{\perp x}$. Then $\\{\;\langle
y\rangle\cup m\;:\;m\in M^{r}(X_{\not\geq
x})\;\\}\leq_{\text{st}}M^{r}(X)_{\perp\langle
x\rangle}\leq_{\text{st}}M^{r}(X_{\not\geq x})$. Therefore
$\bm{w}(M^{r}(X)_{\perp\langle x\rangle})=\bm{w}(M^{r}(X_{\not\geq x}))$ if
$X_{\perp x}\neq\emptyset$, otherwise $\bm{w}(M^{r}(X)_{\perp\langle
x\rangle})=0$.

Equation W, even though its inductive formulation makes it impractical, sparks
our interest for two reasons: First, it proves that $\bm{w}(M^{r}(X)$ is
indecomposable. Second, its structure mirrors the residual equations: it
refers to a residual of $X$, and not the residual that appears in Equation
Res-w as one could expect, but the residual of Equation Res-o. Furthermore, it
is a supremum, indexed not on $X$ but only on elements of $X$ that are
incomparable to other elements. In other words, the supremum is indexed on $X$
stripped of its "linear" elements.

These observations are what led us to the definition of fourth ordinal
invariant: _maximal safe order type_

######  Definition 3.10 (Stripped subset, safe subset, maximal safe order
type).

For any wpo $X$,
$\textit{str}(X)\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\;x\in
X\;:\;X_{\perp x}\neq\emptyset\;\\}$ is the _stripped subset_ of $X$. A subset
$X^{\prime}$ of $X$ is _safe_ if there exists a maximal linearisation
$\ell:X^{\prime}\rightarrow\bm{o}(X^{\prime})$ (i.e. a morphism) such that for
all $x_{1},\dots,x_{n}\in X^{\prime}$, for all $x\in X^{\prime}$ such that
$\ell(x)<\ell(x_{i})$ for any $i\in[1,n]$, $(X_{\not\geq
x_{1},\dots,x_{n}})_{\perp x}\neq\emptyset$. We say that $\ell$ verifies the
_safety condition_.

The _maximal safe order type_ of $X$, denoted with
$\operatorname{\underline{\mathbb{o}}}(X)$, is the supremum of the m.o.t.s of
safe subsets of $X$:

$\operatorname{\underline{\mathbb{o}}}(X)\stackrel{{\scriptstyle\text{def}}}{{=}}\sup\\{\;\bm{o}(X^{\prime})\;:\;X^{\prime}\subseteq
X\text{ safe}\;\\}\;.$

Observe that $\textit{str}(\textit{str}(X))=\textit{str}(X)$, and that for any
safe subset $X^{\prime}$ of $X$, $X^{\prime}\leq_{\text{st}}\textit{str}(X)$,
thus $\operatorname{\underline{\mathbb{o}}}(X)\leq\bm{o}(\textit{str}(X))$. At
first glance, it looks like Equation W could be reformulated to be functional
in $\bm{o}(\textit{str}(X)$, but we will soon see that a more restricted
condition like the safety condition is exactly what we need to develop this
inductive expression.

######  Lemma 3.11.

For any wpo $X$, for any linearisation
$\ell:\textit{str}(X)\rightarrow\bm{o}(\textit{str}(X))$, there exists a safe
subset $X^{\prime}$ of $\textit{str}(X)$ such that $\ell$ restricted to
$X^{\prime}$ verifies the safety condition, and
$\bm{o}(X^{\prime})\geq\delta(\bm{o}(\textit{str}(X)))$, where

$\delta(\alpha)\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{cases}\alpha\text{
if $\alpha$ is limit,}\\\ \gamma+\lfloor n/2\rfloor\text{ if $\alpha=\gamma+n$
with $\gamma$ limit and $n<{\omega}$.}\end{cases}$

######  Proof 3.12.

Let
$\downarrow\beta\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\;\gamma:\gamma<\beta\;\\}$
for any ordinal $\beta$. We prove by induction on
$\beta\leq\bm{o}(\textit{str}(X))$ that there exists
$X_{\beta}\subseteq\ell^{-1}(\downarrow\beta)$ a safe subset of
$\textit{str}(X)$ where $\ell$ restricted to $X_{\beta}$ verifies the safety
condition, such that $\bm{o}(X_{\beta})\geq\delta(\beta)$. Furthermore, for
all $\beta<\beta^{\prime}\leq\bm{o}(\textit{str}(X))$, $X_{\beta}\subseteq
X_{\beta^{\prime}}$.

Let $X_{0}=\emptyset$, and $X_{\beta}=X_{\beta^{\prime}}$ if
$\beta=\beta^{\prime}+1$ with $\beta$ limit.

If $\beta=\beta^{\prime}+2$ for some $\beta^{\prime}$ (it does not have to be
limit), then let $x=\ell^{-1}(\beta^{\prime})$ and
$x^{\prime}=\ell^{-1}(\beta^{\prime}+1)$. If $X_{\beta^{\prime}}\cup\\{x\\}$
is a safe subset of $\textit{str}(X)$ then let
$X_{\beta}=X_{\beta^{\prime}}\cup\\{x\\}$. Otherwise it means that there
exists $y\in X_{\beta^{\prime}}$ such that for any $z\in\textit{str}(X)_{\perp
y}$, we have $z\geq x$. Suppose that $X_{\beta^{\prime}}\cup\\{x^{\prime}\\}$
is not a safe subset either: it would also mean that there exists
$y^{\prime}\in X_{\beta^{\prime}}$ such that for any
$z\in\textit{str}(X)_{\perp y}$, we have $z\geq x^{\prime}$. We know that
$x\not\geq x^{\prime}$ and that $y,y^{\prime}\not\geq x,x^{\prime}$, and we
can deduce that $y\perp x$ and $y^{\prime}\perp x^{\prime}$ and $x\geq
y^{\prime}$. We also deduce that if $x\perp x^{\prime}$ then $x^{\prime}\geq
y$, otherwise $x\perp y^{\prime}$. Thus $y\perp y^{\prime}$, which contradicts
the supposition. Therefore $X_{\beta}=X_{\beta^{\prime}}\cup\\{x^{\prime}\\}$
is safe. In both cases,
$\bm{o}(X_{\beta})=\bm{o}(X_{\beta^{\prime}}+1)\geq\delta(\beta^{\prime})+1\geq\delta(\beta)$
by induction hypothesis.

If $\beta$ is limit, then let
$X_{\beta}=\cup_{\beta^{\prime}<\beta}X_{\beta^{\prime}}$. One can see that
$X_{\beta}$ is safe, and that
$\bm{o}(X_{\beta})\geq\sup_{\beta^{\prime}<\beta}\delta(\beta^{\prime})=\beta$
by induction hypothesis.

Therefore
$\delta(\bm{o}(\textit{str}(X)))\leq\operatorname{\underline{\mathbb{o}}}(X)\leq\bm{o}(\textit{str}(X))$,
hence there exists a safe subset whose m.o.t. reaches
$\operatorname{\underline{\mathbb{o}}}(X)$. We can also observe that
$\operatorname{\underline{\mathbb{o}}}(X)=\bm{o}(\textit{str}(X))$ when
$\bm{o}(\textit{str}(X))$ is a limit ordinal, hence this gives us a sufficient
condition for when maximal safe order type reaches m.o.t.

Here is concrete, non inductive reformulation of Equation W which reveals how
$\bm{w}(M^{r}(X))$ is functional in
$\operatorname{\underline{\mathbb{o}}}(X)$.

######  Theorem 3.13 (Width of the multiset ordering).

Let $X$ be a wpo.

Then $\bm{w}(M^{r}(X))={\omega}^{\operatorname{\underline{\mathbb{o}}}(X)}$.

######  Proof 3.14.

$(\geq)$

Let $X^{\prime}$ be a safe subset of $X$. By induction on
$\bm{o}(X^{\prime})$:

When $\bm{o}(X^{\prime})=0$, $\bm{w}(M^{r}(X))\geq 1$.

Let $\bm{o}(X^{\prime})>0$: According to Theorem 3.8,

$\displaystyle w(M^{r}(X))$ $\displaystyle=\sup\\{\;\bm{w}(M^{r}(X_{\not\geq
x}))\cdot{\omega}\;:\;x\in X,X_{\perp x}\neq\emptyset\;\\}$
$\displaystyle\geq\sup\\{\;\bm{w}(M^{r}(X_{\not\geq x}))\cdot{\omega}\;:\;x\in
X^{\prime}\;\\}\;,$

since for any $x\in X^{\prime}$, $X_{\perp x}\neq 0$.

$X^{\prime}$ is safe so there exists a maximal linearisation
$\ell:X^{\prime}\rightarrow\bm{o}(X^{\prime})$ that verifies the safety
condition. Let $x=\ell(\beta)$ for some $\beta<\bm{o}(X^{\prime})$. Then
$\ell^{-1}(\downarrow\beta)$ is a safe subset of $X^{\prime}_{\not\geq x}$;
the maximal linearisation that verifies the safety condition is $l$ restricted
to $\ell^{-1}(\downarrow\beta)$. Hence by induction hypothesis,
$\bm{w}(M^{r}(X_{\not\geq x}))\geq{\omega}^{\beta}$. Therefore:

$w(M^{r}(X))\geq\sup\\{\;{\omega}^{\beta}\cdot{\omega}\;:\;\beta<\bm{o}(X^{\prime})\;\\}={\omega}^{\bm{o}(X^{\prime})}\;.$

$(\leq)$

By induction on $\operatorname{\underline{\mathbb{o}}}(X)$.

If $\operatorname{\underline{\mathbb{o}}}(X)=0$ then $X$ is linear hence
$\bm{w}(M^{r}(X))=1$.

Otherwise let $\alpha=\operatorname{\underline{\mathbb{o}}}(X)$. Assume there
exists $x\in X$, with $X_{\perp x}\neq\emptyset$, such that
$\operatorname{\underline{\mathbb{o}}}(X_{\not\geq x})=\alpha$. It means that
there exists a safe subset $X^{\prime}$ of $X_{\not\geq x}$ and a maximal
linearisation $\ell:X^{\prime}\rightarrow\alpha$ that verifies the safety
condition. Let $\ell^{\prime}:X_{\not\geq x}\cup\\{x\\}\rightarrow\alpha+1$
such that $\ell^{\prime}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha$ and
$\ell^{\prime}(y)\stackrel{{\scriptstyle\text{def}}}{{=}}l(y)$ for any $y\in
X^{\prime}$. Then $\ell^{\prime}$ is a maximal linearisation that verifies the
safety condition for the subset $X^{\prime}\cup\\{x\\}$ of $X$, which has a
m.o.t. of $\alpha+1$. Hence
$\operatorname{\underline{\mathbb{o}}}(X)\geq\alpha+1$, we reached a
contradiction.

For all $x\in X$ such that $X_{\perp x}\neq\emptyset$, we now know that
$\operatorname{\underline{\mathbb{o}}}(X_{\not\geq x})<\alpha$. Thus
$\bm{w}(M^{r}(X_{\not\geq x}))\cdot{\omega}\leq{\omega}^{\alpha}$ by induction
hypothesis. Hence, according to Theorem 3.8,
$\bm{w}(M^{r}(X))\leq{\omega}^{\operatorname{\underline{\mathbb{o}}}(X)}$.

This opens many questions on this new invariant: we already know that it is
closely bounded (Lemma 3.11) and reached by the m.o.t. of a safe subset. We
also know that the maximal safe order type of a wpo reaches its m.o.t. as soon
as $\bm{o}(\textit{str}(X))=\bm{o}(X)$ is a limit ordinal. It is also quite
easy to compute compositionally:

######  Proposition 3.15.

For any non empty wpo $A,B$,

  * •

$\operatorname{\underline{\mathbb{o}}}(A+B)=\operatorname{\underline{\mathbb{o}}}(A)+\operatorname{\underline{\mathbb{o}}}(B)$,

  * •

$\operatorname{\underline{\mathbb{o}}}(A\sqcup
B)=1+(\bm{o}(A)-1)\oplus(\bm{o}(B)-1)$,

  * •

$\operatorname{\underline{\mathbb{o}}}(A\times
B)\geq(\bm{o}(A)-1)\otimes\bm{o}(B)$.

## Conclusion

We have computed the width of the finite set of multisets with the multiset
embedding. As for the multiset ordering, we have found a simple formula for
its height, and showed its width is not functional in any of the usual ordinal
invariants. Nonetheless, we introduced a new ordinal invariant, the maximal
safe order type, in which the width is functional.

Investigating the maximal safe order type is a subject for further research:
Are there equivalent characterisations? How does it relate to other concepts?
Can it be computed compositionally ? Can we define a interesting class of wpos
where maximal safe order type always coincides with m.o.t. ?

## References

  * [1] U. Abraham and R. Bonnet.  Hausdorff’s theorem for posets that satisfy the finite antichain property.  Fund. Math., 159(1):51–69, 1999.  doi:10.4064/fm-159-1-51-69.
  * [2] H. J. Altman.  Intermediate arithmetic operations on ordinal numbers.  Mathematical Logic Quarterly, 63(3–4):228–242, 2017.  doi:10.1002/malq.201600006.
  * [3] M. Aschenbrenner and Wai Yan Pong.  Orderings of monomial ideals.  Fundamenta Mathematicae, 181(1):27–74, 2004.
  * [4] A. Blass and Y. Gurevich.  Program termination and well partial orderings.  ACM Trans. Computational Logic, 9(3):1–26, 2008.  doi:10.1145/1352582.1352586.
  * [5] R. Bonnet, A. Finkel, S. Haddad, and F. Rosa-Velardo.  Ordinal theory for expressiveness of well-structured transition systems.  Information and Computation, 224:1–22, 2013.  doi:10.1016/j.ic.2012.11.003.
  * [6] D. H. J. de Jongh and R. Parikh.  Well-partial orderings and hierarchies.  Indag. Math., 39(3):195–207, 1977.  doi:10.1016/1385-7258(77)90067-1.
  * [7] N. Dershowitz and Z. Manna.  Proving termination with multiset orderings.  Communications of the ACM, 22(8):465–476, 1979.  doi:10.1145/359138.359142.
  * [8] M. Džamonja, S. Schmitz, and Ph. Schnoebelen.  On ordinal invariants in well quasi orders and finite antichain orders.  In P. Schuster, M. Seisenberger, and A. Weiermann, editors, Well Quasi-Orders in Computation, Logic, Language and Reasoning, volume 53 of Trends in Logic, chapter 2, pages 29–54. Springer, Berlin/Heidelberg, Germany, 2020.  doi:10.1007/978-3-030-30229-0_2.
  * [9] D. Figueira, S. Figueira, S. Schmitz, and Ph. Schnoebelen.  Ackermannian and primitive-recursive bounds with Dickson’s lemma.  In Proc. 26th IEEE Symp. Logic in Computer Science (LICS 2011), Toronto, Canada, June 2011, pages 269–278. IEEE Comp. Soc. Press, 2011\.  doi:10.1109/LICS.2011.39.
  * [10] G. Higman.  Ordering by divisibility in abstract algebras.  Proc. London Math. Soc. (3), 2(7):326–336, 1952.  doi:10.1112/plms/s3-2.1.326.
  * [11] I. Kříž and R. Thomas.  Ordinal types in Ramsey theory and well-partial-ordering theory.  In J. Nešetřil and V. Rödl, editors, Mathematics of Ramsey Theory, volume 5 of Algorithms and Combinatorics, pages 57–95. Springer, Berlin/Heidelberg, Germany, 1990.  doi:10.1007/978-3-642-72905-8_7.
  * [12] J. B. Kruskal.  Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture.  Trans. Amer. Math. Soc., 95(2):210–225, 1960.  doi:10.2307/1993287.
  * [13] D. Schmidt.  Well-partial orderings and their maximal order types.  In P. Schuster, M. Seisenberger, and A. Weiermann, editors, Well Quasi-Orders in Computation, Logic, Language and Reasoning, volume 53 of Trends in Logic, chapter 12, pages 351–391. Springer, 2020.  doi:10.1007/978-3-030-30229-0_13.
  * [14] S. Schmitz.  The parametric complexity of lossy counter machines.  In Proc. 46th Int. Coll. Automata, Languages, and Programming (ICALP 2019), Patras, Greece, July 2019, volume 132 of Leibniz International Proceedings in Informatics, pages 129:1–129:15, Dagstuhl, Germany, 2019. Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2019.129.
  * [15] J. Van der Meeren, M. Rathjen, and A. Weiermann.  Well-partial-orderings and the big Veblen number.  Archive for Mathematical Logic, 54(1–2):193–230, 2015.  doi:10.1007/s00153-014-0408-5.
  * [16] I. Vialard.  On the cartesian product of well-orderings.  arXiv:2202.07487 [cs.LO], February 2022.  Submitted for publication.  URL: http://arxiv.org/abs/2202.07487.
  * [17] A. Weiermann.  Proving termination for term rewriting systems.  In Proc. 5th Workshop on Computer Science Logic (CSL ’91), Berne, Switzerland, Oct. 1991, volume 626 of Lecture Notes in Computer Science, pages 419–428. Springer, 1991.  doi:10.1007/BFb0023786.
  * [18] A. Weiermann.  A computation of the maximal order type of the term ordering on finite multisets.  In Proc. 5th Conf. Computability in Europe (CiE 2009), Heidelberg, Germany, July 2009, volume 5635 of Lecture Notes in Computer Science, pages 488–498. Springer, 2009.  doi:10.1007/978-3-642-03073-4_50.

##  Appendix A On ordinal arithmetic

We suppose well-known the notions of sum $\alpha+\beta$ and product
$\alpha\cdot\beta$ on ordinals [2]. However, let us recall some definitions
that might be less familiar to the reader.

######  Definition A.1 (Left subtraction).

For any ordinals $\alpha\geq\beta$, the subtraction $\alpha-\beta$ is the
unique ordinal such that $\beta+(\alpha-\beta)=\alpha$. In particular,

$\alpha-1\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{cases}\alpha\text{ if
$\alpha$ is infinite,}\\\ n-1\text{ if }\alpha=n<{\omega}\;.\end{cases}$

######  Definition A.2 (Cantor normal form).

Any ordinal $\alpha$ can be expressed in Cantor normal form, as
$\alpha=\sum_{i<n}{\omega}^{\alpha_{i}}$, where
$\alpha_{0},\dots,\alpha_{n-1}$ are ordinals such that
$\alpha_{0}\geq\alpha_{1}\geq\dots\geq\alpha_{n-1}$. This expression is
unique.

######  Definition A.3 (Natural operations).

Let $\alpha=\sum_{i<n}{\omega}^{\alpha_{i}}$ and
$\beta=\sum_{i<m}{\omega}^{\beta_{i}}$ two ordinals in Cantor normal form.

The _natural sum_ , or Hessenberg sum, $\alpha\oplus\beta$ is defined as
$\gamma=\sum_{i<n+m}{\omega}^{\gamma_{i}}$ with
$\gamma_{0}\geq\dots\geq\gamma_{n+m-1}$ a reordering of
$\alpha_{0},\dots,\alpha_{n-1},\beta_{0},\dots,\beta_{m-1}$.

The _natural product_ $\alpha\otimes\beta$ is defined as
$\bigoplus_{i<n,j<m}{\omega}^{\alpha_{i}\oplus\beta_{j}}$.

Another product was derived from the Hessenberg sum:

######  Definition A.4 (Hessenberg-based product [1]).

The _Hessenberg-based product_ $\alpha\odot\beta$ is defined inductively by
the following relations:

$\displaystyle\alpha\odot 0$ $\displaystyle=0\;,$
$\displaystyle\alpha\odot(\beta+1)$
$\displaystyle=(\alpha\odot\beta)\oplus\alpha\;,$
$\displaystyle\alpha\odot\beta$
$\displaystyle=\sup\\{\;\alpha\odot\gamma\;:\;\gamma<\beta\;\\}\text{ for
limit $\beta$.}$

We always have $\alpha\cdot\beta\leq\alpha\odot\beta\leq\alpha\otimes\beta$.

######  Definition A.5.

An ordinal $\alpha$ is:

  * •

an _$\epsilon$ -number_ when ${\omega}^{\alpha}=\alpha$.

  * •

_indecomposable_ when for all $\beta,\delta<\alpha$, we have
$\beta+\delta<\alpha$. Equivalently, indecomposable ordinals are ordinals of
the form ${\omega}^{\beta}$ where $\beta$ is any ordinal. They are sometimes
called principal additive ordinals.

  * •

_multiplicatively indecomposable_ when for all $\beta,\delta<\alpha$, we have
$\beta\cdot\delta<\alpha$. Equivalently, multiplicatively indecomposable
ordinals are ordinals of the form ${\omega}^{\beta}$ where $\beta$ is
indecomposable. They are sometimes called principal multiplicative ordinals.


# Universal Persistence for Local Time of One-dimensional Random Walk

Jing Miao† and  Amir Dembo‡

###### Abstract.

We prove the power law decay $p(t,x)\sim t^{-\phi(x,b)/2}$ in which $p(t,x)$
is the probability that the fraction of time up to $t$ in which a random walk
$S$ of i.i.d. zero-mean increments taking finitely many values, is non-
negative, exceeds $x$ throughout $s\in[1,t]$. Here
$\phi(x,b)=\mathbb{P}(\text{L\'{e}vy}(1/2,\kappa(x,b))<0)$ for
$\kappa(x,b)=\frac{\sqrt{1-x}b-\sqrt{1+x}}{\sqrt{1-x}b+\sqrt{1+x}}$ and
$b=b_{S}\geqslant 0$ measuring the asymptotic asymmetry between positive and
negative excursions of the walk (with $b_{s}=1$ for symmetric increments).

###### Key words and phrases:

random walk, local persistence, Lévy distribution, domain of attraction

##  1\. Introduction

Much efforts have been dedicated to finding the asymptotic converging rate of
$\mathbb{P}(T>t)$, where $T$ is some events defined on the random process
[11]. This kind of problems have attracted a lot of interests in the recent
literature under the denomination persistence probability. In many situation
of interests, and under the condition called ”persistently-skewed power” which
we define later, it turns out that the behavior is polynomial:
$\mathbb{P}(T_{x}>t)=t^{-\theta+o(1)}$, where $\theta$ is called the
persistence exponent. It often appears in conjunction with Spitzer’s formula.
The study of such asymptotic behavior has appealed attractions in the physics
literature as well, where the parameter $\theta$ is often called the survival
exponent. It also appears in reliability theory, where $T_{x}$ is viewed as a
certain failure time whose typical upper tails are Pareto-like [5]. Other
connections of the persistent exponents to physics include regular points of
inviscid Burgers equation with self-similar initial data [6, 7], positivity of
random polynomials and diffusion equations [8, 9], and Wetting models with
Laplacian transformations [10].

In this paper, we solve the problem that the summation of the sign of the
partial sum of a zero-mean random walk is greater than $xs$ for a fixed
$x\in[0,1)$ and any positive integer $s$ such that $s\leqslant t$. Let $S$ be
an one-dimeansional mean-zero random walk, $S_{n}$ the partial sums and
$S_{0}=0$. The sign of the partial sum $S_{n}$ is $+1$ if $S_{n}>0$, and $-1$
if $S_{n}<0$. If $S_{n}=0$, then $\text{sgn}(S_{n})=\text{sgn}(S_{n-1})$ for
$n\geqslant 1$. In particular, we define $\text{sgn}(S_{0})=+1$. Then taking
$0<x<1$, we define the following event:

$\tilde{A}_{t,x}:=\\{\sum\limits_{i=1}^{s}\text{sgn}(S_{i})>xs,\forall
1\leqslant s\leqslant t\\}.$ (1.1)

Our goal is to find the asymptotic probability of $\tilde{A}_{t,x}$. Note that
if we want to know whether the summation of the sign of the partial sum of the
random walk $S$ is greater than $xs$ for all $s\in[1,t]$, it is sufficient for
us to check that at each time point $s^{\prime}$ when the sign of partial sums
changes from $-1$ to $+1$, the summation of the sign is greater than
$xs^{\prime}$. Now let’s define “crossing times” $t_{0},t_{1},...$ in this
way:

$\begin{cases}t_{0}=0\\\
t_{i}=\min\\{s>t_{i-1}:\text{sgn}(S_{s})\times\text{sgn}(S_{s+1})=-1\\}.\end{cases}$
(1.2)

In other words, each $t_{i}$ is a “crossing time” of the random walk $S$
either from the positive axis to the negative axis or from the negative axis
to the positive axis. Denote $t_{2i}$ as the end point of the $i$th complete
excursion, and $t_{2i-1}$ as the end point of the $i$th half excursion. Let
$\tau_{i}=t_{i}-t_{i-1}$ for $i\geqslant 1$ be called the “inter-half-
excursion time”. Then we are also interested in the event

$A_{k,x}:=\\{\sum\limits_{i=1}^{s}\text{sgn}(S_{i})>xs,\forall 1\leqslant
s\leqslant t_{2k}\\}.$ (1.3)

Before we proceed further, let’s make clear some notations that we will use
throughout this paper. Most of the random variables in this paper are from the
class of zero-shift-stable random variable $\mathcal{C}(\alpha,\kappa,c)$,
where $\alpha\in(0,2]$ is the stability parameter, $\kappa\in[-1,1]$ is the
skewness parameter, and $c\in(0,\infty)$ is the scale parameter. Let
$\mathcal{Z}_{[\kappa,c]}=\mathcal{C}(1/2,\kappa,c)$, the subset of zero-
shift-stable random variables with parameters $\alpha=1/2$. A distribution or
a random variable is said to be stable if a linear combination of two
independent copies of a random sample has the same distribution, up to
location and scale parameters.

Godrèche et al[1] evaluated
$\lim\limits_{k\rightarrow\infty}\mathbb{P}(A_{k,x})$ by approximating the
inter-half-excursion time $\\{\tau_{i}\\}_{i=1}^{\infty}$ of simple random
walk with i.i.d. random variables in $\mathcal{Z}_{[1,1]}$. In particular,
they give an explicit expression of the persistent power exponent:

$\mathbb{P}(A_{k,x})=\frac{\Gamma(k+1-\phi(x,1))}{\Gamma(K+1)\Gamma(1-\phi(x,1))}=k^{-\phi(x,1)+o(1)},$
(1.4)

where $\phi(x,1)=\mathbb{P}(Z<0)$, for
$Z\in\mathcal{Z}_{[\frac{\sqrt{1-x}-\sqrt{1+x}}{\sqrt{1-x}+\sqrt{1+x}}]}$. For
simple random walk, $b=1$. Note that $\mathbb{P}(Z_{i}<0)=\mathbb{P}(Z_{2}<0)$
if $Z_{1}\in\mathcal{Z}_{[\kappa,c]},Z_{2}\in\mathcal{Z}_{[\kappa,1]},\forall
c$. In this paper, we make two generalizations of results (1.4). First, we do
not restrict $S$ to be simple random walk, but a larger set of random walk
which gives inter-half-excursion time that has a property called “persistently
power-skewness”, which we will define in a moment. Second, we move from the
number of excursions up to a certain point to the time elapsed before a
certain point and deduce that as time $t\rightarrow\infty$, the persistent
exponent should be $\phi(x,b)/2$.

######  Definition 1.1.

Let $\\{\xi_{i}\\}_{i=1}^{\infty}$ be a sequence of stationary random
variables, and let $W_{n}=\sum\limits_{i=1}^{n}\xi_{i},\forall n$. Then
$\\{\xi_{i}\\}_{i=1}^{\infty}$ is called persistently power-skewed if

$\lim\limits_{n\rightarrow\infty}\bigg{|}\frac{\log(\mathbb{P}(W_{1}\geqslant
0,...,W_{n}\geqslant 0))}{\log n}-\mathbb{P}(W_{n}<0)\bigg{|}=0.$ (1.5)

######  Proposition 1.2.

If $\mathbb{P}(W_{n}<0)$ has a limit as $n\rightarrow\infty$, and $\xi_{i}$
are i.i.d. random variables, then $\\{\xi_{i}\\}_{i=1}^{\infty}$ are
persistently power-skewed.

######  Remark 1.3.

In our context, the role of $\xi_{i}$ is played by
$(1-x)\tau_{2i-1}-(1+x)\tau_{2i}$.

Now we are ready to state our theorem.

######  Theorem 1.4.

If $S$ is an one-dimensional random walk with increment mean 0, and if
$\\{(1-x)\tau_{2i-1}-(1+x)\tau_{2i}\\}_{i=1}^{\infty}$ is persistently power-
skewed, then we have

  1. (a)

$\mathbb{P}(A_{k,x})=k^{-\phi(x,b)+o(1)}$ as $k\rightarrow\infty$, with
$0<\phi(x,b)\leqslant 1$, where
$\phi(x,b)=\mathbb{P}(Z<0)=\displaystyle\frac{1}{\pi}\arccos\bigg{(}\frac{\bar{\psi}-x}{1-\bar{\psi}x}\bigg{)}$,
for
$Z\in\mathcal{Z}_{[\kappa(x,b),1]},\kappa(x,b)=\displaystyle\frac{\sqrt{1-x}b-\sqrt{1+x}}{\sqrt{1-x}b+\sqrt{1+x}}$,
and $b=b(S)$ is a parameter that is a function of the random walk $S$, and
$\psi=\displaystyle\frac{b^{2}-1}{b^{2}+1}$. We call $b$ the relative
asymmetry of the positive half excursion and the negative half excursion.

  2. (b)

$\mathbb{P}(\tilde{A}_{t,x})=t^{(-\phi(x,b)/2+o(1))}$ as $t\rightarrow\infty$,
with $\phi(x,b)$ being the same function as that in $(a)$.

######  Corollary 1.5.

Simple random walk gives
$\\{(1-x)\tau_{2i-1}-(1+x)\tau_{2i}\\}_{i=1}^{\infty}$ that satisfies the
persistently power-skewed property, because the inter-half-excursion times are
i.i.d.. Thus, the conclusion of the above theorem holds. By symmetry, $b=1$,
so $\kappa=\displaystyle\frac{\sqrt{1-x}-\sqrt{1+x}}{\sqrt{1-x}+\sqrt{1+x}}$.

######  Corollary 1.6.

The case when we have only increment of 1 on the positive side and finitely
many negative increments also gives persistently power-skewed
$\\{(1-x)\tau_{2i-1}-(1+x)\tau_{2i}\\}_{i=1}^{\infty}$. Though $\tau_{i}$ are
not i.i.d., $(1-x)\tau_{2i-1}-(1+x)\tau_{2i}$ are i.i.d..

######  Corollary 1.7.

The case when the positive increments follow a truncated geometric
distribution gives persistently power-skewed
$\\{(1-x)\tau_{2i-1}-(1+x)\tau_{2i}\\}_{i=1}^{\infty}$ due to the memory-less
property of geometric distribution.

##  2\. Poof of Theorem 1.1(a)

Before proving the first part of the theorem, let’s prove Proposition 1.2.

###### Proof.

Assume
$\lim\limits_{n\rightarrow\infty}\mathbb{P}\bigg{(}\sum\limits_{i=1}^{n}\xi_{i}\leqslant
0\bigg{)}=q$. By [2, Ch.XII.7 Theorem 4] we have:

$M(s)\equiv\sum\limits_{n=1}^{\infty}p_{n}s^{n}=e^{\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}f(n)},$

where
$f(n)=\mathbb{P}\left\\{\sum\limits_{i=1}^{n}\xi_{i}>0\right\\}=1-q+\varepsilon_{n}$
with $\varepsilon_{n}\rightarrow 0$. Let
$L\bigg{(}\frac{1}{1-s}\bigg{)}:=\exp\\{\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}\varepsilon_{n}\\}$.
Then we have

$M(s)=\exp\left\\{\left(\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}q+\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}\varepsilon_{n}\right)\right\\}=\displaystyle\frac{1}{(1-s)^{(1-q)}}L\bigg{(}\frac{1}{1-s}\bigg{)}.$

Assuming that $L\bigg{(}\frac{1}{1-s}\bigg{)}$ is a slowly varying function,
since $p_{n}$ is monotonically decreasing in $n$, the Tauberian Theorem in [2,
Ch.XIII.5, Theorem 5] gives

$p^{n}\sim\displaystyle\frac{1}{\Gamma(1-q)}n^{-q}L(n).$ (2.1)

Then we will be done with the proof.

Now it only remains to show that $L\bigg{(}\frac{1}{1-s}\bigg{)}$ is indeed a
slowly varying function. If $1/{1-s}=m$, then $s=1-1/{m}$, which gives us

$L(m)=\exp\left\\{\sum\limits_{n=1}^{\infty}\frac{(1-1/m)^{n}}{n}\cdot\varepsilon_{n}\right\\},\text{
}L(km)=\exp\left\\{\sum\limits_{n=1}^{\infty}\frac{(1-1/(km))^{n}}{n}\cdot\varepsilon_{n}\right\\}.$

Since $\varepsilon_{n}\rightarrow 0$, $\forall\delta>0$, $\exists N_{\delta}$,
such that

$1\geqslant\exp\left\\{\sum\limits_{n=N_{\delta}}^{\infty}\bigg{[}\frac{(1-1/m)^{n}}{n}-\frac{(1-1/(km))^{n}}{n}\bigg{]}\cdot\varepsilon_{n}\right\\}\geqslant
k^{-\delta},$ (2.2)

for $k>0$. For any fixed $N_{\delta}$, as $m\rightarrow\infty$, we have

$\exp\left\\{\sum\limits_{n=1}^{N_{\delta}}\bigg{[}\frac{(1-1/m)^{n}}{n}-\frac{(1-1/(km))^{n}}{n}\bigg{]}\cdot\varepsilon_{n}\right\\}\rightarrow
1.$ (2.3)

(2.2) and (2.3) are true for any $\delta>0$. Also $k^{-\delta}\rightarrow 1$
as $\delta\rightarrow 0$. Hence, we have
$\displaystyle\frac{L(km)}{L(m)}\rightarrow 1$ as $m\rightarrow\infty$. Thus,
we proved that $L\bigg{(}\frac{1}{1-s}\bigg{)}$ is slowly varying, which
finishes our proof. ∎

The next lemma show that for any mean zero one-dimensional random walk with
increments taking finitely many values, the inter-half-excursion time
$\tau_{i}$ belongs to $\mathcal{Z}_{[\kappa,c]}$.

######  Lemma 2.1.

Define $\tau_{-y,l}=\inf\\{t:S_{t}=l,S_{t^{\prime}}\leqslant 0,1\leqslant
t^{\prime}<t|S_{0}=-y\\}$ for some $y>0,l>0$ and $\max\\{y,l\\}<\sup X_{1}$,
where $X_{1}=S_{1}-S_{0}$. Then $\tau_{-y,l}\in\mathcal{Z}_{[1,c(y,l)]}$,
where the scaling $c(y,l)$ is a function of $y,l$. Since the increments of the
random walk can only take on finitely many values, the inter-half-excursion
time $\tau_{i}\in Z_{[1,c(S)]}$, where the scaling $c$ is a function of $S$.

###### Proof.

Since $\tau_{-y,l}$ is non-negative, the skewness parameter is 1. With some
modifications of the Fourier methods in [2, Ch.XVIII.3 of], we define

$\begin{split}\rho(s,\zeta)&=\mathbb{E}\left[s^{N}e^{i\zeta S_{N}}\right],\\\
\rho^{\prime}(s,\zeta)&=\mathbb{E}\left[s^{N}e^{i\zeta
S_{N}}{\bf{1}}_{\\{S_{N}=l\\}}\right],\end{split}$

where $N$ is the first time the random walk crosses 0 and reaches some
positive value. Then we have the relationship between $\rho$ and
$\rho^{\prime}$:

$\rho(s,\zeta)=\mathbb{E}\left[s^{N}e^{i\zeta
S_{N}}\right]=\sum\limits_{l=1}^{\infty}\mathbb{E}\left[s^{N}{\bf{1}}_{\\{S_{N}=1\\}}e^{i\zeta
S_{N}}\right]=\sum\limits_{l=1}^{\infty}\mathbb{E}\left[s^{N}{\bf{1}}_{\\{S_{N}=1\\}}e^{i\zeta
l}\right].$ (2.4)

Let $\mathbb{E}\left[s^{N}{\bf{1}}_{\\{S_{N}=l\\}}\right]=f(s,l)$. Then
$\rho(s,\zeta)=\sum\limits_{l=1}^{\infty}f(s,l)e^{i\zeta l}$. Now we can apply
the Laplace transform on $\rho$:

$f(s,l)=\displaystyle\frac{l}{2\pi}\int_{0}^{2\pi/l}\rho(s,\zeta)e^{-i\zeta
l}\,d\zeta.$ (2.5)

We know from [2] that

$\displaystyle\log\frac{1}{1-\rho(s,\zeta)}=\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}\int_{y}^{\infty}e^{i\zeta
z}F^{n\ast}\,dz,$ (2.6)

which gives us

$\rho(s,\zeta)=1-\exp\left\\{-\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}\int_{y}^{\infty}e^{i\zeta
z}F^{n\ast}\,dz\right\\}.$ (2.7)

Note that
$f(s,l)=\mathbb{E}\left[s^{N}{\bf{1}}_{\\{S_{N}=l\\}}\right]=\sum\limits_{n=1}^{\infty}s^{n}P_{-y}\\{N=n,S_{N}=l\\}$,
which is exactly the generating function of the probability we want to
calculate. Therefore, we have

$\begin{split}f(s,l)&=\displaystyle\frac{l}{2\pi}\int_{0}^{2\pi/l}\rho(s,\zeta)e^{-i\zeta
y}\,dy=\displaystyle\frac{l}{2\pi}\int_{0}^{2\pi/l}-\exp\left\\{-i\zeta
y-\sum\limits_{n=1}^{\infty}\frac{s^{n}}{n}\int_{y}^{\infty}e^{i\zeta
z}F^{n\ast}\,dz\right\\}\,d\zeta.\end{split}$ (2.8)

We want to know the behavior of
$\lim\limits_{n\rightarrow\infty}P_{-y}\\{N=n,S_{N}=l\\}$. In other words, we
are interested in the coefficients of $s^{n}$ as $n\rightarrow\infty$ in
(2.4). Taylor expansion tells us the coefficient of $s^{n}$ is
$\left(\displaystyle\frac{d^{n}f(s,l)}{ds^{n}}\Big{|}_{s=0}\right)\Big{/}n!$.
Since what’s inside the integral is always finite, we can exchange integration
and differentiation. After calculation we get

$\begin{split}P_{-y}\\{N=n,S_{N}=l\\}&=\displaystyle\frac{l}{2\pi
n!}\int_{0}^{2\pi/l}-\exp^{-i\zeta l}\left(-(n-1)!)\int_{y}^{\infty}e^{i\zeta
z}F^{n\ast}\,dz\right)\,d\zeta\\\
&\xrightarrow{n\rightarrow\infty}\displaystyle\frac{l}{2\pi
n}\int_{0}^{2\pi/l}\exp^{-i\zeta l}\int_{y}^{\infty}e^{i\zeta
z}\frac{1}{\sigma\sqrt{2\pi n}}e^{-\frac{z^{2}}{2n{\sigma}^{2}}}\,d\zeta.\\\
&\rightarrow\displaystyle\frac{l}{2\pi n}\int_{0}^{2\pi/l}e^{-i\zeta
l}\left(\int_{y}^{\infty}\frac{1}{\sigma\sqrt{2\pi
n}}e^{-\frac{z^{2}}{2n{\sigma}^{2}}+i\zeta z}\,dz\right)\,d\zeta.\end{split}$
(2.9)

The second line results from the central limit theorem. The integrand insided
the parenthesis in the above equation is equal to

$\displaystyle\frac{1}{\sigma\sqrt{2\pi n}}\exp\left\\{-\frac{(y-i\zeta
n{\sigma}^{2})}{2n{\sigma}^{2}}-\frac{n(\sigma\zeta)^{2}}{2}\right\\}\rightarrow
C_{1}(y)\cdot\exp\left\\{-\frac{n(\zeta\sigma)^{2}}{2}\right\\},$

for some constant $C_{1}(y)$ that depends on $y$ (since
$\displaystyle\frac{1}{\sigma\sqrt{2\pi n}}\exp\left\\{-\frac{(y-i\zeta
n{\sigma}^{2})}{2n{\sigma}^{2}}\right\\}$ is analytic in $n$ and bounded).
Define $f\sim g$ if $g/c\leqslant f\leqslant cg$ for some uniform constant
$c$. Then, we have

$\begin{split}P_{-y}\\{N=n,S_{N}=l\\}&\sim\displaystyle\frac{C_{1}(y)}{2\pi
n}\int_{0}^{2\pi/l}\exp\left\\{-i\zeta
l-\frac{n(\zeta\sigma)^{2}}{2}\right\\}\,d\zeta\\\
&\sim\displaystyle\frac{C_{1}(y)}{2\pi
n}\int_{0}^{2\pi/l}\exp\left\\{-\frac{(\zeta\sigma\sqrt{n})^{2}}{2}-\frac{l^{2}}{2}\right\\}\,d\zeta\\\
&\sim\exp\\{-l^{2}/2\\}\displaystyle\frac{l\cdot C_{1}(y)}{2\pi
n}\int_{0}^{2\pi/l}\exp\left\\{-\frac{(\zeta\sigma\sqrt{n})^{2}}{2}\right\\}\,d\zeta\\\
&\sim C_{2}(y,l)\frac{l}{2\pi
n}\int_{0}^{2\pi/l}\exp\left\\{-\frac{(\zeta\sigma\sqrt{n})^{2}}{2}\right\\}\,d\zeta,\end{split}$
(2.10)

where $C_{2}(y,l)$ is a function of $y,l$. If we do a change of variable, that
is, let $w=\sigma\zeta\sqrt{n}$, we get

$\begin{split}P_{-x}\\{N=n,S_{N}=l\\}&\sim
C_{2}(y,l)\int_{0}^{2\pi\sigma\sqrt{n}/l}\exp\\{-(w+il)^{2}/2\\}\cdot\frac{1}{\sigma\sqrt{n}}\,dw\\\
&\sim
C_{2}(y,l)n^{-3/2}\int_{0}^{\infty}\frac{1}{2\pi}\exp\\{-(w+il)^{2}/2\\}\,dw\\\
&\sim C_{3}(y,l)n^{-3/2},\end{split}$ (2.11)

for some finite number $C_{3}(y,l)$.The last step is true because that inside
the integral is almost a density function of a normal distribution except that
the domain is complex so it converges to a constant. Hence,
$\tau_{-x,l}\in\mathcal{Z}_{[1,c(y,l)]}$. For each inter-half-excursion time
$\tau_{i}$, there are finitely many possible starting position $-y^{\prime}$
and ending position $l^{\prime}$. Therefore,
$\tau_{i}\in\mathcal{Z}_{[1,c(S)]}$. ∎

Now we are ready to prove part(a) of our theorem.

###### proof of part (a).

For part (a) of the theorem, we only need to check that $A_{k,x}$ holds at the
end of each excursion. Hence,

$\begin{split}A_{k,x}&=\\{\sum\limits_{i=1}^{m}(\tau_{2i-1}-\tau_{2i}\geqslant
x\sum\limits_{i=1}^{m}(\tau_{2i-1}+\tau_{2i}),\forall 1\leqslant m\leqslant
k\\}\\\
&=\\{(1-x)\sum\limits_{i=1}^{m}\tau_{2k-1}\geqslant(1+x)\sum\limits_{i=1}^{m}\tau_{2k},\forall
1\leqslant m\leqslant k\\}\\\ &=\\{\xi_{1}\geqslant 0,...,\xi_{m}\geqslant
0,\forall 1\leqslant m\leqslant k\\},\end{split}$

where $\xi_{i}=(1-x)\tau_{2i-1}-(1+x)\tau_{2i}$. Since
$\\{\xi_{i}\\}_{i=1}^{\infty}$ are persistently power-skewed,

$\mathbb{P}(A_{k,x})=n^{-q+o(1)},$

where
$q=\lim\limits_{n\rightarrow\infty}\mathbb{P}(\sum\limits_{i=1}^{n}\xi_{i}<0)$.

Consider the sequence
$\\{S_{t_{2i-2}+1},S_{t_{2i-2}},S_{t_{2i-1}+1},S_{t_{2i}+1}\\}$. Intuitively,
these are the starting point , the ending point of the first half-excursion,
and those of the second half-excursion, respectively, in the $i$th complete
excursion. This sequence forms a Markov chain. Since we only have finitely
many choices of positive and negative increments, it is a finite regular
Markov chain with a stationary distribution. From Lemma 2.1 we know
$\tau_{i}\in\mathcal{Z}_{[\kappa,c]}$. Hence $\sum\limits_{i=1}^{n}\xi_{i}$ as
$n\rightarrow\infty$ becomes sum of finitely many types of random variables,
denoted as
$Z_{(u_{T},u^{\prime}_{T})},...,Z_{(u_{T},u^{\prime}_{T})},Z_{(v_{1},v^{\prime}_{1})},...,Z_{(v_{T},v^{\prime}_{T})}$,
where $Z_{(u_{i},u^{\prime}_{i})}$ is the type of a $\tau_{2k-1}$, and
$Z_{(v_{i},v^{\prime}_{i})}$ the type for a $\tau_{2k}$. Note that
$Z_{(u_{i},u^{\prime}_{i})}\in\mathcal{Z}_{[1,c(u_{i},u^{\prime}_{i})]},Z_{(v_{i},v^{\prime}_{i})}\in\mathcal{Z}_{[1,c(v_{i},v^{\prime}_{i})]}$.
Let $\gamma_{u_{1}},..,\gamma_{u_{T}},\gamma_{v_{1}},...,\gamma_{v_{T}}$ be
the corresponding to the stationary probability of seeing each type of
$\tau_{2i-1}$ and $\tau_{2i}$ along the time line.

For a random variable $Z$ such that $Z]in\mathcal{Z}_{[\kappa,c]}$, $Z$ has
characteristic function
$\zeta(t;\kappa,c)=\exp(-c|t|^{1/2}\\{1-i\kappa\text{sgn}(t)\\})$ [12]. The
sum of Markov renewal stable random variable is still a stable random variable
with the same stability parameter. Thus,

$\begin{split}\lim\limits_{n\rightarrow\infty}\mathbb{P}(\sum\limits_{i=1}^{n}\xi_{i}<0)&=\lim\limits_{n\rightarrow\infty}\mathbb{P}(\sum\limits_{i=1}^{n}(1-x)\tau_{2i-1}<\sum\limits_{i=1}^{n}(1+x)\tau_{2i})\\\
&=\lim\limits_{T\rightarrow\infty}\mathbb{P}((1-x)\sum\limits_{i=1}^{T}(\gamma_{u_{i}}c(u_{i},u^{\prime}_{i}))Z_{1}<(1+x)\sum\limits_{i=1}^{T}(\gamma_{v_{i}}c(v_{i},v^{\prime}_{i}))Z_{2}),\end{split}$
(2.12)

where $Z_{1},Z_{2}\in\mathcal{Z}-{[1,1]}$ are independent. We can calculate
the scaling parameter of the sum from the characteristic function.
Specifically, $aZ_{1}+bZ_{2}=(\sqrt{a}+\sqrt{b})^{2}Z,Z\in\mathcal{Z}_{[1,1]}$
for $a,b>0$. Hence,

$\begin{split}\lim\limits_{n\rightarrow\infty}\mathbb{P}(\sum\limits_{i=1}^{n}\xi_{i}<0)&=\lim\limits_{T\rightarrow\infty}\mathbb{P}((1-x)(\sum\limits_{i=1}^{T}\sqrt{\gamma_{u_{i}}c(u_{i},u^{\prime}_{i})})^{2}Z^{\prime}_{1}<(1+x)(\sum\limits_{i=1}^{T}\sqrt{\gamma_{v_{i}}c(v_{i},v^{\prime}_{i})})^{2}Z^{\prime}_{2}\\\
&=\lim\limits_{T\rightarrow\infty}\mathbb{P}((1-x)(b^{+}(S))^{2}Z_{1}<(1+x)\sum\limits_{i=1}^{T}(b^{-}(S))^{2}Z_{2},\end{split}$
(2.13)

where
$b^{+}(S)=\sum\limits_{i=1}^{T}\sqrt{\gamma_{u_{i}}c(u_{i},u^{\prime}_{i})},b^{-}(S)=\sum\limits_{i=1}^{T}\sqrt{\gamma_{v_{i}}c(v_{i},v^{\prime}_{i})}$.
We also know from the characteristic function that $aZ_{1}-bZ^{\prime}_{1}=Z$,
for
$Z\in\mathcal{Z}_{[\frac{\sqrt{a}-\sqrt{b}}{\sqrt{a}+\sqrt{b}},(\sqrt{a}+\sqrt{b})^{2}]}$.
Continuing (2.13), we have
$\lim\limits_{n\rightarrow\infty}\mathbb{P}(\sum\limits_{i=1}^{n}\xi_{i}<0)=\mathbb{P}(Z<0)$,
for $Z\in\mathcal{Z}_{[\kappa(x,b),c]}$, where

$\kappa(x,b)=\frac{\sqrt{1-x}b(S)-\sqrt{1+x}}{\sqrt{1-x}b(S)+\sqrt{1+x}}=\frac{\sqrt{1-x}b^{+}(S)-\sqrt{1+x}b^{-}(S)}{\sqrt{1-x}b^{+}(S)+\sqrt{1+x}b^{-}(S)},$
(2.14)

where $b(S)=b^{+}(S)/b^{-}(S)$. Hence
$q=\mathbb{P}(Z_{\kappa,1}<0)=\phi(x,b(S))$.

[13] gives a way to simulate a randome variable
$Z\in\mathcal{Z}_{[\kappa,c]}$, which is

$Z\stackrel{{\scriptstyle
d}}{{=}}\frac{\sin(1/2(\Phi-\Phi_{0})}{\cos^{2}(\Phi)}\cdot\frac{\cos(\Phi-1/2(\Phi-\Phi_{0}))}{W},$
(2.15)

where $W$ follows standard exponential distribution and $\Phi$ is uniform on
$(-\pi/2,\pi/2)$; also $\Phi_{0}=-2\arctan(\kappa)$. Note that $Z<0$ is
equivalent to $\sin(1/2(\Phi-\Phi_{0}))<0$. Since $\Phi\in[-\pi/2,\pi/2]$ and
$\kappa\in[-1,1],Z<0$ is equivalent to $\Phi<\Phi_{0}$. Hence, we have

$\mathbb{P}(Z<0)=\mathbb{P}(\Phi<\Phi_{0})=\frac{\pi/2-2\arctan(\kappa)}{\pi}=\frac{1}{2}-\frac{2\arctan(\kappa)}{\pi}.$

In our case
$\kappa(x,b)=\displaystyle\frac{\sqrt{1-x}b-\sqrt{1+x}}{\sqrt{1-x}b+\sqrt{1+x}}$.
Let $\kappa(x,b)=\tan(-\theta/2)$. Then
$\phi(x,b)=\displaystyle\frac{1}{\pi}(\pi/2+\theta)$. Let
$m^{2}=\displaystyle\frac{1+x}{1-x}$. We have

$\tan^{2}(\theta/2)=\kappa^{2}(x,b)=\frac{(b-m)^{2}}{(b+m)^{2}}=\frac{1-\cos\theta}{1+\cos\theta}.$

Hence, $\cos\theta=\displaystyle\frac{2bm}{b^{2}+m^{2}}$, which gives us

$\begin{split}\cos(\pi/2+\theta)&=-\sin\theta=\frac{m^{2}-b^{2}}{m^{2}+b^{2}}=\frac{(1+x)-b^{2}(1-x)}{(1+x)+b^{2}(1-x)}\\\
&=\frac{(b^{2}-1)-x(b^{2}+1)}{(b^{2}+1)-x(b^{2}-1)}=\frac{\bar{\psi}-x}{1-\bar{\psi}x},\end{split}$

where $\bar{\psi}=\displaystyle\frac{b^{2}-1}{b^{2}+1}$. Hence,
$\phi(x,b)=\displaystyle\frac{1}{\pi}\arccos\bigg{(}\frac{\bar{\psi}-x}{1-\bar{\psi}x}\bigg{)}$,
which finishes our proof. ∎

##  3\. Proof of Theorem 1.1(b)

Intuitively, as $t\rightarrow\infty$, the number of excursions completed
before time $t$ will have order $t^{1/2}$. Hence, we expect the persistent
exponent of $t$ should be $\phi(S,x)/2$.

###### proof of part (b).

For simplicity, for the proof below $t$ takes on positive real values. The
generalization from positive integer values to positive real values is quite
straightforward. We want to show

$C_{1}t^{-\phi(x,b)/2}\leqslant\mathbb{P}(\tilde{A}_{t,x})\leqslant
C_{2}t^{-\phi(x,b)/2},$ (3.1)

as $t\rightarrow\infty$ for some constants $C_{1},C_{2}$.

Let $N_{t}=\max\\{k:\sum\limits_{i=1}^{k}\tau_{2k}\leqslant t\\}$. That is,
$N_{t}$ is the maximum number of complete excursions the random walk finishes
before time $t$. First, we proved the lower bound power. Since $A_{t},A_{k}$
are monotonic decreasing in $t,k$, we have

$\begin{split}\mathbb{P}(\tilde{A}_{t,x})&\geqslant\mathbb{P}(A_{N_{t}+1,x},N_{t}\leqslant\lfloor{t^{1/2+\delta}}\rfloor-1)\geqslant\mathbb{P}(A_{\lfloor{t^{1/2+\delta}}\rfloor})-\mathbb{P}(N_{t}>t^{1/2+\delta}),\end{split}$
(3.2)

for some small $\delta>0$. For the first term, as $t\rightarrow\infty$,
$\mathbb{P}(A_{\lfloor{t^{1/2+\delta}}\rfloor})\sim
t^{(\lfloor{t^{1/2+\delta}}\rfloor)\phi(S,x)}\rightarrow
t^{(t^{1/2+\delta})\phi(S,x)}$. Let $\delta\rightarrow 0$. Then the exponent
goes to $-\phi(S,x)/2$. For the second term, adopting the same notation as in
the proof of part (a), we have

$\begin{split}\mathbb{P}(N_{t}>t^{1/2+\delta})&=\mathbb{P}\left(\sum\limits_{i=1}^{t^{1/2+\delta}}\tau_{i}<t\right)\\\
&\rightarrow\mathbb{P}\bigg{(}t^{1/2+\delta}(b^{+}(S))^{2}Z_{1}+(b^{-}(S))^{2}Z_{2})<t\bigg{)},\end{split}$
(3.3)

where $Z_{1},Z_{2}\in\mathcal{Z}_{[1,1]}$ are independent, and
$b^{+}(S),b^{-}(S)$ are the same as in the proof of part (a) of Theorem 1.4.
Since we have finitely many possible states, the above equiation simplifies to
$\mathbb{P}(N_{t}>t^{1/2+\delta})\rightarrow\mathbb{P}(\tau_{1}<C_{3}t^{-2\delta})$
for some constant $C_{3}$ and $\tau_{1}\in Z_{[1,1]}$ [3]. From the
probability density function of standard Lévy(1/2) varaible,
$f(\tau_{t}=t)=\displaystyle\sqrt{\frac{1}{2\pi}}\frac{e^{-1/{(2x)}}}{x^{3/2}}$,
we see as $t\rightarrow\infty,t^{-2\delta}\rightarrow 0$. The CDF of
$\tau_{1}$ decays exponentially, faster than any power. Thus,
$\mathbb{P}(N_{t}>t^{1/2+\delta})<t^{-m}$ for any positive $m$. Now taking
$\delta\rightarrow 0$, by the lower bound of the first and the second term in
Equation 3.2, we get our desired lower bound of $C_{1}t^{-\phi(x,b)/2}$.

Now we try to find the appropriate upper bound of
$\mathbb{P}(\tilde{A}_{t,x})$. Note we have

$\mathbb{P}(\tilde{A}_{t,x})=\mathbb{P}(\tilde{A}_{t,x},N_{t}\leqslant
t^{1/2-\delta})+\mathbb{P}(\tilde{A}_{t,x},t^{1/2-\delta}<N_{t}\leqslant
t^{1/2+\delta})+\mathbb{P}(\tilde{A}_{t,x},N_{t}\geqslant t^{1/2-\delta}),$
(3.4)

and the last term is bounded by $t^{-m}$ for arbitray $m<\infty$. We consider
the first two terms. For the middle term, we have

$\begin{split}\mathbb{P}(\tilde{A}_{t,x},t^{1/2-\delta}<N_{t}\leqslant
t^{1/2+\delta})&\leqslant\mathbb{P}(A_{N_{t}+1,x},t^{1/2+\delta}\geqslant
N_{t}\geqslant t^{1/2-\delta})\\\
&\leqslant\mathbb{P}(A_{\lfloor{t^{1/2-\delta}}\rfloor})\sim
t^{(1/2-\delta)\phi(x,b)}.\end{split}$ (3.5)

Thus, as $\delta\rightarrow\infty$, the second term is upper bounded by a
constant times $t^{-\phi(x,b)/2}$. Now we are only left with the first term of
(3.4), namely, $\mathbb{P}(\tilde{A}_{t,x},N_{t}\leqslant t^{1/2-\delta})$. We
approach it using the following method. Note that for any $1\leqslant
k\leqslant t^{1/2-\delta}$,we have

$\begin{split}\mathbb{P}(A_{k,x},N_{t}=k)&\leqslant\mathbb{P}(A_{k,x},N_{t}=k,\max\limits_{1\leqslant
i\leqslant
k}\tau_{i}\geqslant\hat{\delta}t)+\mathbb{P}(A_{k,x},N_{t}=k,\max\limits_{1\leqslant
i\leqslant k}\tau_{i}<\hat{\delta}t),\end{split}$ (3.6)

for some $\hat{\delta}>0$. Fix $\hat{\delta}$, and let
$L=\lfloor{1/{\hat{\delta}}}\rfloor$, and $h\equiv\hat{\delta}t$. Then the
second part is at most

$\mathbb{P}(S_{2k}>Lh,\tau^{*}_{2k}<h),$

where $S_{2k}=\sum\limits_{i=1}^{2k}\tau_{i}$, $\tau_{i}$ not necessarily
i.i.d, but belongs to $\mathcal{Z}_{[\kappa,c]}$, and
$\tau^{*}_{2k}=\max\limits_{1\leqslant i\leqslant 2k}\\{\tau_{i}\\}$. Now we
try to find an upper bound for the above probability [4]. $t_{0}=t\approx Lh$.
Let $t_{1}=t-2h$, and $\tau_{t_{1}}=\inf\\{i:S_{i}\geqslant t_{1}\\}$. So we
have

$\begin{split}\mathbb{P}(S_{2k}>Lh,\tau^{*}_{2k}<h)&=\mathbb{P}(S_{2k}\geqslant
t_{1}+2h,\tau_{t_{1}}\leqslant 2k,S_{\tau_{t_{1}}}\leqslant
t_{1}+h,\tau^{*}_{2k}\leqslant h)\\\
&\leqslant\mathbb{P}(S_{2k}>Lh|A_{\tau_{t_{1}}})P(A_{\tau_{t_{1}}}),\end{split}$

where $A_{\tau_{t_{1}}}=\\{\tau_{t_{1}}\leqslant 2k,S_{\tau_{t_{1}}}\leqslant
t_{1}+h,\tau^{*}_{\tau_{t_{1}}}\leqslant h\\}$. By the strong Markov property
of $S_{k}$ at $\tau_{t_{1}}$, we have

$\begin{split}\mathbb{P}(S_{2k}>Lh|A_{\tau_{t_{1}}})&=\mathbb{E}(\mathbb{P}(S_{2k}-S_{\tau_{t_{1}}}\geqslant
Lh-
S_{\tau_{t_{1}}}|S_{\tau{t_{1}}})|A_{\tau_{t_{1}}}))\leqslant\mathbb{E}(\mathbb{P}(\tilde{S}_{2k-\tau_{t_{1}}}\geqslant
h|A_{\tau_{t_{1}}}))\\\ &=\mathbb{E}(\mathbb{P}(\tilde{\tau}_{h}\leqslant
2k-\tau_{t_{1}}|A_{\tau_{t_{1}}}))\leqslant\mathbb{P}(\tilde{\tau}_{h}\leqslant
2k),\end{split}$

where $\tilde{S}$ and $\tilde{\tau}$ denote a new random walk process starting
at $\tau_{t_{1}}$. By the strong Markov property,$\tilde{S},$ is a mean 0
random walk with the same types of increments which are all in
$\mathcal{Z}_{[\kappa,c]}$. Therefore, we have

$\begin{split}\mathbb{P}(S_{2k}>Lh,\tau^{*}_{2k}<h)&\leqslant\mathbb{P}(\tau_{h}\leqslant
2k)\mathbb{P}(A_{\tau_{t_{1}}})\leqslant\mathbb{P}(\tau_{h}\leqslant
2k)\mathbb{P}(S_{2k}\geqslant t_{1},\tau^{*}_{\tau_{t_{1}}}\leqslant
h)\end{split}$

If we iterate through $t,\tau_{t_{1}},\tau_{t_{2}},\tau_{t_{3}}...$, where
$\tau_{t_{k}}=\tau_{t_{k-1}}-2h$, note that by coupling lemma,
$\mathbb{P}(\tau_{t_{i}}\leqslant
2k)\leqslant\mathbb{P}(\tau^{\prime}\leqslant 2k)$, where
$\tau^{\prime}=\inf\\{i:S^{\prime}_{i}\geqslant t_{i}\\},$ where $S^{\prime}$
is a random walk with each step increment $\tau^{\prime}$ a Lévy random
variable with the biggest scale parameter the original random walk increment
can achieve. We get

$\mathbb{P}(S_{2k}>Lh,\tau^{*}_{2k}<h)\leqslant\mathbb{P}^{L/{2}}(\tau^{\prime}_{h}\leqslant
2k).$

Since $\tau^{\prime}_{i}$, by our definition, is iid Lévy(1/2), and $h=\delta
t$, and $k<t^{1/2-\delta}$, we have $\mathbb{P}(\tau^{\prime}_{h}\leqslant
2k)=\mathbb{P}(\tau>\frac{h}{4k^{2}})\sim\frac{2k}{\sqrt{h}}<C_{0}t^{-\delta},$
which implies

$\mathbb{P}(S_{2k}>Lh,\tau^{*}_{2k}<h)\leqslant Ct^{-L\delta/2},$ (3.7)

for some fixed constant $C>0$. Since we can choose $\hat{\delta}$ to be as
small as we want, $L\delta/2$ can be as big as we want. Thus, the second term
of Equation (3.6) has an upper bound with arbitrarily small power.

Now we can find an appropriate upper bound for the first term of (3.6). Note
that in the event $A_{k}$, we have the relationship
$(1-x)\tau_{2i-1}-x\tau_{2i}\geqslant 0,\forall 1\leqslant i\leqslant k$.
Define $\gamma=\inf\\{m:\tau_{m}\geqslant\hat{\delta}t\\}$. Clearly,
$A_{N_{t}}\subset A_{\gamma/2-1}$. Thus, we have

$\begin{split}&\sum\limits_{k=0}^{t^{1/2-\delta}}\mathbb{P}(\tilde{A}_{t,x},N_{t}=k,\max\limits_{1\leqslant
m\leqslant
2k}\\{\tau_{m}\\}\geqslant\hat{\delta}t)\leqslant\mathbb{P}(A_{N_{t},x},N_{t}\leqslant
t^{1/2-\delta},\max\limits_{1\leqslant m\leqslant
2k}\\{\tau_{m}\\}\geqslant\hat{\delta}t)\\\
&\leqslant\mathbb{P}(A_{\lfloor{\gamma/2-1}\rfloor,x},1\leqslant\gamma\leqslant
2t^{1/2-\delta})\leqslant\sum\limits_{\gamma=1}^{2t^{1/2-\delta}}\mathbb{P}(A_{\max(\gamma/2-1,0)},\tau_{\gamma}\geqslant\hat{\delta}t)\\\
&\leqslant\sum\limits_{\gamma=1}^{2t^{1/2-\delta}}\mathbb{P}(A_{\max(\lfloor{\gamma/2-1}\rfloor,0)}\mathbb{P}(\tau_{\gamma}\geqslant\hat{\delta})\leqslant
C_{4}\sum\limits_{\gamma=0}^{t^{1/2-\delta}}\gamma^{-\phi(S,x)}\frac{1}{\sqrt{\delta}}t^{-1/2}\\\
&\leqslant\frac{C_{5}}{\sqrt{\delta}}t^{-\phi(S,x)/2-\delta(1-\phi(S,x))}.\end{split}$
(3.8)

Thus, combing (3.6), (3.7), (3.8), we get that for $k\leqslant
t^{1/2-\delta}$, and some small fixed $\delta>0$, we can always find big
enough $L$ such that

$\mathbb{P}(\tilde{A}_{t,x},N_{t}\leqslant t^{1/2-\delta})\leqslant
Ct^{-L\delta/2}+\frac{C_{5}}{\sqrt{\delta}}t^{-\phi(S,x)/2-\delta(1-\phi(S,x))}\leqslant
C^{\prime\prime\prime}t^{\phi(S,x)/2},$ (3.9)

for some constant $C^{\prime\prime\prime}$. Thererfore, combining the
arguments for the cases of $k\leqslant t^{1/2-\delta},t^{1/2-\delta}\leqslant
k<t^{1/2+\delta},k\geqslant t^{1/2+\delta}$ together, we get our desired upper
bound in (3.1). Together with the previous arguments on lower bound, we
finished the proof. ∎

## References

  * [1] A. Baldassarri, J.P. Bouchaud, I. Dornic, and C.Godréche, Generalized persistence exponents: an exactly soluble model, Phys. Rev. E59, R20(1999), 10.1103/PhysRevE.59.R20.
  * [2] William Feller, An Introduction to Probability Theory and Its Applications, Volume II, Second Edition,ISBN 0 471 25709 5.
  * [3] B.V. Gnedenko, A.N. Kolmogorov, Limit Distributions for Sums of Independent Random Variables, Addison-Wesley Publishing Company.
  * [4] Alexander E Holroyd, Yuval Peres, Jeffrey E Steif, Wald for non-stopping times: the rewards of impatient prophets, DOI:10.1214/ECP.v19-3609.
  * [5] J.D. Kalblfeisch, R.L. Prentice, The statistical analysis of failure time data. Wiley, New York, 2002
  * [6] Ya.G. Sinaĭ. Statistics of shocks in solutions of inviscid Burgers equation. Comm. Math. Phys. 148(3), 601-621, 1992
  * [7] J. Bertoin. The inviscid Burgers equation with Brownian initial velocity. Comm. Math. Phys. 193(2), 397-406,1998.
  * [8] A. Dembo, B. Poonen, Q-M. Shao and O.Zeitouni. Random polynomials having few or no real zeros. J. Am. Math. Soc. 15(4), 857-892,2002.
  * [9] S.N. Majumdar and A.J. Bray. Spatial persistence of fluctuating interfaces. Phys,. Rev. Lett. 86,3700-3703, 2001.
  * [10] F. Caravenna and J.-D. Deuschel. Pinning and wetting transition for $(1+1)$-dimensional fields with Laplacian interaction. Ann. Probab. 36(6), 2388-2433,2008.
  * [11] F. Aurzada and T. Simon. Persistence probabilities & exponents. arXiv: 1203.6554[math.PR].
  * [12] Rick Durrett, Probability: Theory and Examples, 4th edition. Cambridge University Press, 2010.
  * [13] J.M. Chambers, C.L. Mellows, B.W. Stuck. A Method for Simulating Stable Random Variables. Journal of Applied Statistics Association, Vol. 71, No. 354, 1976, pp.340-344.