2. Analytic properties of the fixed-point equation

We start with the proof of Proposition 1.1. This proof belongs more in [Reference Johnson, Podder and Skerman14] than here, but we give it so that it is spelled out somewhere.

Proof of Proposition 1.1. The proof is just a matter of tying together some more general results from [Reference Johnson, Podder and Skerman14]. The fixed point $x_0$ has an interpretation if and only if the associated pivot tree is subcritical or critical [Reference Johnson, Podder and Skerman14, Theorem 1.7]. (See [Reference Johnson, Podder and Skerman14] for the meaning of pivot tree.) This pivot tree is subcritical or critical if and only if $\Psi'(x_0)\leq 1$ [Reference Johnson, Podder and Skerman14, Lemma 5.3].

Now we start our work towards the proofs of Theorems 1.2 and 1.5. We define the polynomials

(9) \begin{align} B^{=}_{n,k}(x) &= \binom{n}{k}x^k(1-x)^{n-k},\end{align}

(10) \begin{align} B^{\geq}_{n,k}(x) &= \sum_{j=k}^nB^{=}_{n,k}(x).\end{align}

For $x\in[0,1]$ , we have $B^{=}_{n,k}(x) = \mathbb{P}[\textrm{Bin}(n,x)=k]$ and $B^{\geq}_{n,k}(x)=\mathbb{P}[\textrm{Bin}(n,x)\geq k]$ . Note that we take $\binom{0}{0}=1$ and $\binom{n}{k}=0$ if $k>n$ or $k<0$ . Using this notation and assuming $h(\ell)\geq 1$ , we have $\Psi(x) = \sum_{\ell=1}\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)$ . Thus we can understand the derivatives of $\Psi$ by working out the derivatives of $B^{\geq}_{n,k}(x)$ , which we do now.

Proposition 2.2 For $m\geq 1$ ,

(11) \begin{align} \frac{d^{m}}{dx^{m}}B^{\geq}_{n,k}(x) &= (n)_m\sum_{j=1}^{m} (-1)^{j+m}\binom{m-1}{j-1}B^{=}_{{n-m},{k-j}}(x). \end{align}

Proof. By direct calculation,

(12) \begin{align} \frac{d}{dx}B^{=}_{{n},{k}}(x) &= n\bigl( B^{=}_{{n-1},{k-1}}(x) - B^{=}_{{n-1},k}(x) \bigr). \end{align}

Hence

\begin{align*} \frac{d}{dx}B^{\geq}_{n,k}(x) &= n\sum_{j=k}^n\bigl(B^{=}_{{n-1},{j-1}}(x) - B^{=}_{{n-1},j}(x)\bigr), \end{align*}

and this sum telescopes to yield $nB^{=}_{{n-1},{k-1}}(x)$ , establishing the $m=1$ case.

Now assume the result for m and we prove it for $m+1$ . Differentiating the right-hand side of (11) using (12) gives

\begin{align*} \frac{d^{m+1}}{dx^{m+1}}B^{\geq}_{n,k}(x) &= (n)_m\sum_{j=1}^m(-1)^{j+m}\binom{m-1}{j-1}(n-m) \bigl(B^{=}_{{n-m-1},{k-j-1}}(x) - B^{=}_{{n-m-1},{k-j}}(x)\bigr)\\ &= (n)_{m+1}\Biggl(\sum_{j=2}^{m+1}(-1)^{j+m+1}\binom{m-1}{j-2} B^{=}_{{n-m-1},{k-j}}(x) \\&\qquad\qquad\qquad\qquad- \sum_{j=1}^m(-1)^{j+m}\binom{m-1}{j-1}B^{=}_{{n-m-1},{k-j}}(x)\Biggr)\\ &= (n)_{m+1}\sum_{j=1}^{m+1}(-1)^{j+m+1}\binom{m}{j-1}B^{=}_{{n-m-1},{k-j}}(x), \end{align*}

using the identity $\binom{n}{k-1}+\binom{n}{k} = \binom{n+1}{k}$ in the last line.

Proof. We have $\Psi_n(x)=\sum_{\ell=1}^n\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)$ and $\Psi(x)=\lim_{n\to\infty}\Psi_n(x)$ . It suffices to show that $\Psi_n^{(k)}$ converges uniformly on [0, 1] to some limit as $n\to\infty$ for $0\leq k\leq m$ [Reference Rudin20, Theorem 7.17]. For $k\geq 1$ , we apply (11) and bound $B^{=}_{{n},k}(x)$ by 1 to obtain

\begin{align*} \left\lvert{\frac{d^k}{dx^k}B^{\geq}_{{\ell},{h(\ell)}}(x)}\right\rvert &\leq (\ell)_k \sum_{j=1}^k\binom{k-1}{j-1}=(\ell)_k2^{k-1}\leq \ell^k2^k. \end{align*}

The same statement for $k=0$ , that $\lvert{B^{\geq}_{{\ell},{h(\ell)}}(x)}\rvert\leq 1$ , also holds. Hence for all $0\leq k\leq m$ ,

\begin{align*} \left\lvert{\sum_{\ell=n+1}^{\infty}\chi(\ell)\frac{d^k}{dx^k}B^{\geq}_{{\ell},{h(\ell)}}(x)}\right\rvert &\leq 2^{k}\sum_{\ell=n+1}^{\infty}\chi(\ell)\ell^k, \end{align*}

which vanishes as $n\to\infty$ by our assumption that $\chi$ has finite mth moment. This demonstrates that $\Psi_n^{(k)}$ converges uniformly as $n\to\infty$ , completing the proof.

Proof of Theorem 1.2. Let $\chi_n$ be the truncation of $\chi$ to n and let $\Psi_n$ be the automaton distribution map of $(\chi_n,h)$ , as in the previous lemma. Applying Proposition 2.2 to each summand of $\Psi_n(x)=\sum_{\ell=1}^n\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)$ gives

\begin{align*} \Psi_n^{(m)}(x) &= \sum_{\ell=1}^n \chi(\ell)(\ell)_m\sum_{j=1}^m(-1)^{j+m}\binom{m-1}{j-1}B^{=}_{{\ell-m},{h(\ell)-j}}(x). \end{align*}

Observing that $B^{=}_{n,k}(0)=\textbf{1}\{\text{n} \geq 0\ \text{and}\ k = 0\}$ , we obtain

\begin{align*} \Psi_n^{(m)}(0) &= \sum_{\ell=1}^n \chi(\ell)(\ell)_m(-1)^{h(\ell)+m}\binom{m-1}{h(\ell)-1}. \end{align*}

Applying Lemma 2.3, we take $n\to\infty$ to prove (5). Equation (6) follows by grouping together the terms with $h(\ell)=j$ .

Note that this theorem can fail without the moment assumption:

Example 2.4 Let $\chi(\ell) = 1/\ell(\ell-1)$ for $k\geq 2$ , a measure whose expectation is infinite. Let $h(\ell)\equiv 2$ . Observe that

\begin{align*} \mathbb{P}\bigl[ \textrm{Bin}(\ell,x) \leq 1 \bigr] = (1-x)^\ell + \ell (1-x)^{\ell-1}x &= (1-x)^\ell + \ell (1-x)^{\ell-1}\bigl( 1-(1-x)\bigr)\\ &= \ell(1-x)^{\ell-1}-(\ell-1)(1-x)^\ell. \end{align*}

Now, let $L\sim\chi$ and compute

\begin{align*} \Psi(x) = \mathbb{P}\bigl[ \textrm{Bin}(L,x)\geq h(\ell) \bigr] &= 1 - \mathbb{P}\bigl[ \textrm{Bin}(L,x)\leq 1 \bigr] \\ &= 1 - \sum_{\ell=2}^{\infty}\chi(\ell)\mathbb{P}\bigl[ \textrm{Bin}(\ell,x)\leq 1 \bigr]\\ &= 1 - \sum_{\ell=2}^{\infty}\Bigl( (\ell-1)(1-x)^{\ell-1} - \ell(1-x)^\ell \Bigr). \end{align*}

The sum in the last line telescopes and is equal to $1-x$ for $x\in[0,1]$ , yielding $\Psi(x)=x$ . But this means that $\Psi'(0)=1$ even though Theorem 1.2 would give $\Psi'(0)=0$ .

We revisit this recursive tree system in Example 3.4 and show how we arrived at it.

Proof. Suppose $\chi_n\to\chi$ in ${\Pi_{\infty}}$ and let $\Psi_n$ denote the automaton distribution map of $\chi_n$ . We need to show that $\Psi_n^{(m)}(0)\to \Psi^{(m)}(0)$ . We have

\begin{align*} \left\lvert{\sum_{\ell\in\textrm{tier}(j)} \chi_n(\ell)(\ell)_m - \sum_{\ell\in\textrm{tier}(j)} \chi(\ell)(\ell)_m} \right\rvert &\leq \sum_{\ell=1}^{\infty}\left\lvert{\chi_n(\ell)-\chi(\ell)}\right\rvert\ell^m, \end{align*}

which vanishes as $n\to\infty$ by definition of convergence in ${\Pi_{\infty}}$ . Hence, by (6) from Theorem 1.2, we have $\Psi_n^{(m)}(0)\to \Psi^{(m)}(0)$ .

Proof of Theorem 1.5. First, suppose that $\Psi'(0)=1$ and $\Psi''(0)< 0$ . We need to show that for any $\epsilon$ , there exist child distributions arbitrarily close to $\chi$ in ${\Pi_{\infty}}$ with an interpretable fixed point in $(0,\epsilon)$ . To show this, we perturb $\chi$ slightly to push its automaton distribution map up, creating a new fixed point very close to 0. We accomplish this by transferring some small amount of mass to tier 1, which will cause $\Psi'(0)$ to increase, as in the phase transition shown in Figure 2.

