# An Optimal Selection Problem Associated with the Poisson Process

Zakaria Derbazi
Queen Mary University of London

###### Abstract

Cowan and Zabczyk (1978) introduced a continuous-time generalisation of the
best-choice (secretary) problem, where offers arrive at epochs of a
homogeneous Poisson process. We expand their work to encompass the last-
success problem under the Karamata-Stirling success profile. In this setting,
the $k$th trial is a success with probability $p_{k}=\theta/(\theta+k-1)$,
where $\theta>0$. In the best-choice setting ($\theta=1$), the myopic strategy
is optimal, and the proof hinges on verifying the monotonicity of certain
critical roots. We extend this crucial result to the last-success case by
exploiting a connection to the sign of the derivative in the first parameter
of a quotient of Kummer’s hypergeometric functions. Finally, we derive bounds
and asymptotics of the critical roots, strengthening and improving the
findings of Ciesielski and Zabczyk (1979).

##  1 Introduction

Cowan and Zabczyk (1978) considered a continuous-time extension of the
classical secretary problem. In this scenario, the task is to select the best
apartment within a fixed time horizon, $T$. Apartments are presented at epochs
of a homogeneous Poisson process with a known intensity $\lambda>0$. The
decision-maker may accept or discard each presented apartment irrevocably.
Each arrival can be ranked relative to previously seen apartments, and all
permutations of ranks are assumed equally likely and independent of the
arrival process.

The optimal strategy selects the $k$th apartment presented at time $t$ only if
the expected number of remaining arrivals in the time window $(T-t)$ falls
below a predefined cutoff threshold $a_{k}$. To be precise, the condition is

$\displaystyle\lambda(T-t)\leq a_{k}.$ (1)

Each cutoff $a_{k}$ ($k=1,2,\ldots$) is the unique solution to the equation
$h_{k}(x)=0$, where $h_{k}(x)$ is formed by the difference between the
probability of zero successes and exactly one success and is given by

$\displaystyle
h_{k}(x)\coloneqq\frac{1}{k}+\sum_{n=1}^{\infty}\frac{x^{k}}{n!(k+n)}\left(1-\sum_{j=1}^{n}\frac{1}{j+k-1}\right).$
(2)

For a strategy to be optimal, the sequence of roots $(a_{k})_{k\geq 0}$ must
be increasing. Cowan and Zabczyk developed an ingenious argument to establish
this property. They begin by establishing the uniqueness of the roots,
leveraging the continuity of the function $h_{k}$ and all of its derivatives,
along with the behaviour of the first and second derivatives, in the vicinity
of the root $a_{k}$. Subsequently, they exploit a relationship between the
change in probability of exactly one success across consecutive trials and the
difference between the probabilities of one and zero successes to prove
monotonicity (see p. 588–590 in [10]).

Cowan and Zabczyk’s optimal selection model can be categorised as a best-
choice problem with a random number of observations, denoted $N$, with an a
priori Poisson distribution. These observations arrive uniformly and
independently at times in $[0,T]$. This formulation might appear similar to
the best-choice problem introduced by Presman and Sonin (1972), in which $N$
is a Poisson-distributed random variable. However, the key distinction lies in
the role of time as a crucial decision factor [10, 5, 24, 15]. Consequently,
Cowan and Zabczyk’s model is more accurately characterised as a best-choice
problem with random observation times, where the number of items to be
inspected has a Poisson prior distribution.

We aim to extend this framework to encompass last-success problems, where the
decision-maker only observes a sequence of indicator variables. In this
setting, the defining characteristic of the trials (and, consequently, the
problem itself) is the sequence of success probabilities, which we refer to as
the success profile or record profile. In the classical best-choice problem,
the profile is given by the success probability $p_{k}=1/k$ for the $k$th
trial.

Our investigation is closely related to the theory of random records [14, 20].
Gaver (1976) played a pivotal role in linking this theory to optimal stopping
problems. He examined the embedding of record times within a point process and
analysed the problem of selecting the last record appearing between epochs of
a Poisson process. Bruss (1988) further highlighted the strong relationship
between optimal selection problems and optimal stopping related to record
sequences. However, the initial work on last-success problems is attributed to
Pfeifer (1989). He examined a sequence of record indicators and addressed the
problem of selecting the last success within that sequence. For best-choice
problems with a random number of trials, a brief overview of recent
advancements is provided in [15].

A common strategy for solving last-success problems involves checking whether
they fall within the monotone case of optimal stopping theory [8, 13]. Should
this criterion be met, the optimal strategy is deduced via a nonincreasing
sequence of cutoffs. These cutoffs, indexed by the number of arrivals,
represent the earliest instant at which accepting the current offer (record)
becomes optimal. The optimality of the myopic strategy is ensured whenever the
sequence of cutoffs is nonincreasing.

Cowan and Zabczyk’s problem has led to further research on optimal selection
related to Poisson arrivals. Bruss (1987) broadened the framework to
accommodate inhomogeneous Poisson processes. Ano and Ando (2000) considered a
random availability attached to each offer. Schwalko and Szajowski (2003)
explored the variant of the problem of selecting the best or second-best
apartment. Subsequently, Szajowski (2007) introduced a game-theoretic version
of the problem, thus offering a distinct perspective on the optimal selection
strategy. Considering the last-success version of the problem, Hofmann (1997)
investigated Poisson arrivals with successes appearing according to Nevzorov’s
$F^{\alpha}$ record profile. In this setting, success probabilities are given
by $p_{k}=\alpha_{k}/(\alpha_{1}+\cdots+\alpha_{k})$ for some positive
$\alpha^{\prime}s$. However, Hofmann fell short of demonstrating the crucial
property of monotonicity of the roots. In scenarios where trials arrive based
on an inhomogeneous Poisson process, the instances of stopping at the last
success, the last $\ell$th success, and any of the last $\ell$ successes were
studied by Bruss (2000), Bruss and Paindaveine (2000), and Tamaki (2011)
respectively.

Using the Karamata-Stirling profile to model the success probabilities in our
analysis is motivated by two key factors. First, it relates to the well-known
Ewens Sampling Formula (ESF) [11]. The number of distinct components within
the ESF framework can be expressed as a sum of independent indicator
variables. Each of these variables follows the Karamata-Stirling profile,
where the probability of success in the $k$thth trial is given by

$p_{k}=\frac{\theta}{(\theta+k-1)}\,,~{}~{}~{}k\geq 1,$ (3)

with mutation parameter $\theta>0$. The case $\theta=1$ corresponds to the
classical best-choice problem. Second, the generating function of the number
of successes in $n$ Bernoulli trials under the Karamata-Stirling profile
exhibits advantageous analytical properties. This characteristic allows us to
strengthen and simplify the solution presented by Cowan and Zabczyk while
revealing a connection between last-success problems with random observation
times and hypergeometric functions. In this regard, we rely on Kummer’s
confluent hypergeometric function properties to demonstrate that the sequence
of cutoffs $(a_{k})$ is increasing. This approach aligns with the recent work
of [16, 15], who employed the Gaussian hypergeometric function to analyse
other power series distributions.

The paper is structured as follows. Section 2 introduces the fundamental model
based on a generic prior for the number of observations and a generic success
profile. Subsequently, it derives the necessary condition for the optimality
of the myopic strategy. Section 3 presents new findings related to Kummer’s
confluent hypergeometric function, focusing specifically on deriving an
expression to determine the sign of the derivative in parameter of a quotient
of Kummer’s functions. Section 4 establishes the core optimality result,
demonstrating the monotonicity of the cutoffs through a connection to the sign
of the derivative in the first parameter of a quotient of Kummer’s functions.
Section 5 transitions to the scenario where observations are revealed at
epochs of an inhomogeneous Poisson process. By a trivial time-change argument
on the arrivals, we show that the optimal rule is similar to the homogeneous
case. When the success probability is a function of the time parameter, the
problem reduces to selecting the last arrival in an inhomogeneous Poisson
process. This section concludes with an illustrative example that considers an
asymptotic Karamata-Stirling profile as an example of a continuous-time
success probability function. Subsequently, the optimal threshold and the
classical optimal winning probability are derived. Finally, Section 6
generalises the two theorems of Ciesielski and Zabczyk (1979) to encompass the
Karamata-Stirling profile. We improve the upper bound on the roots and derive
their asymptotic values.

##  2 The Mathematical Model

Let $\left\\{T_{n},X_{n}\right\\}_{n\geq 1}$ denote a marked Poisson process
defined on a probability space $(\Omega,{\cal F},\mathbb{P})$, where
$T_{1},T_{2},\ldots$ are the chronologically ordered arrival epochs. The marks
$\left\\{X_{n}\right\\}_{n\geq 1}$ form an i.i.d. sequence of Bernoulli random
variables independent of $\left\\{T_{n}\right\\}_{n\geq 1}$ having a success
profile $\boldsymbol{p}\coloneqq\left(p_{n}\right)_{n\geq 1}$, that is
$\mathbb{P}(X_{n}=1)=p_{n}$. Without loss of generality, assume that
$0<p_{k}<1$ for all $k\geq 1$.

The bivariate process $\left\\{T_{n},X_{n}\right\\}_{n\geq 1}$ is adapted to
the natural filtration $({\cal F}_{t})_{t\in[0,1]}\subseteq{\cal F}$, where
the $\sigma$-algebra ${\cal F}_{t}$ encapsulates the complete knowledge of
epochs and outcomes within the time interval $[0,t]$. The random record
process of points $T_{n}$ at which record marks occur ($X_{n}=1$) can be
regarded as a thinning of $\\{T_{n}\\}_{n\geq 1}$, where each mark $T_{n}$ is
independently retained with probability $p_{n}$ [3].

Another way to model this process is to consider the marks
$X_{1},X_{2},\ldots$ as a sequence of trials, whose number $N$ is Poisson-
distributed. The number of successes among trials $k,k+1,\cdots,n$ has a
Poisson-binomial distribution with probability generating function

$z\mapsto\prod_{j=k}^{n}(1-p_{j}+zp_{j}).$

A simple computation gives the probability of zero successes and the
probability of one success from stage $k\geq 1$ as

$\displaystyle s_{0}(k,n)$
$\displaystyle\coloneqq\prod_{j=k}^{n}(1-p_{j}),~{}~{}~{}~{}k<n,$ (4)
$\displaystyle s_{1}(k,n)$ $\displaystyle\coloneqq
s_{0}(k,n)\sum_{j=k}^{n}\frac{p_{j}}{1-p_{j}},~{}~{}~{}~{}~{}k<n.$ (5)

Without loss of generality, we apply a deterministic time-change to transform
arrivals from $[0,T]$ to $[0,1]$. Furthermore, given $N=n$, the trials arrive
in continuous time at independent, uniformly distributed epochs
$U_{1},U_{2},\cdots,U_{n}$ in [0,1]. We order these arrivals chronologically
so each arrival epoch $T_{k}$ of the Poisson process in the original setting
corresponds to the $k$th order statistic of $U_{1},\cdots,U_{n}$. We associate
with each $T_{k}$, a trial $X_{k}$ resulting in success with probability
$p_{k}$, independently of anything else, and we let $T_{n}$ undefined on the
event $\\{N<n\\}$. The number of arrivals up to time $t$ is a mixed binomial
process defined as

$N_{t}=\sum_{n=1}^{N}\operatorname{\mathbbm{1}}{\\{U_{n}\leq
t\\}},~{}~{}~{}t\in[0,1].$

We introduce the state variable $(t,k)\in[0,1]\times\\{0,1,\cdots\\}$ to
represent the number of arrivals observed up to any epoch $t$. We denote the
occurrence of exactly $k$ arrivals up to time $t$ by the event
$\\{N_{t}=k\\}$. When the $k$th trial occurs at time $T_{k}=t$ and the outcome
is a success, we designate a transition to this success state as
$(t,k)^{\circ}$.

By independence of the trials and the Markov property of mixed binomial
processes [18], the distribution of the point process of epochs and outcomes
of the trials on $(t,1]$ both depend on ${\cal F}_{t}$ only through $N_{t}$.

Let $\boldsymbol{\pi}=(\pi_{1},\pi_{2},\ldots)$ be the prior distribution of
the number of trials, where $\pi_{n}=\mathbb{P}(N=n)$. The posterior
distribution factors as

$\displaystyle\mathbb{P}(N=k+j\,|\,N_{t}=k)$
$\displaystyle=\frac{\displaystyle\binom{k+j}{k}\pi_{k+j}(1-t)^{j}t^{k}}{\displaystyle\sum_{n=k}^{\infty}\binom{n}{k}\pi_{n}(1-t)^{n-k}t^{k}}$
$\displaystyle=f_{k}(t){k+j\choose k}\pi_{k+j}(1-t)^{j},~{}~{}~{}j\geq 0,$ (6)

where

$f_{k}(t)=\left(\sum_{n=k}^{\infty}\binom{n}{k}\pi_{n}(1-t)^{n-k}\right)^{-1}$

is a normalisation function. By (2), the conditional probability that there
are no successes following state $(t,k)$ is given by

${\cal S}_{0}(t,k):=f_{k}(t)\sum_{j=0}^{\infty}\pi_{k+j}{k+j\choose
k}(1-t)^{j}s_{0}(k+1,k+j),$ (7)

which is the adapted reward from stopping at a success state $(t,k)^{\circ}$.
Analogously, the probability of exactly one success following state $(t,k)$ is

${\cal S}_{1}(t,k):=f_{k}(t)\sum_{j=m}^{\infty}\pi_{k+j}{k+j\choose
k}(1-t)^{j}s_{1}(k+1,k+j).$ (8)

Similarly, this probability represents the adapted reward from stopping at the
next success state $(t,k)^{\circ}$.

The following result recalls some properties of ${\cal S}_{1}$ and ${\cal
S}_{0}$ that prove instrumental in the latter sections.

