# Combinatorial games on Galton-Watson trees involving several-generation-jump
moves

Dhruv Bhasin, Moumanti Podder  Moumanti Podder, Indian Institute of Science
Education and Research (IISER) Pune, Dr. Homi Bhabha Road, Pashan, Pune
411008, Maharashtra, India.  Dhruv Bhasin, Indian Institute of Science
Education and Research (IISER) Pune, Dr. Homi Bhabha Road, Pashan, Pune
411008, Maharashtra, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We study the _$k$ -jump normal_ and _$k$ -jump misère_ games on rooted Galton-
Watson trees, expressing the probabilities of various possible outcomes of
these games as specific fixed points of functions that depend on $k$ and the
offspring distribution. We discuss phase transition results pertaining to draw
probabilities when the offspring distribution is Poisson$(\lambda)$. We
compare the probabilities of various outcomes of the $2$-jump normal game with
those of the $2$-jump misère game, and a similar comparison is drawn between
the $2$-jump normal game and the $1$-jump normal game, under the Poisson
regime. We describe the rate of decay of the probability that the first player
loses the $2$-jump normal game as $\lambda\rightarrow\infty$. We also discuss
a sufficient condition for the average duration of the $k$-jump normal game to
be finite.

###### Key words and phrases:

two-player combinatorial games; normal games; misère games; rooted Galton-
Watson trees; fixed points; Poisson offspring; generalized finite state tree
automata

##  1\. Introduction

The simplest yet intriguing versions of the normal and misère games on rooted
random trees were studied in [15]. Each game involves two players (henceforth
addressed as P1 and P2) and a token, and requires visualizing a given rooted
tree as a directed graph in which an edge between a parent vertex $u$ and its
child $v$ is assumed to be directed from $u$ to $v$. In each game, the players
take turns to move the token along these directed edges. In a normal game, the
first player to get stuck at a leaf vertex (i.e. unable to move the token any
further) loses, whereas in a misère game, this same player wins. The two games
share a fair amount of similarities in their analysis, but the objective of
each player in a normal game is precisely the opposite of that in a misére
game. While the authors of [15] provide an incredibly thorough analysis of
these two games when played on rooted Galton-Watson (henceforth abbreviated as
GW) trees, they also pose several open questions. Our paper delves deeper into
the fascinating world of these two-player combinatorial games and asks: _what
if we do not restrict the players to only single-generation moves?_ In other
words, instead of allowing each player, when it is her turn, to move the token
from its current position $u$ to a child of $u$, we now permit her to move the
token from $u$ to any descendant of $u$ that is at a distance at most $k$ away
from $u$, where $k\geqslant 1$ is a pre-assigned positive integer. We call the
corresponding versions of the normal and misére games the _$k$ -jump normal_
and _$k$ -jump misère_ games respectively.

###  1.1. Introduction to the games

We begin with a description of the rooted GW trees on which our games are
played. A Galton-Watson branching process (henceforth denoted
$\mathcal{T}_{\chi}$), introduced in [43] and independently studied in [8] as
a model to investigate the extinction of ancestral family names, begins with a
root $\phi$ giving birth to a random number $X_{0}$ of children where $X_{0}$
follows the _offspring distribution_ $\chi$ (a probability distribution
supported on the set $\mathbb{N}_{0}$ of non-negative integers). If $X_{0}=0$,
we stop the process, whereas if $X_{0}=m$ for some $m\in\mathbb{N}$, the
children of $\phi$ are named $v_{1},\ldots,v_{m}$, and $v_{i}$ gives birth to
$X_{i}$ children with $X_{1},\ldots,X_{m}$ i.i.d. $\chi$. Thus the process
continues, and the resulting tree is infinite with positive probability iff
the expectation of $\chi$ exceeds $1$. We refer the reader to [5], [3] and [4]
for further reading on GW trees.

We now come to a formal description of the games studied in this paper. Given
any realization $T$ of $\mathcal{T}_{\chi}$, any vertex $u$ in $T$, and
$i\in\mathbb{N}$, let $\Gamma_{i}(u)$ denote the set of all descendants $v$ of
$u$ (excluding $u$ itself) such that the distance between $u$ and $v$ is at
most $i$. The vertex at which the token is placed at the beginning of a game
is known as the _initial vertex_. The players P1 and P2 take turns to make
_moves_ (with P1 moving in the first round), where a move constitutes
relocating the token from its current position, which is some vertex $u$ in
$T$, to a vertex $v\in\Gamma_{k}(u)$, where $k\in\mathbb{N}$ is fixed _a
priori_. The player who is unable to make a move loses the $k$-jump normal
game. Hence, in this game, each of P1 and P2 strives to relocate the token,
obeying the rules of the game, from its current position to a leaf vertex of
$T$, thereby making her opponent lose in the next round. On the other hand,
the player who is unable to make a move wins the $k$-jump misère game.
Therefore, in this game, each of P1 and P2 strives to force her opponent to
relocate the token to a leaf vertex of $T$, thereby ensuring that she herself
wins the game in the next round.

It is important to note here that a realization $T$ of the random tree
$\mathcal{T}_{\chi}$ is first generated and then revealed _in its entirety_ to
_both_ P1 and P2, _before_ the game begins. These games are thus _complete
information_ games. We also assume that P1 and P2 are both intelligent agents
who play _optimally_ , i.e. when a game is destined to end in a decision, the
player who wins tries to end the game in as few rounds as possible, while the
player who loses tries to prolong the game as much as possible.

###  1.2. Motivations for studying these games

The primary motivation for studying these games stems from our interest in
examining how allowing each player more room to maneuver in each round ends up
affecting the probability of each possible outcome (these outcomes being a win
for P1, a loss for P1, and a draw for both players). It is also imperative
that we view the $k$-jump versions of the games as broad generalizations of
the versions studied in [15].

It turns out that it is rather hard to draw a direct, analytical comparison
between the ($1$-jump) normal and misère games studied in [15] on one hand and
the corresponding $k$-jump versions (for $k\geqslant 2$) on the other, even
though our intuitions may suggest otherwise. Almost all such questions remain
open and unexplored. For the commonly studied regime where the offspring
distribution $\chi$ of the GW tree is Poisson$(\lambda$), we analytically
compare the $1$-jump normal game with the $2$-jump normal game for
sufficiently large values of $\lambda$ in Theorem 1.9. Further comparisons can
be drawn visually by plotting the curves corresponding to
$\operatorname{n\ell}_{1}$, $\operatorname{n\ell}_{2}$ and
$\operatorname{n\ell}_{3}$, the curves corresponding to
$\operatorname{nw}_{1}$, $\operatorname{nw}_{2}$ and $\operatorname{nw}_{3}$,
and the curves corresponding to $\operatorname{nd}_{1}$,
$\operatorname{nd}_{2}$ and $\operatorname{nd}_{3}$, as functions of
$\lambda$, when $\chi$ is Poisson$(\lambda)$ (see Figures 1, 3 and 3). Here
$\operatorname{n\ell}_{k}$, $\operatorname{nw}_{k}$ and
$\operatorname{nd}_{k}$ respectively denote the probabilities of P1’s loss,
P1’s win, and a draw in the $k$-jump normal game (see §1.3 for detailed
definitions).

Figure 1. Comparing probabilities $\operatorname{n\ell}_{k}$ of P1 losing as
functions of $\lambda$, for $k=1,2,3$

Figure 2. Comparing probabilities $\operatorname{nw}_{k}$ of P1 winning as
functions of $\lambda$, for $k=1,2,3$

Figure 3. Comparing probabilities $\operatorname{nd}_{k}$ of draw as functions
of $\lambda$, for $k=1,2,3$

While direct comparisons seem difficult to deduce analytically for $k\geqslant
3$, it is illuminating to explore the many characteristics of the functions
$H_{k}$ (see Theorem 1.1) and $J_{k}$ (see Theorem 1.2) whose minimum positive
fixed points equal the probabilities $\operatorname{n\ell}_{k}$ and
$\operatorname{m\ell}_{k}$ of P1 losing the $k$-jump normal game and the
$k$-jump misère game respectively. It is instructive to examine how these
functions behave for various values of $k\in\mathbb{N}$. Analyzing these
functions is the key to understanding the probabilities of the various
possible outcomes of the $k$-jump games, and comparing and contrasting $H_{k}$
(respectively $J_{k}$) for different values of $k$ is instrumental in
comparing and contrasting the games themselves.

For a quick appraisal of how $H_{k}$ (respectively $J_{k}$) behaves as we vary
$k$, and the pivotal roles they play in determining various characteristics of
the probabilities $\operatorname{n\ell}_{k}$, $\operatorname{nw}_{k}$,
$\operatorname{nd}_{k}$ (respectively $\operatorname{m\ell}_{k}$,
$\operatorname{mw}_{k}$, $\operatorname{md}_{k}$), we mention here some of our
findings that have been described in detail later on in the paper. In §2.2, we
show that $H_{k}$ (and likewise, $J_{k}$, as mentioned in §3) is increasing on
$[0,c_{k-1}]\subset[0,1]$, where $\\{[0,c_{k}]\\}_{k}$ forms a sequence of
steadily shrinking intervals (see Lemma 2.2). The proof is far more involved
for higher values of $k$ than when we consider $k=1$ (in fact, for $k=1$, we
have $H_{1}$ and $J_{1}$ defined and increasing on the entire interval
$[0,1]$). In §6, it takes considerable work to show that when the offspring
distribution $\chi$ is Poisson$(\lambda)$ with $\lambda\geqslant 2$, the
function $H_{2}$ is strictly convex on the interval $[0,c_{2}]$. Plotting
$H_{2}$ for various values of $\lambda$ (see, for example, Figure 4, where
$\lambda=5$ has been considered) seems to suggest that $H_{2}$ is, in fact,
_not_ convex on the interval $(c_{2},c_{1}]$. When $\chi$ is
Poisson$(\lambda)$, the second assertion of Theorem 1.4 sheds light on the
decay rate of $\operatorname{n\ell}_{k}$ for _all_ values of $k$ as
$\lambda\rightarrow\infty$, whereas Theorem 1.6 provides an even stronger
result on the decay rate of $\operatorname{n\ell}_{k}$ when $k=2$. It is
through a careful analysis of the derivative of $H_{k}$ at the point $c_{k}$
that we obtain Theorems 1.4 and 1.5, both of which shed light on the _phase
transition_ phenomenon pertaining to the draw probability
$\operatorname{nd}_{k}$ when $\chi$ is Poisson$(\lambda)$, i.e. how the value
of $\operatorname{nd}_{k}$ evolves from $0$ to strictly positive as $\lambda$
is increased gradually. The magnitude of $H^{\prime}_{k}(c_{k})$ also plays a
role, in Theorem 1.10, in determining if the expected duration of a $k$-jump
normal game is finite. Finally, comparing $H_{2}$ with $J_{2}$ enables us to
compare the probabilities of the various outcomes of the $2$-jump normal game
with those of the $2$-jump misère game in Theorem 1.7, while comparing $H_{2}$
with $H_{1}$ allows a similar comparison between the $1$-jump normal game and
the $2$-jump normal game in Theorem 1.9.

Figure 4. The function $H_{2}$ is _not_ convex between $c_{2}\approx 0.095$
and $c_{1}\approx 0.265$, when $\chi$ is Poisson$(5)$

A second, and perhaps equally compelling, motivation arises from viewing these
games as tools for understanding a generalized notion of _finite state tree
automata_ (henceforth abbreviated as FSTA). As such, the simplest FSTA is a
state machine that comprises a _finite_ set $\Sigma=\\{1,2,\ldots,r\\}$ of
_states_ or _colours_ , and a _rule_ $f_{1}$, which is a function
$:\mathbb{N}_{0}^{r}\rightarrow\Sigma$, such that if a vertex $v$ in a rooted
tree has $n_{i}$ children that are in state $i$ for each $i\in\Sigma$, then
the state of $v$ is given by $f_{1}(n_{1},n_{2},\ldots,n_{r})$. Given a fixed
$k\in\mathbb{N}$, a _generalized depth- $k$ FSTA_ (henceforth abbreviated as a
$k$-GFSTA), with rule $f_{k}$, extends the above definition as follows: given
a rooted tree $T$, a vertex $v$ of $T$ and an assignment
$\sigma:\Gamma_{k}(v)\rightarrow\Sigma$ of states to the vertices of
$\Gamma_{k}(v)$ (recall from above that $\Gamma_{k}(v)$ is the set of all
descendants of $v$, other than $v$ itself, that are at distance at most $k$
away from $v$), the state of $v$, as dictated by this $k$-GFSTA, is given by
$f_{k}\big{(}(\sigma(w):w\in\Gamma_{k}(v))\big{)}$. For instance, a rule
$f_{k}:\mathbb{N}_{0}^{r}\rightarrow\Sigma$ may be considered such that if
there are $n_{i}$ vertices in $\Gamma_{k}(v)$ that are in state $i$ for each
$i\in\Sigma$, then the state of $v$ is given by
$f_{k}(n_{1},n_{2},\ldots,n_{r})$. Denoting by $\operatorname{NW}_{k}$ the set
of vertices $v$ such that P1 wins the $k$-jump normal game that starts at $v$,
by $\operatorname{NL}_{k}$ the set of vertices $v$ such that P1 loses the
$k$-jump normal game that starts at $v$, and by $\operatorname{ND}_{k}$ the
set of vertices $v$ such that the $k$-jump normal game that starts at $v$ ends
in a draw (see also §1.3 for these definitions), we obtain a $k$-GFSTA with
the state space
$\Sigma=\\{\operatorname{NW}_{k},\operatorname{NL}_{k},\operatorname{ND}_{k}\\}$
and the rule $f_{k}$ defined by (2.1) and (2.2). Yet another $k$-GFSTA is
obtained from the recurrence relations (3.1) and (3.2) arising from the
$k$-jump misère game. It is evident that studying these games may pave the way
for a deeper understanding of $k$-GFSTAs for large values of $k$, the
associated _recursive distributional equations_ and their _fixed points_.

A fixed point of an FSTA is a probability distribution $\nu$ on the state
space $\Sigma$ such that if the children of the root $\phi$ of a GW tree
$\mathcal{T}_{\chi}$ are assigned i.i.d. states from $\Sigma$, each following
the common law $\nu$, then the _induced_ (random) state (via the rule $f_{1}$)
at $\phi$ also follows the law $\nu$. Let $\mathcal{T}$ be the set of _all_
possible rooted trees, and let, for any vertex $v$ in a rooted tree $T$,
$T(v)$ denote the subtree that comprises $v$ and all its descendants. A map
$\iota:\mathcal{T}\rightarrow\Sigma$ is called an _interpretation_ of the FSTA
if assigning the state or colour $\iota(T(v))$ to each vertex $v$ of _any_
arbitrary rooted tree $T$ gives us a colouring of the _entire_ tree $T$ that
is consistent with the rule $f_{1}$ of the FSTA. We call a fixed point $\nu$
of the FSTA _interpretable_ if there exists an interpretation $\iota$ of the
FSTA with $\iota(\mathcal{T}_{\chi})$ following the law $\nu$. Necessary and
sufficient conditions for fixed points of a certain class of FSTAs to be
interpretable were addressed in [18]. We mention here that the notion of
interpretability ties in closely with the concept of _endogeny_ (see, for
instance, §2.4, and in particular, Definition 7, of [1], as well as [21],
[22], [23], [30], [31]).

Let us understand how one may extend the above-mentioned notion of fixed
points to the case of the $2$-GFSTA obtained from the $2$-jump normal game
(with its rule $f_{2}$ given by (2.1) and (2.2) for $k=2$). Let
$\mathcal{C}_{0,1}$ denote the set of all vertices $v$ such that $v$ has at
least one child whose state is $\operatorname{NL}_{2}$, $\mathcal{C}_{0,2}$
the set of all vertices $v$ such that $v$ has no child in state
$\operatorname{NL}_{2}$ but at least one grandchild in state
$\operatorname{NL}_{2}$, and $\mathcal{C}_{1,2}$ the set of all vertices $v$
such that every child of $v$ is in state $\operatorname{NW}_{2}$ and at least
one grandchild of $v$ is in state $\operatorname{NL}_{2}$. It is immediate
from these definitions that $\mathcal{C}_{1,2}\subset\mathcal{C}_{0,2}$. We
mention here that these subsets are analogous to those defined in (2.6) (with
the superscripts $n$, $n+1$ etc. removed).

We now describe the recurrence relations (these have been elaborated upon in
§2 for the general case of _any_ $k\in\mathbb{N}$) that tie the above-
mentioned subsets together. A vertex $v$ is in $\operatorname{NW}_{2}$ if and
only if it is either in $\mathcal{C}_{0,1}$ or $\mathcal{C}_{0,2}$, which is
equivalent to saying that $v$ either has a child that is in
$\operatorname{NL}_{2}$ or a child that is in $\mathcal{C}_{0,1}$. A vertex
$v$ is in $\operatorname{NL}_{2}$ if and only if either $v$ is childless or
every child of $v$ is in $\mathcal{C}_{1,2}$. In all other situations, $v$ is
in $\operatorname{ND}_{2}$. We further note that $v$ is in $\mathcal{C}_{0,1}$
if and only if at least one child of $v$ belongs to $\operatorname{NL}_{2}$.
It is in $\mathcal{C}_{1,2}$ if and only if all its children are in
$\operatorname{NW}_{2}$ and at least one of its children is in
$\mathcal{C}_{0,1}$, which is equivalent to saying that all children of $v$
are in $\mathcal{C}_{0,1}\cup\mathcal{C}_{0,2}$ and at least one of them is in
$\mathcal{C}_{0,1}$. Finally, $v$ is in $\mathcal{C}_{0,2}$ if none of its
children is in $\operatorname{NL}_{2}$ but at least one of them is in
$\mathcal{C}_{0,1}$.

We assign i.i.d. states from the state space
$\Sigma=\\{\mathcal{C}_{0,1},\mathcal{C}_{1,2},\mathcal{C}_{0,2}\setminus\mathcal{C}_{1,2},\operatorname{NL}_{2},\operatorname{ND}_{2}\\}$
to the children of the root $\phi$ of the GW tree $\mathcal{T}_{\chi}$
according to the common law $\nu$, where we set
$p_{0,1}=\nu[\mathcal{C}_{0,1}]$, $p_{1,2}=\nu[\mathcal{C}_{1,2}]$,
$p_{0,2}=\nu[\mathcal{C}_{0,2}]$ (so that
$\nu[\mathcal{C}_{0,2}\setminus\mathcal{C}_{1,2}]=p_{0,2}-p_{1,2}$),
$\operatorname{n\ell}_{2}=\nu[\operatorname{NL}_{2}]$ and
$\operatorname{nd}_{2}=\nu[\operatorname{ND}_{2}]$. For $\nu$ to be a fixed
point of this $2$-GFSTA, the random state induced at $\phi$ must follow the
law $\nu$ as well. This requires that the following equations, derived from
the above-mentioned recurrence relations, hold:

$\displaystyle\operatorname{n\ell}_{2}=\sum_{m=0}^{\infty}p_{1,2}^{m}\chi(m)=G(p_{1,2}),$
(1.1) $\displaystyle
p_{0,1}=\sum_{m=1}^{\infty}\left[1-\left(1-\operatorname{n\ell}_{2}\right)^{m}\right]\chi(m)=1-G\left(1-\operatorname{n\ell}_{2}\right),$
(1.2) $\displaystyle
p_{1,2}=\sum_{m=1}^{\infty}\left[\left(p_{0,1}+p_{0,2}\right)^{m}-p_{0,2}^{m}\right]\chi(m)=G\left(p_{0,1}+p_{0,2}\right)-G\left(p_{0,2}\right),$
(1.3) $\displaystyle
p_{0,2}=\sum_{m=1}^{\infty}\left[\left(1-\operatorname{n\ell}_{2}\right)^{m}-\left(1-\operatorname{n\ell}_{2}-p_{0,1}\right)^{m}\right]\chi(m)=G\left(1-\operatorname{n\ell}_{2}\right)-G\left(1-\operatorname{n\ell}_{2}-p_{0,1}\right),$
(1.4)

where $\chi(m)$ denotes the probability of $\phi$ having $m$ children, for
$m\in\mathbb{N}_{0}$, and $G$ indicates the probability generating function
corresponding to $\chi$. The above equations are used to solve for the fixed
point $\nu$. Note that we do not need a separate equation for
$\operatorname{nd}_{2}$ since
$\operatorname{nd}_{2}=1-\operatorname{n\ell}_{2}-p_{0,1}-p_{0,2}$.