We will choose k from tier 1 and take j to be either 0 or some element of a different tier, and then transfer mass from j to k. First, we must justify that we can find j and k. From (7) and $\Psi'(0)=1$ , we know that tier 1 is non-empty. Choose k arbitrarily from it. If $\chi(0)>0$ , take $j=0$ . If $\chi(0)=0$ , then $\chi$ has expectation strictly greater than 1. By (7), tier 1 does not contain all the mass of $\chi$ , and therefore some other tier is non-empty; choose j from it.

Now, for $t>0$ , define $\chi_t$ by starting with $\chi$ and then shifting mass t from j to k. Let $\Psi_t$ be the automaton distribution map of $\chi_t$ . Fix $\epsilon>0$ . Since $\chi_t\to\chi$ in ${\Pi_{\infty}}$ , we just need to show that for sufficiently small t, the map $\Psi_t$ has an interpretable fixed point in $(0,\epsilon)$ . By Theorem 1.2,

(13) \begin{align}\Psi'_t(0) &= \Psi'(0)+ kt=1+kt, \end{align}

and

(14) \begin{align} \Psi''_t(0) &< \Psi''(0)<0. \end{align}

By (13), we have $\Psi_t(x)>x$ for sufficiently small $x>0$ . Choosing t to be small enough relative to $\Psi''(0)$ and applying Taylor approximation, we can force $\Psi_t(x)<x$ for some $x<\epsilon$ , implying the existence of a fixed point $x_0$ with $\Psi'_t(x_0)<1$ , which is hence interpretable by Proposition 1.1.

Now, suppose $\Psi'(0)=1$ and $\Psi''(0)=0$ . Again we must show the existence of child distributions arbitrarily close to $\chi$ with an interpretable fixed point in $(0,\epsilon)$ . We take the same approach as above, perturbing $\chi$ to increase $\Psi'(0)$ and decrease $\Psi''(0)$ , but we must be careful about the rates of increase and decrease. Choose k from tier 1 as before. From $\Psi''(0)=0$ and (8), we know that $\chi$ assigns positive mass to tier 2; choose j from it. Now define

\begin{align*} \chi_t(\ell) = \begin{cases} \chi(\ell) + t^2 & \text{if $\ell=k$,}\\[4pt] \chi(\ell) - t & \text{if $\ell=j$,}\\[4pt] \chi(0) + t - t^2 & \text{if $\ell=0$,}\\[4pt] \chi(\ell) & \text{otherwise,} \end{cases} \end{align*}

for small values of t, and let $\Psi_t$ be the automaton distribution map of $\chi_t$ . By (7) and (8),

\begin{align*} \Psi'_t(0) &= \Psi'(0)+t^2k = 1 + t^2 k,\\ \Psi''_t(0) &= \Psi''(0)-t j(j-1) -t^2k(k-1)=-t j(j-1) -t^2k(k-1). \end{align*}

Thus $\Psi_t(x)>x$ immediately to the right of 0, and Taylor approximation again shows that when t is sufficiently small $\Psi_t(x)<x$ for some $x<\epsilon$ . This proves the existence of a fixed point $x_0\in(0,\epsilon)$ with $\Psi'_t(x_0)<1$ .

Now we consider the converse. Suppose $\Psi'(0)\neq 1$ . By Lemma 2.5, we can choose a neighbourhood $U\subseteq{\Pi_{\infty}}$ around $\chi$ so that for all $\pi\in U$ , the automaton distribution map of $(\pi,h)$ has first derivative at 0 uniformly bounded away from 1 and second derivative at zero uniformly bounded. By Taylor approximation, all these maps have no fixed points on $(0,\epsilon)$ for some small $\epsilon>0$ , demonstrating that $\chi$ is not critical.

Last, suppose $\Psi'(0)=1$ and $\Psi''(0)>0$ . By Lemma 2.5, we can choose a neighbourhood $U\subseteq{\Pi_{\infty}}$ around $\chi$ such that all automaton distribution maps $\Psi_\pi$ of $(\pi,h)$ for $\pi\in U$ have second derivative at zero uniformly bounded above 0 and third derivative uniformly bounded. Hence for some $\epsilon>0$ , each map $\Psi_\pi$ is strictly convex on $[0,\epsilon]$ . The function $\Psi_\pi(x) - x$ is also strictly convex and hence has at most two roots on $[0,\epsilon]$ . One of them is at 0. By convexity, any other root of $\Psi_\pi(x)-x$ on $[0,\epsilon]$ must occur with the graph crossing the x-axis from below to above as x increases. Thus $\Psi_\pi$ has derivative greater than 1 at this fixed point, and by Proposition 1.1 it has no interpretation. Since no systems $(\pi,h)$ for $\pi\in U$ have an interpretable fixed point in $(0,\epsilon)$ , the measure $\chi$ is not critical.

3. Truncations

Let the maximum threshold of $(\chi, h)$ be the maximum value of $h(\ell)$ over all $\ell$ satisfying $\chi(\ell)>0$ . Define the m-truncation of $\chi$ as the child distribution $\bar\chi$ where for $\ell\geq 1$ ,

\begin{align*} \bar\chi(\ell) &= \begin{cases} \chi(\ell) & \text{if $h(\ell)\leq m$},\\[4pt] 0 & \text{if $h(\ell)>m$}, \end{cases}\end{align*}

with $\bar\chi(0)$ set to make $\bar\chi$ a probability measure. In other words, $\bar\chi$ is obtained from $\chi$ by lopping off tiers $m+1$ and higher, shifting their weight to 0. Recall from Corollary 1.3 that the automaton distribution maps of $(\chi,h)$ and $(\bar\chi,h)$ match to m derivatives at 0. Thus $(\bar\chi,h)$ is a system of maximum threshold m or less whose automaton distribution map approximates that of $(\chi,h)$ near 0.

The point of this section is to prove the following result, which is a major step in proving Theorem 1.8:

The key to this proposition is a thorough understanding of m-concordant recursive tree systems of maximum threshold m, which we call m-critical. If $(\chi,h)$ has at most one element in each tier, we call it primitive. We will work extensively with primitive m-critical recursive tree systems. An example of such a system is

\begin{align*} \chi(\ell)&=\begin{cases} 2/5 & \text{for $\ell=0$,}\\[4pt] 1/2 & \text{for $\ell=2$,}\\[4pt] 1/20 & \text{for $\ell=5$},\\[4pt] 1/20 & \text{for $\ell=6$,} \end{cases}, & h(\ell)&=\begin{cases} 1 & \text{for $\ell=0$,}\\ 1 & \text{for $\ell=2$,}\\ 2 & \text{for $\ell=5$},\\ 3 & \text{for $\ell=6$.} \end{cases}\end{align*}