######  Lemma 1 (Lemma 2 in [15]).

For fixed $k\geq 1$, suppose $\pi_{k}>0$. Then

  * (i)

${\cal S}_{0}(1,k)=1,~{}{\cal S}_{1}(1,k)=0$,

  * (ii)

${\cal S}_{0}(t,k)$ is nondecreasing in $t$, and is strictly increasing if
$~{}\sum_{j=k+1}^{\infty}\pi_{j}>0$,

  * (iii)

There exists cutoffs $a_{k}\in[0,1)$ such that $\operatorname{sgn}\left({\cal
S}_{1}(t,k)-{\cal S}_{0}(t,k)\right)=\operatorname{sgn}(a_{k}-t)$ for
$t\in(0,1]$.

We define a stopping strategy to be a random variable $\tau$ which takes
values in the random set of times $\\{T_{1},\cdots,T_{N},1\\}$ and is adapted
to ${\cal F}_{t}$ for $t\in[0,1]$, where $\\{\tau=1\\}$ is interpreted as not
stopping at all. Our analysis will focus solely on strategies stopping at
success states $(T_{k},k)^{\circ}$, where the objective is to stop at the last
success. For $k\geq 1$, stopping at $(t,k)^{\circ}$ is regarded as a win if
$T_{k}=t$, and no successes occur in $(t,1)$.

With every ‘stopping set’ $A_{k}\subset[0,1)\times{\mathbb{N}}$ we associate a
Markovian stopping strategy which stops at the first success trial
$(t,k)^{\circ}$ with $(t,k)$ falling in $A_{k}$. The optimal strategy exists
for arbitrary $\boldsymbol{\pi}$ and $\boldsymbol{p}$. Moreover, it is
Markovian by a theorem on the exclusion of randomised stopping strategies (see
Theorem 5.3 in [8]).

The myopic strategy $\tau^{*}$ is defined as the strategy stopping at the
first state $(t,k)^{\circ}$ satisfying ${\cal S}_{1}(t,k)\leq{\cal
S}_{0}(t,k)$. This strategy is Markovian with stopping set

$A:=\bigcup\limits_{k=1}^{\infty}([a_{k},1)\times\\{k\\}),$

where the cutoffs $(a_{k})$ are defined in Lemma 1. Each cutoff $a_{k}$
corresponds to the earliest time $\tau^{*}$ can accept a success trial with
index $k$. If $(t,k)\notin A$, then stopping in the state $(t,k)^{\circ}$ is
not optimal.

The so-called monotone case of the optimal stopping theory holds if $A$ is
‘closed’, meaning that after entering $A$, the sequence of successes
$(t,N_{t})^{\circ}$ does not exit the set (see [8, 13]). This condition is
sufficient for the optimality of $\tau^{*}$. Since the sequence of successes
is increasing in both components, this property of $A$ is equivalent to the
condition $a_{1}\geq a_{2}\geq\cdots$, characterising the optimality of
$\tau^{*}$.

##  3 Hypergeoemtrics

Recall the definition of Kummer’s hypergeometric function

$M(a,c,x):=\sum_{j=0}^{\infty}\frac{(a)_{j}}{(c)_{j}}\frac{x^{j}}{j!}\,,$ (9)

viewed as a function of real parameters $a,c$ and $x>0$, where $c>a>0$, its
basic integral representation is given by

$\displaystyle
M(a,c,x)\coloneqq\frac{\Gamma(c)}{\Gamma(a)\Gamma(c-a)}\int_{0}^{1}e^{xu}u^{a-1}(1-u)^{c-a-1}{\mathrm{d}}{u},$
(10)

where $\Gamma$ is the Gamma function, which is defined by Euler’s integral of
the second kind as follows

$\displaystyle\Gamma(x)$
$\displaystyle\coloneqq\int_{0}^{\infty}u^{x-1}e^{-u}{\mathrm{d}}{u}~{}~{}~{}~{}\text{for
}x>0.$ (11)

Let $D_{x}$ denote the derivative with respect to the variable (or the
parameter) $x$. The following elementary results are foundational for the
proofs presented in this section.

######  Lemma 2.

Consider two functions $f:I\to J$ and $g:I\to J$, where
$I,J\subseteq(0,\infty)$. If $f$ and $g$ are differentiable, then it holds
that

$\displaystyle\operatorname{sgn}D_{x}\log f(x)$
$\displaystyle=\operatorname{sgn}D_{x}f(x),$
$\displaystyle\operatorname{sgn}D_{x}\left\\{f(x)g(x)\right\\}$
$\displaystyle=\operatorname{sgn}D_{x}f(x)~{}~{}~{}~{}\text{ if
}\operatorname{sgn}D_{x}f(x)=\operatorname{sgn}D_{x}g(x),$
$\displaystyle\operatorname{sgn}D_{x}\left\\{\frac{f(x)}{g(x)}\right\\}$
$\displaystyle=\operatorname{sgn}D_{x}f(x)~{}~{}~{}~{}\text{ if
}\operatorname{sgn}D_{x}f(x)=-\operatorname{sgn}D_{x}g(x).$

###### Proof.

Given that $f,g$ are strictly positive, it is evident that

$\operatorname{sgn}D_{x}\log
f(x)\coloneqq\operatorname{sgn}\frac{D_{x}f(x)}{f(x)}=\operatorname{sgn}D_{x}f(x).$

From this result and by definition of the $\log$ function, we have the
elementary relations

$\displaystyle\operatorname{sgn}D_{x}\left\\{f(x)g(x)\right\\}=\operatorname{sgn}D_{x}\log\left\\{f(x)g(x)\right\\}=\operatorname{sgn}\left\\{D_{x}\log
f(x)+D_{x}\log g(x)\right\\},$

and

$\displaystyle\operatorname{sgn}D_{x}\left\\{{f(x)}/{g(x)}\right\\}=\operatorname{sgn}D_{x}\log\left\\{{f(x)}/{g(x)}\right\\}=\operatorname{sgn}\left\\{D_{x}\log
f(x)-D_{x}\log g(x)\right\\}.$

The assertions are readily demonstrated by a simple sign analysis. ∎

The next result provides a test for assessing the sign of expressions of the
kind

$D_{x}\frac{\Gamma(ax+x_{1})}{\Gamma(ax+x_{2})},$

for arbitrary real numbers $x_{1},x_{2}$ and $a$. We employ a lengthier but
more instructive argument based on Euler’s integral of the first kind. This
approach circumvents the direct proof, which uses the logarithmic derivative
of the Gamma function.

######  Lemma 3.

For a fixed $c\in\mathbb{R}$, the following sign identity holds:

$\displaystyle\operatorname{sgn}D_{x}\frac{\Gamma(x)}{\Gamma(x+c)}=-\operatorname{sgn}(c)~{}~{}~{}~{}~{}\text{
where }~{}~{}~{}~{}x>0\text{ and }x+c>0.$

###### Proof.

The derivative of the quotient of Gamma functions is given by

$D_{x}\frac{\Gamma(x)}{\Gamma(x+c)}=\frac{D_{x}\Gamma(x)\Gamma(x+c)-D_{x}\Gamma(x+c)\Gamma(x)}{\Gamma^{2}(x+c)}.$

We only need to check the derivative’s numerator as the quotient’s denominator
is positive. Use Euler’s representation of the Gamma function (11) to note
that