It is obvious that the sets $\mathcal{C}_{0,1}$, $\mathcal{C}_{1,2}$,
$\mathcal{C}_{0,2}\setminus\mathcal{C}_{1,2}$, $\operatorname{NL}_{2}$ and
$\operatorname{ND}_{2}$ that arise out of the $2$-jump normal game itself
provide an interpretation $\iota$ of the above $2$-GFSTA with
$\iota(\mathcal{T}_{\chi})$ following the law $\nu$. But there are questions
pertaining to interpretability that remain open when the system of equations
constituting (1.1), (1.2), (1.3) and (1.4) does not yield a unique solution
for $\nu$. For instance, Theorem 1.1 asserts that $\operatorname{n\ell}_{2}$
is the minimum positive fixed point of $H_{2}$, whereas Corollary 4.2 tells us
that $c_{2}$ is also a fixed point of $H_{2}$. From Theorem 1.5, we see that
when $\chi$ is Poisson$(\lambda)$, we have $\operatorname{n\ell}_{2}<c_{2}$
for all $\lambda>\lambda_{c}$ for $\lambda_{c}\approx 2.41$. So now we ask: is
the probability distribution obtained by replacing $\operatorname{n\ell}_{2}$
by $c_{2}$ (and computing the corresponding values of $p_{0,1}$, $p_{0,2}$,
$p_{1,2}$ and $\operatorname{nd}_{2}$ from (1.1), (1.2), (1.3) and (1.4))
interpretable in the sense described earlier (see the definition for
interpretability of fixed points of FSTAs in the previous page)? For higher
values of $k$, $H_{k}$ may have several fixed points other than these two, and
understanding the interpretability of the corresponding probability
distributions is also of interest to us.

A third motivation for investigating these games arises from our speculation
that these games may serve as precursors to more complicated versions where,
for example, each round involves choosing one of P1 and P2 uniformly randomly
and then allowing her to make a move (where a move involves relocating the
token from its current vertex to a child of that vertex), but ensuring that no
player is chosen for more than $k$ consecutive rounds, where $k$ is a pre-
fixed positive integer.

###  1.3. Notations and some definitions

Given a rooted tree $T$, we denote by $V(T)$ its vertex set. As previously
mentioned, for $u\in V(T)$, we define $\Gamma_{i}(u)$, for $i\in\mathbb{N}$,
as the set of descendants $v$ of $u$ (not including $u$ itself) with
$\rho(u,v)\leqslant i$, where $\rho$ denotes the graph metric on $T$. As
mentioned above in §1.2, we shall denote by $G$ the probability generating
function (pgf) of the offspring distribution $\chi$ of the GW tree
$\mathcal{T}_{\chi}$, i.e. $G(x)=\sum_{i=0}^{\infty}x^{i}\chi(i)$ for any
$x\in[0,1]$. All offspring distributions $\chi$ considered in this paper
satisfy $0<\chi(0)<1$.

Given $k\in\mathbb{N}$, we define $\operatorname{NL}_{k}$ (or simply
$\operatorname{NL}$ when the value of $k$ is clear from the context) to be the
set of all vertices $v\in V(\mathcal{T}_{\chi})$ such that if $v$ is the
initial vertex, then P1, who plays the first round, loses the $k$-jump normal
game. Likewise, let $\operatorname{NW}_{k}$ (or simply $\operatorname{NW}$)
denote the set of all $v\in V(\mathcal{T}_{\chi})$ such that if $v$ is the
initial vertex, then P1, playing the first round, wins the $k$-jump normal
game. Let $\operatorname{ND}_{k}$ (or simply $\operatorname{ND}$) denote the
set of all $v\in V(\mathcal{T}_{\chi})$ such that if $v$ is the initial
vertex, the $k$-jump normal game ends in a draw.

It is important to consider refinements of the above subsets of vertices in
order to understand the probabilities of the game’s outcomes better. For every
$n\in\mathbb{N}$, we define $\operatorname{NL}_{k}^{(n)}$ (or
$\operatorname{NL}^{(n)}$ when the value of $k$ is unambiguous from the
context) to be the subset of $\operatorname{NL}_{k}$ comprising vertices $v$
such that if $v$ is the initial vertex, the $k$-jump normal game lasts for
less than $n$ rounds. Likewise, $\operatorname{NW}_{k}^{(n)}$ (or simply
$\operatorname{NW}^{(n)}$) is the subset of $\operatorname{NW}_{k}$ comprising
vertices $v$ such that the $k$-jump normal game starting at $v$ ends in less
than $n$ rounds. We define
$\operatorname{ND}^{(n)}=\operatorname{ND}_{k}^{(n)}=V(\mathcal{T}_{\chi})\setminus\left[\operatorname{NL}_{k}^{(n)}\cup\operatorname{NW}_{k}^{(n)}\right]$,
or in other words, $v\in\operatorname{ND}_{k}^{(n)}$ iff the $k$-jump normal
game starting at $v$ lasts for at least $n$ rounds. We set
$\operatorname{NL}_{k}^{(0)}=\operatorname{NW}_{k}^{(0)}=\emptyset$. By
definition, we have
$\operatorname{NL}_{k}^{(n)}\subset\operatorname{NL}_{k}^{(n+1)}\text{ and
}\operatorname{NW}_{k}^{(n)}\subset\operatorname{NW}_{k}^{(n+1)}$ for all
$n\in\mathbb{N}_{0}$.

We define $\operatorname{n\ell}_{k}$ to be the probability of the event that
the root $\phi$ of $\mathcal{T}_{\chi}$ belongs to $\operatorname{NL}_{k}$,
whereas for each $n\in\mathbb{N}$, we define $\operatorname{n\ell}_{k}^{(n)}$
to be the probability of the event that $\phi$ belongs to
$\operatorname{NL}_{k}^{(n)}$. Likewise, we define $\operatorname{nw}_{k}$,
$\operatorname{nw}_{k}^{(n)}$, $\operatorname{nd}_{k}$ and
$\operatorname{nd}_{k}^{(n)}$. From above, we have
$\operatorname{n\ell}_{k}^{(0)}=\operatorname{nw}_{k}^{(0)}=0$. Once again,
the subscript $k$ is dropped whenever its value is clear from the context.
From the last line of the previous paragraph, we get

$\displaystyle\operatorname{n\ell}_{k}^{(n)}\leqslant\operatorname{n\ell}_{k}^{(n+1)}\text{
and }\operatorname{nw}_{k}^{(n)}\leqslant\operatorname{nw}_{k}^{(n+1)}\text{
for all }n\in\mathbb{N}_{0}.$ (1.5)

The corresponding subsets for the $k$-jump misére games are denoted by
$\operatorname{ML}_{k}$, $\operatorname{MW}_{k}$, $\operatorname{MD}_{k}$,
$\operatorname{ML}_{k}^{(n)}$, $\operatorname{MW}_{k}^{(n)}$ and
$\operatorname{MD}_{k}^{(n)}$, and the corresponding probabilities by
$\operatorname{m\ell}_{k}$, $\operatorname{mw}_{k}$, $\operatorname{md}_{k}$,
$\operatorname{m\ell}_{k}^{(n)}$, $\operatorname{mw}_{k}^{(n)}$ and
$\operatorname{md}_{k}^{(n)}$ (as above, the subscript is removed when the
value of $k$ is clear from the context).

###  1.4. Main results

We begin by introducing a couple of sequences of functions that are defined
recursively. The first is $\\{F_{i}\\}_{i\in\mathbb{N}_{0}}$, where
$F_{0}(x)=1$ for $x\in[0,1]$, and $F_{i}:[0,c_{i-1}]\rightarrow[0,1]$, for all
$i\in\mathbb{N}$, is defined as

$\displaystyle F_{i}(x)=G(F_{i-1}(x)-x),\ x\in[0,c_{i-1}],$ (1.6)

where recall that $G$ is the pgf of $\chi$, and $c_{i}$ is the unique (as
shown in Lemma 2.2) fixed point of $F_{i}$. The second sequence of functions
$\\{g_{i}\\}_{i\in\mathbb{N}}$ is defined as follows. The function
$g_{1}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ is defined as $g_{1}(x,y)=x-y$,
and having defined $g_{i-1}$ for any $i\geqslant 2$, we define
$g_{i}:\mathcal{D}_{i}\rightarrow\mathbb{R}$ as

$\displaystyle
g_{i}(x_{0},x_{1},\ldots,x_{i})=G(g_{i-1}(x_{0},x_{2},\ldots,x_{i}))-G(g_{i-1}(x_{1},x_{2},\ldots,x_{i})),\
(x_{0},x_{1},\ldots,x_{i})\in\mathcal{D}_{i},$ (1.7)

where the sets $\mathcal{D}_{i}$ are also recursively defined, as follows:

$\displaystyle\mathcal{D}_{i}=\\{(x_{0},x_{1},\ldots,x_{i}):g_{i-1}(x_{0},x_{2},\ldots,x_{i})\in[0,1],g_{i-1}(x_{1},x_{2},\ldots,x_{i})\in[0,1]\\}.$
(1.8)

As an example, $\mathcal{D}_{2}=\\{(x_{0},x_{1},x_{2}):x_{2}\leqslant
x_{0}\leqslant x_{2}+1,x_{2}\leqslant x_{1}\leqslant x_{2}+1\\}$. The
motivation behind defining $\mathcal{D}_{i}$ this way is to simply ensure that
the arguments $g_{i-1}(x_{0},x_{2},\ldots,x_{i})$ and
$g_{i-1}(x_{1},x_{2},\ldots,x_{i})$ of the function $G$ in (1.7) belong to the
domain $[0,1]$ on which $G$ is defined.

######  Theorem 1.1.

Consider the $k$-jump normal game for $k\in\mathbb{N}$. Define the function
$H_{k}:[0,c_{k-1}]\rightarrow[0,1]$ as

$\displaystyle H_{k}(x)=G(g_{k}(F_{0}(x),F_{1}(x),\ldots,F_{k}(x))).$ (1.9)

Then $\operatorname{n\ell}_{k}$ is the minimum positive fixed point of
$H_{k}$. Moreover, $\operatorname{nw}_{k}=1-F_{k}(\operatorname{n\ell}_{k})$.

Some discussions are in order regarding the functions defined above, as they
form an integral part of the results in this paper. First, we compare the
findings of Theorem 1.9 with those of Theorem 1 (i) of [15]. Let us define the
function $R(x)=1-G\big{(}1-G(x)\big{)}$ for $x\in[0,1]$. According to the
notation used in this paper, Theorem 1 (i) of [15] states that
$1-\operatorname{n\ell}_{1}$ equals the maximum fixed point and
$\operatorname{nw}_{1}$ the minimum fixed point of $R(x)$ in $[0,1]$. From our
definitions of $g_{1}$ and $F_{0}$, (1.6) and (1.9), we see that
$H_{1}(x)=G\big{(}1-G(1-x)\big{)}$. For any $y\in[0,1]$, we observe that $1-y$
is a fixed point of $R(x)$ if and only if

$1-y=1-G\big{(}1-G(1-y)\big{)}\Longleftrightarrow
y=G\big{(}1-G(1-y)\big{)}=H_{1}(y),$

which is equivalent to $y$ being a fixed point of $H_{1}(x)$. This observation
immediately reveals that $\operatorname{n\ell}_{1}$ is the minimum fixed point
of $H_{1}(x)$ in $[0,1]$ if and only if $1-\operatorname{n\ell}_{1}$ is the
maximum fixed point of $R(x)$ in $[0,1]$, i.e. our conclusion about
$\operatorname{n\ell}_{1}$ from Theorem 1.1 matches with what Theorem 1 (i) of
[15] yields. Moreover, for every $y\in[0,1]$ that is a fixed point of
$H_{1}(x)$, we observe that

$\displaystyle
1-F_{1}(y)=1-G(1-y)=1-G\big{(}1-H_{1}(y)\big{)}=R\big{(}1-G(1-y)\big{)}=R(1-F_{1}(y)),$

showing that $1-F_{1}(y)$ is a fixed point of $R(x)$ in $[0,1]$. Conversely,
under the assumption that $G$ is a strictly increasing function on $[0,1]$
(which is true whenever $\chi(0)<1$), we observe that $1-F_{1}(y)$ is a fixed
point of $R(x)$ in $[0,1]$, for $y\in[0,1]$, if and only if

$\displaystyle R\big{(}1-F_{1}(y)\big{)}=1-F_{1}(y)\Longleftrightarrow
G\big{(}1-G\big{(}1-F_{1}(y)\big{)}\big{)}=F_{1}(y)$
$\displaystyle\Longleftrightarrow
G\big{(}1-G\big{(}1-G(1-y)\big{)}\big{)}=G(1-y)\Longleftrightarrow
1-G\big{(}1-G(1-y)\big{)}=1-y\Longleftrightarrow H_{1}(y)=y,$

thus showing us that $y$ is a fixed point of $H_{1}(x)$ in $[0,1]$. The last
two observations tell us that $y$ is a fixed point of $H_{1}(x)$ in $[0,1]$ if
and only if $1-F_{1}(y)$ is a fixed point of $R(x)$ in $[0,1]$. Since $F_{1}$
is strictly decreasing on $[0,1]$ and $\operatorname{n\ell}_{1}$ has already
been shown above to be the minimum fixed point of $H_{1}(x)$ in $[0,1]$, this
establishes that $1-F_{1}(\operatorname{n\ell}_{1})$ must be the minimum fixed
point of $R(x)$ in $[0,1]$, thus showing that our conclusion about
$\operatorname{nw}_{1}$ from Theorem 1.1 matches with what Theorem 1 (i) of
[15] yields.

We now try to give the reader an idea as to how the functions in (1.6), (1.7)
and (1.9) come to be defined, without going into the actual technical details
(which have been laid out fully in the proof of Theorem 1.1 in §2), and to
this end, we focus on the case of $k=2$. This case has already been discussed,
to some extent, in §1.2. In §1.2, along with $\operatorname{NW}_{2}$,
$\operatorname{NL}_{2}$ and $\operatorname{ND}_{2}$, we defined the subsets
$\mathcal{C}_{0,1}$, $\mathcal{C}_{0,2}$ and $\mathcal{C}_{1,2}$, described
the recurrence relations that tie these subsets to one another, and derived
Equations (1.1), (1.2), (1.3) and (1.4) that relate the probabilities
$\operatorname{n\ell}_{2}$, $\operatorname{nd}_{2}$, $p_{0,1}$, $p_{0,2}$ and
$p_{1,2}$ with each other (where $p_{i,j}$ is the probability that the root of
$\mathcal{T}_{\chi}$ belongs to $\mathcal{C}_{i,j}$, for $0\leqslant
i<j\leqslant 2$).

From the definition of $F_{0}$ and (1.6), we have
$F_{1}(\operatorname{n\ell}_{2})=G(1-\operatorname{n\ell}_{2})$ and
$F_{2}(\operatorname{n\ell}_{2})=G\big{(}G(1-\operatorname{n\ell}_{2})-\operatorname{n\ell}_{2}\big{)}$.
Using the expression for $F_{1}$ and the definition of $g_{1}$, it becomes
immediate from (1.2) that
$p_{0,1}=g_{1}\big{(}F_{0}(\operatorname{n\ell}_{2}),F_{1}(\operatorname{n\ell}_{2})\big{)}$.
Using the expressions for $F_{1}$ and $F_{2}$ and Equations (1.2) and (1.4),
we have

$\displaystyle p_{0,2}$
$\displaystyle=G(1-\operatorname{n\ell}_{2})-G(1-p_{0,1}-\operatorname{n\ell}_{2})=F_{1}(\operatorname{n\ell}_{2})-G(G(1-\operatorname{n\ell}_{2})-\operatorname{n\ell}_{2})$
$\displaystyle=F_{1}(\operatorname{n\ell}_{2})-F_{2}(\operatorname{n\ell}_{2})=g_{1}\big{(}F_{1}(\operatorname{n\ell}_{2}),F_{2}(\operatorname{n\ell}_{2})\big{)}.$

From (1.2), (1.3), (1.4) and (1.7), we see that

$\displaystyle p_{1,2}$
$\displaystyle=G\big{(}1-F_{2}(\operatorname{n\ell}_{2})\big{)}-G\big{(}g_{1}\big{(}F_{1}(\operatorname{n\ell}_{2}),F_{2}(\operatorname{n\ell}_{2})\big{)}\big{)}$
$\displaystyle=G\big{(}g_{1}\big{(}F_{0}(\operatorname{n\ell}_{2}),F_{2}(\operatorname{n\ell}_{2})\big{)}\big{)}-G\big{(}g_{1}\big{(}F_{1}(\operatorname{n\ell}_{2}),F_{2}(\operatorname{n\ell}_{2})\big{)}\big{)}=g_{2}\big{(}F_{0}(\operatorname{n\ell}_{2}),F_{1}(\operatorname{n\ell}_{2}),F_{2}(\operatorname{n\ell}_{2})\big{)}.$

These ideas extend to the general case of arbitrary $k\in\mathbb{N}$, with the
identity
$p_{i,j,n}=g_{i+1}\big{(}F_{j-i-1}(\operatorname{n\ell}_{k}),F_{j-i}(\operatorname{n\ell}_{k}),F_{k-i+1}(\operatorname{n\ell}_{k}),\ldots,F_{k}(\operatorname{n\ell}_{k})\big{)}$
being true for all $0\leqslant i<j\leqslant k$ (see Lemma 2.3 and its proof
for a better understanding of this fact). We now use the expression for
$p_{1,2}$ derived above, (1.1) and (1.9) to conclude that
$\operatorname{n\ell}_{2}$ is indeed a fixed point of $H_{2}(x)$ in $[0,1]$.
Although the proof of Theorem 1.1 is rather involved when arbitrary values of
$k$ are considered, we hope that the above exposition, for $k=2$, helps to
shed some light on how our argument proceeds, how the recursive definitions of
the functions in (1.6), (1.7) and (1.9) arise etc.

In order to state, for the case of $k$-jump misère games, the result that is
analogous to Theorem 1.1, we introduce yet another sequence of functions
$\\{\gamma_{i}\\}_{i\in\mathbb{N}}$ that bears significant resemblance to
(1.7). Setting $\gamma_{1}\equiv g_{1}$, for each $i\geqslant 2$ we define
$\gamma_{i}:\mathcal{D}^{\prime}_{i}\rightarrow\mathbb{R}$ recursively as

$\displaystyle\gamma_{i}(x_{0},x_{1},\ldots,x_{i})=G\left(\chi(0)+\gamma_{i-1}(x_{0},x_{2},\ldots,x_{i})\right)-G\left(\chi(0)+\gamma_{i-1}(x_{1},x_{2},\ldots,x_{i})\right),$
(1.10)

where the sets $\mathcal{D}^{\prime}_{i}$ are recursively defined as
$\mathcal{D}^{\prime}_{i}=\\{(x_{0},x_{1},\ldots,x_{i}):\chi(0)+\gamma_{i-1}(x_{0},x_{2},\ldots,x_{i})\in[0,1],\chi(0)+\gamma_{i-1}(x_{1},x_{2},\ldots,x_{i})\in[0,1]\\}$.

######  Theorem 1.2.

Consider the $k$-jump misère game, $k\in\mathbb{N}$. Define the function
$J_{k}:[0,c_{k-1}]\rightarrow[0,1]$ as

$J_{k}(x)=G\left(\chi(0)+\gamma_{k}(F_{0}(x),F_{1}(x),\ldots,F_{k}(x))\right)-\chi(0).$
(1.11)

Then $\operatorname{m\ell}_{k}$ is the minimum positive fixed point of
$J_{k}$. Moreover,
$\operatorname{mw}_{k}=1-F_{k}(\operatorname{m\ell}_{k})+\chi(0)$.

We mention here, for the convenience of the reader, that much of the proof of
Theorem 1.2 unfolds the same way as that of Theorem 1.1, and the motivations
behind the recursive defintions of the functions in (1.10) and (1.11) are very
similar to those behind the recursive definitions of the functions in (1.7)
and (1.9) respectively.

Theorem 1.3 provides bounds on $\operatorname{n\ell}_{k}$ and
$\operatorname{m\ell}_{k}$, and necessary and sufficient conditions for the
draw probabilities $\operatorname{nd}_{k}$ and $\operatorname{md}_{k}$ to be
positive. Recall that $c_{k}$ is the (unique, by Lemma 2.2) fixed point of
$F_{k}$.

######  Theorem 1.3.