We can check using Theorem 1.2 that this system is 3-concordant (i.e. it has $\Psi'(0)=1$ and $\Psi''(0)=\Psi^{(3)}(0)=0$ ). It is 3-critical because it is 3-concordant and has maximum threshold 3, and it is primitive because tiers 1, 2, and 3 each have one element (recall that the tiers exclude 0 by definition).

These recursive tree systems have many good properties. In Proposition 3.8, we show that m-critical systems decompose into mixtures (i.e. convex combinations) of primitive m-critical systems. And for the primitive m-critical systems $(\chi,h)$ , the automaton distribution map has a useful connection with a martingale $(X_n)_{n\geq 1}$ we describe now.

First, we define a time-inhomogenous Markov chain $(R_n)_{n\geq 1}$ as follows. Let $R_1=1$ . Then, conditional on $R_n$ , let

(15) \begin{align} R_{n+1} &=\begin{cases} R_n & \text{with probability $\frac{n+1-R_n}{n+1}$,}\\[4pt] R_n+1 & \text{with probability $\frac{R_n}{n+1}$.} \end{cases}\end{align}

There is an alternative construction of $(R_n)_{n\geq 1}$ that yields some insight. Start with the permutation $\sigma_1$ of length 1. At each step, form $\sigma_{n+1}$ from $\sigma_n$ by viewing $\sigma_n$ in one-line notation and inserting the digit $n+1$ uniformly at random into the $n+1$ possible locations. For example, if $\sigma_3=213$ , then $\sigma_4$ is equally likely to be each of 4213, 2413, 2143, and 2134. Then let $R_n=\sigma_n^{-1}(1)$ , the location of 1 in the one-line notation of $\sigma_n$ . When we insert $n+1$ into $\sigma_n$ to form $\sigma_{n+1}$ , it has probability $(n+1-R_n)/(n+1)$ of landing to the right of 1 and probability $R_n/(n+1)$ of landing to the left of 1, matching the dynamics given in (15). We note one consequence of this perspective:

Proof. First, we argue by induction that $\sigma_n$ is a uniformly random permutation of length n, with $n=1$ as the trivial base case. To extend the induction, let $\tau$ be an arbitrary permutation of length n and let $\tau'$ be the permutation of of length $n-1$ obtained by deleting n from the one-line notation form of $\tau$ . Then $\sigma_n$ can be equal to $\tau$ only if $\sigma_{n-1}=\tau'$ , and we compute

\begin{align*} \mathbb{P}[\sigma_n=\tau] = \mathbb{P}[\sigma_{n-1}=\tau']\,\mathbb{P}[\sigma_n=\tau\mid\sigma_{n-1}=\tau'] = \frac{1}{(n-1)!}\cdot\frac{1}{n}=\frac{1}{n!} \end{align*}

by the inductive hypothesis and definition of $\sigma_n$ .

To complete the proof, observe that $R_n\overset{d}{=}\sigma_n^{-1}(1)$ and is hence uniform over $\{1,\ldots,n\}$ .

Finally, we give the sequence $(X_n)_{n\geq 1}$ and show that it is a martingale. We define it in terms of $R_n$ and the polynomials $B^{\geq}_{n,k}(x)$ defined in (10).

Lemma 3.3 Fix $x\in[0,1]$ and define

\begin{align*} X_n&=B^{\geq}_{{n},{R_n}}(x). \end{align*}

Then $(X_n)_{n\geq 1}$ is a martingale adapted to the filtration $\mathscr{F}_n=\sigma(R_1,\ldots,R_n)$ .

Proof. First, we claim that

(16) \begin{align} B^{\geq}_{n,k}(x) = B^{\geq}_{{n+1},{k+1}}(x) + \frac{n+1-k}{n+1}B^{=}_{{n+1},k}(x). \end{align}

To see this, consider $n+1$ independent trials with success probability x. Then eliminate one at random and consider the event that there are at least k successes in the remaining n trials. The left-hand side of (16) is the probability of this event, which occurs if either (a) there were $k+1$ or more successes in the original set of trials, or (b) there were exactly k successes but the trial removed was a failure. Then (a) occurs with probability $B^{\geq}_{{n+1},{k+1}}(x)$ and (b) with probability $\frac{n+1-k}{n+1}B^{=}_{{n+1},k}(x)$ , proving (16).

Now, we compute

\begin{align*} \mathbb{E} [X_{n+1}\mid \mathscr{F}_n] &= \mathbb{E}\Biggl[ \sum_{k=R_{n+1}}^{n+1} B^{=}_{{n+1},k}(x) \ \Bigg\vert\ \mathscr{F}_n \Biggr]\\ &= \frac{n+1-R_n}{n+1} \sum_{k=R_n}^{n+1}B^{=}_{{n+1},k}(x) + \frac{R_n}{n+1} \sum_{k=R_n+1}^{n+1}B^{=}_{{n+1},k}(x)\\ &= B^{\geq}_{{n+1},{R_n+1}}(x) + \biggl(\frac{n+1-R_n}{n+1}\biggr) B^{=}_{{n+1},{R_n}}(x) = B^{\geq}_{{n},{R_n}}(x), \end{align*}

applying (16) in the last line. Hence $\mathbb{E}[X_{n+1}\mid\mathscr{F}_n] = X_n$ , confirming that the sequence is a martingale.

We will make use of this martingale by applying the optional stopping theorem to assert that $x=X_1=\mathbb{E} X_T$ for various stopping times T. This expectation has the form

\begin{align*} \mathbb{E} X_T = \sum_{n=1}^{\infty}\mathbb{P}[T=n]\,\mathbb{P}[\textrm{Bin}(n,x)\geq R_n\mid T=n].\end{align*}

For a recursive tree system $(\chi,h)$ where $\chi(n)=\mathbb{P}[T=n]$ , if T is chosen so that $R_n=h(n)$ when $T=n$ , this expression is nearly the same as $\Psi(x)$ . The following example is off track for the section, but it illustrates how to use this idea.

Example 3.4 (Example 2.4 revisited) In Example 2.4, we showed that the system $(\chi,h)$ with $\chi(n)=1/n(n-1)$ for $n\geq 2$ and $h(n)\equiv 2$ has automaton distribution map $\Psi(x)=x$ by an explicit calculation. Now we give a new proof that demonstrates how we arrived at the example. Let T be the first time the chain $R_n$ jumps from 1 to 2; that is, $T=\min\{n\colon R_n=2\}$ . By the chain’s dynamics, for $n\geq 2$

\begin{align*} \mathbb{P}[T\geq n] &= \mathbb{P}[R_{n-1}=1] = \prod_{k=2}^{n-1}\frac{k-1}{k}= \frac{1}{n-1},\end{align*}

and

\begin{align*}\mathbb{P}[T=n\mid T\geq n] &= \mathbb{P}[R_n=2\mid R_{n-1}=1] = \frac1n. \end{align*}

Putting these together, we have $\mathbb{P}[T=n] = 1/n(n-1)$ for $n\geq 2$ . Also observe that $T<\infty$ with probability 1, since $\mathbb{P}[T\geq n]\to 0$ as $n\to\infty$ .

Now, we set $\chi(n)=\mathbb{P}[T=n]$ and $h(n)\equiv 2$ . Since $\left\lvert{X_n}\right\rvert\leq 1$ , the optional stopping theorem applies and yields

\begin{align*} x = \mathbb{E} X_T = \sum_{n=2}^{\infty}\mathbb{P}[T=n]\,\mathbb{P}\bigl[\textrm{Bin}(n,x)\geq R_n\mid T=n\bigr] = \sum_{n=2}^{\infty}\chi(n)\mathbb{P}\bigl[ \textrm{Bin}(n,x)\geq 2 \bigr] = \Psi(x). \end{align*}

The next result uses the optional stopping theorem in the same way to compute primitive m-critical systems with a given set of support. Recall that primitive means that each tier has at most one element, i.e. the values $h(\ell)$ are distinct for all $\ell\geq 1$ in the support of the child distribution.

Proof. Fix a sequence $1\leq\ell_1<\cdots<\ell_m$ and let $h(\ell_k)=k$ . We will first prove that if there exists m-concordant $\chi$ supported on $\{0,\ell_1,\ldots,\ell_m\}$ , then a. holds. This shows that such a $\chi$ is unique, if it exists, since we can apply a. inductively to determine $\chi(\ell_1),\ldots,\chi(\ell_m)$ . (Note that it is not obvious a priori that the values of $\chi(\ell_k)$ given by these formulas are positive numbers or that their sum is 1 or smaller, which is why we cannot construct $\chi$ by this formula.) After this, we will prove existence of $\chi$ , and last we show b.–d.

To prove a. under the assumption of existence of $\chi$ , we simply apply Theorem 1.2. In the $k=1$ case we use (7), yielding $1=\Psi'(0)=\chi(\ell_1)\ell_1$ and proving that $\chi(\ell_1)=1/\ell_1$ . Similarly, for $2\leq k\leq m$ , we have $0=\Psi^{(k)}(0)$ and we apply (6) to deduce the rest of a.

Now, we show that $\chi$ exists. Consider the chain $(R_n)_{n\geq 1}$ defined previously, and let

\begin{align*} T = \min\{\ell_k\colon R_{\ell_k}=k\}, \end{align*}

with $T=\infty$ if $R_{\ell_k}\neq k$ for $k=1,\ldots,n$ . The random variable T is a stopping time for the filtration $(\mathscr{F}_n)_{n\geq 1}$ defined in Lemma 3.3. To get a feeling for T, consider the perspective of $R_n$ as the location of 1 in the one-line notation of a growing random permutation $\sigma_n$ , as described before Lemma 3.2. The idea for T is that we only consider stopping at times $\ell_1,\ell_2,\ldots$ , and that we stop at the first time $\ell_k$ where 1 is in position k in $\sigma_{\ell_k}$ .

We define $\chi$ be setting $\chi(\ell_k) = \mathbb{P}[T=\ell_k]$ for $k=1,\ldots,m$ and setting $\chi(0)=\mathbb{P}[T=\infty]$ . Clearly this is a probability measure supported within $\{0,\ell_1,\ldots,\ell_m\}$ . We now compute

\begin{align*} \Psi(x) &= \sum_{\ell=1}^\infty \chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x) = \sum_{k=1}^m \mathbb{P}[T=\ell_k]B^{\geq}_{{\ell_k},k}(x). \end{align*}

As in Example 3.4, this closely resembles $\mathbb{E} X_T$ for the martingale $(X_n)_{n\geq 1}$ defined in Lemma 3.3, since $B^{\geq}_{{\ell_k},k}(x)=X_T$ when $T=\ell_k$ . Indeed, by the optional stopping theorem,

\begin{align*} x = X_1 = \mathbb{E} X_{T\wedge \ell_m} &= \sum_{k=1}^m\mathbb{P}[T=\ell_k]\mathbb{E}[X_T\mid T=\ell_k] + \mathbb{P}[T=\infty]\mathbb{E}[X_{\ell_m}\mid T=\infty]\\ &= \Psi(x) +\chi(0)\sum_{r=1}^{\ell_m}\mathbb{P}[R_{\ell_m}=r\mid T=\infty]B^{\geq}_{{\ell_m},r}(x). \end{align*}

We claim that if $T=\infty$ , then $R_{\ell_m}\geq m+1$ . Indeed, if $T>\ell_1$ , then $R_{\ell_1}\neq 1$ , and hence $R_{\ell_1}\geq 2$ . Since $(R_n)_{n\geq 1}$ is increasing, we then have $R_{\ell_2}\geq 2$ . If $T>\ell_2$ , then $R_{\ell_2}\neq 2$ , and hence $R_{\ell_2}\geq 3$ . Continuing in this way, if $T>\ell_j$ then $R_{\ell_j}\geq j+1$ . In particular, if $T=\infty$ , then $R_{\ell_m}\geq m+1$ , proving the claim. Hence $\mathbb{P}[R_{\ell_m}=r\mid T=\infty]=0$ for $r\leq m$ , yielding

(17) \begin{align} \Psi(x) = x - \chi(0)\sum_{r=m+1}^{\ell_m}\mathbb{P}[R_{\ell_m}=r\mid T=\infty]B^{\geq}_{{\ell_m},r}(x). \end{align}

Now we can confirm that the system $(\chi,h)$ we have constructed is m-concordant. Since the polynomials $B^{\geq}_{{\ell_m},r}(x)$ for $r\geq m+1$ are divisible by $x^{m+1}$ , we rewrite (17) as