$\displaystyle D_{x}\Gamma(x)\Gamma(x+c)-D_{x}\Gamma(x+c)\Gamma(x)$
$\displaystyle=\int_{0}^{\infty}\frac{1}{u}e^{-u}\log(u){\mathrm{d}}{u}\int_{0}^{\infty}v^{c-1}e^{-v}{\mathrm{d}}{v}-\int_{0}^{\infty}v^{c-1}e^{-v}\log(v){\mathrm{d}}{v}\int_{0}^{\infty}\frac{1}{u}e^{-u}{\mathrm{d}}{u}$
$\displaystyle=\iint_{\overline{\mathbb{R}}_{+}\times\overline{\mathbb{R}}_{+}}\left\\{\frac{1}{uv}e^{-u-v}\right\\}v^{c}\log(u){\mathrm{d}}{u}{\mathrm{d}}{v}-\iint_{\overline{\mathbb{R}}_{+}\times\overline{\mathbb{R}}_{+}}\left\\{\frac{1}{uv}e^{-u-v}\right\\}v^{c}\log(v){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{\overline{\mathbb{R}}_{+}\times\overline{\mathbb{R}}_{+}}\left\\{\frac{u}{v}e^{-u-v}\right\\}v^{c}\log\left(\frac{u}{v}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<u<v<\infty}\left\\{\frac{1}{uv}e^{-u-v}\right\\}v^{c}\log\left(\frac{u}{v}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<v<u<\infty}\left\\{\frac{1}{uv}e^{-u-v}\right\\}v^{c}\log\left(\frac{u}{v}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<u<v<\infty}\left\\{\frac{1}{uv}e^{-u-v}\right\\}v^{c}\log\left(\frac{1}{uv}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<u<v<\infty}\left\\{\frac{1}{uv}e^{-u-v}\right\\}u^{c}\log\left(\frac{v}{u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<u<v<\infty}\left\\{\frac{1}{uv}e^{-u-v}\log\left(\frac{v}{u}\right)\right\\}\left[u^{c}-v^{c}\right]{\mathrm{d}}{u}{\mathrm{d}}{v}.$

The sign of the integrand when $u<v$ depends on the expression $u^{c}-v^{c}$
whose sign matches that of $-c$. This completes the proof. ∎

Next, we proceed to the main result of this section, which is to derive an
expression for the sign of derivative in the first parameter and the second
parameter, respectively, of a quotient of Kummer’s functions.

######  Theorem 4.

For $x>0$, the following sign identities hold

$\displaystyle{\rm(i)}~{}\operatorname{sgn}D_{a}\displaystyle\left(\frac{M(a,c_{1},x)}{M(a,c_{2},x)}\right)=\operatorname{sgn}(c_{1}-c_{2}),\text{
if }c_{1}>a>0\text{ and }c_{2}>a>0,$
$\displaystyle{\rm(ii)}~{}\operatorname{sgn}D_{c}\displaystyle\left(\frac{M(a_{1},c,x)}{M(a_{2},c,x)}\right)=\operatorname{sgn}(a_{2}-a_{1}),\text{
if }c>a_{1}>0\text{ and }c>a_{2}>0.$

###### Proof.

We only prove the first assertion of the theorem and defer part (ii), which is
potentially of broader interest, to the appendix. Use part one of Lemma 2 to
reformulate the analysis to the derivative of the log of a quotient instead
since

$\operatorname{sgn}D_{a}\displaystyle\left(\frac{M(a,c_{1},x)}{M(a,c_{2},x)}\right)=\operatorname{sgn}D_{a}\displaystyle\log\left(\frac{M(a,c_{1},x)}{M(a,c_{2},x)}\right).$

Now, let $\phi$ be this the integral part in Kummer’s function representation
(10)

$\phi(a,c,x)\coloneqq\int_{0}^{1}e^{xu}\left(\frac{u}{1-u}\right)^{a-1}(1-u)^{c-2}{\mathrm{d}}{u}.$

The logarithmic derivative in parameter $a$, where $c_{1},c_{2}$ are constants
satisfying $c_{1}>a>0$ and $c_{2}>a>0$, respectively, is

$\displaystyle
D_{a}\displaystyle\log\left(\frac{M(a,c_{1},x)}{M(a,c_{2},x)}\right)$
$\displaystyle=D_{a}\log M(a,c_{1},x)-D_{a}\log M(a,c_{2},x)$
$\displaystyle=D_{a}\left\\{\log\frac{\Gamma(c_{1})}{\Gamma(c_{2})}+\log\frac{\Gamma(c_{2}-a)}{\Gamma(c_{1}-a)}+\log\frac{\phi(a,c_{1},x)}{\phi(a,c_{2},x)}\right\\}$
$\displaystyle=D_{a}\log\frac{\Gamma(c_{2}-a)}{\Gamma(c_{1}-a)}+D_{a}\log\frac{\phi(a,c_{1},x)}{\phi(a,c_{2},x)}.$
(12)

By the second part of Lemma 2, it is sufficient to show that the two
logarithmic derivatives in (12) have the same sign. Using Lemma 3, the sign of
the first quotient matches the sign of $c_{2}-c_{1}$.

For the second quotient, check the sign of
$D_{a}\left\\{{\phi(a,c_{1},x)}/{\phi(a,c_{2},x)}\right\\}$. Again, we only
need to check the numerator’s sign after taking the derivative. For positive
constants, $c_{1}>a>0$ and $c_{2}>a>0$, use the Eulerian integral
representation (10) to express the derivative as a double integral in the
following way

$\displaystyle D_{a}\left\\{\frac{\phi(a,c_{1},x)}{\phi(a,c_{2},x)}\right\\}$
$\displaystyle=\int_{0}^{1}e^{xu}\left(\frac{u}{1-u}\right)^{a-1}(1-u)^{c_{1}-2}\log\left(\frac{u}{1-u}\right){\mathrm{d}}{u}\int_{0}^{1}e^{xv}\left(\frac{v}{1-v}\right)^{a-1}(1-v)^{c_{2}-2}{\mathrm{d}}{v}$
$\displaystyle\qquad-\int_{0}^{1}e^{xu}\left(\frac{u}{1-u}\right)^{a-1}(1-u)^{c_{1}-2}{\mathrm{d}}{u}\int_{0}^{1}e^{xv}\left(\frac{v}{1-v}\right)^{a-1}(1-v)^{c_{2}-2}\log\left(\frac{v}{1-v}\right){\mathrm{d}}{v}$
$\displaystyle=\iint_{[0,1]\times[0,1]}e^{x(u+v)}\left(\frac{uv}{(1-u)(1-v)}\right)^{a-1}[(1-u)(1-v)]^{c_{1}-2}(1-v)^{c_{2}-c_{1}}\log\left(\frac{u}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle\qquad-\iint_{[0,1]\times[0,1]}e^{x(u+v)}\left(\frac{uv}{(1-u)(1-v)}\right)^{a-1}[(1-u)(1-v)]^{c_{1}-2}(1-v)^{c_{2}-c_{1}}\log\left(\frac{v}{1-v}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{[0,1]\times[0,1]}\left\\{\underbrace{e^{x(u+v)}\left(\frac{uv}{(1-u)(1-v)}\right)^{a-1}[(1-u)(1-v)]^{c_{1}-2}}_{\text{symmetric
in
}u,v}\right\\}(1-v)^{c_{2}-c_{1}}\log\left(\frac{u(1-v)}{v(1-u)}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}(1-v)^{c_{2}-c_{1}}\log\left(\frac{u(1-v)}{v(1-u)}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<u<v<1}\left\\{\cdots\right\\}(1-v)^{c_{2}-c_{1}}\log\left(\frac{u(1-v)}{v(1-u)}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}(1-v)^{c_{2}-c_{1}}\log\left(\frac{u(1-v)}{v(1-u)}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<v<u<1}\left\\{\cdots\right\\}(1-u)^{c_{2}-c_{1}}\log\left(\frac{v(1-u)}{u(1-v)}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}\log\left(\frac{u(1-v)}{v(1-u)}\right)\left\\{(1-v)^{c_{2}-c_{1}}-(1-u)^{c_{2}-c_{1}}\right\\}{\mathrm{d}}{u}{\mathrm{d}}{v}.$

In the given domain of integration where $u>v$, the expression
$\displaystyle\log\left(\frac{u(1-v)}{v(1-u)}\right)$ is positive. This means
that the sign of the last integrand depends solely on
$(1-v)^{c_{2}-c_{1}}-(1-u)^{c_{2}-c_{1}}$. But, the sign of this expression is
precisely that of $c_{2}-c_{1}$ as $1-v>1-u$.

Since the sign of both terms in the right-hand side of (12) coincides, we can
conclude, through part two of Lemma 2, that the sign of
$D_{a}\displaystyle\log\left(\frac{M(a,c_{1},x)}{M(a,c_{2},x)}\right)$ matches
that of $c_{2}-c_{1}$, which is the desired result.

∎

##  4 The Poisson Prior

We specialise our investigation to the case where $N$ follows a Poisson prior
distribution $\boldsymbol{\pi}\coloneqq(\pi_{1},\pi_{2},\ldots)$ with
intensity $\lambda>0$, where

$\pi_{n}=\frac{\lambda^{n}}{n!}e^{-\lambda}~{}~{}~{}~{}n\geq 0.$

This formulation recovers the original scenario where the underlying pacing
process $(N_{t},~{}t\in[0,1])$ is Poisson. By virtue of the stationarity of
increments of the Poisson process, the posterior of $N-N_{t}$ given $N_{t}=k$
is again Poisson with a rescaled intensity

$x=(1-t)\lambda.$ (13)

That is,

$\displaystyle\mathbb{P}(N=k+j\,|\,N_{t}=k)$
$\displaystyle=\frac{x^{j}}{j!}e^{-x}.$

Based on this posterior distribution, the probability generating function of
the number of successes following state $(t,k)$ becomes

$\displaystyle z\mapsto e^{-x}\sum_{j=0}^{\infty}\frac{(k+\theta
z)_{j}}{(k+\theta)_{j}}\,\frac{x^{j}}{j!}$ $\displaystyle=e^{-x}M(k+\theta
z;k+\theta;x)$ $\displaystyle=M(\theta-\theta z;k+\theta;-x).$

where $M(a;c;x)$ is Kummer’s hypergeometric function defined in (9). The last
equality is a consequence of Kummer’s transformation formula, where

$\displaystyle M(a,c;x)$ $\displaystyle=e^{x}M(c-a,c;-x).$

The derivative of the generating function is given by

$\displaystyle z\mapsto\theta e^{-x}D_{a}M(k+\theta z,\theta+k,x).$

Explicit expressions for (7) and (8), which represent the probability of zero
successes and the probability of exactly one success after state $(t,k)$, are
as follows

$\displaystyle{\cal S}_{0}(1-x/\lambda,k)$
$\displaystyle=e^{-x}M(k;\theta+k;x),$ $\displaystyle{\cal
S}_{1}(1-x/\lambda,k)$ $\displaystyle=\theta e^{-x}D_{a}M(k;\theta+k;x).$

As ${\cal S}_{0}$ and ${\cal S}_{1}$ are power series in $x$, the cutoffs,
defined by Lemma 1, can be recast in terms of a sole sequence of critical
roots $(\gamma_{k})$ of equation ${\cal S}_{0}(1-x/\lambda,k)-{\cal
S}_{1}(1-x/\lambda,k)=0$, expressed through the equation

$\theta D_{a}M(k;\theta+k;x)-M(k;\theta+k;x)=0.$ (14)

In the special case where $\theta=1$, the equation reduces to that of Cowan
and Zabczyk (2). Observe that the roots $(\gamma_{k})$ do not depend on the
intensity $\lambda$, and are related to the cutoffs through the following
identity

$a_{k}=\left(1-\frac{\gamma_{k}}{\lambda}\right)_{+}.$ (15)

The optimality of the myopic strategy for all finite $\lambda>0$ is equivalent
to the condition $\gamma_{k}\uparrow$. That is, the roots must be
nondecreasing with $k$. Notably, Cowan and Zabczyk posed and ingeniously
solved this problem in the classical success profile setting ($\theta=1$). The
argument for uniqueness relies on showing that each derivative of
$h_{k}(x)\coloneqq{\cal S}_{0}(1-x/\lambda,k)-{\cal S}_{1}(1-x/\lambda,k)$ has
a unique root. The uniqueness is achieved by exploiting the continuity of this
function and its derivatives. They approach the problem inductively by
starting at higher derivatives and continuing iteratively to lower ones until
$h_{k}(x)$ is reached. They demonstrated the monotonicity of roots based on a
relation between $h_{k+1}(x)$ and the derivative of an expression involving
${\cal S}_{1}(1-x/\lambda,k)-{\cal S}_{1}(1-x/\lambda,k+1)$. In contrast, our
analysis of Cowan and Zabczyk’s problem reveals a distinct structure
characterised by a prominent connection to Kummer’s hypergeometric function.
The following theorem strengthens their original result by utilising a more
general success profile and provides a more straightforward proof that
capitalises on the properties of Kummer’s hypergeometric function.

######  Theorem 5.

The roots $\gamma_{k}$ are increasing. Therefore, the stopping rule $\tau^{*}$
which calls for stopping at state $(t,k)^{\circ}$ satisfying

$(1-t)\lambda\leq\gamma_{k},$ (16)

is optimal.

###### Proof.

First, we need establish that the roots $\gamma_{k}$ of equation (14) are
increasing and hence $\gamma_{k+1}>\gamma_{k}$ for all $k\geq 1$. It is
sufficient to show that

$D_{a}\log(M(k,\theta+k,x))<D_{a}\log(M(k,\theta+k+1,x)),~{}~{}~{}x\in(0,1).$

But this holds by the first identity of Lemma 4. Consequently, by assertion
(iii) of Lemma 1, it is optimal to stop at time $t\geq a_{k}$, where the
cutoff $a_{k}$ is given by (15). Using the definition of the cutoff, we obtain
$t\geq 1-\gamma_{k}/\lambda$. Rearranging this inequality yields the desired
result. ∎

######  Remark 6.

In the setting where $\lambda$ is random with a Gamma prior distribution,
$(N_{t},~{}t\in[0,1])$ becomes a negative binomial process (mixed Poisson).
This scenario has been addressed under different guises in [14, 21, 19, 15].

One can extend Theorem 5 to the inhomogeneous case in a straightforward manner
through a time-change argument, reducing the problem to its homogeneous
counterpart. Nonetheless, the next section tackles the inhomogeneous case and
presents an example that illustrates the reduction of the last-success problem
in continuous time to the problem of stopping at the last arrival of a Poisson
process.

##  5 The Inhomogeneous Case

We now turn to the case where the counting process $(N_{t})$ is an
inhomogeneous Poisson process with known time-dependent intensity
$\lambda(t)$, where the function

$\Lambda(s)=\int_{0}^{s}\lambda(u){\mathrm{d}}{u},$ (17)

is continuous and $s\in[0,1]$.

In the best-choice case, Theorem 3 in [5] established the optimal strategy for
selecting the best apartment, where arrivals are governed by $(N_{t})$. The
extension of this result to the last-success setting is immediate.

######  Theorem 7.

Consider the last success problem with success profile (3), where trials
arrive according to an inhomogeneous Poisson process $(N_{t},~{}t\in[0,1])$
with mean arrivals given by (17). The optimal stopping strategy for selecting
the last success is to stop at state $(t^{*},k)^{\circ}$ such that

$\Lambda(1)-\Lambda(t^{*})\leq\gamma_{k},$

where $\gamma_{k}$ is the root of equation (14).

###### Proof.

Given $N_{1}=n$, the trials arrive at independent epochs $U_{1},U_{2},\cdots$
in [0,1]. These arrival times have a common distribution function $F$, where

$F(s)=\frac{\Lambda(s)}{\Lambda(1)}.$ (18)

The points $F(U_{1}),F(U_{2}),\ldots$ are renewal times of a homogeneous
Poisson process in $[0,1]$ with known intensity $\Lambda(1)$. Therefore, by
Theorem 5, the myopic strategy $\tau^{*}$ is optimal and the optimal rule is
to stop at the success state $(t^{*},k)^{\circ}$ satisfying

$\left[1-F(t^{*})\right]\Lambda(1)\leq\gamma_{k},$ (19)

which is a straightforward generalisation of (16). Plugging (18) into (19)
completes the proof. ∎

###  5.1 The Case of the Poisson Process of Successes

Let $p(t)$ denote the success probability of a trial occurring at time $t$. A
success at time $t$ is independent of the arrival process $(N_{t})$ and
previous outcomes. Our objective is to maximise the probability of stopping at
the last arrival time that coincides with the occurrence of a success.

Fix a positive integer $m$ and let
$\delta_{m}\coloneqq\\{0=t_{0}<t_{1}<\cdots<t_{m}=1\\}$ be an partition of
$[0,1]$. Denote the length of the $k$th subinterval $[t_{k-1},t_{k}]$ by
$\Delta t_{k}$.

Let $p_{k}$ be the probability of a success occurring in the interval
$(t_{k-1},t_{k}]$. From the independence of successes and the properties of
the Poisson process it follows that

$p_{k}=p(t_{k})\lambda(t_{k})\Delta t_{k}+o(\Delta t_{k}).$

As $\lVert\delta_{m}\rVert\coloneqq\max\limits_{1\leq i\leq m}\Delta t_{i}$
tends to 0, the well defined function

$s(t)\coloneqq\lim_{\Delta t\to 0}\frac{p(t)\lambda(t)\Delta t+o(\Delta
t)}{\Delta t}=p(t)\lambda(t).$ (20)

is referred to as the limiting success intensity by Bruss [6]. This function
represents a random record process of points $\lambda(t)$ at which a record
occurs with probability $p(t)$. This thinning of $(N_{t})$ preserves the
Poisson process property, where each point is independently retained with
probability $p(t)$. We denote this new thinned Poisson process of successes by
$(P_{t},~{}t\in[0,1])$. Each arrival generated by $(P_{t})$, whose intensity
is $s(t)$, corresponds to a success event.

Let

$\begin{dcases}m(t)\coloneqq\mathbb{E}[P_{t}]=\int_{0}^{t}s(u){\mathrm{d}}{u},\text{
and }\\\ M(t_{0},t_{1})\coloneqq
m(t_{1})-m(t_{0})=\int_{t_{0}}^{t_{1}}s(u){\mathrm{d}}{u},\end{dcases}$

denote respectively the expected number of arrivals of $(P_{t})$ up to time
$t$ and the expected number of arrivals in the time interval $[t_{0},t_{1}]$,
where $0\leq t_{0}<t_{1}<1$.

In the context of the last success problem in continuous time, the optimal
stopping rule $\tau^{*}$ translates to stopping at the last arrival time of
the inhomogeneous process $(P_{t})$. This case is much simpler than Cowan and
Zabczyk’s problem, given that all the arrivals are successes. Consequently, it
is optimal to stop at the next arrival of $(P_{t})$, if any, which occurs
after time $t^{*}$, where

$t^{*}\coloneqq\sup\bigg{\\{}0,~{}\sup\big{\\{}t\in[0,1]:~{}M(t,1)\geq
1\big{\\}}\bigg{\\}},\text{ and }\sup\\{\varnothing\\}=-\infty.$

The threshold $t^{*}$ corresponds to the last time the expected number of
future arrivals of $(P_{t})$ is at least 1. The optimal stopping rule
$\tau^{*}$ can be readily extended to the problem of stopping at the last
$\ell$th success [7, 12]. This generalisation follows intuitively where
stopping is optimal after time $t^{\star}$ given by

$t^{\star}\coloneqq\sup\bigg{\\{}0,~{}\sup\big{\\{}t\in[0,1]:~{}M(t,1)\geq\ell\big{\\}}\bigg{\\}}.$
(21)

The following example illustrates a problem involving a continuous-time
Karamata-Stirling profile combined with an inhomogeneous arrival process.

#### Example.

Suppose the mutation parameter of the Karamata-Stirling profile exhibits a
linear relationship with the number of trials $n$, such that a finite mutation
rate $\kappa\in(0,\infty)$ exists. In this case

$\kappa\coloneqq\lim_{n\to\infty}\frac{\theta}{n}.$ (22)

To introduce a continuous-time adaptation of the Karamata-Stirling profile, we
divide both the numerator and denominator of (3) by $n$ and let
$t={(k-1)}/{n}$, where $k=1,\ldots,n,$ be the proportion of trials elapsed. As
$n\to\infty$, we obtain an asymptotic Karamata-Stirling profile, denoted by
$p(t)$, where

$\displaystyle p(t)$
$\displaystyle\coloneqq\lim_{n\to\infty}\frac{\theta/n}{\theta/n+(k-1)/n}$
$\displaystyle=\frac{\kappa}{\kappa+t},~{}~{}t\in[0,1].$

With this continuous-time Karamata-Stirling profile established, we shift our
focus to analysing the arrival process governed by the following intensity
function

$\lambda(t)=(t+\kappa)^{\alpha},$

where $\alpha\in\mathbb{R}$ is a fixed number and $\kappa$ is the mutation
rate defined earlier in (22).

The success intensity (20) becomes

$s(t)=\kappa(t+\kappa)^{-1+\alpha}.$

When $\alpha=0$, the original counting process ($N_{t}$) is homogeneous and
$(P_{t})$, the Poisson process of successes, is inhomogeneous as $s(t)=p(t)$.
The expected number of arrivals (successes) between $0\leq t_{0}<t_{1}$ and
$t_{1}<1$ is given by

$M(t_{0},t_{1})=\kappa\log\left(\frac{t_{1}+\kappa}{t_{0}+\kappa}\right).$
(23)

Using (21), the optimal rule for selecting the last $\ell$th success, where
$\ell\geq 1$ is to stop at the first arrival occurring after time $t^{\star}$,
where

$t^{\star}=\sup\bigg{\\{}0,~{}\sup\big{\\{}t\in[0,1]:~{}t\leq(\kappa+1)e^{-^{\ell/\kappa}}-\kappa\big{\\}}\bigg{\\}}.$

Next, recall that $P_{1}-P_{t}$ has a Poisson distribution with intensity
$M(t,1)$, therefore use (23) to express the probability of $\ell$ arrivals as

$\mathbb{P}[P_{1}-P_{t}=\ell]=\frac{1}{\ell!}{\left(-\kappa\log\left(\frac{t+\kappa}{1+\kappa}\right)\right)^{\ell}}\left(\frac{t+\kappa}{1+\kappa}\right)^{\kappa}.$
(24)

Setting $t=(\kappa+1)e^{-^{\ell/\kappa}}-\kappa$ in (24), we obtain the
asymptotic optimal winning probability $e^{-\ell}{\ell^{\ell}}/{\ell!}$ for
stopping at the last $\ell$th success [7, 12]. This result translates to the
ubiquitous winning probability $1/e$ in the last success setting ($\ell=1$).

Now suppose that $\alpha\neq 0$. An easy calculation gives the expected number
of arrivals of $(P_{t})$ between times $t_{0}\in[0,t_{1})$ and $t_{1}\in(0,1)$
as

$\displaystyle
M(t_{0},t_{1})=\frac{\kappa}{\alpha}\left\\{(t_{1}+\kappa)^{\alpha}-(t_{0}+\kappa)^{\alpha}\right\\}.$

Consequently, the optimal threshold becomes, in this case

$t^{\star}\coloneqq\sup\bigg{\\{}0,~{}\sup\big{\\{}t\in[0,1]:~{}t\leq\left((1+\kappa)^{\alpha}-\frac{\alpha\ell}{\kappa}\right)^{\displaystyle\frac{1}{\alpha}}-\kappa\big{\\}}\bigg{\\}},$

and the asymptotic optimal winning probability is once again
$e^{-\ell}{\ell^{\ell}}/{\ell!}.$

In the next section, we revert to the homogenous Poisson setting with a
discrete Karamata-Stirling profile to assess the asymptotic properties of the
roots obtained in Section 4.

##  6 Asymptotics and Bounds

Unlike other priors, such as the negative binomial addressed in [15], the
roots $\gamma_{k}$ do not converge. There is no Poisson process with infinite
prior, which ensures that only finitely many nonzero cutoffs exist for each
$\lambda\in(0,\infty)$. [10, 9, 2, 5] observed that the analogues of
$\gamma_{k}$’s do not accumulate, rather grow about linearly with $k$.

In the best-choice setting, where $\theta=1$, [10] showed that $\gamma_{k}\sim
k$ for large $k$ and [9] derived the bounds

$(e-1)(k-1)\leq\gamma_{k}\leq 4e\left[(e-1)k+1\right],$

and asymptotics

$\lim_{k\to\infty}\frac{\gamma_{k}}{k}=(e-1).$

In the next theorem, we not only extend these results to the last success
setting, where $\theta>0$, but also improve the roots’ upper bound.

######  Theorem 8.

For $k\geq 1$, the roots $(\gamma_{k})$ of the fundamental equation (14)
satisfy

$(e^{1/\theta}-1)(k-1)<\gamma_{k}<(e^{1/\theta}-1)k+1,$

and

$\lim_{k\to\infty}\frac{\gamma_{k}}{k}=(e^{1/\theta}-1).$

Before proving this theorem, we need an auxiliary result to assess the shape
and properties of the following functions

$\begin{dcases}\varphi_{0}(n,k)&\coloneqq\frac{(k)_{n}}{(k+\theta)_{n}},~{}~{}~{}\varphi_{0}(0)=1,\\\
\varphi(n,k)&\coloneqq\psi(n+k)-\psi(k),~{}~{}\psi(0)=0.\end{dcases}$

where $\theta>0$, $k>0$ are fixed and $\psi$ is the log-derivative of the
Gamma function.

######  Proposition 9.

For a fixed integer $k\geq 1$ and a fixed positive real number $\theta$, it
holds that

  * (i)

$\varphi_{0}(\cdot,k)$ is log-convex and decreasing,

  * (ii)

$\varphi(\cdot,k)$ is concave and increasing.

###### Proof.

Fix $k\geq 1$ and recall that if a sequence
$\left\\{\varphi_{0}(n,k)\right\\}_{n\geq 1}$ is log-convex, then it is
convex. For the first part of assertion (i), check that
$\varphi_{0}^{2}(n,k)\leq\varphi_{0}(n+1,k)\varphi_{0}(n-1,k)$ holds. For
fixed $\theta>0$, it is easy to verify that

$\displaystyle\frac{\varphi_{0}(n,k)}{\varphi_{0}(n+1,k)}-\frac{\varphi_{0}(n-1,k)}{\varphi_{0}(n,k)}$
$\displaystyle=\frac{(k)_{n}/(k+\theta)_{n}}{(k)_{n+1}/(k+\theta)_{n+1}}-\frac{(k)_{n-1}/(k+\theta)_{n-1}}{(k)_{n}/(k+\theta)_{n}}$
$\displaystyle=\frac{\theta}{k+n}-\frac{\theta}{k+n-1}<0.$

For the monotonicity of $\varphi_{0}$ in the first parameter, note that

$\displaystyle\frac{\varphi_{0}(n,k)}{\varphi_{0}(n+1,k)}$
$\displaystyle=\frac{(k)_{n}/(k+\theta)_{n}}{(k)_{n+1}/(k+\theta)_{n+1}}$
$\displaystyle=\frac{k+\theta+n}{k+n}>1.$

Moving to assertion (ii). For the first part, it is sufficient to check that
$\psi(\cdot)$ is concave. A straightforward calculation yields

$\displaystyle 2\psi(n)-\psi(n-1)-\psi(n+1)$
$\displaystyle=\frac{1}{n-1}-\frac{1}{n}$ $\displaystyle=\frac{1}{n(n-1)}>0.$

The monotonicity of $\varphi$ in the first parameter follows from observing
that $\displaystyle\psi(n+1)-\psi(n)=\frac{1}{n}>1.$ This completes the proof.
∎

###### Proof of Theorem 8.

Recall the derivative of the Pochhammer symbol of a positive real $x$, which
is given by

$(x)_{n}=(x)_{n}\left\\{\psi(x+n)-\psi(x)\right\\}.$

Using this definition, the derivative in the first parameter of
$M(k,k+\theta,x)$ becomes

$\displaystyle D_{a}M(k,k+\theta;x)$ $\displaystyle=\sum_{n\geq
0}\frac{(k)_{n}}{(k+\theta)_{n}}\frac{x^{n}}{n!}\left\\{\psi(k+n)-\psi(k)\right\\}$
$\displaystyle=\sum_{n\geq 0}\frac{x^{n}}{n!}\varphi_{0}(n)\varphi(n).$

We may rewrite equation (14) as $h_{k}(x)=0$, where

$\displaystyle h_{k}(x)$ $\displaystyle={\cal S}_{1}(1-x/\lambda,k)-{\cal
S}_{0}(1-x/\lambda,k)$ $\displaystyle=\sum_{n\geq
0}\frac{x^{n}}{n!}e^{-x}\varphi_{0}(n,k)(\theta\varphi(n,k)-1)$ (25)
$\displaystyle=\mathbb{E}[\varphi_{0}(\xi_{x},k)\left\\{\theta\varphi(\xi_{x}-1,k)\right\\}].$

where $\xi_{x}$ is a Poisson random variable with mean $x$. By the first
assertion of Proposition 9, $\varphi_{0}(\cdot,k)$ is decreasing. Hence, use
(25) to observe that

$\displaystyle h_{k}(x)$ $\displaystyle=\sum_{n\geq
0}\frac{x^{n}}{n!}e^{-x}\varphi_{0}(n,k)(\theta\varphi(n,k)-1)$
$\displaystyle\leq\varphi_{0}(0)\sum_{n\geq
0}\frac{x^{n}}{n!}e^{-x}(\theta\varphi(n,k)-1)$
$\displaystyle=\theta\mathbb{E}[\varphi(\xi_{x},k)]-1.$

But $\varphi(\cdot,k)$ is concave by assertion (ii) of the same proposition.
Consequently, apply Jensen’s inequality to obtain

$\displaystyle h_{k}(x)$
$\displaystyle\leq\theta\varphi(\mathbb{E}[\xi_{x}],k)-1$
$\displaystyle=\theta\varphi(x,k)-1.$ (26)

We now proceed to establish bounds on this critical root of $h_{k}(x)=0$. Let
this unique root be denoted $\gamma_{k}>0$. It follows by (26) that

$\displaystyle 0$ $\displaystyle=h_{k}(\gamma_{k})$
$\displaystyle\leq\theta\varphi(\gamma_{k},k)-1.$

Therefore,

$\displaystyle\varphi(\gamma_{k},k)\geq\frac{1}{\theta}.$ (27)

Next, let $m$ be a positive integer such that

$\displaystyle\varphi(m,k)\geq\frac{1}{\theta}>\varphi(m-1,k).$ (28)

By the Archimedean property of the reals and the monotonicity of $\varphi$, we
can infer that

$m-1<\gamma_{k}\leq m.$

It is easy to see by using (27) and (28) together with the monotonicity of
$\varphi$ that

$\displaystyle\psi(k+m-1)-\psi(k)$
$\displaystyle<\frac{1}{\theta}\leq\psi(\gamma_{k}+k)-\psi(k)\leq\psi(k+m)-\psi(k).$
(29)

Moreover, by summing the following inequalities

$\log(j+1)-\log(j)=\int_{j}^{j+1}\frac{{\mathrm{d}}{x}}{x}<\frac{1}{j}<\int_{j-1}^{j}\frac{{\mathrm{d}}{x}}{x}=\log(j)-\log(j-1),$

from $j=k$ to $j=k+m-1$, we obtain the classical inequality

$\displaystyle\log\left(\frac{k+m}{k}\right)<\psi(k+m)-\psi(k)<\log\left(\frac{k+m-1}{k-1}\right).$
(30)

Finally, combine (29) and (30) together with the monotonicity of the log
function to form the inequality

$\displaystyle\log\left(\frac{k+\gamma_{k}-1}{k}\right)<\frac{1}{\theta}<\log\left(\frac{k+\gamma_{k}-1}{k-1}\right).$

This inequality ultimately yields the desired bounds

$\displaystyle(e^{1/\theta}-1)(k-1)<\gamma_{k}<(e^{1/\theta}-1)k+1.$ (31)

For the second assertion of the Theorem, dividing each side of (31) by $k$ and
sending $k\to\infty$ completes the proof. ∎

## Appendix

###### Proof of part (ii) of Theorem 4.

The logarithmic derivative in parameter $c$, where $a_{1},a_{2}$ are constants
satisfying $c>a_{1}>0$ and $c>a_{2}>0$ respectively is given by

$\displaystyle
D_{c}\displaystyle\log\left(\frac{M(a_{1},c,x)}{M(a_{1},c,x)}\right)$
$\displaystyle=D_{c}\log\frac{\Gamma(c-a_{2})}{\Gamma(c-a_{1})}+\log
D_{c}\frac{\phi(a,c_{1},x)}{\phi(a,c_{2},x)}.$ (32)

By the elementary Lemma 2, it is sufficient to show that the signs of the two
derivatives of quotients match. First, the sign of the derivative of a
quotient of two Gamma functions coincides with $a_{1}-a_{2}$ based on Lemma 3.

Next, we consider the second logarithmic derivative involving a quotient of
$\phi$’s. Use Lemma 2 once more to switch back to the derivative of the
quotient $\displaystyle{\phi(a_{1},c,x)}/{\phi(a_{2},c,x)}$. Given that the
denominator in the expression of the derivative of a quotient is positive, we
restrict our investigation to the numerator, which we denote $\phi_{c}$.

In much the same way as in the proof of part (i), consider the Eulerian
integral representation (10) to express $\phi_{c}$ as a double integral, where
$c>a_{1}>0$ and $c>a_{2}>0$ respectively

$\displaystyle\phi_{c}\coloneqq-\int_{0}^{1}e^{xu}(1-u)^{c-2}\left(\frac{u}{1-u}\right)^{a_{1}-1}\log(1-u){\mathrm{d}}{u}\int_{0}^{1}e^{xv}(1-v)^{c-2}\left(\frac{v}{1-v}\right)^{a_{2}-1}{\mathrm{d}}{v}$
$\displaystyle\qquad+\int_{0}^{1}e^{xu}(1-u)^{c-2}\left(\frac{u}{1-u}\right)^{a_{1}-1}{\mathrm{d}}{u}\int_{0}^{1}e^{xv}(1-v)^{c-2}\left(\frac{v}{1-v}\right)^{a_{2}-1}\log(1-v){\mathrm{d}}{v}$
$\displaystyle=\iint_{[0,1]\times[0,1]}e^{x(u+v)}[(1-u)(1-v)]^{c-2}\left(\frac{uv}{(1-u)(1-v)}\right)^{a_{1}-1}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log(1-v){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle\qquad-\iint_{[0,1]\times[0,1]}e^{x(u+v)}[(1-u)(1-v)]^{c-2}\left(\frac{uv}{(1-u)(1-v)}\right)^{a_{1}-1}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log(1-u){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{[0,1]\times[0,1]}\left\\{e^{x(u+v)}[(1-u)(1-v)]^{c-2}\left(\frac{uv}{(1-u)(1-v)}\right)^{a_{1}-1}\right\\}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log\left(\frac{1-v}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log\left(\frac{1-v}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<u<v<1}\left\\{\cdots\right\\}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log\left(\frac{1-v}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}\log\left(\frac{1-v}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}+\iint_{0<v<u<1}\left\\{\cdots\right\\}\left(\frac{u}{1-u}\right)^{a_{2}-a_{1}}\log\left(\frac{1-u}{1-v}\right){\mathrm{d}}{u}{\mathrm{d}}{v}$
$\displaystyle=\iint_{0<v<u<1}\left\\{\cdots\right\\}\left\\{\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}-\left(\frac{u}{1-u}\right)^{a_{2}-a_{1}}\right\\}\log\left(\frac{1-v}{1-u}\right){\mathrm{d}}{u}{\mathrm{d}}{v}.$

Mirroring the case of the derivative in parameter $a$, the term
$\displaystyle\log\left(\frac{1-v}{1-u}\right)$ is positive in the domain of
integration, where $u>v$. It follows that the sign of the last integrand
coincides with the sign of

$\displaystyle\left(\frac{v}{1-v}\right)^{a_{2}-a_{1}}-\left(\frac{u}{1-u}\right)^{a_{2}-a_{1}},$

whose sign precisely matches that of $c_{1}-c_{2}$. By the second part of
Lemma 2, this concludes the proof as the sign of both terms in the right-hand
side of (32) matches $c_{1}-c_{2}$. ∎

## References

  * [1] Ano, K. and Ando, M. (2000). A note on Bruss’ stopping problem with random availability. In IMS Lecture Notes - Monograph Series, 35, 71–82.
  * [2] Berezovsky, B.A. and Gnedin, A. V. The best choice problem (in Russian). Nauka, 1984.
  * [3] Browne, S. and Bunge, J. (1995). Random record processes and state dependent thinning. Stochastic Process. Appl. 55 131–142.
  * [4] Bruss, F.T. (1984) A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options. Ann. Probab. 12, 882–889.
  * [5] Bruss, F. T. (1987) On an optimal selection problem of Cowan and Zabczyk. J. Appl. Probab. 24, 918–928.
  * [6] Bruss, F. T. (2000) Sum the odds to one and stop. Ann. Probab. 28, 1384–1391.
  * [7] Bruss, F. T. and Paindaveine, D. (2000). Selecting a Sequence of Last Successes in Independent Trials. J. Appl. Probab. 37, 389–399.
  * [8] Chow, Y.S., Robbins, H. and Siegmund, D. Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin Co., 1971.
  * [9] Ciesielski, Z. and Zabczyk, J. (1979). A note on a selection problem. Banach Center Publ. 5 47–51.
  * [10] Cowan, R. and Zabczyk, J. (1978) An optimal selection problem associated with the Poisson process. Theory Probab. Appl. 23, 584–592.
  * [11] Crane, H. (2016) The ubiquitous Ewens sampling formula. Statist. Sci. 31, 1–19.
  * [12] Derbazi, Z. (2024). Sum the Probabilities to $m$ and Stop. arXiv:2406.07283.
  * [13] Ferguson, T.S. Optimal stopping and applications,
https://www.math.ucla.edu/ tom/Stopping/Contents.html, ebook, UCLA, 2006.

  * [14] Gaver, D. P. (1976) Random record models. J. Appl. Probab. 13, 538–547.
  * [15] Gnedin, A. and Derbazi, Z. (2022), The Last-Success Problem with Random Observation Times, arXiv:2207.05156
  * [16] Gnedin, A. and Derbazi, Z. (2022). Trapping the ultimate success, Mathematics 10, 158.
  * [17] Hofmann, G. A Family of General Record Models, Doctoral dissertation, The Ohio State University, 1997
  * [18] Kallenberg, O. Random Measures: Theory and Applications. New York, Springer, 2017.
  * [19] Kurushima, A. and Ano, K. (2003). A Poisson arrival selection problem for Gamma prior intensity with natural number parameter. Sci. Math. Japon. 57, 217–231.
  * [20] Nevzorov, V. Records: Mathematical Theory (Lecture 25), Translation of Mathematical Monographs 194, AMS, 2001.
  * [21] Orsingher, E. and Battaglia, F. (1979). Record values in Poisson and randomized Poisson models, Publ. Inst. Stat. Univ. Paris 24, fasc. 3-4, 69–78.
  * [22] Schwalko, A. and Szajowski, K. (2003). On Bruss’ stopping problem with general gain function. Game Theory Appl. 9 , 161–171.
  * [23] Szajowski, K. (2007). A game version of the Cowan-Zabczyk-Bruss’ problem. Statist. Probab. Lett. 77 1683–1689.
  * [24] Szajowski, K. J. (2015). An apartment problem. Math. Appl. 42, 193–206.
  * [25] Yasuda, M. (1984). Asymptotic results for the best-choice problem with a random number of objects. J. Appl. Probab. 21, 521–536.


# Partial skew Dyck paths—a kernel method approach

Helmut Prodinger  Helmut Prodinger, Mathematics Department, Stellenbosch
University, 7602 Stellenbosch, South Africa<EMAIL_ADDRESS>
###### Abstract.

Skew Dyck are a variation of Dyck paths, where additionally to steps $(1,1)$
and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided that the
path does not intersect itself. Replacing the south-west step by a red south-
east step, we end up with decorated Dyck paths. We analyze partial versions of
them where the path ends on a fixed level $j$, not necessarily at level 0. We
exclusively use generating functions and derive them with the celebrated
kernel method.

In the second part of the paper, a dual version is studied, where the paths
are read from right to left. In this way, we have two types of up-steps, not
two types of down-steps, as before.

A last section deals with the variation that the negative territory (below the
$x$-axis) is also allowed. Surprisingly, this is more involved in terms of
computations.

###### Key words and phrases:

Skew Dyck paths, decorated Dyck paths, generating functions, kernel method

##  1\. Introduction

Skew Dyck are a variation of Dyck paths, where additionally to steps $(1,1)$
and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided that the
path does not intersect itself. Otherwise, like for Dyck path, it must never
go below the $x$-axis and end eventually (after $2n$ steps) on the $x$-axis.
Here are a few references: [2, 6, 1, 7]. The enumerating sequence is

$1,1,3,10,36,137,543,2219,9285,39587,171369,751236,3328218,14878455,\dots,$

which is A002212 in [9].

Skew Dyck appeared very briefly in our recent paper [7]; here we want to give
a more thorough analysis of them, using generating functions and the kernel
method. Here is a list of the 10 skew paths consisting of 6 steps:

Figure 1. All 10 skew Dyck paths of length 6 (consisting of 6 steps).

We prefer to work with the equivalent model (resembling more traditional Dyck
paths) where we replace each step $(-1,-1)$ by $(1,-1)$ but label it red. Here
is the list of the 10 paths again (Figure 2):

Figure 2. The 10 paths redrawn, with red south-east edges instead of south-
west edges.

The rules to generate such decorated Dyck paths are: each edge $(1,-1)$ may be
black or red, but  and  are forbidden.

Our interest is in particular in _partial_ decorated Dyck paths, ending at
level $j$, for fixed $j\geq 0$; the instance $j=0$ is the classical case.

The analysis of partial skew Dyck paths was recently started in [1] (using the
notion ‘prefix of a skew Dyck path’) using Riordan arrays instead of our
kernel method. The latter gives us _bivariate_ generating functions, from
which it is easier to draw conclusions. Two variables, $z$ and $u$, are used,
where $z$ marks the length of the path and $j$ marks the end-level. We briefly
mention that one can, using a third variable $w$, also count the number of red
edges.

Again, once all generating functions are explicitly known, many corollories
can be derived in a standard fashion. We only do this in a few instances. But
we would like to emphasize that the substitution

$x=\frac{v}{1+3v+v^{2}},$

which was used in [5, 7] allows to write _explicit enumerations_ , using the
notion of a (weighted) trinomial coefficient:

$\binom{n;1,3,1}{k}:=[t^{k}](1+3t+t^{2})^{n}.$

The second part of the paper deals with a dual version, where the paths are
read from right to left.

##  2\. Generating functions and the kernel method

We catch the essence of a decorated Dyck path using a state-diagram:

Figure 3. Three layers of states according to the type of steps leading to
them (up, down-black, down-red).

It has three types of states, with $j$ ranging from 0 to infinity; in the
drawing, only $j=0..8$ is shown. The first layer of states refers to an up-
step leading to a state, the second layer refers to a black down-step leading
to a state and the third layer refers to a red down-step leading to a state.
We will work out generating functions describing all paths leading to a
particular state. We will use the notations $f_{j},g_{j},h_{j}$ for the three
respective layers, from top to bottom. Note that the syntactic rules of
forbidden patterns  and  can be clearly seen from the picture. The functions
depend on the variable $z$ (marking the number of steps), but mostly we just
write $f_{j}$ instead of $f_{j}(z)$, etc.

The following recursions can be read off immediately from the diagram:

$\displaystyle f_{0}=1,\quad f_{i+1}=zf_{i}+zg_{i},\quad i\geq 0,$
$\displaystyle g_{i}=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\geq 0,$ $\displaystyle
h_{i}=zh_{i+1}+zg_{i+1},\quad i\geq 0.$

And now it is time to introduce the promised _bivariate_ generating functions:

$F(z,u)=\sum_{i\geq 0}f_{i}(z)u^{i},\quad G(z,u)=\sum_{i\geq
0}g_{i}(z)u^{i},\quad H(z,u)=\sum_{i\geq 0}h_{i}(z)u^{i}.$

Again, often we just write $F(u)$ instead of $F(z,u)$ and treat $z$ as a
‘silent’ variable. Summing the recursions leads to

$\displaystyle\sum_{i\geq 0}u^{i}f_{i+1}$ $\displaystyle=\sum_{i\geq
0}u^{i}zf_{i}+\sum_{i\geq 0}u^{i}zg_{i},$ $\displaystyle\sum_{i\geq
0}u^{i}g_{i}$ $\displaystyle=\sum_{i\geq 0}u^{i}zf_{i+1}+\sum_{i\geq
0}u^{i}zg_{i+1}+\sum_{i\geq 0}u^{i}zh_{i+1},$ $\displaystyle\sum_{i\geq
0}u^{i}h_{i}$ $\displaystyle=\sum_{i\geq 0}u^{i}zh_{i+1}+\sum_{i\geq
0}u^{i}zg_{i+1}.$

This can be rewritten as

$\displaystyle\frac{1}{u}(F(u)-1)$ $\displaystyle=zF(u)+zG(u),$ $\displaystyle
G(u)$
$\displaystyle=\frac{z}{u}(F(u)-1)+\frac{z}{u}(G(u)-G(0))+\frac{z}{u}(H(u)-H(0)),$
$\displaystyle H(u)$
$\displaystyle=\frac{z}{u}(G(u)-G(0))+\frac{z}{u}(H(u)-H(0)).$

This is a typical application of the kernel method. For a gentle example-
driven introduction to the kernel method, see [8]. First,

$\displaystyle F(u)$
$\displaystyle=\frac{z^{2}uG(0)+z^{2}uH(0)+z^{2}u-u-z^{3}+2z}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u},$
$\displaystyle G(u)$
$\displaystyle=\frac{z(H(0)-uzH(0)+z^{2}+G(0)-zuG(0)-zu)}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u},$
$\displaystyle H(u)$
$\displaystyle=\frac{z(-uzH(0)-z^{2}-zuG(0)+G(0)-z^{2}H(0)+H(0)-z^{2}G(0))}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}.$

The denominator factors as $z(u-r_{1})(u-r_{2})$, with

$r_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z},\quad
r_{2}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

Note that $r_{1}r_{2}=2-z^{2}$. Since the factor $u-r_{2}$ in the denominator
is “bad,” it must also cancel in the numerators. From this we conclude as a
first step

$G(0)=\frac{1-2z^{2}H(0)-3z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z^{2}},$

and by further simplification

$H(0)=\frac{1-4z^{2}+z^{4}+(z^{2}-1)\sqrt{1-6z^{2}+5z^{4}}}{2-z^{2}}.$

Thus (with $W=\sqrt{1-6z^{2}+5z^{4}}=\sqrt{(1-z^{2})(1-5z^{2})}$ )

$\displaystyle F(u)$
$\displaystyle=\frac{-1-z^{2}-W}{2z(u-r_{1})}=\frac{1+z^{2}+W}{2zr_{1}(1-u/r_{1})},$
$\displaystyle G(u)$
$\displaystyle=\frac{-1+z^{2}+W}{2z(u-r_{1})}=\frac{1-z^{2}-W}{2zr_{1}(1-u/r_{1})},$
$\displaystyle H(u)$
$\displaystyle=\frac{-1+3z^{2}+W}{2z(u-r_{1})}=\frac{1-3z^{2}-W}{2zr_{1}(1-u/r_{1})}.$

The total generating function is

$S(u)=F(u)+G(u)+H(u)=\frac{3-3z^{2}-W}{2zr_{1}(1-u/r_{1})}.$

The coefficient of $u^{j}z^{n}$ in $S(u)$ counts the partial paths of length
$n$, ending at level $j$. We will write $s_{j}=[u^{j}]S(u)$. Furthermore

$\displaystyle f_{j}=[u^{j}]F(u)$
$\displaystyle=[u^{j}]\frac{1+z^{2}+W}{2zr_{1}(1-u/r_{1})},$ $\displaystyle
g_{j}=[u^{j}]G(u)$
$\displaystyle=[u^{j}]\frac{1-z^{2}-W}{2zr_{1}(1-u/r_{1})},$ $\displaystyle
h_{j}=[u^{j}]H(u)$
$\displaystyle=[u^{j}]\frac{1-3z^{2}-W}{2zr_{1}(1-u/r_{1})}.$

At this stage, we are only interested in

$s_{j}=f_{j}+g_{j}+h_{j}=[u^{j}]\frac{3-3z^{2}-W}{2zr_{1}(1-u/r_{1})}=\frac{3-3z^{2}-W}{2zr_{1}^{j+1}},$

which is the generating function of all (partial) paths ending at level $j$.
Parity considerations give us that only coefficients $[z^{n}]s_{j}$ are non-
zero if $n\equiv j\bmod 2$. To make this more transparent, we set

$P(z)=zr_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2},$

and then

$s_{j}=f_{j}+g_{j}+h_{j}=z^{j}\frac{3-3z^{2}-W}{2P^{j+1}}.$

Now we read off coefficients. We do this using residues and contour
integration. The path of integration, in both variables $x$ resp. $v$ is a
small circle or an equivalent contour.

$\displaystyle[z^{2m+j}]s_{j}$
$\displaystyle=[z^{2m}]\frac{3-3z^{2}-W}{2P^{j+1}}=[x^{m}]\frac{3-3x-\sqrt{1-6x+5x^{2}}}{2\Big{(}\frac{1+x-\sqrt{1-6x+5x^{2}}}{2}\Big{)}^{j+1}}$
$\displaystyle=[x^{m}]\frac{3-3\frac{v}{1+3v+v^{2}}-\frac{1-v^{2}}{1+3v+v^{2}}}{2\big{(}\frac{v(v+2)}{1+3v+v^{2}}\big{)}^{j+1}}$
$\displaystyle=[x^{m}]\frac{(1+v)(1+2v)}{v^{j+1}(v+2)^{j+1}}(1+3v+v^{2})^{j}$
$\displaystyle=\frac{1}{2\pi
i}\oint\frac{dx}{x^{m+1}}\frac{(1+v)(1+2v)}{v^{j+1}(v+2)^{j+1}}(1+3v+v^{2})^{j}$
$\displaystyle=\frac{1}{2\pi
i}\oint\frac{dv}{v^{m+1}}\frac{(1+v)(1+2v)(1-v^{2})}{v^{j+1}(v+2)^{j+1}}(1+3v+v^{2})^{m-1+j}$
$\displaystyle=[v^{m+j+1}]\frac{(1+v)^{2}(1+2v)(1-v)}{(v+2)^{j+1}}(1+3v+v^{2})^{m-1+j}.$

Note that

$(1+v)^{2}(1+2v)(1-v)=-9+27(v+2)-29(v+2)^{2}+13(v+2)^{3}-2(v+2)^{4};$

consequently

$\displaystyle[v^{k}]$ $\displaystyle\frac{(1+v)^{2}(1+2v)(1-v)}{(v+2)^{j+1}}$
$\displaystyle=-9\frac{1}{2^{j+1+k}}\binom{-j-1}{k}+27\frac{1}{2^{j+k}}\binom{-j}{k}-29\frac{1}{2^{j-1+k}}\binom{-j+1}{k}$
$\displaystyle+13\frac{1}{2^{j-2+k}}\binom{-j+2}{k}-2\frac{1}{2^{j-3+k}}\binom{-j+3}{k}=:\lambda_{j;k}.$

With this abbreviation we find

$[v^{m+j+1}]\frac{(1+v)^{2}(1+2v)(1-v)}{(v+2)^{j+1}}(1+3v+v^{2})^{m-1+j}=\sum_{k=0}^{m+j+1}\lambda_{j;k}\binom{m-1+j;1,3,1}{m+j+1-k}.$

This is not extremely pretty but it is _explicit_ and as good as it gets. Here
are the first few generating functions:

$\displaystyle s_{0}$
$\displaystyle=1+z^{2}+3z^{4}+10z^{6}+36z^{8}+137z^{10}+543z^{12}+\cdots$
$\displaystyle s_{1}$
$\displaystyle=z+2z^{3}+6z^{5}+21z^{7}+79z^{9}+311z^{11}+1265z^{13}+\cdots$
$\displaystyle s_{2}$
$\displaystyle=z^{2}+3z^{4}+10z^{6}+37z^{8}+145z^{10}+589z^{12}+2455z^{14}+\cdots$
$\displaystyle s_{3}$
$\displaystyle=z^{3}+4z^{5}+15z^{7}+59z^{9}+241z^{11}+1010z^{13}+4314^{15}+\cdots$

We could also give such lists for the functions $f_{j}$, $g_{j}$, $h_{j}$, if
desired. We summarize the essential findings of this section:

######  Theorem 1.

The generating function of decorated (partial) Dyck paths, consisting of $n$
steps, ending on level $j$, is given by

$S(z,u)=\frac{3-3z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2zr_{1}(1-u/r_{1})},$

with

$r_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

Furthermore

$[u^{j}]S(z,u)=\frac{3-3z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2zr_{1}^{j+1}}.$

##  3\. Open ended paths

If we do not specify the end of the paths, in other words we sum over all
$j\geq 0$, then at the level of generating functions this is very easy, since
we only have to set $u:=1$. We find

$\displaystyle S(1)$
$\displaystyle=-\frac{(z+1)(z^{2}+3z-2)+(z+2)\sqrt{1-6z^{2}+5z^{4}}}{2z(z^{2}+2z-1)}$
$\displaystyle=1+z+2z^{2}+3z^{3}+7z^{4}+11z^{5}+26z^{6}+43z^{7}+102z^{8}+175z^{9}+416z^{10}+\cdots.$

##  4\. Counting red edges

We can use an extra variable, $w$, to count additionally the red edges that
occur in a path. We use the same letters for generating functions. Eventually,
the coefficient $[z^{n}u^{j}w^{k}]S$ is the number of (partial) paths
consisting of $n$ steps, leading to level $j$, and having passed $k$ red
edges. The endpoint of the original skew path has then coordinates $(n-2k,j)$.
The computations are very similar, and we only sketch the key steps.

$f_{0}=1,\quad f_{i+1}=zf_{i}+zg_{i},\quad i\geq 0,$
$g_{i}=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\geq 0,$
$h_{i}=wzh_{i+1}+wzg_{i+1},\quad i\geq 0;$ $\displaystyle\frac{1}{u}(F(u)-1)$
$\displaystyle=zF(u)+zG(u),$ $\displaystyle G(u)$
$\displaystyle=\frac{z}{u}(F(u)-1)+\frac{z}{u}(G(u)-G(0))+\frac{z}{u}(H(u)-H(0)),$
$\displaystyle H(u)$
$\displaystyle=\frac{wz}{u}(G(u)-G(0))+\frac{wz}{u}(H(u)-G(0));$
$\displaystyle F(u)$ $\displaystyle=\frac{z^{2}uG(0)+z^{2}uH(0)+z^{2}u-u-
wz^{3}+z+wz}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u},$ $\displaystyle G(u)$
$\displaystyle=\frac{z(H(0)-uzH(0)+wz^{2}+G(0)-zuG(0)-zu)}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u},$
$\displaystyle H(u)$
$\displaystyle=\frac{wz(-uzH(0)-z^{2}-zuG(0)+G(0)-z^{2}H(0)+H(0)-z^{2}G(0))}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u}.$