For every $k\in\mathbb{N}$, we have $\chi(0)<\operatorname{n\ell}_{k}\leqslant
c_{k}$ and $\operatorname{m\ell}_{k}\leqslant\hat{c}_{k}$, where $\hat{c}_{k}$
is the unique point of intersection between $y=F_{k}(x)$ and
$y=J_{k}(x)+\chi(0)$ in $(0,c_{k-1})$. Moreover, $\operatorname{nd}_{k}>0$ if
and only if $\operatorname{n\ell}_{k}<c_{k}$ and $\operatorname{md}_{k}>0$ if
and only if $\operatorname{m\ell}_{k}<\hat{c}_{k}$.

It is worthwhile to note that when the offspring distribution $\chi$ of
$\mathcal{T}_{\chi}$ has expectation bounded above by $1$,
$\mathcal{T}_{\chi}$ is finite almost surely, which, for any fixed $k$, forces
the $k$-jump normal game starting at the root $\phi$ of $\mathcal{T}_{\chi}$
to end in a finite number of rounds almost surely. Consequently, the
probability of draw in such a situation is $0$. In particular, this tells us
that when $\chi$ is Poisson$(\lambda)$ for $\lambda\leqslant 1$, the
probability that the $k$-jump normal game results in a draw is $0$. Theorem
1.4 is of an asymptotic nature, asserting that when $\chi$ is
Poisson$(\lambda)$, the probability of the $k$-jump normal game ending in a
draw eventually becomes strictly positive as we keep increasing $\lambda$.
Evidently, this gives rise to a phase transition phenomenon in that, the
probability $\operatorname{nd}_{k}=\operatorname{nd}_{k,\lambda}$ of the event
that a $k$-jump normal game played on a rooted Galton-Watson tree with
Poisson$(\lambda)$ offspring results in a draw goes from being equal to $0$
for $\lambda\leqslant 1$ to being strictly positive for all $\lambda$ large
enough.

######  Theorem 1.4.

Fix any $k\in\mathbb{N}$. When the offspring distribution $\chi$ is
Poisson$(\lambda)$, we have
$\operatorname{nd}_{k}=\operatorname{nd}_{k,\lambda}>0$ for all $\lambda$
sufficiently large. We also have
$\lambda^{k-1}\operatorname{n\ell}_{k}=\lambda^{k-1}\operatorname{n\ell}_{k,\lambda}\rightarrow
0$ as $\lambda\rightarrow\infty$.

Theorem 1.5 provides a more nuanced insight into the phase transition
phenomenon when $k=2$:

######  Theorem 1.5.

For $\lambda\geqslant 2$, the function $H_{2}=H_{2,\lambda}$ is strictly
convex on the interval $[0,c_{2}]=[0,c_{2,\lambda}]$. The slope of
$H_{2,\lambda}$ at $c_{2,\lambda}$ is strictly increasing as a function of
$\lambda$, for all $\lambda\geqslant 1$. As a consequence of these two facts,
there is a unique _critical_ $\lambda_{c}\approx 2.41$ such that for all
$2\leqslant\lambda<\lambda_{c}$ we have
$\operatorname{nd}_{2}=\operatorname{nd}_{2,\lambda}=0$, and for all
$\lambda>\lambda_{c}$, we have $\operatorname{nd}_{2,\lambda}>0$.

The next result is an especially strong one as it sheds light on the rate of
decay of $\operatorname{n\ell}_{k,\lambda}$, when $k=2$ and the offspring
distribution is Poisson$(\lambda)$, as $\lambda\rightarrow\infty$.

######  Theorem 1.6.

We have
$\lim_{\lambda\rightarrow\infty}\lambda^{i}\operatorname{n\ell}_{2,\lambda}=0$
for _all_ $i\in\mathbb{N}$.

Theorem 1.7 compares the $2$-jump normal game with the $2$-jump misère game
(see Proposition LABEL:prop:ml_2_nl_2_more_refined for a more precise
description of the values of $\lambda$ for which the first of the three
inequalities is shown to hold analytically), while Theorem 1.9 compares the
$1$-jump normal game with the $2$-jump normal game, when all of these games
are played on $\mathcal{T}_{\chi}$ with $\chi$ being Poisson$(\lambda)$.

######  Theorem 1.7.

When $k=2$ and $\chi$ is Poisson$(\lambda)$, we have
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}$,
$\operatorname{nd}_{2,\lambda}<\operatorname{md}_{2,\lambda}$ and
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}<\operatorname{nw}_{2,\lambda}$
for all $\lambda$ sufficiently large.

######  Remark 1.8.

From Theorems 1.6 and 1.7, we conclude that
$\lim_{\lambda\rightarrow\infty}\lambda^{i}\operatorname{m\ell}_{2,\lambda}=0$
for all $i\in\mathbb{N}$.

######  Theorem 1.9.

When $k=2$ and $\chi$ is Poisson$(\lambda)$, we have
$\operatorname{n\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{1,\lambda}$,
$\operatorname{nd}_{2,\lambda}<\operatorname{nd}_{1,\lambda}$ and
$\operatorname{nw}_{1,\lambda}<\operatorname{nw}_{2,\lambda}$ for all
$\lambda$ sufficiently large.

Our final result goes back to general offspring distributions $\chi$, and
concerns itself with average durations of $k$-jump normal games. We
conjecture, from the patterns noticed in its proof, that the second assertion
of Theorem 1.10 can be extended to _any_ $k\in\mathbb{N}$, though we cannot
seem to provide an intuitive argument as to why such a relation should be
true.

######  Theorem 1.10.

For any fixed $k$, when $\operatorname{n\ell}_{k}=c_{k}$ and
$\max\left\\{H^{\prime}_{k}(c_{k}),\left|F^{\prime}_{k}(c_{k})\right|\right\\}<1$,
the expected duration of the $k$-jump normal game is finite. Moreover, for
$k=2,3$, if $\operatorname{n\ell}_{k}=c_{k}$ and
$\left|F^{\prime}_{k}(c_{k})\right|<1$, then once again, the expected duration
is finite.

It is worthwhile to note here that while the condition
$\operatorname{n\ell}_{k}=c_{k}$ alone does guarantee that
$\operatorname{nd}_{k}=0$ (by Theorem 1.3) and hence the $k$-jump normal game
ends almost surely in a finite number of rounds, it does not automatically
imply that the expected number of rounds is going to be finite as well.

###  1.5. A brief discussion of the literature on combinatorial games

Before we plunge into our exploration of the $k$-jump normal and $k$-jump
misère games, the rich and variegated literature on combinatorial games that
has developed over the past several decades deserves some delineation. This
extremely broad class of games (see, for example, [12] and [13] for a general
introduction) constitutes primarily two-player games with perfect information,
no chance moves, and the possible outcomes being victory for one player (and
loss for the other) and draw for both players. Aside from being utilized in
studying mathematical problems that belong to complexity classes harder than
NP, these games have intimate connections with disciplines such as
mathematical logic, automata theory, complexity theory, graph and matroid
theory, networks, error-correcting codes, online algorithms. Outside of
mathematics, these games find applications in biology, psychology, economics,
insurance, actuarial studies and political sciences.

[17] studies _percolation games_ on oriented Euclidean lattices. Each site of
$\mathbb{Z}^{2}$, independent of all other sites, is marked a “trap” or a
“target” or “open” with probabilities $p$, $q$ and $1-p-q$ respectively, and
the two players take turns to move a token from its current position $(x,y)$
to either $(x+1,y)$ or $(x,y+1)$. If a player moves to a target, she wins
immediately, and if she moves to a trap, she loses immediately. The game’s
outcome can be interpreted in terms of the evolution of a one-dimensional
discrete-time probablistic cellular automaton (PCA) – specifically, the game
having no chance of ending in a draw is shown to be equivalent to the
ergodicity of this PCA. [17] also establishes a connection between the
_trapping game_ (i.e. where $q=0$) on directed graphs in higher dimensions and
the hard-core model on related undirected graphs with reduced dimensions. [6]
studies the trapping game on undirected graphs, where the players take turns
to move the token from the vertex at which it is currently located to an
adjacent vertex that has never been visited before, and the player unable to
make a move loses (note the evident connection between this game and the
normal game described above). The outcome of this game is shown to have close
ties with maximum-cardinality matchings, and a draw in this game relates to
the sensitivity of such matchings to boundary conditions. [42] studies a
related, two-person zero-sum game called _exploration_ on a _rooted distance
model_ , to analyze minimum-weight matchings in edge-weighted graphs. In a
related game called _slither_ ([2]), the players take turns to claim yet-
unclaimed edges of a simple, undirected graph, such that the chosen edges, at
all times, form a path, and whoever fails to move, loses. This too serves as a
tool for understanding maximum matchings in graphs.

Bearing some resemblance to slither are the _maker-breaker positional games_
([14]), involving a set $X$, a collection $\mathcal{F}$ of subsets of $X$, and
positive integers $a$ and $b$. The players named _Maker_ and _Breaker_ take
turns to claim yet-unclaimed elements of $X$, with Maker choosing $a$ elements
at a time and Breaker $b$ elements at a time, until all elements of $X$ are
exhausted. Maker wins if she has claimed all elements of a subset in
$\mathcal{F}$. When this game is played on a graph, the players take turns to
claim yet-unclaimed edges, and Maker wins if the subgraph induced by her
claimed edges satisfies a desired property (e.g. it is connected, or it forms
a clique of a given size, a Hamiltonian cycle, a perfect matching or a
spanning tree). The game is _unbiased_ when $a=b$, and _biased_ otherwise.
This game has intimate connections with existential fragments of first order
and monadic second order logic on graphs. [38] and [39] study the threshold
probability $p=p_{c}$ beyond which Maker has a winning strategy when this game
is played on Erdős-Rényi random graphs $G(n,p)$; [40] studies the game for
Hamiltonian cycles on the complete graph $K_{n}$; [7] studies the game on
random geometric graphs; [11] studies the _critical bias_ $b^{*}$ of the
$(1:b)$ biased game on $G(n,p(n))$ for $p(n)=\Theta\left(\ln n/n\right)$. In
addition, [38] studies the game where Maker wins if she can claim a non-planar
graph or a non-$k$-colourable graph. [10] indicates a deep connection between
positional games on complete graphs and the corresponding properties being
satisfied by a random graph, and this is consistent with _Erdős’ probabilistic
intuition_ , which states that the course of a combinatorial game between two
players playing optimally often resembles the evolution of a purely random
process. Finally, the _Ehrenfeucht-Fraïssé games_ comprise yet another
extensive subclass of combinatorial games that play a pivotal role in our
understanding of first and monadic second order logic on random rooted trees
and random graphs (see, for example, [34, 35, 36, 19, 9, 26, 41, 25, 44, 20,
24, 45, 32, 28, 29, 16, 27]).

###  1.6. Organization of the paper

Theorem 1.1 is proved in §2, with the two main parts addressed in §2.1 and
§2.2 (Lemma 2.2, Lemma 2.3 and Equation (2.14) are proved in §10.1 of the
Appendix). The (very similar) proof of Theorem 1.2 is briefly discussed in §3.
Theorem 1.3 is proved in §4, Theorem 1.4 in §5 (Lemmas 5.1 and 5.2 proved in
§10.2 of the Appendix), and Theorem 1.5 is proved in §6 (Lemmas 6.1 through
6.6 proved in §10.3 of the Appendix). Theorems 1.6 and 1.7 are proved in §7
(Lemma 7.1 proved in §10.4 of the Appendix), Theorem 1.9 is proved in §8, and
the proof of Theorem 1.10 is covered in §9.

##  2\. Proof of Theorem 1.1

Fix $k\in\mathbb{N}$ throughout §2, and hence the subscript $k$ is dropped
from notations used in this section (for instance, $\operatorname{NW}_{k}$ is
replaced by $\operatorname{NW}$, $\operatorname{NW}_{k}^{(n)}$ is replaced by
$\operatorname{NW}^{(n)}$ etc.). We begin by deducing the two most fundamental
recurrence relations pertaining to the $k$-jump normal game. For a vertex $u$
to be in $\operatorname{NW}$, P1 must be able to move the token, in the first
round, to some descendant $v$ of $u$ in $\Gamma_{k}(u)$ such that, if we now
consider the game that starts at $v$ and P2 plays the first round, P2 loses.
In other words, such a $v$ must be in $\operatorname{NL}$ (note here that the
symmetric roles of the two players is crucial). Thus

$\displaystyle u\in\operatorname{NW}\Leftrightarrow\exists\
v\in\Gamma_{k}(u)\text{ such that
}v\in\operatorname{NL}\Leftrightarrow\Gamma_{k}(u)\cap\operatorname{NL}\neq\emptyset.$
(2.1)

For a vertex $u$ to be in $\operatorname{NL}$, either $u$ is childless, in
which case P1 is unable to make her very first move, or else _every_ vertex
$v$ in $\Gamma_{k}(u)$ is such that, if P1 moves the token there, then the
game that begins at $v$ with P2 playing the first round is won by P2. In other
words, every $v$ in $\Gamma_{k}(u)$ must belong to $\operatorname{NW}$. Thus
we have

$\displaystyle
u\in\operatorname{NL}\Leftrightarrow\Gamma_{1}(u)=\emptyset\text{ or
}v\in\operatorname{NW}\text{ for every
}v\in\Gamma_{k}(u)\Leftrightarrow\Gamma_{k}(u)\subset\operatorname{NW}.$ (2.2)

Next, we establish a compactness result which shows that, if a player is able
to win the $k$-jump normal game on a rooted tree which is _locally finite_
(i.e. every vertex of the tree has finite degree), then she can guarantee to
do so within a finite number of rounds which can be specified in advance.
Mathematically, this result can be stated as follows:

######  Lemma 2.1.

In any $k$-jump normal game, we have
$\operatorname{NW}=\bigcup_{n=1}^{\infty}\operatorname{NW}^{(n)}$ and
$\operatorname{NL}=\bigcup_{n=1}^{\infty}\operatorname{NL}^{(n)}$.

This result is proven essentially the same way as Proposition 7 of [15], but
we include a proof nonetheless (see §10.1 of the Appendix) for the sake of
completeness of this work. We note here that the offspring distribution $\chi$
that we consider for $\mathcal{T}_{\chi}$ is supported on $\mathbb{N}_{0}$,
hence the (random) number of children of any vertex of $\mathcal{T}_{\chi}$ is
almost surely finite.

As a consequence of Lemma 2.1, we have
$\operatorname{NL}^{(n)}\uparrow\operatorname{NL}$ and
$\operatorname{NW}^{(n)}\uparrow\operatorname{NW}$ as $n\uparrow\infty$, which
in turn yields

$\displaystyle\lim_{n\rightarrow\infty}\operatorname{n\ell}^{(n)}=\operatorname{n\ell}\text{
and }\lim_{n\rightarrow\infty}\operatorname{nw}^{(n)}=\operatorname{nw}.$
(2.3)

The two main parts of the proof of Theorem 1.1 are outlined as follows: in
§2.1, we show that $\operatorname{n\ell}$ is a fixed point of the function
$H_{k}$, and in §2.2, we prove that $\operatorname{n\ell}$ is, in fact, the
minimum positive fixed point of $H_{k}$.

###  2.1. Showing that $\operatorname{n\ell}_{k}$ is a fixed point of $H_{k}$

For a vertex $u$ to be in $\operatorname{NW}^{(n+1)}$ for any
$n\in\mathbb{N}$, there must exist some $v\in\Gamma_{k}(u)$ such that, in the
$k$-jump normal game that begins at $v$, the player who plays the first round
loses in less than $n$ rounds. In other words,

$\displaystyle u\in\operatorname{NW}^{(n+1)}\Leftrightarrow\exists\
v\in\Gamma_{k}(u)\text{ with }v\in\operatorname{NL}^{(n)}.$ (2.4)

For $u$ to be in $\operatorname{NL}^{(n+1)}$, either $u$ is childless, or
every descendant $v\in\Gamma_{k}(u)$ must be such that the $k$-jump normal
game that begins at $v$ is won in less than $n$ rounds by the player who plays
the first round. Thus,

$\displaystyle
u\in\operatorname{NL}^{(n+1)}\Leftrightarrow\Gamma_{1}(u)=\emptyset\text{ or
}v\in\operatorname{NW}^{(n)}\text{ for every }v\in\Gamma_{k}(u).$ (2.5)

We emphasize here that for any $m,n\in\mathbb{N}$, the subsets
$\operatorname{NW}^{(m)}$ and $\operatorname{NL}^{(n)}$ are mutually
exclusive.

Figure 5 (for $k=2$) is included here to help the reader visualize the more
refined subsets or _classes_ of vertices that we now introduce to carry out
the full analysis. It may also be helpful for the reader to refer back to the
discussion included right after the statement of Theorem 1.1 for the case of
$k=2$, to keep in mind an outline of how we aim to proceed in the rest of
§2.1.

Figure 5. Here, $k=2$ and $u_{0}\in\operatorname{NL}^{(n+2)}$ (indicated in
red), so that $u_{i}\in\operatorname{NW}^{(n+1)}$ for all $1\leqslant
i\leqslant 6$ (indicated in blue). Since $u_{1}\in\operatorname{NW}^{(n+1)}$
and its children $u_{3}$ and $u_{4}$ are in $\operatorname{NW}^{(n+1)}$,
$u_{1}$ must have at least one grandchild, say $v_{1}$ (indicated in red) in
$\operatorname{NL}^{(n)}$. Note that $v_{1}\in\operatorname{NL}^{(n)}$ ensures
$u_{4}\in\operatorname{NW}^{(n+1)}$. Likewise, $u_{2}$ and its children
$u_{5}$ and $u_{6}$ are in $\operatorname{NW}^{(n+1)}$, hence $u_{2}$ must
have at least one grandchild, say $v_{4}$, in $\operatorname{NL}^{(n)}$. That
$v_{4}\in\operatorname{NL}^{(n)}$ ensures $u_{6}\in\operatorname{NW}^{(n+1)}$.
Let $u_{3}$ and $u_{5}$ have grandchildren $v_{2}$ and $v_{3}$ (respectively)
in $\operatorname{NL}^{(n)}$, but no child in $\operatorname{NL}^{(n)}$. Then
$u_{4}$ and $u_{6}$ are in $\mathcal{C}_{0,1,n}$, $u_{3}$ and $u_{5}$ are in
$\mathcal{C}_{0,2,n}$, and $u_{1}$ and $u_{2}$ are in $\mathcal{C}_{1,2,n}$.

For $0\leqslant i<j\leqslant k$, we define the subsets of vertices

$\displaystyle\mathcal{C}_{i,j,n}=\\{u:\Gamma_{i}(u)\subset\operatorname{NW}^{(n+1)},\Gamma_{j-1}(u)\cap\operatorname{NL}^{(n)}=\emptyset,\Gamma_{j}(u)\cap\operatorname{NL}^{(n)}\neq\emptyset\\}.$
(2.6)

In other words, any vertex $u$ in $\mathcal{C}_{i,j,n}$ satisfies the
following conditions:

  * •

_all_ its descendants that are at distance at most $i$ away from it are in
$\operatorname{NW}^{(n+1)}$,

  * •

_none_ of its descendants at distance at most $j-1$ away from it is in
$\operatorname{NL}^{(n)}$,

  * •

and _at least one_ of its descendants at distance precisely $j$ away from it
is in $\operatorname{NL}^{(n)}$.

Since $j\leqslant k$, the third condition above ensures, via (2.4), that
$\mathcal{C}_{i,j,n}\subset\operatorname{NW}^{(n+1)}$, so that
$\mathcal{C}_{i,j,n}\cap\operatorname{NL}^{(n)}=\emptyset$. The second
condition above implies
$\mathcal{C}_{i,j,n}\cap\mathcal{C}_{i^{\prime},j^{\prime},n}=\emptyset$ for
all $0\leqslant i<j\leqslant k$, $0\leqslant i^{\prime}<j^{\prime}\leqslant k$
and $j\neq j^{\prime}$. We let $p_{i,j,n}$ denote the probability of the event
that the root $\phi$ of $\mathcal{T}_{\chi}$ belongs to $\mathcal{C}_{i,j,n}$.

From (2.4), we see that $u\in\operatorname{NW}^{(n+1)}$ iff
$u\in\bigcup_{j=1}^{k}\mathcal{C}_{0,j,n}$, i.e. either $u$ has a child
$v\in\operatorname{NL}^{(n)}$, or $u$ has a child $v$ with at least one
descendant $w$ such that $\rho(v,w)\leqslant k-1$ and
$w\in\operatorname{NL}^{(n)}$, which means that
$v\in\bigcup_{j=1}^{k-1}\mathcal{C}_{0,j,n}$. Henceforth, given that the
vertex $u$ has $m$ children, $m\in\mathbb{N}$, we name them
$u_{1},u_{2},\ldots,u_{m}$. Thus

$\displaystyle\operatorname{nw}^{(n+1)}$
$\displaystyle=\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}\left[\text{at
least one
}u_{t}\in\bigcup_{j=1}^{k-1}\mathcal{C}_{0,j,n}\cup\operatorname{NL}^{(n)}\text{
for }1\leqslant t\leqslant m\right]\chi(m)$
$\displaystyle=\sum_{m=1}^{\infty}\left[1-\left(1-\operatorname{n\ell}^{(n)}-\sum_{j=1}^{k-1}p_{0,j,n}\right)^{m}\right]\chi(m)=1-G\left(1-\operatorname{n\ell}^{(n)}-\sum_{j=1}^{k-1}p_{0,j,n}\right).$
(2.7)