\begin{align*} \Psi(x) = x - \chi(0)x^{m+1} F(x), \end{align*}

where F(x) is a polynomial. Since

\begin{align*} \frac{d^k}{dx^k}\biggr|_{x=0} \bigl(x^{m+1}F(x)\bigr) = 0 \end{align*}

for $k=1,\ldots,m$ , we see that $\Psi'(0) = 1$ and $\Psi^{(k)}(0) = 0$ for $2\leq k\leq m$ . Thus we have shown existence of $\chi$ so that $(\chi,h)$ is an m-critical system with support $\{0,\ell_1,\ldots,\ell_m\}$ . We have already shown that that there can be at most one probability measure with this property. Henceforth we denote the measure $\chi$ we have constructed by $\textrm{crit}(\ell_1,\ldots,\ell_m)$ .

When $\ell_1=1$ , we have $T=1$ a.s., which makes $\chi=\delta_1$ and $\Psi(x)=x$ . From now on we assume $\ell_1\geq 2$ . To prove b., we must show $\textrm{crit}(\ell_1,\ldots,\ell_m)$ assigns strictly positive mass to each of $0,\,\ell_1\ldots,\,\ell_m$ . We just need to show that the events $\{T=\ell_k\}$ for $k=1,\ldots,m$ and the event $\{T=\infty\}$ have positive probability. We claim that $T=\ell_k$ occurs if $R_1,\,R_2,\,\ldots,\,R_{\ell_k}$ is the sequence

\begin{align*} 1,\,2,\ldots,\,k,\,k,\ldots,\,k. \end{align*}

Indeed, for $j<k$ either $R_{\ell_j}= \ell_j$ or $R_{\ell_j}=k$ . Since $\ell_1>1$ , we have $\ell_j>j$ , and hence we stop only when we reach $\ell_k$ , proving the claim. Similarly, and $T=\infty$ occurs if $R_1,\ldots,R_{\ell_m}$ is

\begin{align*} 1,\,2,\ldots,\, m+1,\,m+1,\ldots,\,m+1. \end{align*}

By the dynamics of the chain $(R_n)$ , it has positive probability of taking on these sequences.

Property c. follows directly from (17) together with $\chi(0)>0$ from b. It remains to prove d. by showing that $\Psi^{(m+1)}(0)<0$ . From c. we have $\Psi(x)\leq x$ . If $\Psi^{(m+1)}(0)>0$ , then by Taylor approximation we would have $\Psi(x)> x$ for sufficiently small x, a contradiction. Hence $\Psi^{(m+1)}(0)\leq 0$ . To rule out $\Psi^{(m+1)}(0)=0$ , we make use of uniqueness. Choose any $\ell_{m+1}>\ell_m$ and extend h by setting $h(\ell_{m+1})=m+1$ . If $\Psi^{(m+1)}(0)=0$ , then $(\chi,h)$ is $(m+1)$ -concordant and supported within $\{0,\ell_1,\ldots,\ell_{m+1}\}$ . But by what we have already proven, the unique measure with these properties places positive weight on $\ell_{m+1}$ , a contradiction since $\chi(\ell_{m+1})=0$ . Hence $\Psi^{(m+1)}(0)<0$ , completing the proof.

Remark 3.6 Lemma 3.5 has a combinatorial interpretation. Let $\mathfrak{S}_n$ denote the set of permutations of $\{1,\ldots,n\}$ . Fix $1<\ell_1<\cdots<\ell_m$ , and for $\pi\in\mathfrak{S}_m$ consider the sequence of permutations $\pi_1,\ldots,\pi_m=\pi$ where $\pi_k\in\mathfrak{S}_{\ell_k}$ is obtained from $\pi$ by deleting values larger than $\ell_k$ from the one-line notation of $\pi$ . For example, if $(\ell_1,\ell_2,\ell_3)=(3,4,6)$ and $\pi=621435$ , then

\begin{align*} (\pi_1,\pi_2,\pi_3)=(213,\,2143,\,621435). \end{align*}

Now, let $A_k$ consist of all $\pi\in\mathfrak{S}_m$ such that $\pi_k^{-1}(1)=k$ but $\pi_j^{-1}(1)\neq j$ for $j<k$ . In other words, $A_k$ is made up of the permutations $\pi$ in which 1 is in position j in $\pi_j$ for the first time when $j=k$ . For example, in the example above, $621435\in A_2$ , because 1 is not in position 1 in $\pi_1$ but is in position 2 in $\pi_2$ .

Counting the number of permutations in $A_k$ corresponds to computing $\mathbb{P}[T=k]$ in the proof of Lemma 3.5 Thus, for $\chi=\textrm{crit}(\ell_1,\ldots,\ell_m)$ , we have $\left\lvert{A_k}\right\rvert=\ell_m!\chi(k)$ . Lemma 3.5a then yields:

\begin{align*} \left\lvert{A_1}\right\rvert &= \frac{\ell_m!}{\ell_1},\\ \left\lvert{A_k}\right\rvert &= \frac{1}{(\ell_k)_k}\sum_{j=1}^{k-1}(-1)^{k+j+1}\binom{k-1}{j-1}\left\lvert{A_j}\right\rvert(\ell_j)_k, \qquad \text{for $2\leq k\leq m$.} \end{align*}

In this form, the formula suggests an explanation via the inclusion–exclusion principle, though we could not come up with one.

Lemma 3.5 gives us an excellent understanding of primitive m-critical systems. We will extend our knowledge to the nonprimitive m-critical systems in Proposition 3.8. First we need a technical lemma.

Proof. Let $\Psi$ and $\bar\Psi$ be the automaton distribution maps of $(\chi,h)$ and $(\bar\chi,h)$ , respectively. Let $\alpha_k$ be the scalar satisfying $(\bar\chi(p))_{p\in\textrm{tier}(k)}=\alpha_k(\chi(p))_{p\in\textrm{tier}(k)}$ . We will show that $\alpha_k=1$ for all $k\in\{1,\ldots,m\}$ by induction on k. The idea is that m-concordancy together with $\alpha_1=\cdots=\alpha_{k-1}=1$ together with Theorem 1.2 implies that $\alpha_k=1$ .

For the $k=1$ case, we see from (7) that $\bar\Psi'(0)=\alpha_1\Psi'(0)$ . Since $\chi$ and $\bar\chi$ are m-concordant, we have $\Psi'(0)=\bar\Psi'(0)=1$ , showing that $\alpha_1=1$ . Next, assume $\alpha_1=\cdots=\alpha_{k-1}=1$ , and we show that $\alpha_{k}=1$ . By m-concordancy of $\chi$ and $\bar\chi$ , the inductive hypothesis, and (6),

\begin{align*} 0 = \Psi^{(k)}(0) = \sum_{\ell\in\textrm{tier}(k)}\chi(\ell)(\ell)_k + \sum_{j=1}^{k-1}(-1)^{k+j}\binom{k-1}{j-1}\sum_{\ell\in\textrm{tier}(j)}\chi(\ell)(\ell)_k,\end{align*}

and

\begin{align*}0 = \bar\Psi^{(k)}(0) = \alpha_k\sum_{\ell\in\textrm{tier}(k)}\chi(\ell)(\ell)_k + \sum_{j=1}^{k-1}(-1)^{k+j}\binom{k-1}{j-1}\sum_{\ell\in\textrm{tier}(j)}\chi(\ell)(\ell)_k. \end{align*}

By our assumption that $\textrm{tier}(k)$ is non-empty and that $h(\ell)\leq \ell$ , the term $\sum_{\ell\in\textrm{tier}(k)}\chi(\ell)(\ell)_k$ is non-zero. It follows that $\alpha_k=1$ .

Proof. For each $k\in\{1,\ldots,m\}$ and $\ell\in\textrm{tier}(k)$ , define

(18) \begin{align} a_\ell = \frac{\chi(\ell)(\ell)_k}{\sum_{i\in\textrm{tier}(k)}\chi(i)(i)_k}. \end{align}

Note that the denominator in this expression is non-zero: the sum includes $\chi(\ell)(\ell)_k$ , and $\chi(\ell)>0$ for $\ell\in\textrm{tier}(k)$ by definition of $\textrm{tier}(k)$ , and $\ell\geq k$ by our assumption that $h(\ell)\leq\ell$ . Now, we define

(19) \begin{align} \widetilde\chi=\sum_{\ell_1\in\textrm{tier}(1)}\cdots\sum_{\ell_m\in\textrm{tier}(m)}a_{\ell_1}\cdots a_{\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_m). \end{align}

If tiers $1,\ldots,m$ are non-empty, then this sum is a convex combination, since $\sum_{\ell_k\in\textrm{tier}(k)} a_{\ell_k}=1$ and hence

\begin{align*} \sum_{\ell_1\in\textrm{tier}(1)}\cdots\sum_{\ell_m\in\textrm{tier}(m)}a_{\ell_1}\cdots a_{\ell_m} &=\Biggl( \sum_{\ell_1\in\textrm{tier}(1)} a_{\ell_1}\Biggr)\cdots\Biggl( \sum_{\ell_m\in\textrm{tier}(m)} a_{\ell_m}\Biggr)=1. \end{align*}

As a convex combination of m-concordant measures, $\widetilde\chi$ itself is m-concordant. Indeed, its automaton distribution map $\widetilde\Psi$ satisfies $\widetilde\Psi'(0)=1$ and $\widetilde\Psi^{(k)}(0)=0$ for $2\leq k\leq m$ since it is then a convex combination of functions satisfying the same derivative condition. In fact, we will eventually show that $\chi=\widetilde\chi$ and that the assumption of non-empty tiers is automatically satisfied under the assumptions of this proposition. See Example 3.9 to see this decomposition in practice.