The denominator factors as $z(u-r_{1})(u-r_{2})$, with

$\displaystyle r_{1}$
$\displaystyle=\frac{1+wz^{2}+\sqrt{1-(4+2w)z^{2}+(4w+w^{2})z^{4}}}{2z},$
$\displaystyle r_{2}$
$\displaystyle=\frac{1+wz^{2}-\sqrt{1-(4+2w)z^{2}+(4w+w^{2})z^{4}}}{2z}.$

Note the factorization
$1-(4+2w)z^{2}+(4w+w^{2})z^{4}=(1-z^{2}w)(1-(4+w)z^{2})$. Since the factor
$u-r_{2}$ in the denominator is “bad,” it must also cancel in the numerators.
From this we eventually find, with the abbreviation
$W=\sqrt{1-(4+2w)z^{2}+(4w+w^{2})z^{4}}\,$)

$\displaystyle F(u)$ $\displaystyle=\frac{-1-wz^{2}-W}{2z(u-r_{1})},$
$\displaystyle G(u)$ $\displaystyle=\frac{-1+wz^{2}+W}{2z(u-r_{1})},$
$\displaystyle H(u)$ $\displaystyle=\frac{-1+(2+w)z^{2}+W}{2z(u-r_{1})}.$

The total generating function is

$S(u)=F(u)+G(u)+H(u)=\frac{-2-w+z^{2}(w+w^{2})+wW}{2z(u-r_{1})}.$