From (2.5), we see that $u\in\operatorname{NL}^{(n+2)}$ if and only if either
$u$ is childless, or every child $v$ of $u$ as well as every vertex in
$\Gamma_{k-1}(v)$ is in $\operatorname{NW}^{(n+1)}$. However,
$v\in\operatorname{NW}^{(n+1)}$ iff some vertex in $\Gamma_{k}(v)$ is in
$\operatorname{NL}^{(n)}$. Thus $v$ must have a descendant $w$ such that
$\rho(v,w)=k$ and $w\in\operatorname{NL}^{(n)}$, i.e.
$v\in\mathcal{C}_{k-1,k,n}$. Thus

$\displaystyle\operatorname{n\ell}^{(n+2)}$
$\displaystyle=\sum_{m=0}^{\infty}\operatorname{\mathbf{P}}\left[u_{t}\in\mathcal{C}_{k-1,k,n}\text{
for all }1\leqslant t\leqslant
m\right]\chi(m)=\sum_{m=0}^{\infty}p_{k-1,k,n}^{m}\chi(m)=G(p_{k-1,k,n}).$
(2.8)

We now establish recurrence relations for the probabilities $p_{i,j,n}$. For a
vertex $u$ to be in $\mathcal{C}_{0,1,n}$, it must have at least one child in
$\operatorname{NL}^{(n)}$, i.e.

$\displaystyle
p_{0,1,n}=\sum_{m=1}^{\infty}\left[1-\left(1-\operatorname{n\ell}^{(n)}\right)^{m}\right]\chi(m)=1-G\left(1-\operatorname{n\ell}^{(n)}\right).$
(2.9)

For $2\leqslant j\leqslant k$, $u\in\mathcal{C}_{0,j,n}$ iff at least one
child of $u$ is in $\mathcal{C}_{0,j-1,n}$ and no child is in
$\bigcup_{\ell=1}^{j-2}\mathcal{C}_{0,\ell,n}\cup\operatorname{NL}^{(n)}$:

$\displaystyle p_{0,j,n}$
$\displaystyle=\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}\left[u_{t}\notin\bigcup_{\ell=1}^{j-2}\mathcal{C}_{0,\ell,n}\cup\operatorname{NL}^{(n)},1\leqslant
t\leqslant
m\right]\chi(m)-\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}\left[u_{t}\notin\bigcup_{\ell=1}^{j-1}\mathcal{C}_{0,\ell,n}\cup\operatorname{NL}^{(n)},1\leqslant
t\leqslant m\right]\chi(m)$
$\displaystyle=\sum_{m=1}^{\infty}\left(1-\operatorname{n\ell}^{(n)}-\sum_{\ell=1}^{j-2}p_{0,\ell,n}\right)^{m}\chi(m)-\sum_{m=1}^{\infty}\left(1-\operatorname{n\ell}^{(n)}-\sum_{\ell=1}^{j-1}p_{0,\ell,n}\right)^{m}\chi(m)$
$\displaystyle=G\left(1-\operatorname{n\ell}^{(n)}-\sum_{\ell=1}^{j-2}p_{0,\ell,n}\right)-G\left(1-\operatorname{n\ell}^{(n)}-\sum_{\ell=1}^{j-1}p_{0,\ell,n}\right).$
(2.10)

Finally, for a vertex $u$ to be in $\mathcal{C}_{i,j,n}$ for any $1\leqslant
i<j\leqslant k$, the following are necessary:

  * •

_every_ child $v$ of $u$ must be in $\operatorname{NW}^{(n+1)}$,

  * •

_every_ vertex in $\Gamma_{i-1}(v)$ must be in $\operatorname{NW}^{(n+1)}$,
for _every_ child $v$ of $u$,

  * •

_no_ vertex in $\Gamma_{j-2}(v)$ is in $\operatorname{NL}^{(n)}$ for _any_
child $v$ of $u$,

  * •

there exists _at least one_ child $v$ of $u$ with _at least one_ descendant
$w$ such that $\rho(v,w)=j-1$ and $w\in\operatorname{NL}^{(n)}$.

The first condition, along with (2.4), implies that every child $v$ of $u$ has
a descendant in $\Gamma_{k}(v)$ that is in $\operatorname{NL}^{(n)}$. This,
along with the second and third conditions, implies that each child of $u$
must be in $\bigcup_{\ell=j-1}^{k}\mathcal{C}_{i-1,\ell,n}$. The fourth
condition implies that at least one child of $u$ must be in
$\mathcal{C}_{i-1,j-1,n}$. Thus we have

$\displaystyle
p_{i,j,n}=\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}\left[u_{t}\in\bigcup_{\ell=j-1}^{k}\mathcal{C}_{i-1,\ell,n},1\leqslant
t\leqslant
m\right]\chi(m)-\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}\left[u_{t}\in\bigcup_{\ell=j}^{k}\mathcal{C}_{i-1,\ell,n},1\leqslant
t\leqslant m\right]\chi(m)$
$\displaystyle=\sum_{m=1}^{\infty}\left(\sum_{\ell=j-1}^{k}p_{i-1,\ell,n}\right)^{m}\chi(m)-\sum_{m=1}^{\infty}\left(\sum_{\ell=j}^{k}p_{i-1,\ell,n}\right)^{m}\chi(m)=G\left(\sum_{\ell=j-1}^{k}p_{i-1,\ell,n}\right)-G\left(\sum_{\ell=j}^{k}p_{i-1,\ell,n}\right).$
(2.11)

We now state a couple of lemmas, with their proofs deferred to §10.1 of the
Appendix, the first of which is concerned with important properties of the
function sequence $\\{F_{i}\\}_{i\in\mathbb{N}_{0}}$, whereas the second
provides expressions for the probabilities $p_{i,j,n}$ using (2.9), (2.1) and
(2.1) (once again, it helps if the reader recalls the discussion for $k=2$
presented after the statement of Theorem 1.1). We then combine and consolidate
the recurrence relations in (2.1) and (2.8) with the conclusion of Lemma 2.3
in order to obtain the final result.

######  Lemma 2.2.

Recall the functions $F_{i}$ defined in (1.6). For each $i\in\mathbb{N}$,
$F_{i}$ is a strictly decreasing function on $[0,c_{i-1}]$, and consequently,
$c_{i}$ is uniquely defined. Moreover, $\chi(0)<c_{i}<c_{i-1}$ for each
$i\in\mathbb{N}$.

######  Lemma 2.3.

We have
$p_{i,j,n}=g_{i+1}(F_{j-i-1}(\operatorname{n\ell}^{(n)}),F_{j-i}(\operatorname{n\ell}^{(n)}),F_{k-i+1}(\operatorname{n\ell}^{(n)}),\ldots,F_{k}(\operatorname{n\ell}^{(n)}))$
for $0\leqslant i<j\leqslant k$, where $F_{i}$s and $g_{i}$s are as defined in
(1.6) and (1.7) respectively.

From (2.8), Lemma 2.3 and (1.9), we get

$\displaystyle\operatorname{n\ell}^{(n+2)}=G(g_{k}(F_{0}(\operatorname{n\ell}^{(n)}),F_{1}(\operatorname{n\ell}^{(n)}),F_{2}(\operatorname{n\ell}^{(n)}),\ldots,F_{k}(\operatorname{n\ell}^{(n)})))=H_{k}(\operatorname{n\ell}^{(n)}).$
(2.12)

Taking the limit as $n\rightarrow\infty$ and using (2.3), we conclude that
$\operatorname{n\ell}$ is a fixed point of $H_{k}$ (the continuity of the pgf
$G$ guarantees the continuity of $H_{k}$). By (2.1), Lemma 2.3 and (1.6), we
have

$\operatorname{nw}^{(n+1)}=1-G(1-\operatorname{n\ell}^{(n)}-\sum_{j=1}^{k-1}\\{F_{j-1}(\operatorname{n\ell}^{(n)})-F_{j}(\operatorname{n\ell}^{(n)})\\})=1-F_{k}(\operatorname{n\ell}^{(n)}),$
(2.13)

so that taking the limit as $n\rightarrow\infty$ and using (2.3), we have
$\operatorname{nw}=1-F_{k}(\operatorname{n\ell})$, as desired.

###  2.2. Showing that $\operatorname{n\ell}_{k}$ is the minimum positive
fixed point of $H_{k}$

We begin with an outline for the contents of §2.2. The primary intention of
§2.2 is to establish that $g_{k}(F_{0}(x),F_{1}(x),F_{2}(x),\ldots,F_{k}(x))$,
and consequently $H_{k}$, are both increasing on $[0,c_{k-1}]$, for every
$k\in\mathbb{N}$. Once established, this fact aids, as follows, in concluding
that $\operatorname{n\ell}=\operatorname{n\ell}_{k}$ is the smallest positive
fixed point of $H_{k}$.

Let $0<\eta\leqslant c_{k}$ be a fixed point of $H_{k}$. From (2.12), we have
$\operatorname{n\ell}^{(2n)}=H_{k}^{(n)}(\operatorname{n\ell}^{(0)})=H_{k}^{(n)}(0)$,
where $H_{k}^{(n)}$ indicates the $n$-fold composition of $H_{k}$ with itself.
Note that,

  1. (i)

since $c_{k}$ is a fixed point of $H_{k}$ by Corollary 4.2,

  2. (ii)

since the proof of Lemma 2.2 yields $0<c_{k}<c_{k-1}$ and $H_{k}(0)=\chi(0)$
(which follows from the fact that $F_{i}(0)=1$ for all $i$),

  3. (iii)

and since $H_{k}$ is increasing on $[0,c_{k-1}]$,

we have $0<\chi(0)\leqslant
H_{k}^{(n)}(0)=\operatorname{n\ell}^{(2n)}\leqslant
H_{k}^{(n)}(\eta)=\eta\leqslant H_{k}^{(n)}(c_{k})=c_{k}<c_{k-1}$ for each
$n\in\mathbb{N}$. Upon taking the limit as $n\rightarrow\infty$ and using
(2.3), this yields
$\operatorname{n\ell}=\lim_{n\rightarrow\infty}\operatorname{n\ell}^{(2n)}\leqslant\eta$,
thus allowing us to conclude that $\operatorname{n\ell}$ is, indeed, the
smallest positive fixed point of $H_{k}$.

We prove that $g_{k}(F_{0}(x),F_{1}(x),F_{2}(x),\ldots,F_{k}(x))$ is
increasing on $[0,c_{k-1}]$ by showing that the derivative

$\displaystyle\frac{d}{dx}g_{k}\big{(}F_{0}(x),F_{1}(x),F_{2}(x),\ldots,F_{k}(x)\big{)}=G^{\prime}\big{(}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),$
$\displaystyle\ldots,F_{k}(x)\big{)}-G^{\prime}\big{(}g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)},$

is non-negative for $x\in[0,c_{k-1}]$. We accomplish this by showing that, for
each $x\in[0,c_{k-1}]$,

  1. (i)

that
$G^{\prime}\big{(}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
G^{\prime}\big{(}g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}$,

  2. (ii)

that
$\frac{d}{dx}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\geqslant\frac{d}{dx}g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}$,

  3. (iii)

and the product
$G^{\prime}\big{(}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}$
is non-negative.

We note that $G^{\prime}(x)=\sum_{i=1}^{\infty}i\chi(i)x^{i-1}\geqslant 0$ for
all $x\in[0,1]$, so that
$G^{\prime}\big{(}g_{k-1}\big{(}1,F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
0$ for each $x\in[0,c_{k-1}]$. So, to show (iii), it suffices to prove that
$\frac{d}{dx}g_{k-1}\big{(}1,F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}$ is non-
negative. Furthermore,
$G^{\prime\prime}(x)=\sum_{i=2}^{\infty}i(i-1)\chi(i)x^{i-2}\geqslant 0$ for
all $x\in[0,1]$, showing that $G^{\prime}$ is increasing on $[0,1]$.
Consequently, to show (i), it suffices to show that
$g_{k-1}\big{(}1,F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\geqslant
g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}$.

Each of (i), (ii) and (iii) will be established if we show that for any
$0\leqslant i_{1}<i_{2}\leqslant k-j$ and all $x\in[0,c_{k-1}]$,

$\displaystyle 1\geqslant
g_{j}\big{(}F_{i_{1}}(x),F_{k-j+1}(x),F_{k-j+2}(x),\ldots,F_{k}(x)\big{)}\geqslant
g_{j}\big{(}F_{i_{2}}(x),F_{k-j+1}(x),F_{k-j+2}(x),\ldots,F_{k}(x)\big{)}\geqslant
0,$ (2.14)

and for $k\geqslant 2$, $1\leqslant i\leqslant k-j$ and all $x\in[0,c_{k-1}]$,
we have

$\displaystyle\frac{d}{dx}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),F_{k-j+2}(x),\ldots,F_{k}(x)\big{)}\geqslant\max\big{\\{}0,\frac{d}{dx}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),F_{k-j+2}(x),\ldots,F_{k}(x)\big{)}\big{\\}}.$
(2.15)