We first argue that $\chi=\widetilde\chi$ under the assumption that tiers $1,\ldots, m$ of $(\chi,h)$ are non-empty. With the aim of applying Lemma 3.7, we will show that the vector $(\widetilde\chi(p))_{p\in\textrm{tier}(k)}$ is a scalar multiple of $(\chi(p))_{p\in\textrm{tier}(k)}$ for each $k=1,\ldots,m$ . To prove this, we define

\begin{align*} b_1 = \frac{1}{\sum_{i\in\textrm{tier}(1)}\chi(i)i},\end{align*}

and

\begin{align*} b_k(x_1,\ldots,x_{k-1}) = \frac{1}{\sum_{i\in\textrm{tier}(k)}\chi(i)(i)_k}\sum_{j=1}^{k-1}(-1)^{k+j+1}\binom{k-1}{j-1}\chi(x_j)(x_j)_k, \end{align*}

for $k\geq 2$ . The denominators on the right-hand side of these equations are non-zero by our assumption of non-empty tiers and that $h(\ell)\leq \ell$ . Now, fix an arbitrary $k\in\{1,\ldots,m\}$ . For any $\ell_k\in\textrm{tier}(k)$ , we have

\begin{align*} a_{\ell_k}\textrm{crit}(\ell_1,\ldots,\ell_m)\{\ell_k\} &= \chi(\ell_k)b_k(\ell_1,\ldots,\ell_{k-1}) \end{align*}

by Lemma 3.5a, using the notation $\textrm{crit}(\ell_1,\ldots,\ell_m)\{i\}$ to denote the mass placed on the value i by the measure $\textrm{crit}(\ell_1,\ldots,\ell_m)$ . Now, let $p\in\textrm{tier}(k)$ . Since $\textrm{crit}(\ell_1,\ldots,\ell_m)$ is supported on $\{\ell_1,\ldots,\ell_m\}$ , the following holds for any $\ell_1,\ldots,\ell_{k-1},\ell_{k+1},\ldots,\ell_m$ with $\ell_i\in\textrm{tier}(i)$ :

\begin{align*} \sum_{\ell_k\in\textrm{tier}(k)} a_{\ell_1}\cdots &a_{\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_m)\{p\}\\ &= a_{\ell_1}\cdots a_{\ell_{k-1}}a_p a_{\ell_{k+1}}\cdots a_{\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_{k-1},p,\ell_{k+1},\ldots,\ell_m)\{p\}\\ &= a_{\ell_{k-1}}a_{\ell_{k+1}}\cdots a_{\ell_m} \chi(p)b_k(\ell_1,\ldots,\ell_{k-1}). \end{align*}

Now we use this to compute

\begin{align*} \widetilde\chi(p) &= \sum_{\ell_1\in\textrm{tier}(1)}\cdots\sum_{\ell_m\in\textrm{tier}(m)}a_{\ell_1}\cdots a_{\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_m)\{p\}\\ &= \chi(p)\overbrace{\sum_{\ell_1\in\textrm{tier}(1)}\cdots\sum_{\ell_m\in\textrm{tier}(m)}}^{\text{kth sum omitted}} a_{\ell_1}\cdots a_{\ell_{k-1}}a_{\ell_{k+1}}\cdots a_{\ell_m}b_k(\ell_1,\ldots,\ell_{k-1}). \end{align*}

Thus, for each $p\in\textrm{tier}(k)$ , we have shown that $\widetilde\chi(p)$ is equal to $\chi(p)$ scaled by a factor not depending on p. This completes the proof that $(\widetilde\chi(p))_{p\in\textrm{tier}(k)}$ is a scalar multiple of $(\chi(p))_{p\in\textrm{tier}(k)}$ for each $k=1,\ldots,m$ .

As we noted earlier, $\widetilde\chi$ is m-concordant. Lemma 3.7 applies and shows that $\chi=\widetilde\chi$ . Thus part a. of the proposition is proven under the extra assumption of non-empty tiers.

Finally, we show that this assumption holds whenever $\chi\neq\delta_1$ . This proves b., and it proves a when $\chi\neq\delta_1$ . This will complete the proof, since a. is trivial when $\chi=\delta_1$ since $\chi=\textrm{crit}(1)$ . Thus, we suppose that $(\chi,h)$ satisfies all the conditions of the proposition and has an empty tier. Let k be the smallest value so that tier k is empty. From (7) and $\Psi'(0)=1$ , we have $k\geq 2$ . Let $\bar\chi$ be the k-truncation of $\chi$ , which is equal to the $(k-1)$ -truncation since tier k is empty. Now $(\bar\chi,h)$ is $(k-1)$ -concordant with maximum threshold $k-1$ , and $h(\ell)$ is still increasing, and $\bar\chi$ has finite support. Also tiers $1,\ldots,\,k-1$ are all non-empty in $\bar\chi$ . Thus all conditions of this proposition are satisfied with m as $k-1$ as well as the non-empty tiers assumption, and therefore $\bar\chi$ decomposes into a convex combination of measures $\textrm{crit}(\ell_1,\ldots,\ell_{k-1})$ with $\ell_i\in\textrm{tier}(i)$ .

By definition of the k-truncation, the measures $\chi$ and $\bar\chi$ place the same weight on all values in tiers $1,\ldots,k$ . By Corollary 1.3, this implies that $\bar\Psi^{(k)}(0)=\Psi^{(k)}(0)$ . And since $\chi$ is m-concordant, we have $\Psi^{(k)}(0)=0$ and can conclude that $\bar\Psi^{(k)}(0)=0$ as well.

Now, consider the decomposition of $\bar\chi$ into a convex combination of measures of the form $\textrm{crit}(\ell_1,\ldots,\ell_{k-1})$ . Let $\Psi_{\ell_1,\ldots,\ell_{k-1}}$ denote the automaton distribution maps of these measures, and note that $\bar\Psi$ is a convex combination of these maps. By Lemma 3.5d, each measure $\textrm{crit}(\ell_1,\ldots,\ell_{k-1})$ is either k-subcordant or is equal to $\delta_1$ . In the first case, $\Psi_{\ell_1,\ldots,\ell_{k-1}}^{(k)}(0)<0$ , and in the second $\Psi_{\ell_1,\ldots,\ell_{k-1}}^{(k)}(0)=0$ . Since $\bar\Psi^{(k)}(0)=0$ , we have $\textrm{crit}(\ell_1,\ldots,\ell_{k-1})=\delta_1$ for all measures in the decomposition of $\bar\chi$ , and therefore $\bar\chi=\delta_1$ . But if the k-truncation of $\chi$ is $\delta_1$ , then $\chi$ itself is equal to $\delta_1$ . Hence $\chi=\delta_1$ if any of tiers $1,\ldots,m$ are empty.

Here is an example of the decomposition of a critical system into primitive ones. We find it helpful for understanding both Lemma 3.5 and Proposition 3.8.

Example 3.9 Let

\begin{align*} \chi(\ell)=\begin{cases} 64/135 & \text{for $\ell=0$,}\\[4pt] 1/3 & \text{for $\ell=2$,}\\[4pt] 1/9 & \text{for $\ell=3$},\\[4pt] 1/27 & \text{for $\ell=4$,}\\[4pt] 2/45 & \text{for $\ell=5$,} \end{cases}\qquad\qquad \text{and} \qquad\qquad h(\ell)=\begin{cases} 1 & \text{for $\ell=0$,}\\[4pt] 1 & \text{for $\ell=2$,}\\[4pt] 1 & \text{for $\ell=3$,}\\[4pt] 2 & \text{for $\ell=4$},\\[4pt] 2 & \text{for $\ell=5$.} \end{cases}\end{align*}

We claim that $(\chi,h)$ is 2-critical. Indeed, it has maximum threshold 2, and by (7) and (8), the automaton distribution map $\Psi$ satisfies

\begin{align*} \Psi'(0) &= \chi(2)(2) + \chi(3)(3) = 1,\\[4pt] \Psi''(0) &= \chi(4)(4)(3) + \chi(5)(5)(4) - \chi(2)(2)(1) - \chi(3)(3)(2) = 0.\end{align*}

By Proposition 3.8, we can express $\chi$ as a mixture of the measures $\textrm{crit}(2,4)$ , $\textrm{crit}(2,5)$ , $\textrm{crit}(3,4)$ , and $\textrm{crit}(3,5)$ . First, we compute these measures, which can be done most easily using Lemma 3.5a:

\begin{align*} \textrm{crit}(2,4)\{\ell\} &= \begin{cases} 5/12 & \text{for $\ell=0$,}\\[4pt] 1/2 & \text{for $\ell=2$,}\\[4pt] 1/12 & \text{for $\ell=4$,} \end{cases} & \textrm{crit}(3,4)\{\ell\} &= \begin{cases} 1/2 & \text{for $\ell=0$,}\\[4pt] 1/3 & \text{for $\ell=3$,}\\[4pt] 1/6 & \text{for $\ell=4$,} \end{cases}\\[4pt] \textrm{crit}(2,5)\{\ell\} &= \begin{cases} 9/20 & \text{for $\ell=0$,}\\ 1/2 & \text{for $\ell=2$,}\\ 1/20 & \text{for $\ell=5$,} \end{cases} & \textrm{crit}(3,5)\{\ell\} &= \begin{cases} 17/30 & \text{for $\ell=0$,}\\ 1/3 & \text{for $\ell=3$,}\\ 1/10 & \text{for $\ell=5$.} \end{cases}\end{align*}

We can find a decomposition of $\chi$ using the technique from the proof of Proposition 3.8. We apply (18) to compute