The special case $u=0$ (return to the $x$-axis) is to be noted:

$S(0)=\frac{-2-w+z^{2}(w+w^{2})+wW}{-2zr_{1}}=\frac{1-wz^{2}-W}{2z^{2}}.$

Since there are only even powers of $z$ in this function, we replace $x=z^{2}$
and get

$\displaystyle S(0)$
$\displaystyle=\frac{1-wx-\sqrt{1-(4+2w)x+(4w+w^{2})x^{2}}}{2x}$
$\displaystyle=1+x+(w+2)x^{2}+(w^{2}+4w+5)x^{3}+(w^{3}+6w^{2}+15w+14)x^{4}+\cdots.$

Compare the factor $(w^{2}+4w+5)$ with the earlier drawing of the 10 paths.

There is again a substitution that allows for better results:

$z=\frac{v}{1+(2+w)v+v^{2}},\quad\text{then}\quad S(0)=1+v.$

Reading off coefficients can now be done using modified trinomial
coefficients:

$\binom{n;1,2+w,1}{k}=[t^{k}]\bigl{(}1+(2+w)t+t^{2}\bigr{)}^{n}.$

Again, we use contour integration to extract coefficients:

$\displaystyle[x^{n}](1+v)$ $\displaystyle=\frac{1}{2\pi
i}\oint\frac{dx}{x^{n+1}}(1+v)$ $\displaystyle=\frac{1}{2\pi
i}\oint\frac{dx}{v^{n+1}}\frac{1-v^{2}}{(1+(2+w)v+v^{2})^{2}}(1+(2+w)v+v^{2})^{n+1}(1+v)$
$\displaystyle=[v^{n}](1-v)(1+v)^{2}(1+(2+w)v+v^{2})^{n-1}$
$\displaystyle=\binom{n-1;1,2+w,1}{n}+\binom{n-1;1,2+w,1}{n-1}$
$\displaystyle\qquad-\binom{n-1;1,2+w,1}{n-2}-\binom{n-1;1,2+w,1}{n-3}.$