The proof of (2.14) is deferred to §10.1 of the Appendix, whereas (2.15) is
proved below via induction on $j$. Setting $j=k-1$, $i_{1}=0$ and $i_{2}=1$ in
(2.14), we obtain
$g_{k-1}\big{(}F_{0}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\in[0,1]$ and
$g_{k-1}\big{(}F_{1}(x),F_{2}(x),F_{3}(x),\ldots,F_{k}(x)\big{)}\in[0,1]$, so
that
$\big{(}F_{0}(x),F_{1}(x),F_{2}(x),\ldots,F_{k}(x)\big{)}\in\mathcal{D}_{k}$
due to (1.8). Consequently, by (1.9), we conclude that $H_{k}$ is well-defined
on $[0,c_{k-1}]$.

We now come to the inductive argument for proving (2.15). For $1\leqslant
i<k$, since $F^{\prime}_{i}(x)$ and $F^{\prime}_{k}(x)$ are both negative for
$x\in[0,c_{k-1}]$ (due to Lemma 2.2), we have

$\frac{d}{dx}g_{1}\big{(}F_{0}(x),F_{k}(x)\big{)}=-F^{\prime}_{k}(x)\geqslant\max\big{\\{}0,F^{\prime}_{i}(x)-F^{\prime}_{k}(x)\big{\\}}=\max\big{\\{}0,\frac{d}{dx}g_{1}\big{(}F_{i}(x),F_{k}(x)\big{)}\big{\\}},$

proving (2.15) for $j=1$. Suppose (2.15) holds for some $j<k-1$. From (1.7),
for $x\in[0,c_{k-1}]$, we have

$\displaystyle\frac{d}{dx}g_{j+1}\big{(}F_{0}(x),F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}=G^{\prime}\big{(}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),$
$\displaystyle\ldots,F_{k}(x)\big{)}-G^{\prime}\big{(}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\geqslant
0,$ (2.16)

  1. (i)

since
$G^{\prime}\big{(}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
G^{\prime}\big{(}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
0$ due to (2.14) (setting $i_{0}=0$ and $i_{2}=k-j$) and the fact (already
shown above) that $G^{\prime}$ is increasing on $[0,1]$,

  2. (ii)

and since, by the induction hypothesis (2.15), we have
$\frac{d}{dx}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\geqslant\max\big{\\{}0,\frac{d}{dx}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{\\}}$.

Next, for $1\leqslant i<k-j$, using (1.7) once again, we have

$\displaystyle\frac{d}{dx}g_{j+1}\big{(}F_{0}(x),F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}-\frac{d}{dx}g_{j+1}\big{(}F_{i}(x),F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}$
$\displaystyle=\Big{[}G^{\prime}\big{(}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{0}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}$
$\displaystyle-G^{\prime}\big{(}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\Big{]}$
$\displaystyle-\Big{[}G^{\prime}\big{(}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}$
$\displaystyle-G^{\prime}\big{(}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{k-j}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\Big{]}$
$\displaystyle=G^{\prime}\big{(}g_{j}\big{(}1,F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}1,F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}$
$\displaystyle-G^{\prime}\big{(}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\frac{d}{dx}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\geqslant
0,$

  1. (i)

since
$G^{\prime}\big{(}g_{j}\big{(}1,F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
G^{\prime}\big{(}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{)}\geqslant
0$ due to (2.14) and the fact (already justified above) that $G^{\prime}$ is
increasing on $[0,1]$,

  2. (ii)

and since, by the induction hypothesis (2.15), we have
$\frac{d}{dx}g_{j}\big{(}1,F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\geqslant\max\big{\\{}0,\frac{d}{dx}g_{j}\big{(}F_{i}(x),F_{k-j+1}(x),\ldots,F_{k}(x)\big{)}\big{\\}}$.

This completes the proof of (2.15) by induction on $j$, as desired, and it
brings us to the end of our proof that $\operatorname{n\ell}$ is the minimum
positive fixed point of $H_{k}$, accomplishing the goal of §2.2.

##  3\. Proof of Theorem 1.2

As the proof of Theorem 1.2 closely resembles that of Theorem 1.1, we only
point out the major modifications. Instead of (2.1) and (2.2), we now have
(omitting the subscript $k$, as $k$ is fixed throughout §3):

$\displaystyle
u\in\operatorname{MW}\Leftrightarrow\Gamma_{1}(u)=\emptyset\text{ or }\exists\
v\in\Gamma_{k}(u)\text{ with }v\in\operatorname{ML},$ (3.1) $\displaystyle
u\in\operatorname{ML}\Leftrightarrow\Gamma_{1}(u)\neq\emptyset\text{ and
}v\in\operatorname{MW}\text{ for every }v\in\Gamma_{k}(u).$ (3.2)

The recursions (2.4) and (2.5) are also accordingly replaced by

$\displaystyle
u\in\operatorname{MW}^{(n+1)}\Leftrightarrow\Gamma_{1}(u)=\emptyset\text{ or
}\exists\ v\in\Gamma_{k}(u)\text{ with }v\in\operatorname{ML}^{(n)},$ (3.3)
$\displaystyle
u\in\operatorname{ML}^{(n+1)}\Leftrightarrow\Gamma_{1}(u)\neq\emptyset\text{
and }v\in\operatorname{MW}^{(n)}\text{ for every }v\in\Gamma_{k}(u).$ (3.4)

Analogous to the classes of vertices $\mathcal{C}_{i,j,n}$ defined in (2.6),
we now define, for $0\leqslant i<j\leqslant k$,

$\displaystyle\mathcal{D}_{i,j,n}=\\{u:\Gamma_{i}(u)\subset\operatorname{MW}^{(n+1)},\Gamma_{j-1}(u)\cap\operatorname{ML}^{(n)}=\emptyset,\Gamma_{j}(u)\cap\operatorname{ML}^{(n)}\neq\emptyset\\}.$
(3.5)

Then $\mathcal{D}_{i,j,n}\cap\mathcal{D}_{i^{\prime},j^{\prime},n}=\emptyset$
when $j\neq j^{\prime}$, and (3.3) implies
$\mathcal{D}_{i,j,n}\subset\operatorname{MW}^{(n+1)}$, so that
$\mathcal{D}_{i,j,n}\cap\operatorname{ML}^{(n)}=\emptyset$. Let $q_{i,j,n}$ be
the probability of the event that the root $\phi$ of $\mathcal{T}_{\chi}$
belongs to $\mathcal{D}_{i,j,n}$. From (3.3) and (3.5):

$\displaystyle\operatorname{mw}^{(n+1)}=\chi(0)+\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}[\text{at
least one
}u_{t}\in\bigcup_{j=1}^{k-1}\mathcal{D}_{0,j,n}\cup\operatorname{ML}^{(n)}\text{
for }1\leqslant t\leqslant m]\chi(m)$
$\displaystyle=\chi(0)+\sum_{m=1}^{\infty}\\{1-(1-\operatorname{m\ell}^{(n)}-\sum_{j=1}^{k-1}q_{0,j,n})^{m}\\}\chi(m)=\chi(0)+1-G(1-\operatorname{m\ell}^{(n)}-\sum_{j=1}^{k-1}q_{0,j,n}),$
(3.6)

where, as in §2, we denote the $m$ children of $\phi$ by $u_{1}$, $u_{2}$,
$\ldots$, $u_{m}$. From (3.4) and (3.5), we have

$\operatorname{m\ell}^{(n+2)}=\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}[u_{t}\in\mathcal{D}_{k-1,k,n}\text{
or }\Gamma_{1}(u_{t})=\emptyset,\text{ for each }1\leqslant t\leqslant
m]\chi(m)\\\
=\sum_{m=1}^{\infty}(q_{k-1,k,n}+\chi(0))^{m}\chi(m)=G(q_{k-1,k,n}+\chi(0))-\chi(0).$
(3.7)

The recurrence relations for $q_{i,j,n}$, $1\leqslant i<j\leqslant k$, differs
from (2.1) in that, for $u$ to be in $\mathcal{D}_{i,j,n}$, each child $v$ of
$u$ is either childless or in
$\bigcup_{\ell=j-1}^{k}\mathcal{D}_{i-1,\ell,n}$, and at least one child of
$u$ must be in $\mathcal{D}_{i-1,j-1,n}$. Thus

$\displaystyle
q_{i,j,n}=\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}[u_{t}\in\bigcup_{\ell=j-1}^{k}\mathcal{D}_{i-1,\ell,n}\text{
or }\Gamma_{1}(u_{t})=\emptyset\text{ for each }1\leqslant t\leqslant
m]\chi(m)-\sum_{m=1}^{\infty}\operatorname{\mathbf{P}}[u_{t}\in\bigcup_{\ell=j}^{k}\mathcal{D}_{i-1,\ell,n}\text{
or }$ $\displaystyle\Gamma_{1}(u_{t})=\emptyset\text{ for each }1\leqslant
t\leqslant
m]\chi(m)=G(\chi(0)+\sum_{\ell=j-1}^{k}q_{i-1,\ell,n})-G(\chi(0)+\sum_{\ell=j}^{k}q_{i-1,\ell,n}).$
(3.8)

Analogous to Lemma 2.3, we have the following relation: for every $0\leqslant
i<j\leqslant k$,

$q_{i,j,n}=\gamma_{i+1}(F_{j-i-1}(\operatorname{m\ell}^{(n)}),F_{j-i}(\operatorname{m\ell}^{(n)}),F_{k-i+1}(\operatorname{m\ell}^{(n)}),\ldots,F_{k}(\operatorname{m\ell}^{(n)})),$
(3.9)

where the functions $\gamma_{i}$ are as defined in (1.10). From (3.7) and
(3.9), we have
$\operatorname{m\ell}^{(n+2)}=J_{k}\left(\operatorname{m\ell}^{(n)}\right)$,
where $J_{k}$ is as defined in (1.11). Taking the limit as
$n\rightarrow\infty$, we see that $\operatorname{m\ell}$ is a fixed point of
$J_{k}$. From (3) and (3.9), we have
$\operatorname{mw}^{(n+1)}=\chi(0)+1-F_{k}\left(\operatorname{m\ell}^{(n)}\right)$,
and taking the limit as $n\rightarrow\infty$, we get
$\operatorname{mw}=\chi(0)+1-F_{k}(\operatorname{m\ell})$. The approach to
showing that $\operatorname{m\ell}$ is the minimum positive fixed point of
$J_{k}$ is nearly identical to that adopted in §2.2, and is therefore omitted.

##  4\. Proof of Theorem 1.3

Fix any $k\in\mathbb{N}$. Recall that the objective of §4 is to show that
$\chi(0)<\operatorname{n\ell}_{k}\leqslant c_{k}$, and that the probability of
draw $\operatorname{nd}_{k}$ is strictly positive if and only if
$\operatorname{n\ell}_{k}<c_{k}$, in case of $k$-jump normal games, where
$c_{k}$ is the unique fixed point of $F_{k}$ in $(0,c_{k-1})$; on the other
hand, $\operatorname{m\ell}_{k}\leqslant\hat{c}_{k}$, and the probability of
draw $\operatorname{md}_{k}$ is strictly positive if and only if
$\operatorname{m\ell}_{k}<\hat{c}_{k}$, in case of $k$-jump misère games,
where $\hat{c}_{k}$ is the unique point of intersection between $y=F_{k}(x)$
and $y=J_{k}(x)+\chi(0)$ in $(0,c_{k-1})$ (recall the definitions of the
functions $F_{k}(x)$ and $J_{k}(x)$ from (1.6) and (1.11) respectively).

######  Lemma 4.1.

For all $k\geqslant 2$, $j\leqslant k$ and $0\leqslant i\leqslant k-j$, we
have

$\displaystyle
g_{j}\left(F_{i}(c_{k}),F_{k-j+1}(c_{k}),F_{k-j+2}(c_{k}),\ldots,F_{k}(c_{k})\right)=F_{j+i-1}(c_{k})-c_{k}.$
(4.1)

###### Proof.

When $j=1$, the left side of (4.1) equals
$g_{1}\left(F_{i}(c_{k}),F_{k}(c_{k})\right)=F_{i}(c_{k})-c_{k}$, since
$c_{k}$ is the fixed point of $F_{k}$. Suppose (4.1) holds for some $j<k$ and
all $0\leqslant i\leqslant k-j$. For $0\leqslant i\leqslant k-j-1$, we have

$\displaystyle
g_{j+1}(F_{i}(c_{k}),F_{k-j}(c_{k}),F_{k-j+1}(c_{k}),\ldots,F_{k}(c_{k}))=G(g_{j}(F_{i}(c_{k}),F_{k-j+1}(c_{k}),\ldots,F_{k}(c_{k})))-G(g_{j}(F_{k-j}(c_{k}),$
$\displaystyle
F_{k-j+1}(c_{k}),\ldots,F_{k}(c_{k})))=G\left(F_{j+i-1}(c_{k})-c_{k}\right)-G\left(F_{k-1}(c_{k})-c_{k}\right)=F_{j+i}(c_{k})-F_{k}(c_{k})=F_{j+i}(c_{k})-c_{k}.\qed$

As an immediate consequence of Lemma 4.1, we get the following corollary:

######  Corollary 4.2.

For any $k\in\mathbb{N}$, $c_{k}$ is a fixed point of $H_{k}$.

###### Proof.

We set $j=k$ and $i=0$ in Lemma 4.1 to get
$g_{k}(F_{0}(c_{k}),F_{1}(c_{k}),\ldots,F_{k}(c_{k}))=F_{k-1}(c_{k})-c_{k}$,
which yields
$H_{k}(c_{k})=G(g_{k}(F_{0}(c_{k}),F_{1}(c_{k}),\ldots,F_{k}(c_{k})))=G(F_{k-1}(c_{k})-c_{k})=F_{k}(c_{k})=c_{k}$.
∎

By Theorem 1.1, $\operatorname{n\ell}_{k}$ is the minimum positive fixed point
of $H_{k}$, and by Corollary 4.2 and Lemma 2.2, $c_{k}$ is a positive fixed
point of $H_{k}$. Hence $\operatorname{n\ell}_{k}\leqslant c_{k}$. The lower
bound on $\operatorname{n\ell}_{k}$ in Theorem 1.3 follows simply from
observing that if the root has no child, which happens with probability
$\chi(0)$, then P1 loses the game starting at the root. From Theorem 1.1, we
have
$\operatorname{nd}_{k}=1-\operatorname{nw}_{k}-\operatorname{n\ell}_{k}=F_{k}(\operatorname{n\ell}_{k})-\operatorname{n\ell}_{k}$.
We already know from Lemma 2.2 that $F_{k}$ is strictly decreasing on
$[0,c_{k-1}]$ and $c_{k}\in(0,c_{k-1})$ is its unique fixed point, which is
equivalent to saying that for $x\in[0,c_{k-1}]$, we have $F_{k}(x)-x$ strictly
positive if and only if $x<c_{k}$. Therefore, $\operatorname{nd}_{k}$ is
strictly positive if and only if $\operatorname{n\ell}_{k}<c_{k}$.

Note that $F_{k}(0)=1$ (since the proof of Lemma 2.2 yields $F_{i}(0)=1$ for
all $i\in\mathbb{N}$) and $J_{k}(0)+\chi(0)=G(\chi(0))<1$ as $\chi(0)<1$
(which also ensures that $G$ is strictly increasing on $[0,1]$), implying that
the curve $y=F_{k}(x)$ lies _above_ the curve $y=J_{k}(x)+\chi(0)$ at $x=0$.
On the other hand, $F_{k}(c_{k-1})=G(F_{k-1}(c_{k-1})-c_{k-1})=G(0)$ as
$c_{k-1}$ is the fixed point of $F_{k-1}$, whereas
$J_{k}(c_{k-1})+\chi(0)=G\big{(}\chi(0)+\gamma_{k}\big{(}1,F_{1}(c_{k-1}),\ldots,F_{k}(c_{k-1})\big{)}\big{)}>G(0)$
since
$\chi(0)+\gamma_{k}\big{(}1,F_{1}(c_{k-1}),\ldots,F_{k}(c_{k-1})\big{)}>0$,
thus implying that the curve $y=F_{k}(x)$ lies _below_ the curve
$y=J_{k}(x)+\chi(0)$ at $x=c_{k-1}$. Lemma 2.2 shows that $F_{k-1}(x)$ is
strictly decreasing on $[0,c_{k-1}]$, whereas an argument analogous to that
used for showing that $H_{k}$ is increasing on $[0,c_{k-1}]$ (as outlined in
§2.2) can be employed to show that $J_{k}$, and hence $J_{k}+\chi(0)$, is
increasing on $[0,c_{k-1}]$. Thus $y=F_{k}(x)$ and $y=J_{k}(x)+\chi(0)$
intersect at a _unique_ point inside $(0,c_{k-1})$, which we call
$\hat{c}_{k}$. From Theorem 1.2, we have
$\operatorname{md}_{k}=1-\operatorname{mw}_{k}-\operatorname{m\ell}_{k}=F_{k}(\operatorname{m\ell}_{k})-\\{J_{k}(\operatorname{m\ell}_{k})+\chi(0)\\}$.
Since $F_{k}(x)$ is strictly decreasing on $[0,c_{k-1}]$ and
$J_{k}(x)+\chi(0)$ is increasing on $[0,c_{k-1}]$ and they intersect at
$\hat{c}_{k}$, we must have $\operatorname{m\ell}_{k}\leqslant\hat{c}_{k}$ to
ensure that $\operatorname{md}_{k}\geqslant 0$, and $\operatorname{md}_{k}>0$
iff $\operatorname{m\ell}_{k}<\hat{c}_{k}$. This brings us to the end of the
proof of Theorem 1.3.

##  5\. Proof of Theorem 1.4

Throughout §5, we fix any $k\in\mathbb{N}$ and let the offspring distribution
$\chi$ of the GW tree $\mathcal{T}_{\chi}$ be Poisson$(\lambda)$. In order to
emphasize the dependence of all functions and quantities involved on
$\lambda$, we replace, from the third paragraph of §5 onward, all of $G$,
$F_{i}$, $H_{k}$, $g_{i}$, $c_{i}$, $\operatorname{n\ell}_{k}$,
$\operatorname{nw}_{k}$ and $\operatorname{nd}_{k}$ by $G_{\lambda}$,
$F_{i,\lambda}$, $H_{k,\lambda}$, $g_{i,\lambda}$, $c_{i,\lambda}$,
$\operatorname{n\ell}_{k,\lambda}$, $\operatorname{nw}_{k,\lambda}$ and
$\operatorname{nd}_{k,\lambda}$ respectively (for all $1\leqslant i\leqslant
k$).

The proof of Lemma 2.2 shows that $F_{i}(0)=1$ for all $i\in\mathbb{N}$, so
that $H_{k}(0)=\chi(0)>0$. The curve $y=H_{k}(x)$ thus lies _above_ the curve
$y=x$ at $x=0$. By Theorem 1.1, we know that $x=\operatorname{n\ell}_{k}$ is
the smallest positive value of $x$ at which the curve $y=H_{k}(x)$ either
touches or starts going _beneath_ the curve $y=x$, so that the slope of
$y=H_{k}(x)$ at $x=\operatorname{n\ell}_{k}$ has to be less than or equal to
the slope of $y=x$. Therefore, we must have
$H^{\prime}_{k}(\operatorname{n\ell}_{k})\leqslant 1$.

The goal of §5 is to establish that $H^{\prime}_{k,\lambda}(c_{k,\lambda})>1$
for all $\lambda$ sufficiently large. This ensures, via the conclusion drawn
in the previous paragraph, that $\operatorname{n\ell}_{k,\lambda}\neq
c_{k,\lambda}$. By Theorem 1.3, we conclude that
$\operatorname{n\ell}_{k,\lambda}<c_{k,\lambda}$ and hence
$\operatorname{nd}_{k,\lambda}>0$ for all such values of $\lambda$. This would
then conclude the proof of the first part of the statement of Theorem 1.4.

We outline here the salient steps of the argument employed to prove that
$H^{\prime}_{k,\lambda}(c_{k,\lambda})>1$ for all $\lambda$ sufficiently
large. In Lemma 5.1, we obtain an expression for the derivative of the
function $g_{k,\lambda}\big{(}r_{0}(x),r_{1}(x),\ldots,r_{k}(x)\big{)}$ with
respect to $x$, where $r_{i}(x)$, for $0\leqslant i\leqslant k$, are
differentiable, and
$\big{(}r_{0}(x),r_{1}(x),\ldots,r_{k}(x)\big{)}\in\mathcal{D}_{k}$ (which is
necessary because of how we define the function $g_{k}$ in (1.7)). Letting
$r_{i}(x)$ be the function $F_{i,\lambda}(x)$ for all $0\leqslant i\leqslant
k$, and using Lemma 5.2 that reveals a pattern in the derivatives of the
functions $F_{i,\lambda}(x)$, we show (via (1.9)) that the leading term in the
expansion of $H^{\prime}_{k,\lambda}(c_{k,\lambda})$ is of the same order of
magnitude as $\lambda^{2k}c^{2}_{k,\lambda}$, while the remaining terms are
$O(\lambda^{2k-1}c^{2}_{k,\lambda})$. Our final task is to show that

$\lim_{\lambda\rightarrow\infty}\lambda^{k-1}c_{k,\lambda}=0\text{ and
}\lim_{\lambda\rightarrow\infty}\lambda^{k}c_{k,\lambda}=\infty,$ (5.1)

which allows us to conclude, in fact, that
$\lim_{\lambda\rightarrow\infty}H^{\prime}_{k,\lambda}(c_{k,\lambda})=\infty$.
Note that the second part of the statement of Theorem 1.4, asserting
$\lambda^{k-1}\operatorname{n\ell}_{k,\lambda}\rightarrow 0$ as
$\lambda\rightarrow\infty$, follows immediately from the first part of (5.1)
and the fact that $\operatorname{n\ell}_{k,\lambda}\leqslant c_{k,\lambda}$
that we obtain from Theorem 1.3.

###  5.1. Understanding the behaviour of $c_{k,\lambda}$ as a function of
$\lambda$

We begin the proof of (5.1) by attempting to understand how $c_{k,\lambda}$
behaves as a function of $\lambda$. The first task we accomplish in §5.1 is
showing that $c_{k,\lambda}$ is, in fact, differentiable with respect to
$\lambda$, for which we implement the well-known implicit function theorem.

To this end, we _redefine_ the functions $F_{i,\lambda}(x)$ on the _extended_
interval $[0,1]$ (instead of only on the sub-interval $[0,c_{i-1,\lambda}]$,
as done in (1.6)) as follows:

$F_{1,\lambda}(x)=e^{-\lambda x}\text{ and }F_{i+1,\lambda}(x)=\exp\\{\lambda
F_{i,\lambda}(x)-\lambda x-\lambda\\}\text{ for all }x\in[0,1],\text{ for
}i\in\mathbb{N}.$ (5.2)

Note that these functions are well-defined. It is immediate that
$0<F_{1,\lambda}(x)<1$ for all $x\in(0,1)$. We now show, via induction on $i$,
that the inequalities $0<F_{i,\lambda}(x)<1$ hold for all $x\in(0,1)$, for
each $i\in\mathbb{N}$. Suppose we have already shown that
$0<F_{i,\lambda}(x)<1$ holds for every $x\in(0,1)$, for some $i\in\mathbb{N}$.
This yields

$\lambda F_{i,\lambda}(x)-\lambda x-\lambda<-\lambda x<0\implies
0<F_{i+1,\lambda}(x)<1\text{ for all }x\in(0,1),$ (5.3)

completing the inductive argument. Next, we note that
$F^{\prime}_{1,\lambda}(x)=-\lambda e^{-\lambda x}<0$. We show, by induction
on $i$, that $F^{\prime}_{i,\lambda}(x)<0$ for all $x\in(0,1)$, for each
$i\in\mathbb{N}$. Suppose we have already shown that
$F^{\prime}_{i,\lambda}(x)<0$ for all $x\in(0,1)$, for some $i\in\mathbb{N}$.
We then have

$F^{\prime}_{i+1,\lambda}(x)=(\lambda
F^{\prime}_{i,\lambda}(x)-\lambda)F_{i+1,\lambda}(x)<0\text{ for all
}x\in(0,1).$

This completes the inductive argument. Let us define
$f_{i}(\lambda,x)=F_{i,\lambda}(x)-x$ on $\Omega=(0,\infty)\times(0,1)$, so
that $(\lambda,c_{i,\lambda})$ is a point on the curve $f_{i}(\lambda,x)=0$,
and $\frac{\partial}{\partial
x}f_{i}(\lambda,x)=F^{\prime}_{i,\lambda}(x)-1<0$ for all $x\in(0,1)$. By the
implicit function theorem, for every $\lambda>0$, there exists an open
$U\times V\subset\Omega$, containing $(\lambda,c_{i,\lambda})$, and a function
$h:U\mapsto V$, differentiable on $U$, such that $c_{i,\lambda}=h(\lambda)$.
This concludes our first task, i.e. showing that $c_{k,\lambda}$ is
differentiable with respect to $\lambda$.

The second task we accomplish in §5.1 is showing that $c_{k,\lambda}$ is a
strictly decreasing function of $\lambda$, by showing that
$\frac{d}{d\lambda}c_{k,\lambda}$ is strictly negative for all $\lambda>0$.
For any function $f(x)$ that is defined and differentiable for all $x>0$, and
$0<f(x)<1$, we show, by induction on $i$, that

$\frac{d}{d\lambda}F_{i,\lambda}(f(\lambda))=A_{i}(f(\lambda))+B_{i}(f(\lambda))f^{\prime}(\lambda)\text{
where }A_{i}(f(\lambda))<0\text{ and }B_{i}(f(\lambda))<0,$ (5.4)

for all $\lambda>0$ and $i\in\mathbb{N}$. We note that
$A_{1}(f(\lambda))=-f(\lambda)e^{-\lambda f(\lambda)}$ and
$B_{1}(f(\lambda))=-\lambda e^{-\lambda f(\lambda)}$, so that the base case is
verified. Assuming that (5.4) holds for some $i\in\mathbb{N}$, we have

$\displaystyle\frac{d}{d\lambda}F_{i+1,\lambda}\big{(}f(\lambda)\big{)}=\left[F_{i,\lambda}\big{(}f(\lambda)\big{)}-f(\lambda)-1+\lambda\left\\{\frac{d}{d\lambda}F_{i,\lambda}\big{(}f(\lambda)\big{)}-f^{\prime}(\lambda)\right\\}\right]F_{i+1,\lambda}\big{(}f(\lambda)\big{)}$
$\displaystyle=\left[F_{i,\lambda}\big{(}f(\lambda)\big{)}-f(\lambda)-1+\lambda\left\\{A_{i}\big{(}f(\lambda)\big{)}+B_{i}\big{(}f(\lambda)\big{)}f^{\prime}(\lambda)-f^{\prime}(\lambda)\right\\}\right]F_{i+1,\lambda}\big{(}f(\lambda)\big{)}$
$\displaystyle=\left[F_{i,\lambda}\big{(}f(\lambda)\big{)}-1-f(\lambda)+\lambda
A_{i}\big{(}f(\lambda)\big{)}\right]F_{i+1,\lambda}\big{(}f(\lambda)\big{)}+\lambda\left[B_{i}\big{(}f(\lambda)\big{)}-1\right]F_{i+1,\lambda}\big{(}f(\lambda)\big{)}f^{\prime}(\lambda),$

so that

$A_{i+1}(f(\lambda))=\left[F_{i,\lambda}\big{(}f(\lambda)\big{)}-1-f(\lambda)+\lambda
A_{i}\big{(}f(\lambda)\big{)}\right]F_{i+1,\lambda}(f(\lambda))$

and

$B_{i+1}\big{(}f(\lambda)\big{)}=\lambda\left[B_{i}\big{(}f(\lambda)\big{)}-1\right]F_{i+1,\lambda}\big{(}f(\lambda)\big{)}.$

These are both negative due to the induction hypothesis and because
$0<F_{i,\lambda}\big{(}f(\lambda)\big{)}<1$ for all $\lambda>0$ (due to
(5.3)). This completes the proof by induction.

When $f(\lambda)=c_{k,\lambda}$, differentiating both sides of the identity
$F_{k,\lambda}(c_{k,\lambda})=c_{k,\lambda}$ (since $c_{k,\lambda}$, recall,
is the unique fixed point of $F_{k,\lambda}$), we have

$c^{\prime}_{k,\lambda}=\frac{d}{d\lambda}c_{k,\lambda}=\frac{A_{k}(c_{k,\lambda})}{1-B_{k}(c_{k,\lambda})}.$

By (5.4), we see that the numerator is strictly negative whereas the
denominator is strictly positive, thus ensuring that
$c^{\prime}_{k,\lambda}<0$ for all $\lambda>0$. This concludes our proof of
the fact that $c_{k,\lambda}$ is strictly decreasing in $\lambda$ for all
$\lambda>0$.

As an immediate consequence of this observation, we note that the limit
$\lim_{\lambda\rightarrow\infty}c_{k,\lambda}$ exists as $c_{k,\lambda}$ is
bounded below by $0$ for all $\lambda>0$. From (5.2) and the fact that
$c_{k,\lambda}$ is the fixed point of $F_{k,\lambda}$, we obtain

$F_{k,\lambda}(c_{k,\lambda})=\exp\left\\{\lambda
F_{k-1,\lambda}(c_{k,\lambda})-\lambda
c_{k,\lambda}-\lambda\right\\}=c_{k,\lambda}\Longleftrightarrow
F_{k-1,\lambda}(c_{k,\lambda})-c_{k,\lambda}-1=\frac{\ln
c_{k,\lambda}}{\lambda}.$ (5.5)

If $\lim_{\lambda\rightarrow\infty}c_{k,\lambda}=c$ for some $c>0$, then the
right side will go to $0$, while the left side remains bounded above by $-c$
since $F_{k-1,\lambda}(c_{k,\lambda})<1$ (due to (5.3)), yielding a
contradiction. Therefore, we must have
$\lim_{\lambda\rightarrow\infty}c_{k,\lambda}=0$.

###  5.2. Understanding the behaviour of $F_{j,\lambda}(c_{k,\lambda})$ for
all $1\leqslant j\leqslant k-1$

Before we can establish the claims made in (5.1), we need to understand the
behaviour of $F_{j,\lambda}(c_{k,\lambda})$ as a function of $\lambda$, as
$\lambda\rightarrow\infty$, for each $1\leqslant j\leqslant k-1$. To this end,
note that, given _any_ infinite sequence $\\{\lambda_{n}\\}_{n}$ of positive
reals with $\lambda_{n}\rightarrow\infty$, since
$0<F_{k-1,\lambda_{n}}\left(c_{k,\lambda_{n}}\right)<1$ for every
$n\in\mathbb{N}$ due to (5.3), the Bolzano-Weierstrass Theorem guarantees the
existence of an infinite subsequence $\left\\{\lambda_{n_{i}}\right\\}_{i}$
such that

$\lim_{i\rightarrow\infty}F_{k-1,\lambda_{n_{i}}}(c_{k,\lambda_{n_{i}}})\text{
exists and is in }[0,1]\implies\lim_{i\rightarrow\infty}\frac{\ln
c_{k,\lambda_{n_{i}}}}{\lambda_{n_{i}}}\text{ exists and is in }[-1,0],\text{
due to \eqref{claim_3}}.$

Suppose we assume that

$\lim_{i\rightarrow\infty}\frac{\ln
c_{k,\lambda_{n_{i}}}}{\lambda_{n_{i}}}=-c\text{ for some }0<c\leqslant 1.$
(5.6)

In what follows, our aim is to show that (5.6) leads to a contradiction.

####  5.2.1. Proving that (5.6) leads to a contradiction

Given any $0<\epsilon<c$, (5.6) implies that there exists $i_{\epsilon}$ such
that $c_{k,\lambda_{n_{i}}}<e^{(-c+\epsilon)\lambda_{n_{i}}}$ for all
$i\geqslant i_{\epsilon}$. We then show, using an inductive argument with
respect to the index $j$, that

$F_{j,\lambda_{n_{i}}}\left(c_{k,\lambda_{n_{i}}}\right)>\exp\left\\{-\sum_{t=1}^{j}\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\}\text{
for all }i\geqslant i_{\epsilon},\text{ for }1\leqslant j\leqslant k.$ (5.7)

For $i\geqslant i_{\epsilon}$, we have

$F_{1,\lambda_{n_{i}}}\left(c_{k,\lambda_{n_{i}}}\right)=e^{-\lambda_{n_{i}}c_{k,\lambda_{n_{i}}}}>\exp\left\\{-\lambda_{n_{i}}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\},$

so that (5.7) holds for $j=1$, and the base case for the induction is thus
verified. Assuming that (5.7) holds for some $j<k$ and using $e^{-x}-1>-x$ for
all $x>0$, we have, for all $i\geqslant i_{\epsilon}$,

$\displaystyle F_{j+1,\lambda_{n_{i}}}\left(c_{k,\lambda_{n_{i}}}\right)$
$\displaystyle=\exp\left\\{\lambda_{n_{i}}F_{j,\lambda_{n_{i}}}\left(c_{k,\lambda_{n_{i}}}\right)-\lambda_{n_{i}}c_{k,\lambda_{n_{i}}}-\lambda_{n_{i}}\right\\}$
$\displaystyle>\exp\left\\{\lambda_{n_{i}}\exp\left\\{-\sum_{t=1}^{j}\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\}-\lambda_{n_{i}}e^{(-c+\epsilon)\lambda_{n_{i}}}-\lambda_{n_{i}}\right\\}$
$\displaystyle\geqslant\exp\left\\{-\lambda_{n_{i}}\sum_{t=1}^{j}\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}-\lambda_{n_{i}}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\}=\exp\left\\{-\sum_{t=1}^{j+1}\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\},$

thus proving (5.7) by induction. Setting $j=k$, since $c_{k,\lambda_{n_{i}}}$
is the fixed point of $F_{k,\lambda_{n_{i}}}$, we have, for $i\geqslant
i_{\epsilon}$,

$c_{k,\lambda_{n_{i}}}=F_{k,\lambda_{n_{i}}}\left(c_{k,\lambda_{n_{i}}}\right)>\exp\left\\{-\sum_{t=1}^{k}\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}\right\\}.$

We know from §5.1 that the left side of the above inequality goes to $0$ as
$i\rightarrow\infty$, whereas the right side approaches $1$, since
$\lambda_{n_{i}}^{t}e^{(-c+\epsilon)\lambda_{n_{i}}}\rightarrow 0$ as
$\lambda_{n_{i}}\rightarrow\infty$ for every $1\leqslant t\leqslant k$ (since
$-c+\epsilon<0$). This yields the desired contradiction.

####  5.2.2. Concluding about the limit of $F_{j,\lambda}(c_{k,\lambda})$, for
all $1\leqslant j\leqslant k-1$

The contradiction obtained in §5.2.1 tells us that our assumption in (5.6) is
wrong, which in turn implies that

$\lim_{\lambda\rightarrow\infty}\frac{\ln c_{k,\lambda}}{\lambda}=0.$ (5.8)

By (5.5) and (5.8), we conclude that

$\lim_{\lambda\rightarrow\infty}F_{k-1,\lambda}(c_{k,\lambda})=1.$ (5.9)

Recall that in the proof of (2.14), we have shown that
$F_{i,\lambda}(x)\geqslant F_{i+1,\lambda}(x)$ for all $0\leqslant i\leqslant
k-1$ and $x\in[0,c_{k-1,\lambda}]$. Using this fact and (5.9), we obtain

$1>F_{1,\lambda}(c_{k,\lambda})\geqslant
F_{2,\lambda}(c_{k,\lambda})\geqslant\cdots\geqslant
F_{k-1,\lambda}(c_{k,\lambda})\text{ for
}\lambda>0\implies\lim_{\lambda\rightarrow\infty}F_{i,\lambda}(c_{k,\lambda})=1\text{
for }1\leqslant i\leqslant k-1.$ (5.10)

###  5.3. The behaviour of $\lambda^{i}c_{k,\lambda}$, for $1\leqslant
i\leqslant k$, as functions of $\lambda$

We lay down the final steps of the proof of (5.1). Setting $i=1$ in (5.10) and
using (5.2), we have $\lim_{\lambda\rightarrow\infty}\lambda c_{k,\lambda}=0$.
We show, via induction on $i$, that

$F_{i,\lambda}(c_{k,\lambda})=\exp\\{-\lambda^{i}c_{k,\lambda}(1+O(\lambda^{-1}))\\}\text{
for }1\leqslant i\leqslant k-1.$ (5.11)

Assuming that (5.11) holds for some $i\leqslant k-2$, we have

$\lim_{\lambda\rightarrow\infty}\lambda^{i}c_{k,\lambda}=0$ (5.12)

due to (5.10), which further ensures that $c_{k,\lambda}=O(\lambda^{-i})$ for
all $\lambda$ large enough. Using this fact, (5.2) and a Taylor expansion, we
have

$\displaystyle F_{i+1,\lambda}(c_{k,\lambda})$
$\displaystyle=\exp\left\\{\lambda\left[e^{-\lambda^{i}c_{k,\lambda}(1+O(\lambda^{-1}))}-c_{k,\lambda}-1\right]\right\\}$
$\displaystyle=\exp\left\\{\lambda\left[-\lambda^{i}c_{k,\lambda}(1+O(\lambda^{-1}))+O\left(\left\\{\lambda^{i}c_{k,\lambda}(1+O(\lambda^{-1}))\right\\}^{2}\right)-c_{k,\lambda}\right]\right\\}$
$\displaystyle=\exp\left\\{-\lambda^{i+1}c_{k,\lambda}(1+O(\lambda^{-1}))\left[1+O\left(\lambda^{i}c_{k,\lambda}(1+O(\lambda^{-1}))\right)+O(\lambda^{-i})\right]\right\\}$
$\displaystyle=\exp\left\\{-\lambda^{i+1}c_{k,\lambda}\left[1+O(\lambda^{-1})+O(\lambda^{i}c_{k,\lambda})+O(\lambda^{-i})\right]\right\\}$
(5.13)

for all $\lambda$ sufficiently large. Note that each of the terms
$O(\lambda^{-1})$, $O(\lambda^{i}c_{k,\lambda})$ (by (5.12)) and
$O(\lambda^{-i})$ is $o(1)$ as $\lambda\rightarrow\infty$, so that the
dominant term in the exponent of (5.3) is $-\lambda^{i+1}c_{k,\lambda}$. This
fact, along with (5.10), yields
$\lim_{\lambda\rightarrow\infty}\lambda^{i+1}c_{k,\lambda}=0$. This in turn
yields $\lambda^{i}c_{k,\lambda}=o(\lambda^{-1})$, so that the dominant term
out of $O(\lambda^{-1})$, $O(\lambda^{i}c_{k,\lambda})$ and $O(\lambda^{-i})$
in (5.3) is $O(\lambda^{-1})$. This completes the proof of (5.11) by
induction.

Combining (5.10) and (5.11) for $i=k-1$, we conclude that
$\lim_{\lambda\rightarrow\infty}\lambda^{k-1}c_{k,\lambda}=0$. Using this fact
and setting $i=k-1$ in (5.3), we have
$c_{k,\lambda}=F_{k,\lambda}(c_{k,\lambda})=\exp\\{-\lambda^{k}c_{k,\lambda}[1+O(\lambda^{-1})+O(\lambda^{k-1}c_{k,\lambda})]\\}$,
which leads to $\lambda^{k}c_{k,\lambda}\rightarrow\infty$ because of the
final conclusion of §5.1. The two conclusions drawn in this paragraph bring us
to the end of the proof of (5.1).

###  5.4. Stating the lemmas and connecting the dots

As promised in the outline of our argument chalked out right before (5.1), we
now state two important lemmas (whose proofs are deferred to §10.2 of the
Appendix).

######  Lemma 5.1.

Let $\\{r_{i}\\}_{0\leqslant i\leqslant k}$ be a sequence of functions defined
and differentiable on an interval $I$, with
$(r_{i}(x),r_{k-j+1}(x),r_{k-j+2}(x),\ldots,r_{k}(x))\in\mathcal{D}_{j}$ (see
(1.8)) for all $x\in I$ and all $0\leqslant i<i+j\leqslant k$. Then

$\displaystyle\frac{d}{dx}g_{k,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))=\lambda^{k-1}\sum_{i=0}^{k-1}f_{k,i,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))(r^{\prime}_{i}(x)-r^{\prime}_{k}(x)),$
(5.14)

in which

$\displaystyle
f_{k,0,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))=\prod_{t=1}^{k-1}G_{\lambda}\left(g_{t,\lambda}\left(r_{0}(x),r_{k-t+1}(x),r_{k-t+2}(x),\ldots,r_{k}(x)\right)\right)$
(5.15)

and

$\displaystyle
f_{k,i,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))=\prod_{t=1}^{k-i}G_{\lambda}\left(g_{t,\lambda}(r_{i}(x),r_{k-t+1}(x),r_{k-t+2}(x),\ldots,r_{k}(x))\right)\alpha_{k,i,\lambda}\left(r_{0}(x),r_{1}(x),\ldots,r_{k}(x)\right)$
(5.16)