\begin{align*} a_2 &= \frac{\chi(2)(2)}{\chi(2)(2) + \chi(3)(3)} = \frac23,& a_4 &= \frac{\chi(4)(4)(3)}{\chi(4)(4)(3) + \chi(5)(5)(4)}=\frac13,\\[4pt] a_3 &= \frac{\chi(3)(3)}{\chi(2)(2) + \chi(3)(3)} = \frac13, & a_5 &=\frac{\chi(5)(5)(4)}{\chi(4)(4)(3) + \chi(5)(5)(4)}=\frac23.\end{align*}

Now (19) gives

\begin{align*} \chi &= a_2a_4\textrm{crit}(2,4) + a_2a_5\textrm{crit}(2,5) + a_3a_4\textrm{crit}(3,4) + a_3a_5\textrm{crit}(3,5)\\[4pt] &= (2/9)\textrm{crit}(2,4) + (4/9)\textrm{crit}(2,5) + (1/9)\textrm{crit}(3,4) + (2/9)\textrm{crit}(3,5).\end{align*}

It follows from Lemma 3.5 and Proposition 3.8 that m-critical systems have no non-zero fixed points. We show this together with some other simple consequences of these lemmas:

Proof. The statement about $\bigl(x-\Psi(x)\bigr)/\chi(0)$ is a direct consequence of Lemma 3.5 and Proposition 3.8: We use Proposition 3.8 to decompose $\chi$ as

\begin{align*} \chi=\sum_{\ell_1,\ldots,\ell_m} a_{\ell_1,\ldots,\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_m), \end{align*}

where the sum ranges over all $\ell_k\in\textrm{tier}(k)$ for $k=1,\ldots,m$ and the coefficients $a_{\ell_1,\ldots,\ell_m}$ are non-negative and sum to 1. Let $\Psi_{\ell_1,\ldots,\ell_m}$ denote the automaton distribution map for $\textrm{crit}(\ell_1,\ldots,\ell_m)$ , and observe that the automaton distribution map $\Psi$ of $(\chi,h)$ also decomposes as

\begin{align*} \Psi(x) = \sum_{\ell_1,\ldots,\ell_m} a_{\ell_1,\ldots,\ell_m}\Psi_{\ell_1,\ldots,\ell_m}(x). \end{align*}

When $\ell_1\geq 2$ , the expression $x-\Psi_{\ell_1,\ldots,\ell_m}(x)$ is a linear combination of the polynomials

\begin{align*} B^{\geq}_{{\ell_m},r}(x),\quad r\in\{m+1,\ldots,\ell_m\} \end{align*}

with non-negative coefficients summing to $\textrm{crit}(\ell_1,\ldots,\ell_m)\{0\}$ by Lemma 3.5c. In fact, this holds when $\ell_1=1$ as well, since then $x-\Psi_{\ell_1,\ldots,\ell_m}(x)=0$ and $\textrm{crit}(\ell_1,\ldots,\ell_m)\{0\}=0$ . Hence,

\begin{align*} x - \Psi(x) = x - \sum_{\ell_1,\ldots,\ell_m} a_{\ell_1,\ldots,\ell_m}\Psi_{\ell_1,\ldots,\ell_m}(x) = \sum_{\ell_1,\ldots,\ell_m} a_{\ell_1,\ldots,\ell_m}\bigl(x-\Psi_{\ell_1,\ldots,\ell_m}(x)\bigr) \end{align*}

is a linear combination of polynomials $B^{\geq}_{{\ell_m},r}(x)$ for $\ell_m\in\textrm{tier}(m)$ and $m+1\leq r\leq \ell_m$ , with non-negative coefficients summing to

(20) \begin{align} \sum_{\ell_1,\ldots,\ell_m} a_{\ell_1,\ldots,\ell_m}\textrm{crit}(\ell_1,\ldots,\ell_m)\{0\}=\chi(0). \end{align}

Finally, we show that $\Psi(x)<x$ for $x\in(0,1]$ . Since $x-\Psi(x)$ is a linear combination with non-negative coefficients of polynomials $B^{\geq}_{{\ell_m},r}(x)$ that are non-negative on [0,Reference Auffinger and Cable1], we have $\Psi(x)\leq x$ for $x\in[0,1]$ . Since these polynomials are strictly positive for $x\in(0,1]$ , the statement holds so long any of them are included in the decomposition of $x-\Psi(x)$ . Since each summand on the left-hand side of (20) is non-zero whenever $\ell_1\geq 2$ by Lemma 3.5b, this is true unless $a_{\ell_1,\ldots,\ell_m}=0$ for all $\ell_1\geq 2$ . But since $\textrm{crit}(\ell_1,\ldots,\ell_m)=\delta_1$ if $\ell_1=1$ , this would imply that $\chi=\delta_1$ .

The following is a trivial but useful observation:

Lemma 3.11 For any $x\in(0,1]$ and positive integer r satisfying $h(r)\leq r$ , the system $(\chi,h)$ has x as a fixed point if and only if

(21) \begin{align} \chi(r) = \frac{x - \sum_{\ell\neq r}\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)}{B^{\geq}_{{r},{h(r)}}(x)}. \end{align}

Proof. Since $B^{\geq}_{{r},{h(r)}}(x)=\mathbb{P}[\textrm{Bin}(r,x)\geq h(r)]$ is positive by our assumption that $x>0$ and $h(r)\leq r$ , equation (21) is equivalent to

\begin{align*} \chi(r)\mathbb{P}[\textrm{Bin}(r,x)\geq h(r)] + \sum_{\ell\neq r}\chi(\ell)\mathbb{P}[\textrm{Bin}(\ell,x)\geq h(\ell)] = x. \end{align*}

That is, equation (21) is equivalent to the statement $\Psi(x)=x$ .

Suppose that $(\chi,h)$ has maximum support n and is m-critical, and that $h(\ell)$ is increasing and satisfies $h(\ell)\leq\ell$ for $\ell\geq 1$ . By Proposition 3.10, this system has no fixed points other than 0. Now suppose that $r\geq n+1$ and $h(r)=m+1$ , and that we wish to modify $\chi$ by shifting mass from 0 onto r to create a given fixed point. (There is no obvious reason we would want to do this, but it turns out to be a key step in the proof of Proposition 3.1.) The previous lemma suggests that we can do so by setting $\chi(r)$ to make (21) hold. But this might not be possible, since (21) may demand that $\chi(r)$ be too small (i.e. negative) or too large (i.e. greater than $\chi(0)$ ). The following result combines with Lemma 3.11 to show that neither of these occurs.

Lemma 3.12 Suppose that $(\chi,h)$ is m-critical and $\chi\neq\delta_1$ . Assume that $\chi$ is supported on $\{0,\ldots,n\}$ , that $h(\ell)$ is increasing, and that $h(\ell)\leq \ell$ for all $\ell\geq 1$ . Fix some integer $r\geq n+1$ and suppose that $h(r)=m+1$ . Define $\varphi(x)$ for $x\in(0,1]$ by

(22) \begin{align} \varphi(x) = \frac{x - \sum_{\ell=1}^{n}\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)}{B^{\geq}_{{r},{m+1}}(x)}. \end{align}

Then $\varphi(x)\in(0,\chi(0)]$ , and $\varphi(x)$ is strictly increasing.

Proof. Let $\Psi$ be the automaton distribution map of $(\chi,h)$ , and note that the numerator on the right-hand side of (22) is equal to $x-\Psi(x)$ . By Proposition 3.10, this quantity is strictly positive, proving that $\varphi(x)>0$ . Proposition 3.10 also lets us express $x-\Psi(x)$ as a linear combination of polynomials $B^{\geq}_{{\ell},j}(x)$ for $\ell<r$ and $j\geq m+1$ , with non-negative coefficients. Lemma 3.13 to follow shows that $B^{\geq}_{{\ell},j}(x)/B^{\geq}_{{r},m+1}(x)$ is strictly increasing for all $\ell<r$ and $j\geq m+1$ , proving that $\varphi$ is strictly increasing. Finally, direct evaluation shows that $\varphi(1)=1-\sum_{\ell=1}^n\chi(\ell)=\chi(0)$ , and since $\varphi$ is increasing we have $\varphi(x)\leq\chi(0)$ for $x\in(0,1]$ .

Lemma 3.13 Let $1\leq j\leq p$ and $1\leq k\leq r$ . If $p< r$ and $j\geq k$ , or if $p\leq r$ and $j > k$ , then

(23) \begin{align} \frac{B^{\geq}_{p,j}(x)}{B^{\geq}_{r,k}(x)} \end{align}

is strictly increasing in x for $x\in(0,1]$ .

Proof. First we consider the case where $j=k$ and $r=p+1$ . The event $\{\textrm{Bin}(p+1,x)\geq j\}$ occurs if the first p coin flips yield at least j successes, or if they yield exactly $j-1$ successes and the final coin flip is a success. Hence

\begin{align*} \mathbb{P}[\textrm{Bin}(p+1,x)\geq j]=\mathbb{P}[\textrm{Bin}(p,x)\geq j] + x\mathbb{P}[\textrm{Bin}(p,x)=j-1], \end{align*}

giving us

\begin{align*} \frac{\mathbb{P}[\textrm{Bin}(p,x)\geq j]}{\mathbb{P}[\textrm{Bin}(p+1,x)\geq j]} &= 1 - \frac{x\mathbb{P}[\textrm{Bin}(p,x)=j-1]}{\mathbb{P}[\textrm{Bin}(p+1,x)\geq j]}\\[5pt] &= 1 - \frac{\binom{p}{j-1}x^{j}(1-x)^{p-j+1}}{\sum_{n=j}^{p+1}\binom{p+1}{n}x^n(1-x)^{p-n+1}}\\[5pt] &= 1 - \frac{\binom{p}{j-1}}{\sum_{n=j}^{p+1}\binom{p+1}{n}x^{n-j}(1-x)^{j-n}}. \end{align*}