Now we want to count the average number of red edges. For that, we
differentiate $S(0)$ w.r.t. $w$, followed by $w:=1$. This leads to

$\frac{-1+6x-5x^{2}+(1+3x)\sqrt{1-6x+5x^{2}}}{2(1-x)(1-5x)}.$

A simple application of singularity analysis leads to

$\frac{\frac{1}{2\sqrt{5}}[x^{n}]\frac{1}{\sqrt{1-5x}}}{-\sqrt{5}[x^{n}]\sqrt{1-5x}}\sim\frac{n}{5}.$

So, a random path consisting of $2n$ steps has about $n/5$ red steps, on
average.

For readers who are not familiar with singularity analysis of generating
functions [3, 4], we just mention that one determines the local expansion
around the dominating singularity, which is at $z=\frac{1}{5}$ in our
instance. In the denominator, we just have the total number of skew Dyck
paths, according to the sequence A002212 in [9].

In the example of Figure 2, the exact average is $6/10$, which curiously is
exactly the same as $3/5$.

We finish the discussion by considering fixed powers of $w$ in $S(0)$,
counting skew Dyck paths consisting of zero, one, two, three, …red edges. We
find

$\displaystyle[w^{0}]S(0)$ $\displaystyle=\frac{1-\sqrt{1-4x}}{2x},$
$\displaystyle[w^{1}]S(0)$
$\displaystyle=\frac{1-2x-\sqrt{1-4x}}{2\sqrt{1-4x}},$
$\displaystyle[w^{2}]S(0)$ $\displaystyle=\frac{x^{3}}{(1-4x)^{3/2}},$
$\displaystyle[w^{3}]S(0)$ $\displaystyle=\frac{x^{4}(1-2x)}{(1-4x)^{5/2}},$
$\displaystyle[w^{4}]S(0)$
$\displaystyle=\frac{x^{5}(1-4x+5x^{2})}{(1-4x)^{7/2}},\quad\&\text{c}.$