for $1\leqslant i\leqslant k-1$, where
$\alpha_{k,1,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))=-1$ and
$\left|\alpha_{k,i,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))\right|$ is
bounded above by a constant $a_{k,i}$ that depends on $k$ and $i$ but not on
$\lambda$ nor on the functions $r_{0},\ldots,r_{k}$, for $2\leqslant
i\leqslant k$.

######  Lemma 5.2.

For $i\geqslant 1$ and $x\in(0,c_{i-1})$, we have

$F^{\prime}_{i,\lambda}(x)=-\lambda\left[\sum_{t=1}^{i-1}\lambda^{i-t}\prod_{j=t}^{i-1}F_{j,\lambda}(x)+1\right]F_{i,\lambda}(x).$
(5.17)

We set $r_{i}(x)$ to be the function $F_{i,\lambda}(x)$ for each $i$, and
$x=c_{k,\lambda}$, in Lemma 5.1. Recall, from the outline chalked out right
above §5.1, that we aim to show that the leading term in (5.14), in this case,
will be of the same order of magnitude as $\lambda^{2k-1}c_{k,\lambda}$, so
that the leading term of $H^{\prime}_{k,\lambda}(c_{k,\lambda})$ is shown to
be of the same order of magnitude as $\lambda^{2k}c_{k,\lambda}^{2}$. To this
end, from (4.1), we have

$G_{\lambda}(g_{k-i,\lambda}(F_{i,\lambda}(c_{k,\lambda}),F_{i+1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda})))=G_{\lambda}(F_{k-1,\lambda}(c_{k,\lambda})-c_{k,\lambda})=F_{k,\lambda}(c_{k,\lambda})=c_{k,\lambda},$

so that from (5.16), using the fact that both
$\left|\alpha_{k,i,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))\right|$ and
$G_{\lambda}(x)$ are $O(1)$, we obtain

$f_{k,i,\lambda}(r_{0}(x),r_{1}(x),\ldots,r_{k}(x))=O(c_{k,\lambda})\text{ for
}1\leqslant i\leqslant k-1.$ (5.18)

Next, from Lemma 5.2 and (5.10), and using (5.18) in the second step, we
deduce that

$\displaystyle
F^{\prime}_{i,\lambda}(c_{k,\lambda})=O\left(\lambda^{i}\prod_{j=1}^{i}F_{j,\lambda}(c_{k,\lambda})\right)=O(\lambda^{i})\text{
as }\lambda\rightarrow\infty,\text{ for }1\leqslant i\leqslant k-1$
$\displaystyle\implies\sum_{i=1}^{k-1}f_{k,i,\lambda}\left(F_{0,\lambda}(c_{k,\lambda}),F_{1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda})\right)F^{\prime}_{i,\lambda}(c_{k,\lambda})=\sum_{i=1}^{k-1}O\left(\lambda^{i}c_{k,\lambda}\right).$
(5.19)

Next, for any $0<\epsilon<1$, Lemma 5.2, the fact that $c_{k,\lambda}$ is the
fixed point of $F_{k,\lambda}$, and (5.10) together yield

$\displaystyle
O(\lambda^{k}c_{k,\lambda})\geqslant-F^{\prime}_{k,\lambda}(c_{k,\lambda})=\lambda^{k}\prod_{j=1}^{k}F_{j,\lambda}(c_{k,\lambda})+O\left(\sum_{t=2}^{k}\lambda^{k-t+1}\prod_{j=t}^{k}F_{j,\lambda}(c_{k,\lambda})\right)\geqslant\lambda^{k}c_{k,\lambda}(1-\epsilon)+O(\lambda^{k-1}c_{k,\lambda})$
(5.20)

as $\lambda\rightarrow\infty$. From (5.18) and (5.20), we deduce that

$\sum_{i=1}^{k-1}f_{k,i,\lambda}(F_{0,\lambda}(c_{k,\lambda}),F_{1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda}))(-F^{\prime}_{k,\lambda}(c_{k,\lambda}))=O(\lambda^{k}c_{k,\lambda}^{2}).$
(5.21)

Finally, (5.15), (4.1) and (5.10) together yield, as
$\lambda\rightarrow\infty$,

$f_{k,0,\lambda}\left(F_{0,\lambda}(c_{k,\lambda}),F_{1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda})\right)=\prod_{t=1}^{k-1}G_{\lambda}\left(F_{t-1,\lambda}(c_{k,\lambda})-c_{k,\lambda}\right)=\prod_{t=1}^{k-1}F_{t,\lambda}(c_{k,\lambda})\rightarrow
1.$ (5.22)

Hence, from (5.20) and (5.22), for any $0<\epsilon<1$, as
$\lambda\rightarrow\infty$, we have

$f_{k,0,\lambda}(F_{0,\lambda}(c_{k,\lambda}),F_{1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda}))(-F^{\prime}_{k,\lambda}(c_{k,\lambda}))\geqslant(1-\epsilon)\lambda^{k}c_{k,\lambda}+O(\lambda^{k-1}c_{k,\lambda}).$
(5.23)

Substituting (5.4), (5.21) and (5.23) in (5.14), using the fact that
$G_{\lambda}(x)=e^{\lambda(x-1)}$ so that $G^{\prime}_{\lambda}(x)=\lambda
G_{\lambda}(x)$, and using Corollary 4.2, we have, as
$\lambda\rightarrow\infty$,

$\displaystyle
H^{\prime}_{k,\lambda}(c_{k,\lambda})=G^{\prime}_{\lambda}(g_{k,\lambda}(F_{0,\lambda}(c_{k,\lambda}),F_{1,\lambda}(c_{k,\lambda}),\ldots,F_{k,\lambda}(c_{k,\lambda})))\frac{d}{dx}g_{k,\lambda}(F_{0,\lambda}(x),F_{1,\lambda}(x),\ldots,F_{k,\lambda}(x))\big{|}_{x=c_{k,\lambda}}$
$\displaystyle\geqslant\lambda
H_{k,\lambda}(c_{k,\lambda})\lambda^{k-1}\left[\sum_{i=1}^{k-1}O(\lambda^{i}c_{k,\lambda})+O(\lambda^{k}c_{k,\lambda}^{2})+(1-\epsilon)\lambda^{k}c_{k,\lambda}+O(\lambda^{k-1}c_{k,\lambda})\right]$
$\displaystyle=\lambda^{k}c_{k,\lambda}\left[O(\lambda^{k-1}c_{k,\lambda})+O(\lambda^{k}c_{k,\lambda}^{2})+(1-\epsilon)\lambda^{k}c_{k,\lambda}\right]=(1-\epsilon)\lambda^{2k}c_{k,\lambda}^{2}+O(\lambda^{2k-1}c_{k,\lambda}^{2}),$