The expression $x^{n-j}(1-x)^{j-n}$ is increasing in x for $n\geq j$ and strictly increasing for $n>j$ . Since $j\leq p$ , the sum contains at least one strictly increasing term. Hence this expression is strictly increasing.

Next, consider the case where $j = k+1$ and $p=r$ . Here, we have

\begin{align*} \frac{\mathbb{P}[\textrm{Bin}(p,x)\geq k+1]}{\mathbb{P}[\textrm{Bin}(p,x)\geq k]} &= \frac{\mathbb{P}[\textrm{Bin}(p,x)\geq k]-\mathbb{P}[\textrm{Bin}(p,x)=k]}{\mathbb{P}[\textrm{Bin}(p,x)\geq k]} = 1 - \frac{\mathbb{P}[\textrm{Bin}(p,x)=k]}{\mathbb{P}[\textrm{Bin}(p,x)\geq k]}. \end{align*}

Hence it suffices to show that $\mathbb{P}[\textrm{Bin}(p,x)\geq k] / \mathbb{P}[\textrm{Bin}(p,x)=k]$ is strictly increasing. We express this quantity as

\begin{align*} \frac{\mathbb{P}[\textrm{Bin}(p,x)\geq k]}{ \mathbb{P}[\textrm{Bin}(p,x)=k]} &= \frac{\sum_{n=k}^p\binom{p}{n}x^n(1-x)^{p-n}}{\binom{p}{k}x^k(1-x)^{p-k}} = \sum_{n=k}^p \frac{\binom{p}{n}}{\binom{p}{k}} x^{n-k}(1-x)^{k-n}. \end{align*}

As in the previous case, the expression $x^{n-k}(1-x)^{n-k}$ is increasing in x for $n\geq k$ and is strictly increasing for $n>k$ , and at least one of the strictly increasing terms appears.

Finally, the general case follows from the two special cases by expressing (23) as a product of quotients considered in the special cases. For example,

\begin{align*} \frac{B^{\geq}_{5,3}(x)}{B^{\geq}_{7,2}(x)} &= \frac{B^{\geq}_{5,3}(x)}{B^{\geq}_{6,3}(x)}\frac{B^{\geq}_{6,3}(x)}{B^{\geq}_{7,3}(x)}\frac{B^{\geq}_{7,3}(x)}{B^{\geq}_{7,2}(x)}, \end{align*}

and is hence the product of strictly increasing functions.

Proof of Proposition 3.1. Let $(\chi,h)$ be the m-truncation of an m-supercordant system, and let $\Psi$ be its automaton distribution map. We must show that $\Psi$ has a single fixed point on (0,1]. We observe that $(\chi,h)$ is m-supercordant itself, since by Theorem 1.2 the first m derivatives of $\Psi$ at 0 are equal to those of the automaton distribution map of the original m-supercordant system (see Corollary 1.3).

If $h(\ell)\leq\ell$ does not hold for all $\ell\geq 1$ , define a new system $(\widetilde\chi,\widetilde{h})$ where for $\ell\geq 1$ ,

\begin{align*} \widetilde\chi(\ell) &= \begin{cases} \chi(\ell) & \text{if $h(\ell)\leq \ell$,}\\[5pt] 0 & \text{if $h(\ell)>\ell$,} \end{cases},& \widetilde{h}(\ell) &= \begin{cases} h(\ell) & \text{if $h(\ell)\leq \ell$,}\\[5pt] \ell & \text{if $h(\ell)>\ell$,} \end{cases} \end{align*}

with $\widetilde\chi(0)$ set to make $\widetilde\chi$ a probability measure. Note that $\widetilde{h}(\ell)$ is still increasing. Since $B^{\geq}_{{\ell},{h(\ell)}}(x)=0$ when $h(\ell)>\ell$ , the systems $(\chi,h)$ and $(\widetilde\chi,\widetilde{h})$ have identical automaton distribution maps, and we can work with $(\widetilde\chi,\widetilde{h})$ in place of $(\chi,h)$ . Thus we will assume without loss of generality that $h(\ell)\leq\ell$ for all $\ell\geq 1$ .

We first give a proof for the case that tier m of $(\chi,h)$ consists of a single value r. Since the system is supercordant, by Taylor approximation we have $\Psi(x)>x$ for $x\in(0,\epsilon)$ for some sufficiently small $\epsilon>0$ . Since $\Psi(1)\leq 1$ , the graph of $\Psi$ eventually dips down below or onto the line $y=x$ , and hence $\Psi$ has some non-zero fixed point. Now we show it has at most one. Let $\bar\chi$ be the $(m-1)$ -truncation of $\chi$ . The system $(\bar\chi,h)$ is $(m-1)$ -concordant by Corollary 1.3. Its maximum threshold is $m-1$ or less by definition of truncation. By Proposition 3.8b, it is $(m-1)$ -critical. Define a map $\varphi\colon(0,1]\to\mathbb{R}$ by

(24) \begin{align} \varphi(x) &= \frac{x - \sum_{\ell=1}^{r-1}\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)}{B^{\geq}_{r,m}(x)} = \frac{x - \sum_{\ell=1}^{r-1}\bar\chi(\ell)B^{\geq}_{{\ell},{h(\ell)}}(x)}{B^{\geq}_{r,m}(x)}. \end{align}

By Lemma 3.11, the non-zero fixed points of $(\chi,h)$ make up the set $\varphi^{-1}\bigl(\chi(r)\bigr)$ . By Lemma 3.12 applied to $(\bar\chi,h)$ , the function $\varphi(x)$ is strictly increasing. Thus $\varphi^{-1}\bigl(\chi(r)\bigr)$ contains no more than one point, and $(\chi,h)$ has at most one non-zero fixed point. This shows that $(\chi,h)$ has exactly one non-zero fixed point $x_0$ , with $\Psi(x)>x$ for $x\in(0,x_0)$ and $\Psi(x)<x$ for $x\in(x_0,1]$ .

To extend the proof to the case where tier m contains more than one value, again assume that $(\chi,h)$ has maximum threshold m and is m-supercordant. As before, by Taylor approximation $\Psi(x)$ has at least one fixed point on (0,1]. Since the fixed points form a closed subset of (0,1], there is a largest fixed point; call it $x_0$ . Let r be the smallest value in tier m of $(\chi,h)$ . Our strategy now will be to construct a new system $(\widetilde\chi,h)$ where all of tier m is concentrated on r. By the special case of the proposition we have already proven, this system has a unique non-zero fixed point. Then we will compare this system’s automaton distribution map to $\Psi$ and show that $\Psi$ must also have a unique fixed point (see Figure 4).

Figure 4. Let $\chi$ place vector of probabilities $\bigl(\frac{1}{10},0,\frac12,\frac15,\frac15\bigr)$ on values 0, 1, 2, 3, 4, and let $h(0)=h(2)=1$ and $h(3)=h(4)=2$ . The system $(\chi,h)$ is 2-supercordant; its automaton distribution map can be computed to be $\Psi(x)=x + \frac{13}{10}x^2 -2x^3 + \frac35 x^4$ , with fixed point $x_0=(10-\sqrt{22})/6\approx 0.885$ . The system $(\widetilde\chi,h)$ with the same fixed point but only a single value in tier 2 is found by computing $p=\varphi(x_0)\approx 0.406$ , where $\varphi$ is given in (24), and then letting $\widetilde\chi$ place vector of probabilities $\bigl(\frac{1}{2}-p,0,\frac12,p,0\bigr)$ on 0, 1, 2, 3, 4. The automaton distribution map $\widetilde{\Psi}$ of $(\widetilde\chi,h)$ is shown above together with $\Psi$ .

To carry this out, first let $\bar\chi$ be the $(m-1)$ -truncation of $\chi$ and define $\varphi$ by (24) again. Let $p=\varphi(x_0)$ . Now we define a new probability measure $\widetilde\chi$ supported on $\{0,\ldots,r\}$ by

\begin{align*} \widetilde\chi(\ell) &= \begin{cases} \bar\chi(\ell) & \text{if $1\leq\ell\leq r-1$,}\\[5pt] \bar\chi(0)-p & \text{if $\ell=0$,}\\[5pt] p & \text{if $\ell=r$.} \end{cases} \end{align*}

Note that this is a valid probability measure since $p\in(0,\bar\chi(0)]$ by Lemma 3.12 applied to $(\bar\chi,h)$ . Now we consider the system $(\widetilde\chi,h)$ . By Lemma 3.11, it has $x_0$ as a fixed point. By the special case of this proposition we have already proven, the system $(\widetilde\chi,h)$ has no other non-zero fixed points besides $x_0$ , and $\widetilde\Psi(x)>x$ for $0<x<x_0$ , where $\widetilde\Psi$ is the automaton distribution map of $(\widetilde\chi,h)$ .

We claim that $\Psi(x)\geq \widetilde\Psi(x)$ for $0<x<x_0$ . Indeed, comparing the two functions, we have

\begin{align*} \Psi(x) - \widetilde\Psi(x) = \sum_{\ell=r}^{\infty}\chi(\ell)B^{\geq}_{{\ell},m}(x) - pB^{\geq}_{r,m}(x). \end{align*}

Hence

\begin{align*} \frac{\Psi(x) - \widetilde\Psi(x)}{B^{\geq}_{r,m}(x)} &= \chi(r) + \sum_{\ell=r+1}^{\infty}\chi(\ell)\frac{B^{\geq}_{{\ell},m}(x)}{B^{\geq}_{r,m}(x)} - p. \end{align*}