The generating function $[w^{0}]S(0)$ is of course the generating function of
Catalan numbers, since no red edges just means: ordinary Dyck paths. We can
also conclude that the asymptotic behaviour is of the form $n^{k-3/2}4^{n}$,
where the polynomial contribution gets higher, but the exponential growth
stays the same: $4^{n}$. This is compared to the scenario of an _arbitrary_
number of red edges, when we get an exponential growth of the form $5^{n}$.

##  5\. Dual skew Dyck paths

The mirrored version of skew Dyck paths with two types of up-steps, $(1,1)$
and $(-1,1)$ are also cited among the objects in A002212 in [9]. We call them
dual skew paths and drop the ‘dual’ when it isn’t necessary. When the paths
come back to the $x$-axis, no new enumeration is necessary, but this is no
longer true for paths ending at level $j$.

Here is a list of the 10 skew paths consisting of 6 steps:

Figure 4. All 10 dual skew Dyck paths of length 6 (consisting of 6 steps).

We prefer to work with the equivalent model (resembling more traditional Dyck
paths) where we replace each step $(-1,-1)$ by $(1,-1)$ but label it blue.
Here is the list of the 10 paths again (Figure 2):

Figure 5. All 10 dual skew Dyck paths of length 6 (consisting of 6 steps).

The rules to generate such decorated Dyck paths are: each edge $(1,-1)$ may be
black or blue, but  and  are forbidden.

Our interest is in particular in _partial_ decorated Dyck paths, ending at
level $j$, for fixed $j\geq 0$; the instance $j=0$ is the classical case.

The analysis of partial skew Dyck paths was recently started in [1] (using the
notion ‘prefix of a skew Dyck path’) using Riordan arrays instead of our
kernel method. The latter gives us _bivariate_ generating functions, from
which it is easier to draw conclusions. Two variables, $z$ and $u$, are used,
where $z$ marks the length of the path and $j$ marks the end-level. We briefly
mention that one can, using a third variable $w$, also count the number of
blue edges.

The substitution

$x=\frac{v}{1+3v+v^{2}},$

which was used in [5, 7] is the key to the success and allows to write
_explicit enumerations_ , using the notion of a (weighted) trinomial
coefficient:

$\binom{n;1,3,1}{k}:=[t^{k}](1+3t+t^{2})^{n}.$

##  6\. Generating functions and the kernel method

We catch the essence of a decorated (dual skew) Dyck path using a state-
diagram:

Figure 6. Three layers of states according to the type of steps leading to
them (down, up-black, up-blue).

It has three types of states, with $j$ ranging from 0 to infinity; in the
drawing, only $j=0..8$ is shown. The first layer of states refers to an up-
step leading to a state, the second layer refers to a black down-step leading
to a state and the third layer refers to a blue down-step leading to a state.
We will work out generating functions describing all paths leading to a
particular state. We will use the notations $c_{j},a_{j},b_{j}$ for the three
respective layers, from top to bottom. Note that the syntactic rules of
forbidden patterns  and  can be clearly seen from the picture. The functions
depend on the variable $z$ (marking the number of steps), but mostly we just
write $a_{j}$ instead of $a_{j}(z)$, etc.

The following recursions can be read off immediately from the diagram:

$\displaystyle a_{0}=1,\quad a_{i+1}=za_{i}+zb_{i}+zc_{i},\quad i\geq 0,$
$\displaystyle b_{i}=za_{i+1}+zb_{i+1},\quad i\geq 0,$ $\displaystyle
c_{i+1}=za_{i}+zc_{i},\quad i\geq 0.$

And now it is time to introduce the promised _bivariate_ generating functions:

$A(z,u)=\sum_{i\geq 0}a_{i}(z)u^{i},\quad B(z,u)=\sum_{i\geq
0}b_{i}(z)u^{i},\quad C(z,u)=\sum_{i\geq 0}c_{i}(z)u^{i}.$

Again, often we just write $A(u)$ instead of $A(z,u)$ and treat $z$ as a
‘silent’ variable. Summing the recursions leads to

$\displaystyle\sum_{i\geq 0}u^{i}a_{i}$ $\displaystyle=1+u\sum_{i\geq
0}u^{i}(za_{i}+zb_{i}+zc_{i})$ $\displaystyle=1+uzA(u)+uzB(u)+uzC(u),$
$\displaystyle\sum_{i\geq 0}u^{i}b_{i}$ $\displaystyle=\sum_{i\geq
0}u^{i}(za_{i+1}+zb_{i+1})$ $\displaystyle=\frac{z}{u}\sum_{i\geq
1}u^{i}a_{i}+\frac{z}{u}\sum_{i\geq 1}u^{i}b_{i},$ $\displaystyle\sum_{i\geq
1}u^{i}c_{i}$ $\displaystyle=uz\sum_{i\geq 0}u^{i}a_{i}+uz\sum_{i\geq
0}u^{i}c_{i}.$

This can be rewritten as

$\displaystyle A(u)$ $\displaystyle=1+uzA(u)+uzB(u)+uzC(u),$ $\displaystyle
B(u)$ $\displaystyle=\frac{z}{u}(A(u)-a_{0})+\frac{z}{u}(B(u)-b_{0}),$
$\displaystyle C(u)$ $\displaystyle=c_{0}+uzA(u)+uzC(u).$

Note that $a_{0}=1$, $c_{0}=0$. Simplification leads to

$C(u)=\frac{uzA(u)}{1-uz}$

and

$B(u)=\frac{z(A(u)-1-B(0))}{u-z}$

leaving us with just one equation

$A(u)={\frac{\left(z-u+u{z}^{2}+u{z}^{2}B(0)\right)\left(uz-1\right)}{{u}^{2}{z}^{3}+u{z}^{2}-2{u}^{2}z-z+u}}.$

This is a typical application of the kernel method, [8].

${u}^{2}{z}^{3}+u{z}^{2}-2{u}^{2}z-z+u=z(z^{2}-2)(u-s_{1})(u-s_{2})$

The denominator factors as $2z(z^{2}-2)(u-s_{1})(u-s_{2})$, with

$s_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z(2-z^{2})},\quad
s_{2}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z(2-z^{2})}.$

Note that $s_{1}s_{2}=\frac{1}{2-z^{2}}$. Since the factor $u-s_{2}$ in the
denominator is “bad,” it must also cancel in the numerators. From this we
conclude (again with the abbreviation $W=\sqrt{1-6z^{2}+5z^{4}}\,$)

$B(0)=\frac{zs_{2}}{1-2zs_{2}},$

and further

$A(u)=\frac{(1-uz)(1+z^{2}+W)}{2z(z^{2}-2)(u-s_{1})},$
$B(u)=\frac{1-2z^{2}-W}{z(2-z^{2})(u-s_{1})},$
$C(u)=\frac{1+z^{2}+W}{2(z^{2}-2)}\frac{u}{u-s_{1}},$

and for the function of main interest

$G(u)=A(u)+B(u)+C(u)=\frac{3z^{2}-3+W}{2z(2-z^{2})(u-s_{1})}.$

Note that

$\displaystyle\frac{1}{s_{1}}$
$\displaystyle=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z}=zS,$
$\displaystyle\frac{1}{s_{2}}$
$\displaystyle=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

Then

$\displaystyle[u^{j}]G(u)$
$\displaystyle=[u^{j}]\frac{3z^{2}-3+W}{2z(z^{2}-2)s_{1}(1-u/s_{1})}$
$\displaystyle=\frac{3z^{2}-3+W}{2z(z^{2}-2)s_{1}^{j+1}}=\frac{3z^{2}-3+W}{2(z^{2}-2)}z^{j}S^{j+1}.$

So $[u^{j}]G(u)$ contains only powers of the form $z^{j+2N}$. Now we continue

$\displaystyle[z^{j+2N}u^{j}]G(u)$
$\displaystyle=[z^{2N}]\frac{3z^{2}-3+W}{2(z^{2}-2)}S^{j+1}$
$\displaystyle=[x^{N}]\frac{3x-3+\sqrt{1-6x+5x^{2}}}{2(x-2)}\bigg{(}\frac{1+x-\sqrt{1-6x+5x^{2}}}{2x}\bigg{)}^{j+1}$
$\displaystyle=[x^{N}](v+1)(v+2)^{j}$

which is the generating function of all (partial) paths ending at level $j$.

Now we read off coefficients. We do this using residues and contour
integration. The path of integration, in both variables $x$ resp. $v$ is a
small circle or an equivalent contour;

$\displaystyle[z^{j+2N}u^{j}]G(u)$ $\displaystyle=[x^{N}](v+1)(v+2)^{j}$
$\displaystyle=\frac{1}{2\pi i}\oint\frac{dx}{x^{N+1}}(v+1)(v+2)^{j}$
$\displaystyle=\frac{1}{2\pi
i}\oint\frac{dv}{v^{N+1}}(1+3v+v^{2})^{N+1}\frac{(1-v^{2})}{(1+3v+v^{2})^{2}}(v+1)(v+2)^{j}$
$\displaystyle=[v^{N}](1+3v+v^{2})^{N-1}(1-v)(1+v)^{2}(v+2)^{j}.$

Note that

$(1-v)(1+v)^{2}=3-7(v+2)+5(v+2)^{2}-(v+2)^{3};$

consequently

$\displaystyle[z^{j+2N}u^{j}]G(u)$
$\displaystyle=[v^{N}](1+3v+v^{2})^{N-1}\Big{[}3-7(v+2)+5(v+2)^{2}-(v+2)^{3}\Big{]}(v+2)^{j}.$

We abbreviate:

$\displaystyle\mu_{j;k}$
$\displaystyle=[v^{k}]\Big{[}3(v+2)^{j}-7(v+2)^{j+1}+5(v+2)^{j+2}-(v+2)^{j+3}\Big{]}$
$\displaystyle=3\binom{j}{k}2^{j-k}-7\binom{j+1}{k}2^{j+1-k}+5\binom{j+2}{k}2^{j+2-k}-\binom{j+3}{k}2^{j+3-k}.$

With this notation we get

$[z^{j+2N}u^{j}]G(u)=\sum_{0\leq k\leq N-1}\mu_{j;k}\binom{N-1;1,3,1}{N-k}.$

Here are the first few generating functions:

$\displaystyle G_{0}$
$\displaystyle=1+{z}^{2}+3{z}^{4}+10{z}^{6}+36{z}^{8}+137{z}^{10}+543{z}^{12}+2219{z}^{14}+\cdots$
$\displaystyle G_{1}$
$\displaystyle=2z+3{z}^{3}+10{z}^{5}+36{z}^{7}+137{z}^{9}+543{z}^{11}+2219{z}^{13}+9285{z}^{15}+\cdots$
$\displaystyle G_{2}$
$\displaystyle=4{z}^{2}+8{z}^{4}+29{z}^{6}+111{z}^{8}+442{z}^{10}+1813{z}^{12}+7609{z}^{14}+32521{z}^{16}+\cdots$
$\displaystyle G_{3}$
$\displaystyle=8{z}^{3}+20{z}^{5}+78{z}^{7}+315{z}^{9}+1306{z}^{11}+5527{z}^{13}+23779{z}^{15}+103699{z}^{17}+\cdots$

We could also give such lists for the functions $a_{j}$, $b_{j}$, $c_{j}$, if
desired. We summarize the essential findings of this section:

######  Theorem 2.

The generating function of decorated (partial) dual skew Dyck paths,
consisting of $n$ steps, ending on level $j$, is given by

$G(z,u)=\frac{3z^{2}-3+\sqrt{1-6z^{2}+5z^{4}}}{2z(2-z^{2})(u-s_{1})},$

with

$s_{1}=\frac{2z}{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}.$

Furthermore

$[u^{j}]G(z,u)=\frac{3z^{2}-3+\sqrt{1-6z^{2}+5z^{4}}}{2(z^{2}-2)}z^{j}S^{j+1},$

with

$S=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z^{2}}.$

##  7\. Open ended paths

If we do not specify the end of the paths, in other words we sum over all
$j\geq 0$, then at the level of generating functions this is very easy, since
we only have to set $u:=1$. We find

$\displaystyle G(1)$
$\displaystyle=\frac{(1+z)(1-3z)}{2z(z^{2}+2z-1)-\sqrt{1-6z^{2}+5z^{4}}}$
$\displaystyle=1+2z+5{z}^{2}+11{z}^{3}+27{z}^{4}+62{z}^{5}+151{z}^{6}+354{z}^{7}+859{z}^{8}+2036{z}^{9}+\cdots.$

##  8\. Counting blue edges

We can use an extra variable, $w$, to count additionally the blue edges that
occur in a path. We use the same letters for generating functions. Eventually,
the coefficient $[z^{n}u^{j}w^{k}]S$ is the number of (partial) paths
consisting of $n$ steps, leading to level $j$, and having passed $k$ blue
edges. The endpoint of the original skew path has then coordinates $(n-2k,j)$.
The computations are very similar, and we only sketch the key steps.

$\displaystyle a_{0}=1,\quad a_{i+1}=za_{i}+zb_{i}+zc_{i},\quad i\geq 0,$
$\displaystyle b_{i}=za_{i+1}+zb_{i+1},\quad i\geq 0,$ $\displaystyle
c_{i+1}=wza_{i}+wzc_{i},\quad i\geq 0.$

This leads to

$\displaystyle A(u)$ $\displaystyle=1+uzA(u)+uzB(u)+uzC(u),$ $\displaystyle
B(u)$ $\displaystyle=\frac{z}{u}(A(u)-a_{0})+\frac{z}{u}(B(u)-b_{0}),$
$\displaystyle C(u)$ $\displaystyle=c_{0}+wuzA(u)+wuzC(u).$

Solving,

$S(u)=A(u)+B(u)+C(u)={\frac{u-wu{z}^{2}-zA(0)-zB(0)+uw{z}^{2}A(0)+uw{z}^{2}B(0)}{{u}^{2}{z}^{3}w+u-w{u}^{2}z-{u}^{2}z-z+wu{z}^{2}}}.$