so that the leading term of $H^{\prime}_{k,\lambda}(c_{k,\lambda})$ is indeed
of the same order of magnitude as $\lambda^{2k}c_{k,\lambda}^{2}$, and
$H^{\prime}_{k,\lambda}(c_{k,\lambda})\rightarrow\infty$ due to the second
assertion made in (5.1). This concludes the proof of Theorem 1.4.

##  6\. Proof of Theorem 1.5

###  6.1. Showing strict convexity of $H_{2,\lambda}$ on $[0,c_{2,\lambda}]$
for $\lambda\geqslant 2$

We begin by stating the first of the three objectives we wish to achieve in
§6. We fix $k=2$, and we let the offspring distribution $\chi$ of
$\mathcal{T}_{\chi}$ be Poisson$(\lambda)$. We show that the curve
$y=H_{2,\lambda}(x)$ is strictly convex for all $x\in[0,c_{2,\lambda}]$,
whenever $\lambda\geqslant 2$ – we accomplish this by proving that the second
derivative $H^{\prime\prime}_{2,\lambda}(x)$ is strictly positive for all
$x\in[0,c_{2,\lambda}]$, for every $\lambda\geqslant 2$.

In order to keep the expression for $H^{\prime\prime}_{2,\lambda}(x)$ as
uncluttered as possible, we set

$\alpha(x)=G_{\lambda}(1-F_{2,\lambda}(x))\text{ and
}\beta(x)=G_{\lambda}(F_{1,\lambda}(x)-F_{2,\lambda}(x)),$

so that, from (1.9), we obtain

$H_{2,\lambda}(x)=G_{\lambda}(\alpha(x)-\beta(x)).$

Note, at the very outset, that since $F_{1,\lambda}(x)\leqslant 1$ (evident
from (5.2)) and $G_{\lambda}$ is increasing, hence
$\alpha(x)\geqslant\beta(x)$ for $x\in[0,c_{1,\lambda}]$. From Lemma 5.2,
which yields $F^{\prime}_{1,\lambda}(x)=-\lambda F_{1,\lambda}(x)$ and
$F^{\prime}_{2,\lambda}(x)=-\lambda\left(\lambda
F_{1,\lambda}(x)+1\right)F_{2,\lambda}(x)$, we have

$\displaystyle\alpha^{\prime}(x)=\lambda^{2}\alpha(x)\left(\lambda
F_{1,\lambda}(x)+1\right)F_{2,\lambda}(x),$
$\displaystyle\beta^{\prime}(x)=\lambda^{2}\beta(x)\left\\{-F_{1,\lambda}(x)+\left(\lambda
F_{1,\lambda}(x)+1\right)F_{2,\lambda}(x)\right\\}.$

Utilizing these expressions, we have

$\displaystyle H^{\prime}_{2,\lambda}(x)$
$\displaystyle=\frac{d}{dx}G_{\lambda}(\alpha(x)-\beta(x))=\lambda
H_{2,\lambda}(x)(\alpha^{\prime}(x)-\beta^{\prime}(x)),$ (6.1)

and substituting the expressions for $\alpha^{\prime}(x)$ and
$\beta^{\prime}(x)$ in (6.1), then differentiating again,

$\displaystyle H^{\prime\prime}_{2,\lambda}(x)$
$\displaystyle=\lambda^{4}H_{2,\lambda}(x)\big{[}\lambda^{2}\\{\alpha(x)-\beta(x)\\}^{2}\left(\lambda
F_{1,\lambda}(x)+1\right)^{2}(F_{2,\lambda}(x))^{2}+\lambda^{2}(\beta(x))^{2}(F_{1,\lambda}(x))^{2}+$
$\displaystyle 2\lambda^{2}\beta(x)\\{\alpha(x)-\beta(x)\\}\left(\lambda
F_{1,\lambda}(x)+1\right)F_{1,\lambda}(x)F_{2,\lambda}(x)+\lambda\\{\alpha(x)-\beta(x)\\}\left(\lambda
F_{1,\lambda}(x)+1\right)^{2}(F_{2,\lambda}(x))^{2}$
$\displaystyle-\lambda\\{\alpha(x)-\beta(x)\\}F_{1,\lambda}(x)F_{2,\lambda}(x)-\\{\alpha(x)-\beta(x)\\}(\lambda
F_{1,\lambda}(x)+1)^{2}F_{2,\lambda}(x)$
$\displaystyle+2\lambda\beta(x)\left(\lambda
F_{1,\lambda}(x)+1\right)F_{1,\lambda}(x)F_{2,\lambda}(x)-\beta(x)F_{1,\lambda}(x)(\lambda
F_{1,\lambda}(x)+1)\big{]}$ (6.2)
$\displaystyle=\lambda^{4}H_{2,\lambda}(x)\big{[}A_{1}+A_{2}+2A_{3}+A_{4}-A_{5}-A_{6}+2A_{7}-A_{8}\big{]},$
(6.3)

where

$\displaystyle A_{1}=\lambda^{2}\\{\alpha(x)-\beta(x)\\}^{2}\left(\lambda
F_{1,\lambda}(x)+1\right)^{2}(F_{2,\lambda}(x))^{2},$ $\displaystyle
A_{2}=\lambda^{2}(\beta(x))^{2}(F_{1,\lambda}(x))^{2},$ $\displaystyle
A_{3}=\lambda^{2}\beta(x)\\{\alpha(x)-\beta(x)\\}\left(\lambda
F_{1,\lambda}(x)+1\right)F_{1,\lambda}(x)F_{2,\lambda}(x),$ $\displaystyle
A_{4}=\lambda\\{\alpha(x)-\beta(x)\\}\left(\lambda
F_{1,\lambda}(x)+1\right)^{2}(F_{2,\lambda}(x))^{2},$ $\displaystyle
A_{5}=\lambda\\{\alpha(x)-\beta(x)\\}F_{1,\lambda}(x)F_{2,\lambda}(x),$
$\displaystyle A_{6}=\\{\alpha(x)-\beta(x)\\}(\lambda
F_{1,\lambda}(x)+1)^{2}F_{2,\lambda}(x),$ $\displaystyle
A_{7}=\lambda\beta(x)\left(\lambda
F_{1,\lambda}(x)+1\right)F_{1,\lambda}(x)F_{2,\lambda}(x),$ $\displaystyle
A_{8}=\beta(x)F_{1,\lambda}(x)(\lambda F_{1,\lambda}(x)+1),$

and each $A_{i}$ is non-negative (in fact, strictly positive except for
$A_{1},A_{3},A_{4},A_{5}$ and $A_{6}$ at $x=0$). Thus, our aim now is to
establish that the sum within the square brackets in (6.3) is strictly
positive for each $x\in[0,c_{2,\lambda}]$, for every $\lambda\geqslant 2$.
This is where Lemmas 6.2 through 6.6, all of whose proofs are deferred to
§10.3 of the Appendix, come in. The objective each of them accomplishes is the
collection of various terms from (6.3) and showing that their sums are
strictly positive for $\lambda\geqslant 2$.

The primary idea we employ here is as follows: we split the interval
$[0,c_{2,\lambda}]$ into three pairwise disjoint sub-intervals (in some cases,
we may combine two consecutive sub-intervals), namely $[0,\delta_{\lambda}]$,
$(\delta_{\lambda},\gamma_{\lambda}]$ and $(\gamma_{\lambda},c_{2,\lambda}]$,
where we define $\gamma_{\lambda}$ and $\delta_{\lambda}$ as follows:

$F_{2,\lambda}(\gamma_{\lambda})=\frac{1}{\lambda}\text{ and
}F_{2,\lambda}(\delta_{\lambda})=\frac{5}{4\lambda}.$ (6.4)

Evidently, to be able to do the above, we require

$0<\delta_{\lambda}<\gamma_{\lambda}<c_{2,\lambda}.$ (6.5)

Several aspects of the above paragraph need justification right away, before
we can proceed. By Lemma 2.2, we know that $F_{2,\lambda}$ is strictly
decreasing on $[0,c_{1,\lambda}]$, and $F_{2,\lambda}(0)=1$. By definition of
$c_{2,\lambda}$, we have $F_{2,\lambda}(c_{2,\lambda})=c_{2,\lambda}$.
Therefore, if we can show that

$c_{2,\lambda}<\frac{1}{\lambda}<\frac{5}{4\lambda}<1\text{ for all
}\lambda\geqslant 2,$ (6.6)

of which the second and third inequalities are immediately seen to hold, we
can conclude that $\gamma_{\lambda}$ and $\delta_{\lambda}$, defined via
(6.4), exist and are unique, and that (6.5) holds as well. This is where Lemma
6.1 proves useful:

######  Lemma 6.1.

The function $\eta_{\lambda}=\lambda c_{2,\lambda}$ is strictly increasing for
$\lambda\in(0,\lambda_{0})$ and strictly decreasing for
$\lambda\in(\lambda_{0},\infty)$, where $\lambda_{0}\approx 2.43634$. The
maximum value of $\eta_{\lambda}$ is $\approx 0.52839925$.

The proof of this lemma is deferred to §10.3. This lemma guarantees that for
all $\lambda>0$, we have $\eta_{\lambda}<1\implies
c_{2,\lambda}<\frac{1}{\lambda}$, thus proving that (6.6) indeed holds.

Let us come back to chalking out an outline of our argument for showing that
the expression in (6.3) is strictly positive for all $\lambda\geqslant 2$: for
each $\lambda\geqslant 2$, on each of the sub-intervals
$[0,\delta_{\lambda}]$, $(\delta_{\lambda},\gamma_{\lambda}]$ and
$(\gamma_{\lambda},c_{2,\lambda}]$, we group the terms within the square
brackets in the expression of (6.3) judiciously, so that the sum of the terms
in each such group is strictly positive. We are now ready to state the lemmas
that help accomplish this task.

######  Lemma 6.2.

For each $\lambda\geqslant 2.5$, for all
$x\in(\gamma_{\lambda},c_{2,\lambda}]$, we have $A_{1}+A_{4}-A_{6}>0$.

######  Lemma 6.3.

For each $\lambda\geqslant 2$ and all $x\in(\gamma_{\lambda},c_{2,\lambda}]$,
we have $A_{3}-A_{5}>0$.

######  Lemma 6.4.

For $\lambda\geqslant 2$ and $x\in(\gamma_{\lambda},c_{2,\lambda}]$, we have
$A_{3}+2A_{7}-A_{8}>0$.

Before we state the last couple of lemmas, we note that if we add up the
expressions to the left of the inequalities in Lemmas 6.2, 6.3 and 6.4, we can
conclude that

$A_{1}+2A_{3}+A_{4}-A_{5}-A_{6}+2A_{7}-A_{8}>0\text{ for all
}x\in(\gamma_{\lambda},c_{2,\lambda}],\text{ for }\lambda\geqslant 2.5.$ (6.7)

######  Lemma 6.5.

For $2\leqslant\lambda<2.5$ and $x\in(\gamma_{\lambda},c_{2,\lambda}]$, we
have $A_{1}+A_{4}-A_{6}+2A_{3}-A_{5}+2A_{7}-A_{8}>0$.

######  Lemma 6.6.

For $\lambda\geqslant 2$ and $x\in[\delta_{\lambda},\gamma_{\lambda}]$, we
have $2A_{3}-A_{5}>0$.

Next, we note that as $F_{2,\lambda}$ is strictly decreasing (Lemma 2.2), we
have $F_{2,\lambda}(x)\geqslant\frac{1}{\lambda}$ for
$x\in[0,\gamma_{\lambda}]$, so that

$\displaystyle A_{4}-A_{6}\geqslant 0\text{ and }2A_{7}-A_{8}>0.$ (6.8)

Likewise, we have $F_{2,\lambda}(x)\geqslant\frac{5}{4\lambda}$ for
$x\in[0,\delta_{\lambda}]$, so that

$\displaystyle
A_{4}-A_{5}-A_{6}\geqslant\frac{1}{4}\\{\alpha(x)-\beta(x)\\}\left(\lambda
F_{1,\lambda}(x)+1\right)^{2}F_{2,\lambda}(x)-\lambda\\{\alpha(x)-\beta(x)\\}F_{1,\lambda}(x)F_{2,\lambda}(x)>0$
(6.9)

by an application of the AM-GM inequality.

We are now ready to consolidate all of the findings above to achieve the
desired conclusion. Combining (6.7) and Lemma 6.5, we obtain

$A_{1}+2A_{3}+A_{4}-A_{5}-A_{6}+2A_{7}-A_{8}>0\text{ for all
}x\in(\gamma_{\lambda},c_{2,\lambda}],\text{ for }\lambda\geqslant 2.$ (6.10)

Adding the inequalities in Lemma 6.6 and (6.8) (for the shorter interval
$(\delta_{\lambda},\gamma_{\lambda}]$), we obtain

$\displaystyle 2A_{3}-A_{5}+A_{4}-A_{6}+2A_{7}-A_{8}>0\text{ for all
}x\in(\delta_{\lambda},\gamma_{\lambda}],\text{ for }\lambda\geqslant 2.$
(6.11)

Adding the inequality in (6.9) to the second inequality in (6.8) (again, for
the shorter interval $[0,\delta_{\lambda}]$), we obtain

$2A_{7}-A_{8}+A_{4}-A_{5}-A_{6}>0\text{ for all
}x\in[0,\delta_{\lambda}],\text{ for }\lambda\geqslant 2.$ (6.12)

Combining the conclusions of (6.10), (6.11) and (6.12), we complete the proof
of the desired claim that the expression in (6.3) is strictly positive for all
$x\in[0,c_{2,\lambda}]$, for all $\lambda\geqslant 2$. This concludes the
proof of the fact that $H_{2,\lambda}$ is strictly convex on
$[0,c_{2,\lambda}]$, for all $\lambda\geqslant 2$.

###  6.2. Studying the behaviour of the slope of $H_{2,\lambda}$ at
$c_{2,\lambda}$ as a function of $\lambda$

The second objective of §6 is to show that the slope of $H_{2,\lambda}$ at
$x=c_{2,\lambda}$ is strictly increasing in $\lambda$ for all
$\lambda\geqslant 1$. We start by noting, since $c_{2,\lambda}$ is the fixed
point of $F_{2,\lambda}$, that
$\alpha(c_{2,\lambda})=F_{1,\lambda}(c_{2,\lambda})$ whereas
$\beta(c_{2,\lambda})=c_{2,\lambda}$ (using (1.6)). Using these observations,
the expression from (6.1), the conclusion of Corollary 4.2 and the notation
$\eta_{\lambda}=\lambda c_{2,\lambda}$ introduced in Lemma 6.1, we obtain

$\displaystyle H^{\prime}_{2,\lambda}(c_{2,\lambda})=\lambda
H_{2,\lambda}(c_{2,\lambda})(\alpha^{\prime}(c_{2,\lambda})-\beta^{\prime}(c_{2,\lambda}))=\lambda^{2}\eta_{\lambda}^{2}e^{-2\eta_{\lambda}}+2\lambda\eta_{\lambda}^{2}e^{-\eta_{\lambda}}-\lambda\eta_{\lambda}^{3}e^{-\eta_{\lambda}}-\eta_{\lambda}^{3}.$
(6.13)

For ease of computation, we perform a term-by-term differentiation of the
expression in (6.13) with respect to $\lambda$, and substitute from (10.6) the
expression for $\eta^{\prime}_{\lambda}$ (the derivative of $\eta_{\lambda}$
with respect to $\lambda$). This yields

$\displaystyle\frac{d}{d\lambda}[\lambda^{2}\eta_{\lambda}^{2}e^{-2\eta_{\lambda}}]=\frac{4\lambda\eta_{\lambda}^{2}e^{-2\eta_{\lambda}}+2\lambda^{2}\eta_{\lambda}^{2}e^{-3\eta_{\lambda}}-2\lambda^{2}\eta_{\lambda}^{2}e^{-2\eta_{\lambda}}+2\lambda^{2}\eta_{\lambda}^{3}e^{-2\eta_{\lambda}}}{1+\lambda\eta_{\lambda}e^{-\eta_{\lambda}}+\eta_{\lambda}};$
$\displaystyle\frac{d}{d\lambda}[2\lambda\eta_{\lambda}^{2}e^{-\eta_{\lambda}}]=\frac{6\eta_{\lambda}^{2}e^{-\eta_{\lambda}}+4\lambda\eta_{\lambda}^{2}e^{-2\eta_{\lambda}}-4\lambda\eta_{\lambda}^{2}e^{-\eta_{\lambda}}+2\lambda\eta_{\lambda}^{3}e^{-\eta_{\lambda}}}{1+\lambda\eta_{\lambda}e^{-\eta_{\lambda}}+\eta_{\lambda}};$
$\displaystyle\frac{d}{d\lambda}[-\lambda\eta_{\lambda}^{3}e^{-\eta_{\lambda}}]=\frac{-4\eta_{\lambda}^{3}e^{-\eta_{\lambda}}-3\lambda\eta_{\lambda}^{3}e^{-2\eta_{\lambda}}+3\lambda\eta_{\lambda}^{3}e^{-\eta_{\lambda}}-\lambda\eta_{\lambda}^{4}e^{-\eta_{\lambda}}}{1+\lambda\eta_{\lambda}e^{-\eta_{\lambda}}+\eta_{\lambda}};$
$\displaystyle\frac{d}{d\lambda}[-\eta_{\lambda}^{3}]=\frac{-3\eta_{\lambda}^{3}-3\lambda\eta_{\lambda}^{3}e^{-\eta_{\lambda}}+3\lambda\eta_{\lambda}^{3}}{\lambda\left(1+\lambda\eta_{\lambda}e^{-\eta_{\lambda}}+\eta_{\lambda}\right)}.$

The numerator of $\frac{d}{d\lambda}H^{\prime}_{2,\lambda}(c_{2,\lambda})$ is
then given by

$\displaystyle\eta_{\lambda}^{2}\big{[}4\lambda^{2}e^{-2\eta_{\lambda}}+2\lambda^{3}e^{-3\eta_{\lambda}}-2\lambda^{3}e^{-2\eta_{\lambda}}+2\lambda^{3}\eta_{\lambda}e^{-2\eta_{\lambda}}+6\lambda
e^{-\eta_{\lambda}}+4\lambda^{2}e^{-2\eta_{\lambda}}-4\lambda^{2}e^{-\eta_{\lambda}}+$
$\displaystyle
2\lambda^{2}\eta_{\lambda}e^{-\eta_{\lambda}}-4\lambda\eta_{\lambda}e^{-\eta_{\lambda}}-3\lambda^{2}\eta_{\lambda}e^{-2\eta_{\lambda}}+3\lambda^{2}\eta_{\lambda}e^{-\eta_{\lambda}}-\lambda^{2}\eta_{\lambda}^{2}e^{-\eta_{\lambda}}-3\eta_{\lambda}-3\lambda\eta_{\lambda}e^{-\eta_{\lambda}}+3\lambda\eta_{\lambda}\big{]}$
$\displaystyle=\eta_{\lambda}^{2}\big{\\{}2\lambda^{3}e^{-2\eta_{\lambda}}[e^{-\eta_{\lambda}}-1+\eta_{\lambda}]+\lambda^{2}e^{-\eta_{\lambda}}[8e^{-\eta_{\lambda}}-3\eta_{\lambda}e^{-\eta_{\lambda}}-4+5\eta_{\lambda}-\eta_{\lambda}^{2}]$
$\displaystyle+\lambda
e^{-\eta_{\lambda}}[6-7\eta_{\lambda}]+3\eta_{\lambda}(\lambda-1)\big{\\}}$
$\displaystyle=\eta_{\lambda}^{2}\big{\\{}2\lambda^{3}e^{-2\eta_{\lambda}}[e^{-\eta_{\lambda}}-1+\eta_{\lambda}]+\lambda^{2}e^{-\eta_{\lambda}}[8e^{-\eta_{\lambda}}-4]+\lambda^{2}e^{-\eta_{\lambda}}[5\eta_{\lambda}-3\eta_{\lambda}e^{-\eta_{\lambda}}-\eta_{\lambda}^{2}]$
$\displaystyle+\lambda
e^{-\eta_{\lambda}}[6-7\eta_{\lambda}]+3\eta_{\lambda}(\lambda-1)\big{\\}},$