By Lemma 3.13, this expression is strictly decreasing in x. It equals 0 at $x=x_0$ since $\Psi(x)=\widetilde\Psi(x_0)=x_0$ , and hence it is positive when $0<x<x_0$ , establishing the claim.

Since $\Psi(x)\geq\widetilde\Psi(x)$ for $0<x<x_0$ , and we have already shown that $\widetilde\Psi(x)>x$ for $0<x<x_0$ , the function $\Psi$ has no non-zero fixed points smaller than $x_0$ . Since $x_0$ was taken to be the largest fixed point of $\Psi$ , it is the only one.

4. Proofs of main theorems

Recall the notation $n_t(v)$ for the number of children of v in a rooted tree t and the definition that S is an admissible subtree of a rooted tree T if S contains the root of T and $n_S(v)\geq h(n_T(v))$ for all vertices v in S. Also recall that t(v) denotes the subtree of t consisting of v and all its descendants.

Proof of Proposition 1.9. Let

\begin{align*} \mathcal{T}_1=\{\text{T contains an admissible subtree}\}. \end{align*}

The largest fixed point $x_1$ of $(\chi,h)$ always has a corresponding interpretation [Reference Johnson, Podder and Skerman14, Proposition 5.6]. To prove that $\mathcal{T}_1$ is this interpretation, we first establish that $\mathcal{T}_1$ is an interpretation (i.e. it behaves consistently with the threshold function h). Then, we show that for any interpretation $\mathcal{T}$ , there exists an admissible subtree on the event $\mathcal{T}$ , and hence $\mathcal{T}_1$ must have the largest probability of any interpretation.

To show that $\mathcal{T}_1$ is an interpretation, we must show the following: Let t be a tree with root $\rho$ that has $\ell$ children. Then we have $t\in\mathcal{T}_1$ if and only if $t(v)\in\mathcal{T}_1$ for at least $h(\ell)$ children v of $\rho$ . To prove this, first observe that if s is an admissible subtree of t containing a vertex v, then s(v) is an admissible subtree of t(v). Now, suppose $t\in\mathcal{T}_1$ . It thus contains an admissible subtree s. For each child $v\in s$ of $\rho$ , we have $t(v)\in\mathcal{T}_1$ since s(v) is an admissible subtree of t(v). And since s is admissible, $n_s(\rho)\geq h(\ell)$ . Conversely, suppose there are at least $h(\ell)$ children v of $\rho$ such that $t(v)\in\mathcal{T}_1$ . Each subtree t(v) contains an admissible subtree. The concatenation of all of them together with $\rho$ is then admissible. This completes the proof that $\mathcal{T}_1$ is an interpretation.

Now, let $\mathcal{T}$ be an arbitrary interpretation of $(\chi,h)$ , and we argue that on the event $\mathcal{T}$ there exists an admissible subtree S of T. To form S when $\mathcal{T}$ occurs, let it include $\rho$ . Then let it contain all children $v_1$ of $\rho$ for which $T(v_1)\in\mathcal{T}$ , and then let it contain all children $v_2$ of these children for which $T(v_2)\in\mathcal{T}$ , and so on. Since a tree t with root $\rho$ is in $\mathcal{T}$ if and only if at least $h(n_t(\rho))$ of its root-child subtrees are in $\mathcal{T}$ , the tree S is admissible.

To complete the proof, observe that $\textrm{GW}_{{\chi}}(\mathcal{T}_1)$ is a fixed point of $(\chi,h)$ since $\mathcal{T}_1$ is an interpretation. For any interpretation $\mathcal{T}_1$ , we have $\textrm{GW}_{{\chi}}(\mathcal{T})\leq\textrm{GW}_{{\chi}}(\mathcal{T}_1)$ , since $\mathcal{T}\subseteq\mathcal{T}_1$ . Thus $\mathcal{T}_1$ must correspond to the largest interpretable fixed point, which is $x_1$ .

Next, we show that any admissible subtree contains a minimal admissible subtree within it. This is akin to showing that a tree in which all vertices have at least two children contains a subtree in which all vertices have exactly two children.

Proof. We construct s’ one level at a time. We start by including the root of t in it. Now, suppose we have constructed it to level n. Consider a level n vertex v in $s'$ . By admissibility it has at least $h(n_t(v))$ children in s. Arbitrarily choose exactly $h(n_t(v))$ of them to include in $s'$ . Proceeding like this for all of the level n vertices in $s'$ and then continuing on to successive levels produces $s'\subseteq s$ that is an admissible subtree of t.

Proof of Theorem 1.8. Let r be the highest value in tier m of $(\chi,h)$ . Let $\mathcal{T}_0$ be the event described in the statement of this theorem, that T contains an admissible subtree S in which all but finitely many vertices v satisfy $n_S(v)\leq m$ . First, we show that $\mathcal{T}_0$ is an interpretation. The argument is mostly the same as for $\mathcal{T}_1$ being an interpretation in the proof of Proposition 1.9. Let t be a tree with root $\rho$ that has $\ell$ children. First, suppose that $t(v)\in\mathcal{T}_0$ holds for at least $h(\ell)$ of the children v of $\rho$ . For each such vertex v, the root-child subtree t(v) thus contains an admissible subtree s(v) for which all but finitely many vertices $u\in s(v)$ satisfy $n_{s(v)}(u)\leq m$ . Combining each subtree s(v) together with $\rho$ yields an admissible subtree of t for which all but finitely many vertices have m or fewer children, showing that $t\in\mathcal{T}_0$ . Conversely, suppose that $t\in\mathcal{T}_0$ , and let s be an admissible subtree of t for which all but finitely many vertices $v\in s$ satisfy $n_s(v)\leq m$ . In general, for any admissible subtree s of t and $v\in s$ , the tree s(v) is an admissible subtree of t(v). And if all but finitely many vertices in s have m or fewer children, then the same is true for any subtree s(v). Thus for any child v of $\rho$ in s, we have $t(v)\in\mathcal{T}_0$ . By admissibility of s, we have $n_s(\rho)\geq h(\ell)$ . Hence $t(v)\in\mathcal{T}_0$ for at least $h(\ell)$ children v of $\rho$ . This completes the proof that $\mathcal{T}_0$ is an interpretation and its probability is therefore one of the fixed points of $\Psi$ .

Now we must determine which fixed point is associated with $\mathcal{T}_0$ . Since $(\chi,h)$ is m-supercordant, by Taylor approximation we have $\Psi(x)>x$ for $x\in(0,\epsilon)$ for a sufficiently small $\epsilon$ . We cannot have $\Psi(x)>x$ for all $x\in(0,1]$ since $\Psi(1)\leq 1$ . Hence $\Psi$ has a smallest non-zero fixed point $x_0$ . Our goal now is to show that $\textrm{GW}_{{\chi}}(\mathcal{T}_0)=x_0$ .

Let $\bar\chi$ be the m-truncation of $\chi$ , and consider the system $(\bar\chi,h)$ . Its automaton distribution map $\bar\Psi$ has a unique non-zero fixed point $\bar x_0$ by Proposition 3.1. Directly from the definition of the automaton distribution map, we have $\bar\Psi(x)\leq\Psi(x)$ . Also $(\bar\chi,h)$ remains m-supercordant by Corollary 1.3, and hence the graph of $\bar\Psi$ is above the line $y=x$ near 0. These last two facts prove that $\bar x_0\leq x_0$ . Let ${\overline{T}}\sim\textrm{GW}_{{\bar\chi}}$ . Since $\bar x_0$ is the only non-zero fixed point of $\bar\Psi$ , by Proposition 1.9 the interpretation $\overline{\mathcal{T}}$ of $(\bar\chi,h)$ associated with $\bar x_0$ is that ${\overline{T}}$ contains an admissible subtree.

Couple ${\overline{T}}$ with T by defining ${\overline{T}}$ as the connected component of the root in the subgraph of T consisting of the root together with each vertex whose parent v satisfies $n_T(v)\leq r$ . We claim that under this coupling, $\overline{\mathcal{T}}$ holds if and only if T contains an admissible subtree S made up entirely of vertices v satisfying $n_S(v)\leq m$ . To prove this, first observe that under this coupling, we have $n_{{\overline{T}}}(v)=n_T(v)\textbf{1}\{n_T(v)\leq r\}$ for $v\in{\overline{T}}$ . If ${\overline{S}}$ is an admissible subtree of ${\overline{T}}$ , then it has no leaves by the positivity of h; hence $n_{{\overline{T}}}(v)\geq n_{{\overline{S}}}(v)\geq 1$ for $v\in{\overline{S}}$ . Therefore $n_{\overline{T}}(v)=n_T(v)$ for all $v\in {\overline{S}}$ . This proves that ${\overline{S}}$ is an admissible subtree not just of ${\overline{T}}$ but also of T. For every vertex $v\in {\overline{S}}$ besides the root, the parent u of v satisfies $n_{\overline{T}}(v)=n_T(v)\leq r$ . Since ${\overline{S}}$ has no leaves, every vertex in ${\overline{S}}$ is the parent of some other vertex, and hence $n_T(v)\leq r$ for all $v\in{\overline{S}}$ . This proves that if $\overline{\mathcal{T}}$ holds, then T contains an admissible subtree ${\overline{S}}$ made up entirely of vertices v satisfying $n_T(v)\leq r$ . By Lemma 4.1, there exists a subtree $S'\subset{\overline{S}}$ that is also an admissible subtree of T and which satisfies $n_{S'}(v)=h(n_T(v))$ for all $v\in S'$ . Since $n_T(v)\leq r$ and $h(r)=m$ , we have $n_{S'}(v)\leq m$ for all $v\in S'$ .