The denominator factors as $-z(1+w-z^{2}w)(u-s_{1})(u-s_{2})$, with

$\displaystyle s_{1}$
$\displaystyle={\frac{1+{z}^{2}w+\sqrt{1-2\,{z}^{2}w+{z}^{4}{w}^{2}-4\,{z}^{2}+4{z}^{4}w}}{2z\left(1+w-{z}^{2}w\right)}},$
$\displaystyle s_{2}$
$\displaystyle={\frac{1+{z}^{2}w-\sqrt{1-2\,{z}^{2}w+{z}^{4}{w}^{2}-4\,{z}^{2}+4{z}^{4}w}}{2z\left(1+w-{z}^{2}w\right)}}.$

Note the factorization
$1-(4+2w)z^{2}+(4w+w^{2})z^{4}=(1-z^{2}w)(1-(4+w)z^{2})$. Since the factor
$u-r_{2}$ in the denominator is “bad,” it must also cancel in the numerators.
From this we eventually find, with the abbreviation
$W=\sqrt{1-(4+2w)z^{2}+(4w+w^{2})z^{4}}\,$)

$G(0)={\frac{1-{z}^{2}w-W}{2{z}^{2}}},$

and further

$G(u)=\frac{w-{z}^{2}{w}^{2}-wW+2-2{z}^{2}w}{2z\left(-w-1+{z}^{2}w\right)(u-s_{1})}.$

The special case $u=0$ (return to the $x$-axis) is to be noted:

$G(0)=1+{z}^{2}+\left(w+2\right){z}^{4}+\left({w}^{2}+4w+5\right){z}^{6}+\left(w+2\right)\left({w}^{2}+4w+7\right){z}^{8}+\cdots.$

Compare the factor $(w^{2}+4w+5)$ with the earlier drawing of the 10 paths.
There is again a substitution that allows for better results:

$z=\frac{v}{1+(2+w)v+v^{2}},\quad\text{then}\quad G(0)=1+v.$

Since $S(u)=G(u)$ with $S(u)$ from the first part of the paper, as it means
the same objects, read from left to right resp. from right to left, no new
analysis is required.

##  9\. Skew paths that can go into negative territory

For Dyck paths and the standard random walk on the integers, the enumeration,
if the negative territory is allowed, is easier. In our instance of paths
equipped with an additional red down-step and the usual restrictions (up–red
and red–up are forbidden) this is not so; it is rather more complicated. The
paths may be described by another directed graph Figure 7.

$0$$1$$2$$3$$4$$\mathit{-1}$$\mathit{-2}$$\mathit{-3}$$\mathit{-4}$ Figure 7.
Three layers of states according to the type of steps leading to them (up,
down-black, down-red).

We have the following recursions,

$\displaystyle f_{i}=[i=0]+zf_{i-1}+zg_{i-1},$ $\displaystyle
g_{i}=zf_{i+1}+zg_{i+1}+zh_{i+1},$ $\displaystyle h_{i}=zg_{i+1}+zh_{i+1}.$

For negative indices we need to introduce separate sequences,

$a_{i}=f_{-i},\ b_{i}=g_{-i},\ c_{i}=h_{-i}.$

Then we find

$\displaystyle f_{-i}=[-i=0]+zf_{-i-1}+zg_{-i-1},$ $\displaystyle
g_{-i}=zf_{-i+1}+zg_{-i+1}+zh_{-i+1},$ $\displaystyle
h_{-i}=zg_{-i+1}+zh_{-i+1}$

and, rewriting,

$\displaystyle a_{i}=[i=0]+za_{i+1}+zb_{i+1},$ $\displaystyle
b_{i}=za_{i-1}+zb_{i-1}+zc_{i-1},$ $\displaystyle c_{i}=zb_{i-1}+zc_{i-1}.$

Introducing

$F(u)=\sum_{i\geq 0}f_{i}u^{i},\ G(u)=\sum_{i\geq 0}g_{i}u^{i},\
H(u)=\sum_{i\geq 0}h_{i}u^{i}$

and

$A(u)=\sum_{i\geq 0}a_{i}u^{i},\ B(u)=\sum_{i\geq 0}b_{i}u^{i},\
C(u)=\sum_{i\geq 0}c_{i}u^{i}$

we get the following 6 equations:

$\displaystyle F(u)-f_{0}$ $\displaystyle=zu(F(u)+G(u)),$ $\displaystyle G(u)$
$\displaystyle=\frac{z}{u}(F(u)+G(u)+H(u)-f_{0}-g_{0}-h_{0}),$ $\displaystyle
H(u)$ $\displaystyle=\frac{z}{u}(G(u)+H(u)-g_{0}-h_{0}),$ $\displaystyle A(u)$
$\displaystyle=1+\frac{z}{u}(A(u)+B(u)-f_{0}-g_{0}),$ $\displaystyle
B(u)-g_{0}$ $\displaystyle=zu(A(u)+B(u)+C(u)),$ $\displaystyle C(u)-h_{0}$
$\displaystyle=zu(B(u)+C(u)).$

Solving the system,

$\displaystyle F$
$\displaystyle={\frac{{z}^{2}ug_{0}+{z}^{2}uh_{0}+{z}^{2}u{f_{0}}-u{f_{0}}-{z}^{3}{f_{0}}+2z{f_{0}}}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}},$
$\displaystyle G$
$\displaystyle=-{\frac{z\left(zu{h_{0}}-{z}^{2}{f_{0}}-{g_{0}}-{h_{0}}+uz{f_{0}}+zu{g_{0}}\right)}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}},$
$\displaystyle H$
$\displaystyle=-{\frac{z\left(zu{h_{0}}+{z}^{2}{f_{0}}+zu{g_{0}}+{z}^{2}{h_{0}}-{g_{0}}+{z}^{2}{g_{0}}-{h_{0}}\right)}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}},$
$\displaystyle A$
$\displaystyle={\frac{2{z}^{2}u{f_{0}}+{z}^{2}u{g_{0}}+{z}^{2}u{h_{0}}-2z{u}^{2}-z{f_{0}}+u}{{z}^{2}u+{z}^{3}{u}^{2}+u-2z{u}^{2}-z}},$
$\displaystyle B$
$\displaystyle={\frac{z{u}^{2}-{z}^{2}u{f_{0}}+u{g_{0}}-z{g_{0}}-{z}^{2}{u}^{3}+{z}^{3}{u}^{2}{f_{0}}+{z}^{3}{u}^{2}{g_{0}}-z{u}^{2}{g_{0}}+z{u}^{2}{h_{0}}-{z}^{2}u{h_{0}}}{{z}^{2}u+{z}^{3}{u}^{2}+u-2z{u}^{2}-z}},$
$\displaystyle C$
$\displaystyle=-{\frac{-{z}^{2}{u}^{3}+{z}^{3}{u}^{2}{f_{0}}+{z}^{3}{u}^{2}{g_{0}}-u{h_{0}}-z{u}^{2}{g_{0}}+z{u}^{2}{h_{0}}+z{h_{0}}+{z}^{2}u{g_{0}}}{{z}^{2}u+{z}^{3}{u}^{2}+u-2z{u}^{2}-z}},$

and

$-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u=z(u-r_{1})(u-r_{2})$

with

$r_{1,2}=\frac{1+z^{2}\pm\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

As usual, the factor $u-r_{2}$ must cancel out. The other denominators are

${z}^{2}u+{z}^{3}{u}^{2}+u-2z{u}^{2}-z=z(z^{2}-2)(u-s_{1})(u-2_{2})$

and $s_{1}=1/r_{2}$, $s_{2}=1/r_{1}$. The factor $u-s_{1}$ must cancel out as
well. This leads to

$\displaystyle F(u)$
$\displaystyle=\frac{{z}^{2}g_{0}+{z}^{2}h_{0}+{z}^{2}f_{0}-f_{0}}{r_{2}z-1-{z}^{2}+zu},$
$\displaystyle G(u)$
$\displaystyle=-{\frac{\left(f_{0}+g_{0}+h_{0}\right){z}^{2}}{r_{2}z-1-{z}^{2}+zu}},$
$\displaystyle H(u)$
$\displaystyle=-{\frac{{z}^{2}\left(g_{0}+h_{0}\right)}{r_{2}z-1-{z}^{2}+zu}},$
$\displaystyle A(u)$
$\displaystyle=-{\frac{2s_{1}z-2{z}^{2}f_{0}-{z}^{2}g_{0}-{z}^{2}h_{0}-1+2zu}{s_{1}{z}^{3}-2s_{1}z+1+{z}^{2}+u{z}^{3}-2zu}},$
$\displaystyle B(u)$
$\displaystyle=-\frac{\mathcal{X}}{s_{1}{z}^{3}-2s_{1}z+1+{z}^{2}+u{z}^{3}-2zu},$
$\displaystyle C(u)$
$\displaystyle={\frac{{s_{1}}^{2}{z}^{2}-s_{1}{z}^{3}f_{0}-s_{1}{z}^{3}g_{0}+s_{1}zg_{0}-s_{1}zh_{0}+s_{1}{z}^{2}u+h-{z}^{2}g_{0}-u{z}^{3}f_{0}-u{z}^{3}g_{0}+zug_{0}-zuh_{0}+{z}^{2}{u}^{2}}{s_{1}{z}^{3}-2s_{1}z+1+{z}^{2}+u{z}^{3}-2zu}}$

with
$\mathcal{X}={s_{1}}^{2}{z}^{2}-s_{1}z-s_{1}{z}^{3}f_{0}-s_{1}{z}^{3}g_{0}+s_{1}zg_{0}-s_{1}zh_{0}+s_{1}{z}^{2}u+{z}^{2}f_{0}-g_{0}+{z}^{2}h_{0}-zu-u{z}^{3}f_{0}-u{z}^{3}g_{0}+zug_{0}-zuh_{0}+{z}^{2}{u}^{2}$.
The computation of $f_{0}$, $g_{0}$, $h_{0}$ requires some care. From the
equations for $G$ and $H$ we conclude

$g_{0}=\frac{z^{2}f_{0}+h_{0}}{1-z^{2}}$

and from the expression for $H$, as just derived, we find

$h_{0}=f_{0}{\frac{{z}^{4}}{r_{2}{z}^{3}-r_{2}z+1-2{z}^{2}}}.$

So both, $g_{0}$ and $h_{0}$ are multiples of $f_{0}$. As any $f_{0}$ would
solve the first 3 equations with the appropriate $g_{0}$, $h_{0}$, we need to
resort to $A(u)$ since there we find that $f_{0}=1+\cdots$. By elimination,

$A(u)={\frac{-2z{u}^{2}+u+g_{0}{z}^{2}u+{z}^{2}uh_{0}+2f_{0}{z}^{2}u-zf_{)}}{{z}^{2}u-z+{z}^{3}{u}^{2}-2z{u}^{2}+u}}.$

Substitute $u=0$ and use $g_{0}$ and $h_{0}$ from before and then solve
$A(0)=f_{0}$ leads to

$f_{0}={\frac{r_{2}{z}^{3}-r_{2}z+1-2{z}^{2}}{-{z}^{6}+{z}^{4}+2r_{2}{z}^{3}-3{z}^{2}-r_{2}z+1}}.$

It can be made explicit:

$f_{0}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z^{2}(2-z^{2})}.$

Now everything is explicit:

$\displaystyle f_{0}$
$\displaystyle=1+z^{2}+2z^{4}+6z^{6}+21z^{8}+79z^{10}+311z^{12}+1265z^{14},$
$\displaystyle g_{0}$
$\displaystyle=z^{2}+3z^{4}+10z^{6}+37z^{8}+145z^{10}+589z^{12}+2455z^{14},$
$\displaystyle h_{0}$
$\displaystyle=z^{4}+5z^{6}+21z^{8}+87z^{10}+365z^{12}+1555z^{14}.$

The expressions for $g_{0}$ and $h_{0}$ are a bit long, but

$\displaystyle f_{0}+g_{0}+h_{0}$
$\displaystyle=\frac{1-3z^{2}+2z^{4}-\sqrt{1-6z^{2}+5z^{4}}}{2z^{4}(2-z^{2})}$
$\displaystyle=1+2z^{2}+6z^{4}+21z^{6}+79z^{8}+311z^{10}+1265z^{12}+5275z^{14}.$

The coefficients $1,2,6,21,\dots$ are sequence A033321 in [9]. In the comments
to this sequence, the number of skew Dyck paths of semilength $n$ ending with
a down step $(1,-1)$ is mentioned, something that follows from our results for
$g_{0}$ in section 2.

## References

  * [1] Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba.  Counting Prefixes of Skew Dyck Paths.  Journal of integer sequences, Article 21.8.2, 2021.
  * [2] Emeric Deutsch, Emanuele Munarini, Simone Rinaldi.  Skew Dyck paths.  J. Stat. Plann. Infer., 140 (8) (2010) 2191–2203.
  * [3] Philippe Flajolet and Andrew M. Odlyzko.  Singularity analysis of generating functions.  3:216–240, 1990.
  * [4] Philippe Flajolet and Robert Sedgewick.  Analytic combinatorics.  Cambridge University Press, Cambridge, 2009.
  * [5] Clemens Heuberger, Helmut Prodinger, and Stephan Wagner.  The height of multiple edge plane trees.  Aequationes Math., 90(3):625–645, 2016.
  * [6] Hana Kim and Richard P. Stanley.  A refined enumeration of hex trees and related polynomials.  European J. Combin., 54:207–219, 2016.
  * [7] Helmut Prodinger.  Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures.  preprint, 2021.
  * [8] Helmut Prodinger.  The Kernel Method: A Collection of Examples,  Séminaire Lotharingien de Combinatoire, B50f (2004), 19 pp.
  * [9] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences, 2021.