and our aim now is to prove that this entire expression is strictly positive
for $\lambda\geqslant 1$.

From Lemma 6.1, we have $8e^{-\eta_{\lambda}}-4\geqslant 8e^{-0.5284}-4\approx
0.7164>0$ and $6-7\eta_{\lambda}\geqslant 6-7\cdot 0.5284\approx 2.3012>0$. We
also note that
$5\eta_{\lambda}-3\eta_{\lambda}e^{-\eta_{\lambda}}-\eta_{\lambda}^{2}=3\eta_{\lambda}(1-e^{-\eta_{\lambda}})+\eta_{\lambda}(1-\eta_{\lambda})+\eta_{\lambda}>0$
and $e^{-\eta_{\lambda}}\geqslant 1-\eta_{\lambda}$. Thus
$\frac{d}{d\lambda}H^{\prime}_{2,\lambda}(c_{2,\lambda})>0$ for
$\lambda\geqslant 1$, hence proving the second part of Theorem 1.5.

###  6.3. Proving the third and final part of Theorem 1.5

The objective of §6.3 is to prove that there exists a critical value
$\lambda_{c}$ of $\lambda$ such that
$\operatorname{n\ell}_{2,\lambda}=c_{2,\lambda}$ (and hence, by Theorem 1.3,
$\operatorname{nd}_{2,\lambda}=0$) for all $2\leqslant\lambda<\lambda_{c}$,
and $\operatorname{n\ell}_{2,\lambda}<c_{2,\lambda}$ (and hence,
$\operatorname{nd}_{2,\lambda}>0$) for all $\lambda>\lambda_{c}$.

The argument can be outlined as follows. The convexity of $H_{2,\lambda}$ on
$[0,c_{2,\lambda}]$ for $\lambda\geqslant 2$, as proved in §6.1, guarantees
that $y=H_{2,\lambda}(x)$ intersects $y=x$ at most twice in
$[0,c_{2,\lambda}]$. If the intersection happens twice, it must happen at the
points $x=\operatorname{n\ell}_{2,\lambda}$ and $x=c_{2,\lambda}$, in which
case $\operatorname{n\ell}_{2,\lambda}<c_{2,\lambda}$. If the intersection
takes place only once, then this must be at the point $x=c_{2,\lambda}$, in
which case $\operatorname{n\ell}_{2,\lambda}=c_{2,\lambda}$. Recall, from §5,
the justification as to why
$H^{\prime}_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})\leqslant 1$ for
every $\lambda>0$.

If we can show that $H^{\prime}_{2,\lambda}(c_{2,\lambda})$ is strictly less
than $1$ at $\lambda=2$ and it is strictly greater than $1$ for some value of
$\lambda$ strictly exceeding $2$, then using our conclusion from §6.2, we can
deduce that there is precisely one $\lambda_{c}>2$ such that
$H^{\prime}_{2,\lambda}(c_{2,\lambda})<1$ for $\lambda<\lambda_{c}$ and
$H^{\prime}_{2,\lambda}(c_{2,\lambda})>1$ for $\lambda>\lambda_{c}$. In the
former case, $c_{2,\lambda}$ has to be the only point of intersection between
$y=H_{2,\lambda}(x)$ and $y=x$ within the interval $[0,c_{2,\lambda}]$ (this
follows by noticing that the curve $y=H_{2,\lambda}(x)$ travels from above
$y=x$ to below $y=x$ at $x=\operatorname{n\ell}_{2,\lambda}$, and travels from
below $y=x$ to above $y=x$ at $x=c_{2,\lambda}$ when
$\operatorname{n\ell}_{2,\lambda}<c_{2,\lambda}$, so that in such a scenario,
we would have $H^{\prime}_{2,\lambda}(c_{2,\lambda})>1$). In the latter case,
there have to be two points of intersection between $y=H_{2,\lambda}(x)$ and
$y=x$ within the interval $[0,c_{2,\lambda}]$.

At $\lambda=2$, we have $H^{\prime}_{2,\lambda}(c_{2,\lambda})\approx
0.721129<1$, and at $\lambda=2.5$, we have
$H^{\prime}_{2,\lambda}(c_{2,\lambda})\approx 1.06445>1$. This accomplishes
the task we set for ourselves in the previous paragraph. Solving
$H^{\prime}_{2,\lambda_{c}}\left(c_{2,\lambda_{c}}\right)=1$ numerically, we
obtain $\lambda_{c}\approx 2.41$. This accomplishes what we set out to prove
in §6.3, and concludes the proof of Theorem 1.5.

######  Remark 6.7.

Although our proof technique does not cover the range $1<\lambda<2$, plotting
$H_{2,\lambda}$ on $[0,c_{2,\lambda}]$ for various values of $\lambda$ in
$(1,2)$ does seem to suggest that $H_{2,\lambda}$ is strictly convex on
$[0,c_{2,\lambda}]$ for $\lambda\in(1,2)$ (see Figure 6). If this were to be
proved analytically, it would give us a _unique_ threshold for the phase
transition phenomenon, showing that $\operatorname{nd}_{2,\lambda}=0$ for all
$0<\lambda<\lambda_{c}$ and $\operatorname{nd}_{2,\lambda}>0$ for all
$\lambda>\lambda_{c}$.

Figure 6. $H_{2,\lambda}(x)$ strictly convex for $x\in[0,c_{2,\lambda}]$, for
$\lambda=1.2$ and $\lambda=1.6$

##  7\. Proofs of Theorems 1.6 and 1.7

Recall that the two objectives we accomplish in §7 are  (i) showing that
$\lambda^{i}\operatorname{n\ell}_{2,\lambda}\rightarrow 0$ as
$\lambda\rightarrow\infty$, for every $i\in\mathbb{N}$, which is a far
stronger claim than the second part of Theorem 1.4 as far as $k=2$ is
concerned,  (ii) establishing the inequalities
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}$,
$\operatorname{nd}_{2,\lambda}<\operatorname{md}_{2,\lambda}$ and
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}<\operatorname{nw}_{2,\lambda}$
for all $\lambda$ sufficiently large, giving us a means to compare the
probabilities of the various outcomes of the $2$-jump normal game with those
of the $2$-jump misère game when both are played on $\mathcal{T}_{\chi}$ with
$\chi$ being Poisson$(\lambda)$.

###  7.1. Proof of Theorem 1.6

We outline the key idea for our argument. First and foremost, we note that the
proof is already done for $i=1$ due to Theorem 1.4. For any fixed
$i\in\mathbb{N}$ with $i\geqslant 2$, to show that
$\lambda^{i}\operatorname{n\ell}_{2,\lambda}\rightarrow 0$ as
$\lambda\rightarrow\infty$, it suffices to show, for _any arbitrary_ $c>0$,
that
$\lambda^{i}\operatorname{n\ell}_{2,\lambda}<c\Longleftrightarrow\operatorname{n\ell}_{2,\lambda}<c\lambda^{-i}$
for all $\lambda$ sufficiently large.

For the same value of $i\geqslant 2$ and $c>0$ considered above, by the second
part of (5.1), we know that $\lambda^{i}c_{2,\lambda}>c\Longleftrightarrow
c_{2,\lambda}>c\lambda^{-i}$ for all $\lambda$ large enough. Recall, from
Theorem 1.5 and the discussion included towards the beginning of §5, that
$\operatorname{n\ell}_{2,\lambda}<c_{2,\lambda}$ for all $\lambda$
sufficiently large, and that the curve $y=H_{2,\lambda}(x)$ stays _above_ the
curve $y=x$ for all $x\in[0,\operatorname{n\ell}_{2,\lambda})$, then stays
_beneath_ it for all $x\in(\operatorname{n\ell}_{2,\lambda},c_{2,\lambda})$,
for all $\lambda$ sufficiently large. Therefore, it suffices for us to show
that the curve $y=H_{2,\lambda}(x)$ lies beneath the curve $y=x$ at
$x=c\lambda^{-i}$, for all $\lambda$ sufficiently large. In other words,

######  Lemma 7.1.

Fix $c>0$ and $i\in\mathbb{N}$ with $i\geqslant 2$. Then
$H_{2,\lambda}(c\lambda^{-i})<c\lambda^{-i}$ for all $\lambda$ sufficiently
large.

The proof of this lemma is deferred to §10.4 of the Appendix.

###  7.2. Proof of Theorem 1.7

We first show that
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}$
for all $\lambda$ sufficiently large. In fact, we prove that the inequality
$\operatorname{m\ell}_{2,\lambda}^{(n)}<\operatorname{n\ell}_{2,\lambda}^{(n)}$
holds for all $n\in\mathbb{N}$, via induction on $n$ (recall the definitions
of these probabilities from §1.3). It is straightforward to see that
$\operatorname{m\ell}_{2,\lambda}^{(1)}=0$ and
$\operatorname{n\ell}_{2,\lambda}^{(1)}=e^{-\lambda}$, thus verifying the base
case for the inductive argument. Suppose
$\operatorname{m\ell}_{2,\lambda}^{(n)}<\operatorname{n\ell}_{2,\lambda}^{(n)}$
for some $n\in\mathbb{N}$. From (2.12) and (1.9) (which is applied to $k=2$
and Poisson$(\lambda)$ offspring distribution), we have

$\displaystyle\operatorname{n\ell}_{2,\lambda}^{(n+2)}=H_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})=G_{\lambda}\left(g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})\right)\right).$
(7.1)

We also note (to be used later) that as $\operatorname{n\ell}_{2,\lambda}$ is
a fixed point of $H_{2,\lambda}$ (by Theorem 1.1), we have

$\operatorname{n\ell}_{2,\lambda}=G_{\lambda}\left(g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})\right)\right)=\exp\left\\{\lambda
g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})\right)-\lambda\right\\}.$
(7.2)

A relation analogous to (2.12) derived in §3, (1.11) (again, for $k=2$ and
Poisson$(\lambda)$ offspring), the fact (mentioned in §3 and argued the same
way as in §2.2) that $J_{2,\lambda}$ is increasing on $[0,c_{1,\lambda}]$, the
fact (deduced from (1.7) and (1.10)) that
$\gamma_{2}(1,F_{1,\lambda}(x),F_{2,\lambda}(x))=e^{\lambda
e^{-\lambda}}g_{2,\lambda}(1,F_{1,\lambda}(x),F_{2,\lambda}(x))$, and the
induction hypothesis together yield

$\displaystyle\operatorname{m\ell}_{2,\lambda}^{(n+2)}=J_{2,\lambda}(\operatorname{m\ell}_{2,\lambda}^{(n)})\leqslant
J_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})=G_{\lambda}\left(e^{\lambda
e^{-\lambda}}g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})\right)+e^{-\lambda}\right)-e^{-\lambda}.$
(7.3)

Therefore, to complete the inductive step of showing that
$\operatorname{m\ell}_{2,\lambda}^{(n+2)}<\operatorname{n\ell}_{2,\lambda}^{(n+2)}$,
it suffices to show that the expression in (7.3) is strictly less than that in
(7.1) for all $\lambda$ large enough.

Note that $G^{\prime}_{\lambda}(x)=\lambda G_{\lambda}(x)$ for all $x\in[0,1]$
when we consider Poisson$(\lambda)$ to be our offspring distribution. Since
$G^{\prime\prime}_{\lambda}(x)=\sum_{i=2}^{\infty}i(i-1)\chi(i)x^{i}\geqslant
0$ for $x\in[0,1]$, hence $G_{\lambda}$ is convex. Theorem 21.2 of [33] states
that a continuously differentiable function $f$ defined on an interval $I$ of
$\mathbb{R}$ is convex if and only if $f(y)-f(x)\geqslant f^{\prime}(x)(y-x)$
for all $x,y\in I$. Applying this result with $f$ replaced by $G_{\lambda}$,
we obtain, from (7.1) and (7.3):

$\displaystyle\operatorname{n\ell}_{2,\lambda}^{(n+2)}-\operatorname{m\ell}_{2,\lambda}^{(n+2)}$
$\displaystyle\geqslant-\lambda G_{\lambda}\left(e^{\lambda
e^{-\lambda}}g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})\right)+e^{-\lambda}\right)$
$\displaystyle\left[g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})\right)\left(e^{\lambda
e^{-\lambda}}-1\right)+e^{-\lambda}\right]+e^{-\lambda}.$ (7.4)

In what follows, we show that the expression on the right side of (7.2) is
non-negative for all $\lambda$ large enough.

####  7.2.1. Bound on the first factor of the first term of (7.2)

Since $J_{2,\lambda}$ is increasing on $[0,c_{1,\lambda}]$ and
$\operatorname{n\ell}_{2,\lambda}^{(n)}\leqslant\operatorname{n\ell}_{2,\lambda}$
(evident from (1.5) and (2.3)), given any $\epsilon>0$, we have

$\displaystyle G_{\lambda}\left(e^{\lambda
e^{-\lambda}}g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)})\right)+e^{-\lambda}\right)\leqslant
G_{\lambda}\left(e^{\lambda
e^{-\lambda}}g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})\right)+e^{-\lambda}\right)$
$\displaystyle=\exp\left\\{e^{\lambda
e^{-\lambda}}\lambda\left[g_{2,\lambda}\left(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})\right)-1\right]+\lambda
e^{-\lambda}+\lambda e^{\lambda e^{-\lambda}}-\lambda\right\\}$
$\displaystyle=(\operatorname{n\ell}_{2,\lambda})^{e^{\lambda
e^{-\lambda}}}\exp\\{\lambda e^{\lambda e^{-\lambda}}+\lambda
e^{-\lambda}-\lambda\\},\text{ using \eqref{nl_lambda}};$
$\displaystyle\leqslant\operatorname{n\ell}_{2,\lambda}\exp\left\\{\lambda\sum_{i=1}^{\infty}\frac{(\lambda
e^{-\lambda})^{i}}{i!}+\lambda e^{-\lambda}\right\\},\quad\text{since
}e^{\lambda e^{-\lambda}}>1\text{ and
}\operatorname{n\ell}_{2,\lambda}<1\text{ implies
}(\operatorname{n\ell}_{2,\lambda})^{e^{\lambda
e^{-\lambda}}}\leqslant\operatorname{n\ell}_{2,\lambda};$
$\displaystyle=\operatorname{n\ell}_{2,\lambda}\exp\left\\{\lambda^{2}e^{-\lambda}\sum_{j=0}^{\infty}\frac{(\lambda
e^{-\lambda})^{j}}{(j+1)!}+\lambda
e^{-\lambda}\right\\}\leqslant\operatorname{n\ell}_{2,\lambda}\exp\left\\{\lambda^{2}e^{-\lambda}\sum_{j=0}^{\infty}\frac{(\lambda
e^{-\lambda})^{j}}{j!}+\lambda e^{-\lambda}\right\\}$
$\displaystyle\leqslant\operatorname{n\ell}_{2,\lambda}\exp\\{\lambda^{2}e^{-\lambda}e^{\lambda
e^{-\lambda}}+\lambda
e^{-\lambda}\\}\leqslant\operatorname{n\ell}_{2,\lambda}\exp\\{\lambda^{2}e^{-\lambda}e^{e^{-1}}+\lambda
e^{-\lambda}\\}<(1+\epsilon)\operatorname{n\ell}_{2,\lambda}$ (7.5)

for all $\lambda$ sufficiently large, where, in the last line, we utilize the
fact that the maximum value of $\lambda e^{-\lambda}$ is $e^{-1}$, and that
both $\lambda^{2}e^{-\lambda}$ and $\lambda e^{-\lambda}$ converge to $0$ as
$\lambda\rightarrow\infty$. It is crucial to note that how large $\lambda$
needs to be for (7.2.1) to hold depends on $\epsilon$ alone, and _not_ on $n$.

Note that, as a step in the derivation of (7.2.1), we obtain the bound
$e^{\lambda e^{-\lambda}}-1\leqslant\lambda e^{-\lambda}e^{\lambda
e^{-\lambda}}\leqslant\lambda e^{-\lambda}e^{e^{-1}}$. This will prove useful
in obtaining a bound for the entire expression on the right side of (7.2).

####  7.2.2. Bound on the entire right side of (7.2)

Applying the bound from (7.2.1), the bound mentioned at the very end of
§7.2.1, and the rather crude bound
$g_{2,\lambda}(1,F_{1,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}),F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda}^{(n)}))\leqslant
1$ to (7.2), we obtain

$\displaystyle\operatorname{n\ell}_{2,\lambda}^{(n+2)}-\operatorname{m\ell}_{2,\lambda}^{(n+2)}$
$\displaystyle\geqslant-\lambda(1+\epsilon)\operatorname{n\ell}_{2,\lambda}[\lambda
e^{-\lambda}e^{e^{-1}}+e^{-\lambda}]+e^{-\lambda}=e^{-\lambda}[1-(1+\epsilon)\\{e^{e^{-1}}\lambda^{2}\operatorname{n\ell}_{2,\lambda}+\lambda\operatorname{n\ell}_{2,\lambda}\\}]$
(7.6)

for all $\lambda$ sufficiently large. Theorem 1.6 guarantees that both
$\lambda^{2}\operatorname{n\ell}_{2,\lambda}$ and
$\lambda\operatorname{n\ell}_{2,\lambda}$ converge to $0$ as
$\lambda\rightarrow\infty$, so that
$(1+\epsilon)\\{e^{e^{-1}}\lambda^{2}\operatorname{n\ell}_{2,\lambda}+\lambda\operatorname{n\ell}_{2,\lambda}\\}$
converges to $0$ as well. Consequently, the final expression of (7.6) is
strictly positive for all $\lambda$ sufficiently large. Note, once again, that
how large $\lambda$ needs to be for this to happen depends on $\epsilon$
alone, and _not_ on $n$. This completes the inductive argument, showing that
for all $\lambda$ sufficiently large, we have
$\operatorname{m\ell}_{2,\lambda}^{(n)}<\operatorname{n\ell}_{2,\lambda}^{(n)}$
for every $n\in\mathbb{N}$. Taking the limit as $n\rightarrow\infty$, using
(2.3) and an analogous relation for the misère games, we deduce that
$\operatorname{m\ell}_{2,\lambda}\leqslant\operatorname{n\ell}_{2,\lambda}$,
thus completing the proof of the first part of Theorem 1.7.

####  7.2.3. Proving that
$\operatorname{nd}_{2,\lambda}<\operatorname{md}_{2,\lambda}$ for all
$\lambda$ large enough

Proving $\operatorname{nd}_{2,\lambda}<\operatorname{md}_{2,\lambda}$ for all
$\lambda$ sufficiently large establishes the second claim of Theorem 1.7. From
§4, we know that
$\operatorname{nd}_{2,\lambda}=F_{2,\lambda}(\operatorname{n\ell}_{2,\lambda})-\operatorname{n\ell}_{2,\lambda}$,
whereas
$\operatorname{md}_{2,\lambda}=F_{2,\lambda}(\operatorname{m\ell}_{2,\lambda})-\operatorname{m\ell}_{2,\lambda}-e^{-\lambda}$.
The rest of §7.2.3 is dedicated to comparing these two expressions.

We set out to find a suitable upper bound on $\operatorname{nd}_{2,\lambda}$
for all $\lambda$ sufficiently large. We start by obtaining suitable
approximations to a couple of infinite series. From Theorem 1.6, we know that
$\lambda\operatorname{n\ell}_{2,\lambda}\rightarrow 0$ as
$\lambda\rightarrow\infty$, implying that for all $\lambda$ sufficiently
large,

$\displaystyle\lambda\operatorname{n\ell}_{2,\lambda}<i+1\Longleftrightarrow\frac{(\lambda\operatorname{n\ell}_{2,\lambda})^{i+1}}{(i+1)!}<\frac{(\lambda\operatorname{n\ell}_{2,\lambda})^{i}}{i!}\text{
for all }i\in\mathbb{N}_{0}\text{ and
}\lim_{\rightarrow\infty}\frac{(\lambda\operatorname{n\ell}_{2,\lambda})^{i}}{i!}=0,$

so that by the well-known alternating series estimation theorem (see, for
instance, §8.4 of [37]), we have

$e^{-\lambda\operatorname{n\ell}_{2,\lambda}}-1\leqslant-\lambda\operatorname{n\ell}_{2,\lambda}+\frac{\lambda^{2}\operatorname{n\ell}_{2,\lambda}^{2}}{2}.$
(7.7)

Applying Theorem 1.6 one more time, we know that each of