ESTIMATING MONOTONE DENSITIES

BY CELLULAR BINARY TREES

Luc Devroye and Jad Hamdan

School of Computer Science, McGill University

Abstract. We propose a novel, simple density estimation algorithm for bounded
monotone densities with compact support under a cellular restriction. We show
that its expected error ($L_{1}$ distance) converges at a rate of $n^{-1/3}$,
that its expected runtime is sublinear and, in doing so, find a connection to
the theory of Galton–Watson processes. Keywords. Density estimation, cellular
computation, binary trees, Galton–Watson trees. MSC2020 subject
classification. Primary 62G07, 68Q87, 68W40; secondary 60C05, 60J85.

## . ntroduction

In this note, we consider density estimation on $[0,1]$ from an i.i.d. sample
$X_{1},...,X_{n}$ drawn from an unknown density $f$ that is monotonically
decreasing on its support.

The idea of estimating a density using a recursive partition of the space into
intervals (or rectangles in $\mathbf{R}^{d}$) is quite old. In fact, histogram
estimates based on a regular grid can be viewed as estimates that use a
complete tree to partition the space. We take the view that the creation of
the partition is the main problem: given a partition, we estimate the density
by the standard histogram estimate. The data mining community (Schmidberger,
2009 [20]; Ram and Gray, 2011 [19]; Anderlini, 2016 [2]) refers to this
general method as “density estimation trees”.

We take a view similar to Biau and Devroye (2013) [7] in their cellular
approach to classification. The recursive partition of the space is achieved
by a simple immediate decision taken independently for each node in the tree,
assuming each node corresponds to a region of the space, and the data in it.
If the decision is not to split, then the node is a leaf in the tree, and the
region is a set in the final partition. If the decision is to split, then
there are two child nodes in the tree, corresponding to two disjoint regions
whose union is the parent region. All decisions must be restricted to the
locally available data—the region and the points in it—so, no decision can use
the original data size, “$n$”, for example.

To illustrate this principle, we look at the benchmark problem of the
estimation of a monotonically decreasing density $f$ on $[0,1]$.

Imagine that an interval $C$ is given, and a sample drawn from $f$ restricted
to that interval. Let $C^{\prime}$ and $C^{\prime\prime}$ be the left and
right halves of $C$, and let $N^{\prime}$ and $N^{\prime\prime}$ be the number
of sample points falling in $C^{\prime}$ and $C^{\prime\prime}$, respectively.
We are asked to decide whether it is best to use a histogram estimate on $C$
(estimating $f$ on it by $(N^{\prime}+N^{\prime\prime})/(n\cdot\lambda(C))$
where $\lambda(C)$ is the length of $C$), or to split $C$ into $C^{\prime}$
and $C^{\prime\prime}$. That decision is only allowed to depend on
$N^{\prime}$ and $N^{\prime\prime}$. This design restriction is at once an
advantage—as it leads to a simple and easy-to-understand estimator—and a
curse—since we do not know if one can even get consistency or good rates of
convergence.

The process can be viewed as a binary tree of intervals (or cells), with the
leaves corresponding to the intervals on which we apply the time-honored
histogram estimate. As each decision to split is made locally, the process of
partitioning $[0,1]$ into a set of intervals is perfectly geared to
distributive computing.

The rule we propose is extremely simple: split when
$N^{\prime}-N^{\prime\prime}>\gamma\sqrt{N^{\prime}+N^{\prime\prime}}$ for
fixed universal design constant $\gamma$. We will show that

$\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}(x)-f(x)|\,dx\bigg{\\}}=O\bigg{(}\frac{B^{2/3}}{n^{1/3}}\bigg{)}$

where $B=f(0)$ is the value at the mode, and $f_{n}$ is the histogram estimate
on the partition induced by the leaves. Also, when $B=\infty$, we still have
consistency, i.e., $\mathbf{E}\\{\int|f_{n}-f|\\}\to 0$ as $n\to\infty$.

It is noteworthy that if $\mathcal{M}_{B}$ denotes the class of all monotone
densities on $[0,1]$ bounded by $B$, then

$\inf_{\mbox{all estimators
$f_{n}$}}\,\,\sup_{f\in\mathcal{M}_{B}}\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}(x)-f(x)|\,dx\bigg{\\}}\geq\alpha\left(\frac{\log(1+B)}{n}\right)^{1/3}$

for a universal constant $\alpha>0$ (Birgé, 1983 [5]; see also Devroye and
Györfi, 1985 [8]). Our estimate achieves the minimax rate of convergence,
albeit with a worse constant multiplicative factor. Several estimates achieve
the minimax rate with the correct multiplicative factor, notably Grenander’s
histogram estimate (Grenander, 1956 [11]) (which uses a partition based on the
smallest concave majorant of the distribution function) and Birgé’s histogram
estimate (Birgé, 1983 [5]) (which uses a partition of exponentially increasing
widths). Standard histogram estimates of equal bin widths can at best achieve
a rate of $(B/n)^{1/3}$.

The design principle used here can be extended and generalized to densities
with special structures—convex or concave densities, log-concave or log-convex
densities, and unimodal densities spring to mind. More generalizations will be
discussed in the conclusion of the paper (section $7$). We start with our main
theorem (section $2$) and discuss its computational complexity (section $3$).
Then we note the importance of Galton–Watson trees in the analysis (section
$4$): as every density is locally nearly uniform, the performance of our
splitting rule on a uniform density $f$ matters a lot to explain the behaviour
near the bottom of the tree. We will show in section $4$ that for uniform $f$,
the binary tree is essentially an extinct Galton–Watson tree of constant
expected size.

In sections $5$ and $6$, we develop the partly combinatorial and partly
probabilistic proof of Theorem 1.

## . ain Theorem

Throughout this section and the paper, $f_{n}$ is the histogram estimate, i.e.

$f_{n}(x)=\frac{N(C)}{n\lambda(C)},\quad x\in C$

where $C$ is the unique interval to which $x$ belongs, $\lambda(C)$ is the
length (or Lebesgue measure) of $C$, and $N(C)$ is the number of $X_{i}$’s
falling in $C$. For our $f_{n}$ we will show:

######  Theorem 1.

Let $f$ be a bounded decreasing probability density function on $[0,1]$ with
$B=f(0)$. Then

$\sup_{f\in\mathcal{M}_{B}}\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}(x)-f(x)|dx\bigg{\\}}\leq\beta\left(\frac{B^{2/3}}{n^{1/3}}\right)$

for a universal constant $\beta$.

######  Remark 1.

Note that if we partition $[0,1]$ into $k$ equal intervals, then

$\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}-f|\bigg{\\}}\leq\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}-\mathbf{E}f_{n}|\bigg{\\}}+\int_{0}^{1}|\mathbf{E}f_{n}-f|,$

where $\mathbf{E}\\{f_{n}(x)\\}=p(C)/\lambda(C)$, $x\in C$, and
$p(C)=\int_{C}f$. Thus, $\mathbf{E}\\{f_{n}(x)\\}=kp(C)$.

A simple shifting argument shows that

$\int_{0}^{1}|\mathbf{E}f_{n}-f|\leq\frac{B}{k}.$

Also,

$\displaystyle\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}-\mathbf{E}f_{n}|\bigg{\\}}$
$\displaystyle=\sum_{C}\mathbf{E}\bigg{\\{}\bigg{|}\frac{N(C)}{n}-p(C)\bigg{|}\bigg{\\}}$
$\displaystyle\leq\sqrt{\sum_{C}1\cdot\sum_{C}\mathbf{E}\bigg{\\{}\bigg{|}\frac{N(C)}{n}-p(C)\bigg{|}^{2}\bigg{\\}}}$
$\displaystyle\leq\sqrt{\frac{k}{n}\sum_{C}p(C)}=\sqrt{\frac{k}{n}},$

and therefore, taking $k=\lceil(2B)^{2/3}n^{1/3}\rceil$ to optimize the sum,
we obtain

$\sup_{f\in\mathcal{M}_{B}}\mathbf{E}\bigg{\\{}\int_{0}^{1}|f_{n}-f|\bigg{\\}}\leq\left(\frac{1}{2^{2/3}}+2^{1/3}+o(1)\right)\left(\frac{B}{n}\right)^{1/3}.$

Note that without knowledge of $B$, the histogram estimate does not have a
better convergence rate than our estimate, despite the significant
restrictions under which the latter operates.

## . lgorithm and Time Complexity

From an algorithmic standpoint, the splitting described above amounts to a
branching process that constructs a binary tree. For any $x\in\mathbf{R}$ and
sorted list of numbers $L$, let $i(L,x)$ denote the index of $x$ if it were
inserted into $L$. Given a sorted list of size $n$ whose elements are an
i.i.d. sample $X_{1},...,X_{n}$ drawn from an unkown density $f$ on
$[a,b]\subseteq\mathbf{R}$, the following recursive algorithm constructs a
partition tree of $[a,b]$ according to our splitting rule.

Algorithm 1 Interval partitioning using a binary tree

1:

2:function BuildTree($r$, $[X_{1},...,X_{n}],[a,b]$) $\triangleright$ $r$ is a
tree node

3: $L$ $\leftarrow$ $i([X_{1},...,X_{n}],(a+b)/2)$ $\triangleright$ $L$ is the
number of data points in the left half of $[a,b]$

4: $R$ $\leftarrow$ $n-L$ $\triangleright$ $R$ is the number of data points on
the right half of $[a,b]$

5: if $L-R>\gamma\sqrt{n}$ then $\triangleright$ $\gamma$ is a parameter in
$(0,\infty)$

6: BuildTree($r$.left, $[X_{1},...,X_{L}],[a,(a+b)/2]$)

7: BuildTree($r$.right, $[X_{L+1},...,X_{n}],[(a+b)/2,b]$)

8: else

9: $r$.value $\leftarrow$ $[a,b]$

10: end if

11:end function

12:Initialize new tree node $r$

13:BuildTree($r,[X_{1},...,X_{n}],[a,b]$)

14:return $r$

While not strictly necessary, the assumption that $[X_{1},...,X_{n}]$ is
sorted allows us to decide whether or not to split in logarithmic time by
using binary search to compute the number of points on the left and right
halves of $[a,b]$. It also greatly simplifies the algorithm’s pseudocode to
construct left and right sublists in the case where we perform a recursive
call.

As a corollary to the results shown later in the paper, we can derive the
following sublinear upper bound on the expected runtime of our algorithm.

######  Corollary 2.

This algorithm’s expected runtime is $O(n^{1/3}\log_{2}(n))$ if the input data
are sorted.

###### Proof.

See appendix. ∎

## . alton–Watson trees and the uniform case

We recall the definition of a Galton–Watson tree (see, e.g., Athreya and Ney,
1972 [3]): every node in the tree has a number of children distributed as $Z$,
where $Z\geq 0$ has a fixed distribution. All realizations of $Z$ are
independent. If $\mathbf{E}Z=m<1$, then the expected size of the tree is
$1/(1-m)$. See, e.g., Lyons and Peres, 2016 [17].

As previously discussed, our splitting procedure can be viewed as a (randomly
generated) binary tree of intervals which we will henceforth denote by
$T_{n}$. An elegant connection to the theory of branching processes can be
established in the case where our data are sampled from a uniform
distribution. More specifically, one can show that the resulting tree would
closely resemble a Galton–Watson tree whose nodes have two children with
probability $p_{2}=\mathbf{P}\\{\mathcal{N}(0,1)>\gamma\\}:=\Phi(\gamma)$ and
no children with probability $p_{0}=1-p_{2}$ (where $\mathcal{N}(0,1)$ is a
standard normal and $\gamma$ is the parameter chosen in the algorithm, which
is assumed to be $\leq 1$ in this section).

Let $C$ be an arbitrary subinterval of $[0,1]$ and assume that $C$ contains
$N$ data points. The number of points in the left and right halves of $C$,
which we denote by $N^{\prime}$ and $N^{\prime\prime}$ respectively, are both
binomial random variables with parameters $N$ and $1/2$. Noting that
$2N^{\prime}-N=N^{\prime}-N^{\prime\prime}$, the probability of splitting the
interval is

$\mathbf{P}\\{N^{\prime}-N^{\prime\prime}>\gamma\sqrt{N}\\}=\mathbf{P}\bigg{\\{}\frac{N^{\prime}-N/2}{\sqrt{N/4}}>{\gamma}\bigg{\\}}$

which by the Berry-Esseen theorem (Berry, 1941 [4], see also Petrov, 1975
[18]) is equal to $\Phi(\gamma)+\theta/\sqrt{N}=:p_{2}$ for some $|\theta|\leq
1$.

Let $\epsilon>0$ be arbitrary, and let $T^{\prime}_{n}$ be the subtree of
$T_{n}$ in which all nodes $C$ (we refer to $C$ as a node as well as an
interval associated with that node) contain at least $N_{\epsilon}:=\lceil
1/(\epsilon\cdot\Phi(\gamma))^{2}\rceil$ points. Then for these nodes, the
probability $p_{2}$ of splitting is smaller than

$(1+\theta\cdot\epsilon)\Phi(\gamma).$

We infer that for $\epsilon$ small enough,

$\mathbf{E}\\{|T^{\prime}_{n}|\\}\leq\frac{1}{1-2(1+\epsilon)\Phi(\gamma)}.$

Furthermore, every leaf of $T^{\prime}_{n}$ is either a leaf of $T_{n}$ or an
internal node containing less than $N_{\epsilon}$ points. In the latter case,
we can derive a uniform upper bound for the expected size of subtrees that
hang from such leaves as a function of $\epsilon$.

$0$$1$$(N_{\epsilon}-1)\ \ points$ Figure 1: Dyadic splitting until each
interval contains at most one point.

Our splitting criterion is such that any interval with a single point is never
split. By analyzing the expected minimum distance between any two points in an
interval, we can determine an upper bound for the expected height (and in turn
size) of a tree.

Consider $N_{\epsilon}$ uniformly distributed points on an interval (without
loss of generality, $[0,1]$). Let $D$ be an integer random variable taking
value $i$ when the minimum distance between two points of the interval lies in
$(2^{-i-1},2^{-i}]$.

We split $[0,1]$ dyadically until each interval has $0$ or $1$ point (as
depicted in figure 1). The expected number of internal nodes of this tree is

$\displaystyle\sum_{\ell=0}^{\infty}2^{\ell}\cdot$
$\displaystyle\mathbf{P}\Bigg{\\{}\bigg{[}0,\frac{1}{2^{\ell}}\bigg{]}\text{
contains at least 2 points}\Bigg{\\}}$
$\displaystyle\leq\sum_{\ell=0}^{\infty}2^{\ell}\cdot\binom{N_{\epsilon}-1}{2}\frac{1}{2^{2\ell}}\leq\frac{(N_{\epsilon}-1)^{2}}{2}\sum_{\ell=0}^{\infty}\frac{1}{2^{\ell}}=(N_{\epsilon}-1)^{2}$

where $\ell$ is the level number in the tree.

Thus, the expected size is $\leq 2(N_{\epsilon}-1)^{2}+1<2N_{\epsilon}^{2}$
since the number of leaves equals the number of internal nodes plus one.

We conclude that the expected tree size is finite and uniformly bounded over
all values of $n$:

$\displaystyle\mathbf{E}\\{|T_{n}|\\}$
$\displaystyle\leq\inf_{\epsilon>0}\,\frac{1}{1-2(1+\epsilon)\Phi(\gamma)}\cdot
2N_{\epsilon}^{2}$
$\displaystyle\leq\inf_{\epsilon>0}\,\frac{2}{1-2(1+\epsilon)\Phi(\gamma)}\cdot\left(\frac{1}{\big{(}\epsilon\cdot\Phi(\gamma)\big{)}^{2}}+1\right)^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\varphi(\gamma)<\infty.$

For this example, we have $\mathbf{E}\int|f_{n}-f|=O\big{(}1/\sqrt{n}\big{)}$
by elementary calculations.

## . he deterministic infinite tree

### 5.1. Notation, setup and main proposition

Towards our goal of proving Theorem 1, we begin with the analysis of the
infinite full binary tree depicted in figure 3 and denoted by
$\mathcal{T_{\infty}}$. It is analogous to $T_{n}$ in that each node of
$\mathcal{T_{\infty}}$ is associated with a subinterval of $[0,1]$; more
specifically, if $C_{1},...,C_{2^{\ell}}$ are $\mathcal{T_{\infty}}$’s level
$\ell$ nodes labelled left to right, then $C_{i}$ corresponds to the interval
$[(i-1)/2^{\ell},i/2^{\ell}]$ for any $1\leq i\leq 2^{\ell}$. When we later
analyze the random tree $T_{n}$, it will be useful to view it as a subset of
this infinite deterministic tree.

As in the introduction, the left and right halves of a node
$C\in\mathcal{T}_{\infty}$ are denoted by $C^{\prime}$ and $C^{\prime\prime}$,
respectively. It is said to be balanced (and is uncoloured in figure 3) if it
satisfies

$p(C^{\prime})-p(C^{\prime\prime})\leq\gamma\sqrt{\frac{{p(C)}}{n}},$ (1)

where $\gamma$ is the parameter previously defined for the algorithm
$(\ref{algo}$) and, as above, $p(C)=\int_{C}f$. The set of all such nodes is
denoted by $\mathcal{B}$. All other (coloured) nodes are said to be unbalanced
and belong to $\mathcal{B}^{c}$, the complement of $\mathcal{B}$. Similarly,
for any positive real number $\alpha$, we denote by $\mathcal{B}^{(\alpha)}$
the set of nodes satisfying

$p(C^{\prime})-p(C^{\prime\prime})\leq(\alpha\gamma)\sqrt{\frac{{p(C)}}{n}},$

noting that $\mathcal{B}=\mathcal{B}^{(1)}$. The integer $\ell^{*}$ is defined
as

$\ell^{*}=\min\bigg{\\{}\ell\in\mathbf{Z}_{>0}:\frac{B}{2^{\ell+1}}\leq\gamma\cdot
2^{\ell/2}\sqrt{\frac{{B}}{n}}\bigg{\\}}.$

We denote by $\mathcal{P}_{j}(\mathcal{T}_{\infty})=\mathcal{P}_{j}$ the set
of nodes of $\mathcal{T}_{\infty}$ with exactly $j$ balanced ancestors.
Lastly, for any node $C$, the average value of $f$ on $C$ is denoted by
$f(C)$.

Note that if we were to truncate $\mathcal{T}_{\infty}$ by deleting nodes that
fall below those belonging to $\mathcal{B}\cap\mathcal{P}_{0}$, the resulting
tree (with leaf set $\mathcal{B}\cap\mathcal{P}_{0}$) would be the tree
generated by the algorithm (1) if every interval $C$ contained its expected
number of data points, $np(C)$ (in which case our splitting rule becomes the
negation of (1)). If this were the case, the density estimate extracted from
this tree would therefore, on each leaf $C$, be equal to $f(C)$. We begin by
showing that Theorem 1 holds for this function, as stated in the following
proposition.

######  Proposition 3.

Let $f$ be a bounded decreasing probability density function on $[0,1]$ with
$B=f(0)<\infty$, and let $\mathcal{F}_{n}$ be the function that takes the
value $f(C)$ on every $C\in\mathcal{P}_{0}\cap\mathcal{B}$. Then the $L_{1}$
distance between these two functions does not exceed
$c_{0}\cdot(B^{2/3}/n^{1/3})$ for some constant $c_{0}\in\mathbf{R}_{>0}$ that
does not depend on $B$ or $n$.

### 5.2. Preliminary results and lemmas

The following three lemmas are needed to prove Proposition 3.

$0.125$$0.25$$0.5$$0.75$$1$$f(x)$$f_{n}(x)$$0$ Figure 2: An estimate $f_{n}$
using a finite,
random tree $T_{n}$. $0$$1$ Figure 3: The infinite tree
$\mathcal{T}_{\infty}$.

######  Lemma 4.

For any $C\in\mathcal{T}_{\infty}$,

$p(C^{\prime})-p(C^{\prime\prime})\leq\int_{C}|f-f(C)|\leq
2\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}.$

###### Proof.

Let $x_{0}:=\sup\\{x\in C:f(x)\geq f(C)\\}$. Without loss of generality,
assume $C=[0,1]$ and $p(C)>0$. Our result is clear when $f$ is constant on
$C$, so we assume otherwise. Assume first that $x_{0}<1/2$, and define

$A:=\int_{0}^{x_{0}}\big{(}f-f(C)\big{)},\quad
B_{1}:=\int_{x_{0}}^{1/2}\big{(}f(C)-f\big{)},\quad
B_{2}:=\int_{1/2}^{1}\big{(}f(C)-f\big{)}.$

Our assumption on $f$ guarantees that $A$, $B_{1}$ and $B_{2}$ are all
positive. It is clear that $\int_{c}|f-f(C)|=A+B_{1}+B_{2}$ and
$p(C^{\prime})-p(C^{\prime\prime})=A+(B_{2}-B_{1})$, which shows the leftmost
inequality. Note that $B_{2}\geq B_{1}$, since otherwise we would have

$p(C^{\prime})-p(C^{\prime\prime})=A+(B_{2}-B_{1})<A,$

which would only be possible $|x_{0}-1/2|\geq 1/2$, forcing $x_{0}=0$, $A=0$
and $f$ to be constant. Using the fact that $A=B_{1}+B_{2}$ (by definition of
$x_{0}$),

$2\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}=A+B_{1}+B_{2}+2(B_{2}-B_{1})\geq\int_{C}|f-f(C)|.$

The case $x_{0}>1/2$ can be taken care of similarly. ∎

######  Lemma 5.

Let $\ell\in\mathbf{Z}^{+}$ be fixed, and let $\mathcal{A}_{\ell}$ be the set
of nodes in $\mathcal{T}_{\infty}$ of depth $\ell$. Then

$\sum_{C\in\mathcal{A}_{\ell}}\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}\leq\frac{B}{2^{\ell+1}}.$

###### Proof.

Let $\\{C_{i}\\}_{i=1}^{2^{\ell}}$ be an enumeration of $\mathcal{A}_{\ell}$
from left to right (where the leftmost node has $0$ as one of its interval
endpoints). We have

$\displaystyle\sum_{C\in\mathcal{A}_{\ell}}\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}$
$\displaystyle=\sum_{i=1}^{2^{\ell}}\big{(}p(C_{i}^{\prime})-p(C_{i}^{\prime\prime})\big{)}$
$\displaystyle\leq p(C_{1}^{\prime})-p(C_{2^{\ell}}^{\prime\prime})\leq
p(C_{1}^{\prime})\leq\frac{B}{2^{\ell+1}}.$

∎

######  Lemma 6.

Let $\ell\in\mathbf{Z}^{+}$ be fixed, and let $\mathcal{A}_{\ell}$ be the set
of nodes in $\mathcal{T}_{\infty}$ of depth $\ell$. Then

$\sum_{C\in\mathcal{A}_{\ell}}\sqrt{\frac{p(C)}{n}}\leq
2^{\ell/2}\sqrt{\frac{B}{n}}.$

###### Proof.

By Jensen’s inequality, $\sqrt{f(C)}\leq\int_{C}\sqrt{f}/\lambda(C)$ and

$\sqrt{p(C)}=\sqrt{\lambda(C)f(C)}\leq\frac{\int_{C}\sqrt{f}}{\sqrt{\lambda(C)}}.$

It follows that

$\sum_{C\in\mathcal{A}_{\ell}}\sqrt{\frac{p(C)}{n}}\leq
2^{\ell/2}\frac{1}{\sqrt{n}}\int_{C}\sqrt{f}\leq
2^{\ell/2}\sqrt{\frac{B}{n}}.$

∎

### 5.3. Proof of proposition 3

Armed with these lemmas, we may now prove Proposition 3.

###### Proof.

The $L_{1}$ distance between $f$ and $f_{n}$ on the whole of $[0,1]$ can be
computed by summing the error over the leaf set
$\mathcal{B}\cap\mathcal{P}_{0}$, and is thus equal to

$\sum_{C\in\mathcal{B}\cap\mathcal{P}_{0}}\int_{C}|f-f(C)|.$

Using lemma 4 and the definition $\mathcal{B}\cap\mathcal{P}_{0}$, we can
upper bound this quantity and write

$\displaystyle\sum_{C\in\mathcal{B}\cap\mathcal{P}_{0}}\int_{C}|f-f(C)|\leq
2\cdot\sum_{C\in\mathcal{B}\cap\mathcal{P}_{0}}\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}\leq
2\cdot\sum_{C\in\mathcal{B}\cap\mathcal{P}_{0}}\gamma\sqrt{\frac{p(C)}{n}}.$
(2)

By lemmas 5 and 6,

$\sum_{C\in\mathcal{B}\cap\mathcal{P}_{0}}\int_{C}|f-f(C)|\leq
2\cdot\sum_{\ell=0}^{\infty}\,\min\left(\frac{B}{2^{\ell+1}},\gamma\cdot
2^{\ell/2}\sqrt{\frac{B}{n}}\right).$ (3)

Recall that
$\ell^{*}=\min\\{\ell\in\mathbf{Z}_{>0}:{B}/{2^{\ell+1}}\leq\gamma\cdot
2^{\ell/2}\sqrt{{{B}/{n}}}\\}$ and note that $\ell^{*}$ is within 1 of

$\log_{2}\left\\{\bigg{(}\frac{Bn}{4}\bigg{)}^{1/3}\bigg{(}\frac{1}{\gamma}\bigg{)}^{2/3}\right\\},$

and that the summation in (3) is bounded above by

$\displaystyle
2\left(\sum_{\ell=0}^{\ell^{*}-1}\gamma\sqrt{\frac{B}{n}}2^{\ell/2}+\sum_{\ell=\ell^{*}}^{\infty}\frac{B}{2^{\ell+1}}\right)$
$\displaystyle\leq
2\gamma\sqrt{\frac{B}{n}}2^{(\ell^{*}-1)/2}\left(\frac{1}{1-1/\sqrt{2}}\right)+\frac{2B}{2^{\ell^{*}}}$
$\displaystyle\leq\frac{\gamma^{2/3}B^{2/3}}{n^{1/3}}\left(\frac{2^{7/6}}{(\sqrt{2}-1)}+{2^{5/3}}\right).$

Note that this a nonasymptotic bound that is uniform over all bounded monotone
densities $f$.

∎

### 5.4. Additional results regarding the infinite tree

We conclude this section by stating a few properties of $\mathcal{T}_{\infty}$
that we will make use of in the proof of Theorem 1. The following two lemmas
are proved in subsections 1 and 2 of the appendix, respectively.

######  Lemma 7.

If $\ell\geq\ell^{*}$,

$|\mathcal{A}_{\ell}\setminus\mathcal{B}|\leq\frac{2\sqrt{2}}{\gamma}\frac{\sqrt{Bn}}{{2^{\ell/2}}},$

and it follows, using the definition of $\ell^{*}$, that

$|\mathcal{B}^{c}|\leq 14\cdot\frac{B^{1/3}n^{1/3}}{\gamma^{2/3}}.$

Furthermore, for any $\alpha>0$,

$\big{|}\big{(}\mathcal{B}^{(\alpha)}\big{)}^{c}\big{|}\leq\bigg{(}2+\frac{13}{\alpha}\bigg{)}\frac{B^{1/3}n^{1/3}}{\gamma^{2/3}}.$

######  Lemma 8.

Recall that $\mathcal{B}$ is the subset of balanced nodes and
$\mathcal{B}^{c}$ the subset of unbalanced nodes of $\mathcal{T}_{\infty}$.
For any $j\in\mathbf{Z}_{>0}$, define
$\mathcal{P}_{j}=\mathcal{P}_{j}(\mathcal{T}_{\infty})$ to be the set of nodes
of $\mathcal{T}_{\infty}$ with exactly $j$ ancestors in $\mathcal{B}$, then

$|\mathcal{P}_{j}|\leq(|\mathcal{B}^{c}|+1)*2^{j}.$

## . roof of Theorem 1

Making use of the results above, we now turn our attention to the proof of our
main result, Theorem 1. Our approach will be similar in that the expected
$L_{1}$ distance between $f$ and $f_{n}$ (as defined previously) will be
computed by summing over $T_{n}$’s leaf set, denoted by $L$. By Scheffé’s
identity (see Devroye and Györfi, 1985 [8]), we have

$\displaystyle\mathbf{E}\left\\{\int_{0}^{1}|f-f_{n}|\right\\}=2*\mathbf{E}\left\\{\int_{0}^{1}(f-f_{n})_{+}\right\\}$
(4)

where $(x)_{+}:=\max(x,0)$. Now, (4) is bounded from above by

$2\underbrace{\mathbf{E}\Bigg{\\{}\sum_{C\in
L}\int_{C}(f-f(C))_{+}\Bigg{\\}}}_{\mbox{(I)}}+2\underbrace{\mathbf{E}\Bigg{\\{}\sum_{C\in
L}\int_{C}\Big{(}f(C)-\frac{N(C)/n}{\lambda(C)}\Big{)}_{+}\Bigg{\\}}}_{\mbox{(II)}}.$

where $N(C)$ is defined to be the number of data points in $C$. Our strategy
will be to bound each of these terms separately.

Before we proceed, we make the following remarks regarding notation. As
mentioned previously, we view $T_{n}$ as a subtree of $\mathcal{T}_{\infty}$.
This allows us to recycle most of the notation introduced above. For instance,
leaves of $T_{n}$ with depth $\ell$ are the elements of
$L\cap\mathcal{A}_{\ell}$, while leaves that are balanced are elements of
$L\cap\mathcal{B}$.

### 6.1. Upper bound for (I)

We begin with a few preliminary results.

######  Lemma 9.

Let $C$ be any non-leaf node of $T_{n}$ with depth $\ell$ and let $D\subseteq
L$ be the set of leaves of the subtree rooted at $C$, then

$\sum_{C^{*}\in
D}\int_{C^{*}}\big{(}f-f(C^{*})\big{)}_{+}\leq\int_{C}\big{(}f-f(C)\big{)}_{+}.$

$C_{1}$$C_{2}$$f(C_{1})$$f(C)$$f(C_{2})$$A$$B$$C$$x_{1}$$x_{2}$ Figure 4:
Definitions used in the proof of lemma 9.

###### Proof.

See appendix. ∎

######  Lemma 10.

Let $C\in T_{n}\setminus\mathcal{B}^{(\sqrt{2})}$, and
$\xi(C):=p(C^{\prime})-p(C^{\prime\prime})-\gamma\sqrt{{2p(C)}/{n}}>0$. Then
for such $C$, we have

$\mathbf{P}\\{C\in L\\}\leq\frac{2p(C)}{2p(C)+n\xi(C)^{2}}+\frac{4}{np(C)}.$

###### Proof.

See appendix. ∎

Using these lemmas, we prove the following proposition.

######  Proposition 11.

$\sup_{f\in\mathcal{M}_{B}}\mathbf{E}\Bigg{\\{}\sum_{C\in
L}\int_{C}(f-f(C))_{+}\Bigg{\\}}\leq\frac{B^{2/3}}{n^{1/3}}c_{1}(\gamma)+o(n^{-1/3})$

where

$c_{1}(\gamma):=\bigg{(}4\gamma^{2/3}+\frac{6(\gamma+\sqrt{\gamma^{2}+1})}{\gamma^{1/3}}\bigg{)}$

is a strictly positive constant depending only upon $\gamma$.

###### Proof.

The term we are trying to bound can be viewed as the expected $L_{1}$ distance
between $f$ and the estimator obtained by taking the (random) partition of
$[0,1]$ given by $T_{n}$, and estimating $f$ by its average value on each
interval in said partition. Informally, one notices that if the branching
process that generated $T_{n}$ behaved “as expected”, this estimator would be
more or less equal to $\mathcal{F}_{n}$ from Proposition 3.

Deeper leaves in $T_{n}$ yield a finer partition of $[0,1]$. Taking intuition
from the Riemann integral, one would guess that since we approximate $f$ by
its average value on each interval of this partition, a finer partition would
help us minimize $L_{1}$ distance. Conversely, we can use a coarser partition
to upper bound said distance, as shown by lemma 9.

It follows that we can use the partition given by $T_{n}$ truncated below
level $\ell^{*}$ to derive our upper bound. By lemmas 4 and 9, we have

$\mbox{(I)}\leq\mathbf{E}\left\\{\sum_{\ell=0}^{\ell^{*}}\sum_{C\in
L\cap\mathcal{A}_{\ell}}\int_{C}\big{(}f-f(C)\big{)}_{+}\right\\}+2\cdot\mathbf{E}\Bigg{\\{}\sum_{C\in
A_{\ell^{*}}}\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}\Bigg{\\}},$ (5)

and an application of lemma 5 yields

$\mathbf{E}\Bigg{\\{}\sum_{C\in
A_{\ell^{*}}}\big{(}p(C^{\prime})-p(C^{\prime\prime})\big{)}\Bigg{\\}}\leq\frac{B}{2^{\ell^{*}+1}}\leq\frac{B^{2/3}\gamma^{2/3}}{n^{1/3}}*4^{1/3}.$
(6)

Next, we recall that $\mathcal{B}^{(\sqrt{2})}$ is the set of nodes of
$\mathcal{T}_{\infty}$ satisfying

$p(C^{\prime})-p(C^{\prime\prime})\leq\gamma\sqrt{\frac{2p(C)}{n}},$

as defined earlier. Any node $C$ belonging to the complement of
$\mathcal{B}^{(\sqrt{2})}$ satisfies

$p(C^{\prime})-p(C^{\prime\prime})=\gamma\sqrt{\frac{2p(C)}{n}}+\xi(C)$

where $\xi(C):=p(C^{\prime})-p(C^{\prime\prime})-\gamma\sqrt{{2p(C)}/{n}}$ is
a strictly positive real number.

We use lemma 4 once more to bound the leftmost term in (5), writing

$\displaystyle\mathbf{E}$
$\displaystyle\Bigg{\\{}\sum_{\ell=0}^{\ell^{*}}\sum_{C\in
L\cap\mathcal{A}_{\ell}}\int_{C}\big{(}f-f(C)\big{)}_{+}\Bigg{\\}}$
$\displaystyle=\mathbf{E}\Bigg{\\{}\sum_{\ell=0}^{\ell^{*}}\sum_{C\in\mathcal{A}_{\ell}}\int_{C}\big{(}f-f(C)\big{)}_{+}\mathbf{1}_{[C\in
L]}\Bigg{\\}}$
$\displaystyle\leq\sum_{\ell=0}^{\ell^{*}}\Bigg{(}\sum_{C\in\mathcal{B}^{(\sqrt{2})}\cap\mathcal{A}_{\ell}}\gamma\sqrt{\frac{2p(C)}{n}}$
$\displaystyle\quad\quad\quad\quad+\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}\min\Big{(}\gamma\sqrt{\frac{2p(C)}{n}}+\xi(C),\,p(C^{\prime})-p(C^{\prime\prime})\Big{)}\mathbf{P}\\{{C\in
L}\\}\Bigg{)}.$ (7)

Applying lemma 6, we find that the first of the two inner summations in (6.1)
is bounded above by

$\gamma\sqrt{\frac{B}{n}}2^{{(\ell+1)}/2}.$ (8)

To bound the second summation, we use lemma 10 as well as the fact that
$(p(C^{\prime})-p(C^{\prime\prime}))/p(C)\leq 1$ to write

$\displaystyle\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}$
$\displaystyle\min\Big{(}\gamma\sqrt{\frac{2p(C)}{n}}+\xi(C),\,p(C^{\prime})-p(C^{\prime\prime})\Big{)}\mathbf{P}\\{{C\in
L}\\}$
$\displaystyle\leq\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}\Bigg{(}\Big{(}\gamma\sqrt{\frac{2p(C)}{n}}+\xi(C)\Big{)}\frac{1}{1+\xi(C)^{2}/(2p(C)/n)}+\frac{4}{n}\Bigg{)}.$
(9)

For any positive real numbers $a$ and $b$, the following identity holds:

$\frac{a+b}{1+b^{2}}\leq\sqrt{a^{2}+1}.$

Using it on $a=\gamma$ and $b=\xi(C)/\sqrt{2p(C)/n}$ inside the summation in
(6.1), we have

$\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}\bigg{(}\sqrt{\frac{2p(C)}{n}}\Big{(}\frac{a+b}{1+b^{2}}\Big{)}+\frac{4}{n}\bigg{)}\leq\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}\bigg{(}\sqrt{\frac{2p(C)}{n}}\sqrt{\gamma^{2}+1}+\frac{4}{n}\bigg{)}.$
(10)

Since we are only bounding the quantity above for values of $\ell$ that are
smaller than $\ell^{*}$, we have

$|\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}|\leq|\mathcal{A}_{\ell}|\leq|A_{\ell^{*}}|\leq
2^{\ell^{*}}.$

By definition of $\ell^{*}$, this yields

$|\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}|\leq
2^{\ell^{*}}\leq\frac{2(Bn)^{1/3}}{\gamma^{2/3}}.$

It follows by lemma 6 that for any $\ell\leq\ell^{*}$,

$\sum_{C\in\mathcal{A}_{\ell}\setminus\mathcal{B}^{(\sqrt{2})}}\bigg{(}\sqrt{\frac{2p(C)}{n}}\sqrt{\gamma^{2}+1}+\frac{4}{n}\bigg{)}\leq\left(\sqrt{\gamma^{2}+1}\right)\sqrt{\frac{B}{n}}2^{(\ell+1)/2}+\frac{2B^{1/3}}{(\gamma
n)^{2/3}}.$

Invoking equations (6) and (8), our bound on (I) in (5) becomes

(I)
$\displaystyle\leq\frac{4B^{2/3}\gamma^{2/3}}{n^{1/3}}+\sum_{\ell=0}^{\ell^{*}}\left(\left(\gamma+2\sqrt{\gamma^{2}+1}\right)\sqrt{\frac{B}{n}}2^{(\ell+1)/2}+\frac{2B^{1/3}}{(\gamma
n)^{2/3}}\right)$
$\displaystyle\leq\frac{B^{2/3}}{n^{1/3}}c_{1}(\gamma)+\frac{2(\ell^{*}+1)B^{1/3}}{(\gamma
n)^{2/3}}.$

Note that $\ell^{*}/n^{2/3}=O(\log_{2}(n)/n^{2/3})$ uniformly over all
monotone densities bounded by $B$. This completes the proof of Proposition 11.
∎

### 6.2. Upper bound for (II)

Our final step towards proving Theorem 1 is deriving an upper bound for (II),
as stated in Proposition 13 below. The latter proof relies on the following
preliminary result.

######  Lemma 12.

Assume that $\gamma>2$, then if $C\in\mathcal{B}^{(1/2)}$,

$\mathbf{E}\bigg{\\{}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}_{+}\mathbf{1}_{[C\in
L]}\bigg{\\}}\leq c_{2}(\gamma)^{j/2}\sqrt{\frac{p(C)}{n}}$

where

$c_{2}(\gamma)=\frac{1}{1+\gamma^{2}/4}<\frac{1}{2}.$

###### Proof.

See appendix. ∎

######  Proposition 13.

Assume that $\gamma>2$, then

$\mathbf{E}\Bigg{\\{}\sum_{C\in
L}\int_{C}\Big{(}f(C)-\frac{N(C)/n}{\lambda(C)}\Big{)}_{+}\Bigg{\\}}\leq
c_{3}(\gamma)\frac{B^{1/6}}{n^{1/3}}$

where

$c_{3}(\gamma)=\gamma^{-1/3}\bigg{(}4+\frac{5}{1-\sqrt{2c_{2}(\gamma)}}\bigg{)}.$

###### Proof.

We have

$\displaystyle\mathbf{E}\Bigg{\\{}\sum_{C\in
L}\int_{C}\Big{(}f(C)-\frac{N(C)/n}{\lambda(C)}\Big{)}_{+}\Bigg{\\}}=$
$\displaystyle\,\mathbf{E}\bigg{\\{}\sum_{C\in
L}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}_{+}\bigg{\\}}.$ (11)

Our strategy will be to partition nodes $C\in L$ according to which
$\mathcal{P}_{j}$ they belong to, as well as whether or not they belong to
$\mathcal{B}^{(1/2)}$, seeing that lemmas 7 and 8 provide upper bounds to the
number of elements in these sets. We write

$\displaystyle\mathbf{E}$ $\displaystyle\bigg{\\{}\sum_{C\in
L}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}_{+}\bigg{\\}}$
$\displaystyle\leq\sum_{j=0}^{\infty}\sum_{C\in\mathcal{B}^{(1/2)}\cap\mathcal{P}_{j}}\mathbf{E}\bigg{\\{}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}_{+}\mathbf{1}_{[C\in
L]}\bigg{\\}}+\sum_{C\notin\mathcal{B}^{(1/2)}}\sqrt{\frac{p(C)}{n}},$ (12)

then use the Cauchy-Schwarz inequality to obtain

$\displaystyle\sum_{C\notin\mathcal{B}^{(1/2)}}\sqrt{\frac{p(C)}{n}}$
$\displaystyle\leq\sqrt{\bigg{(}\sum_{C\notin\mathcal{B}^{(1/2)}}1\bigg{)}\bigg{(}\sum_{C\notin\mathcal{B}^{(1/2)}}\frac{p(C)}{n}\bigg{)}}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\sqrt{\big{|}\big{(}\mathcal{B}^{(1/2)}\big{)}^{c}\big{|}\cdot\sum_{C\notin\mathcal{B}^{(1/2)}}p(C)}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\sqrt{\big{|}\big{(}\mathcal{B}^{(1/2)}\big{)}^{c}\big{|}}.$

By lemma 7, the latter is dominated by

$6\cdot\frac{B^{1/6}}{\gamma^{1/3}n^{1/3}}.$

Lastly, we use lemma 12 to write

$\displaystyle\sum_{j=0}^{\infty}\sum_{C\in\mathcal{B}^{(1/2)}\cap\mathcal{P}_{j}}$
$\displaystyle\mathbf{E}\bigg{\\{}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}_{+}\mathbf{1}_{[C\in
L]}\bigg{\\}}$
$\displaystyle\leq\sum_{j=0}^{\infty}\sum_{C\in\mathcal{B}^{(1/2)}\cap\mathcal{P}_{j}}c_{2}(\gamma)^{j/2}\sqrt{\frac{p(C)}{n}}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\sum_{j=0}^{\infty}c_{2}(\gamma)^{j/2}\sqrt{|\mathcal{P}_{j}|\cdot\sum_{C\in\mathcal{P}_{j}}p(C)}$
(by Jensen’s inequality)
$\displaystyle\leq\frac{1}{\sqrt{n}}\sum_{j=0}^{\infty}c_{2}(\gamma)^{j/2}\sqrt{(14\cdot\gamma^{-2/3}B^{1/3}n^{1/3}+1)\cdot
2^{j}}$ (by lemmas 7 and 8) $\displaystyle\leq\sqrt{\frac{14\cdot
B^{1/3}n^{1/3}+1}{\gamma^{2/3}n}}\cdot\frac{1}{1-\sqrt{2c_{2}(\gamma)}}$
$\displaystyle\leq\left(\frac{1}{1-\sqrt{2c_{2}(\gamma)}}\right)\left(\frac{4B^{1/6}+1}{\gamma^{1/3}n^{1/3}}\right)$
$\displaystyle\leq c_{3}(\gamma)\frac{B^{1/6}}{n^{1/3}}.$

∎

Theorem 1 is a direct consequence of propositions 11 and 13.

## . onclusion

Within the same framework, we can replace the histogram on each set of the
partition by a linear estimate with parameter (slope and intercept at the
center point of an interval) only depending upon
$N^{\prime},N^{\prime\prime}$, and $\lambda(C)$. Such estimates should adapt
better to the smoothness of the density, and should be studied for the larger
class of bounded monotone densities with bounded first derivative.

Simple extensions include more complex local rules that depend upon the
cardinalities $N(C_{1}),...,N(C_{k})$, where $C$ is split into $k$ equal-size
intervals. The tree would still be binary but the decision to split or not is
allowed to depend upon the given cardinalities. Such rules could lead to nice
and simple estimates of convex, concave, log-convex and log-concave densities.

Unimodal densities on $[0,1]$ with unknown location of the mode offer a
particular challenge. In fact, under our restrictions, it should be possible
to estimate the mode itself using a $k=4$ rule (referring to the $k$ of the
previous paragraph) since the subinterval containing the mode is always the
maximal probability interval (among the $k$ intervals under consideration) or
one of its neighbours).

A natural rule for splitting whenever
$|N^{\prime}-N^{\prime\prime}|\geq\gamma\sqrt{N^{\prime}+N^{\prime\prime}}$
could be of use for a large class of densities.

Finally, one can easily picture extensions to $[0,1]^{d}$ for monotone
densities (e.g., monotone in each coordinate when all others are held fixed).
Splitting decisions would then depend upon the $2^{d}$ cardinalities of all
equal quadrants that partition a cell $C$. The splits themselves could either
be binary (along a preferred dimension) or $d$-ary. In the latter case, on
would obtain random quadtrees.

## . ppendix

### 8.1. Proof of lemma 7

List the unbalanced nodes of $\mathcal{A}_{\ell}$ in order from right to left,
where the leftmost node is that for which the left interval endpoint is the
smallest. Denote this list $\\{C_{i}\\}_{i=1}^{k}$, where
$k=|\mathcal{A}_{\ell}\setminus\mathcal{B}|$.

By monotonicity of $f$, we have $p(C_{0})\leq p(C_{1})\leq\dots\leq p(C_{k})$,
and we can therefore write $p(C_{i})=\sum_{j=0}^{i}q_{j}$ for every $i$, where
$q_{1},\dots,q_{k}$ are nonnegative. Since every $C_{i}$ is unbalanced, we
have $p(C_{i}^{\prime})-p(C_{i}^{\prime\prime})>\gamma\sqrt{p(C_{i})/n}$
which, combined with the fact that
$p(C_{i})=p(C_{i}^{\prime})+p(C_{i}^{\prime\prime})$, yields
$2p(C_{i}^{\prime})\geq\gamma\sqrt{p(C_{i})/n}+p(C_{i})$ and in turn

$p(C_{i+1})\geq\gamma\sqrt{\frac{p(C_{i})}{n}}+p(C_{i})$

for any $1\leq i\leq k$. We use this fact to prove that for any $1\leq i\leq
k$, $q_{i}\geq({\gamma^{2}}/{4n})(i+1)$. If $i=0$, we have
$q_{0}=p(C_{0})\geq\gamma^{2}/n\geq\gamma^{2}/(4n)$. Now assume that the claim
regarding $q_{i}$ holds for some $i$, then

$\displaystyle q_{i+1}$ $\displaystyle=p(C_{i+1})-p(C_{i})$
$\displaystyle\geq\gamma\sqrt{\frac{p(C_{i})}{n}}$
$\displaystyle\geq\frac{\gamma}{\sqrt{n}}\Big{(}\frac{\gamma^{2}}{4n}\frac{(i+1)(i+2)}{2}\Big{)}^{1/2}$
$\displaystyle\geq\frac{\gamma^{2}}{4n}(i+2)$

and it follows by induction that this claim holds for any $i$. We therefore
have

$\displaystyle
p(C_{k})=\sum_{i=1}^{k}q_{k}\geq\frac{\gamma^{2}}{4n}\sum_{i=1}^{k}(i+1)\geq\frac{\gamma^{2}k^{2}}{8n},$

and the first part of the lemma follows since $p(C_{k})\leq B/2^{\ell}$. The
upper bound on $|\mathcal{B}^{c}|$ follows from the fact that it is no larger
than
$2^{\ell^{*}}+\sum_{\ell\geq\ell^{*}}|\mathcal{A}_{\ell}\setminus\mathcal{B}|$.
Lastly, an identical argument yields the upper bound for
$|(\mathcal{B}^{(\alpha)})^{c}|$.

### 8.2. Proof of lemma 8

We begin by noticing that all but finitely many nodes of
$\mathcal{T}_{\infty}$ are in $\mathcal{B}$. It follows that for any
$i\in\mathbf{Z}_{>0}$, $|\mathcal{P}_{i}|\leq|\mathcal{P}_{i+1}|$ since any
node in $\mathcal{P}_{i}$ is the root of a tree that contains at least one
balanced node in $\mathcal{P}_{i+1}$.

Next, we examine the effect that switching a balanced node with its parent has
on the various $|\mathcal{P}_{i}|$’s. Let $C$ be an arbitrary balanced node of
$\mathcal{T}_{\infty}$, $D$ be its parent and $a$ be the number of balanced
ancestors of $D$. We may assume that $D$ is unbalanced, since otherwise
switching $D$ and $C$ would leave the tree unaffected. Our operation is
depicted in figure 5. If we let $\mathcal{T}$ be the subtree of
$\mathcal{T}_{\infty}$ rooted at $C$’s sibling, then switching $C$ and $D$
applies the map

$|\mathcal{P}_{j}|\mapsto\begin{cases}|\mathcal{P}_{j}|&\text{if $j\geq a$}\\\
|\mathcal{P}_{j}|-|\mathcal{P}_{j}(\mathcal{T})|+|\mathcal{P}_{j+1}(\mathcal{T})|&\text{if
$j<a$}\end{cases}$

to every $|\mathcal{P}_{j}|$.

$D$$C$$\mathcal{T}$$\mathcal{T}$ Figure 5: Switching a balanced
node with its parent. $Balanced$$Unbalanced$ Figure 6: Tree for which
$|\mathcal{P}_{j}|$
is maximized (for all $j$).

Since $|\mathcal{P}_{j}(\mathcal{T})|\leq|\mathcal{P}_{j+1}(\mathcal{T})|$ for
any $j$, this map’s output is always greater than or equal to
$|\mathcal{P}_{j}|$. In other words, the node configuration that maximizes
$|\mathcal{P}_{j}|$ for every $j$ is that in which all the unbalanced nodes
are pushed to the top. This forms a tree of unbalanced nodes whose leaves are
the roots of full, infinite binary trees where all nodes are balanced.

In this configuration, it is clear that
$|\mathcal{P}_{0}|\leq(|\mathcal{B}^{c}|+1|)$ and that
$|\mathcal{P}_{j+1}|\leq 2|\mathcal{P}_{j}|$, from which the lemma follows.

### 8.3. Proof of lemma 9

It suffices to show that for all pairs of disjoint intervals
$C_{1},C_{2}\subseteq C$ such that $C_{1}\cup C_{2}=C$

$\int_{C_{1}}\big{(}f-f(C_{1})\big{)}_{+}+\int_{C_{2}}\big{(}f-f(C_{2})\big{)}_{+}\leq\int_{C}\big{(}f-f(C)\big{)}_{+}.$

The lemma then follows by induction. Without loss of generality, assume that
$C=[0,1]$.

Let $C_{1}$, $C_{2}$ be an arbitrary such pair and note that $f(C_{2})\leq
f(C)\leq f(C_{1})$ since $f$ is decreasing. Let $x_{1}:=\sup\\{x:f(x)\geq
f(C_{1})\\}$, $x_{2}:=\sup\\{x:f(x)\geq f(C_{2})\\}$, and let
$A:=\int_{0}^{x_{1}}(f-f(C_{1}))$ and $B:=\int_{x_{2}}^{1}(f-f(C_{2}))$ as
depicted in figure 4. Then it is obvious that

$A+B=\int_{C_{1}}\big{(}f-f(C_{1})\big{)}_{+}+\int_{C_{2}}\big{(}f-f(C_{2})\big{)}_{+}\leq\int_{C}\big{(}f-f(C)\big{)}_{+}.$

### 8.4. Proof of lemma 10

Let $C\in T_{n}$ be arbitrary. Recall that $N(C)$ is the number of data points
lying in $C$ (similarly, $N(C^{\prime})$ and $N(C^{\prime\prime})$ are the
number of points lying in the left/right halves of $C$ respectively). Notice
that $N(C)\stackrel{{\scriptstyle\mathcal{L}}}{{=}}\mathrm{Bin}(n,p(C))$
(where $\stackrel{{\scriptstyle\mathcal{L}}}{{=}}$ denotes equivalence in law
and $\mathrm{Bin}(n,p)$ a binomial $n$, $p$). For $C$ to be a leaf, we must
have decided not to split its node. Therefore

$\displaystyle\mathbf{P}\\{C\in L\\}$
$\displaystyle\leq\mathbf{P}\Big{\\{}N(C^{\prime})-N(C^{\prime\prime})<\gamma\sqrt{N(C)}\Big{\\}}$
$\displaystyle\leq\sup_{m\geq
np(C)/2}\mathbf{P}\bigg{\\{}{N(C^{\prime})-N(C^{\prime\prime})}<{\gamma\sqrt{N(C)}}\,\,\Big{|}\,\,N(C)=m\bigg{\\}}$
$\displaystyle\quad\quad+\mathbf{P}\big{\\{}|N(C)-np(C)|>np(C)/2\big{\\}}.$
(13)

A simple application of Chebyshev’s inequality gives

$\mathbf{P}\big{\\{}|N(C)-np(C)|>np(C)/2\big{\\}}\leq\frac{4(1-p(C))}{np(C)}\leq\frac{4}{np(C)}.$

Next, given $N(C)=m$,
$N(C^{\prime})\stackrel{{\scriptstyle\mathcal{L}}}{{=}}\mathrm{Bin}(m,p(C^{\prime})/p(C))$.
Note that

$\displaystyle p(C^{\prime})+p(C^{\prime\prime})=p(C)$ $\displaystyle
p(C^{\prime})-p(C^{\prime\prime})=\gamma\sqrt{\frac{2p(C)}{n}}+\xi(C)$

so that

$\frac{p(C^{\prime})}{p(C)}=\frac{1}{2}+\frac{1}{2}\gamma\sqrt{\frac{2}{np(C)}}+\frac{1}{2}\frac{\xi(C)}{p(C)}.$

Using these observations and the fact that
$N(C^{\prime})-N(C^{\prime\prime})=2N(C^{\prime})-N(C)$, we find that

$\displaystyle\mathbf{P}$
$\displaystyle\bigg{\\{}{N(C^{\prime})-N(C^{\prime\prime})}<{\gamma\sqrt{N(C)}}\,\,\Big{|}\,\,N(C)=m\bigg{\\}}$
$\displaystyle=\mathbf{P}\Bigg{\\{}\mathrm{Bin}\bigg{(}m,\frac{p(C^{\prime})}{p(C)}\bigg{)}-m\frac{p(C^{\prime})}{p(C)}<\gamma\frac{\sqrt{m}}{2}-\gamma\frac{m}{2}\sqrt{\frac{2}{np(C)}}-\frac{m}{2}\frac{\xi(C)}{p(C)}\Bigg{\\}}$
$\displaystyle\leq\mathbf{P}\Bigg{\\{}\mathrm{Bin}\bigg{(}m,\frac{p(C^{\prime})}{p(C)}\bigg{)}-m\frac{p(C^{\prime})}{p(C)}<-\frac{m}{2}\frac{\xi(C)}{p(C)}\Bigg{\\}}$

if $m\geq np(C)/2$, which is the case in the supremum taken in (13). Using the
Chebyshev-Cantelli inequality (see Lugosi, Massart and Boucheron, 2013 [16])
and the fact that the variance of a binomial $n$, $p$ is at most $n/4$, we
have

$\displaystyle\mathbf{P}\Bigg{\\{}\mathrm{Bin}\bigg{(}m,\frac{p(C^{\prime})}{p(C)}\bigg{)}-m\frac{p(C^{\prime})}{p(C)}<-\frac{m}{2}\frac{\xi(C)}{p(C)}\Bigg{\\}}$
$\displaystyle\leq\frac{m/4}{m/4+\frac{m^{2}\xi(C)^{2}}{4(p(C))^{2}}}$
$\displaystyle\leq\frac{2p(C)}{2p(C)+n\xi(C)^{2}}\quad\bigg{(}\text{since
$m\geq\frac{np(C)}{2}$}\bigg{)}$

and the lemma follows.

### 8.5. Proof of lemma 12

Using Cauchy-Schwarz, we write

$\displaystyle\mathbf{E}\bigg{\\{}\mathbf{1}_{[C\in
L]}\Big{(}p(C)-\frac{N(C)}{n}\Big{)}\bigg{\\}}\leq\sqrt{\mathbf{P}\\{C\in
L,N(C)\leq np(C)\\}}\cdot\sqrt{\frac{p(C)}{n}}.$

We claim that

$\mathbf{P}\\{C\in L,N(C)\leq np(C)\\}\leq c_{2}(\gamma)^{j},$

where $c_{2}(\gamma)$ is defined in the lemma’s statement. Note that this
bound does not depend on the level $\ell$ at which the node is located. To
prove this, it suffices to show that for any balanced node
$C\in\mathcal{B}^{(1/2)}$, if $N(C)\leq np(C)$,

$\mathbf{P}\\{N(C^{\prime})-N(C^{\prime\prime})>\gamma\sqrt{N(C)}\,\,|\,\,N(C)\\}\leq
c_{2}(\gamma),$

since consecutive splits are independent given the values of $N(C)$. For
simplicity, temporarily denote $N(C)$, $N(C^{\prime})$ and
$N(C^{\prime\prime})$ by $N,N^{\prime}$ and $N^{\prime\prime}$ respectively,
and similarly for $p,p^{\prime},p^{\prime\prime}$. Then observe that

$\displaystyle\mathbf{P}\Big{\\{}N^{\prime}$
$\displaystyle-N^{\prime\prime}>\gamma\sqrt{N}\,\,\Big{|}\,\,N\Big{\\}}$
$\displaystyle\leq\mathbf{P}\bigg{\\{}N^{\prime}-N^{\prime\prime}-N\Big{(}\frac{p^{\prime}-p^{\prime\prime}}{p}\Big{)}>\gamma\sqrt{N}-N\Big{(}\frac{p^{\prime}-p^{\prime\prime}}{p}\Big{)}\,\,\bigg{|}\,\,N\bigg{\\}}$
$\displaystyle\leq\mathbf{1}_{[N(p^{\prime}-p^{\prime\prime})/p\geq\gamma\sqrt{N}/2]}+\mathbf{P}\bigg{\\{}N^{\prime}-N^{\prime\prime}-N\Big{(}\frac{p^{\prime}-p^{\prime\prime}}{p}\Big{)}>\frac{\gamma}{2}\sqrt{N}\,\,\bigg{|}\,\,N\bigg{\\}}$
$\displaystyle\leq\mathbf{1}_{[\sqrt{N}>(\gamma/2)(p/(p^{\prime}-p^{\prime\prime}))]}+\mathbf{P}\left\\{\frac{N^{\prime}-N^{\prime\prime}-N\cdot\frac{p^{\prime}-p^{\prime\prime}}{p}}{\sqrt{4N\cdot\frac{p^{\prime}}{p}\frac{p^{\prime\prime}}{p}}}>\frac{\gamma}{2}\frac{p/2}{\sqrt{p^{\prime}p^{\prime\prime}}}\,\,\bigg{|}\,\,N\right\\}.$

By definition of $\mathcal{B}^{(1/2)}$, we have
$p^{\prime}-p^{\prime\prime}<(\gamma/2)\sqrt{p/n}$. If the indicator in the
expression above were one, this would imply that $\sqrt{N}>\sqrt{np}$ which
cannot be true since $N\leq np$, hence the indicator is equal to 0. As for the
probability term, notice that

$\sqrt{4N\cdot\frac{p^{\prime}}{p}\frac{p^{\prime\prime}}{p}}$

is the conditional variance of

$N^{\prime}-N^{\prime\prime}-N\cdot\frac{p^{\prime}-p^{\prime\prime}}{p},$

which is a random variable with mean 0 and unit variance. Noting that
$p/2\geq\sqrt{p^{\prime}p^{\prime\prime}}$ and that $\gamma>2$ by assumption,
we can apply the Chebyshev-Cantelli inequality to get

$\mathbf{P}\left\\{\frac{N^{\prime}-N^{\prime\prime}-N\cdot\frac{p^{\prime}-p^{\prime\prime}}{p}}{\sqrt{4N\cdot\frac{p^{\prime}}{p}\frac{p^{\prime\prime}}{p}}}>\frac{\gamma}{2}\frac{p/2}{\sqrt{p^{\prime}p^{\prime\prime}}}\,\,\bigg{|}\,\,N\right\\}\leq\frac{1}{1+(\gamma/2)^{2}}\stackrel{{\scriptstyle\text{def}}}{{=}}c_{2}(\gamma)<1/2.$

### 8.6. Proof of corollary 2

The decision whether to split an interval containing $k$ points can be made in
order $\log_{2}(k)$ time, which is the time taken to determine which points
lie on the left and right halves of the interval, respectively, via binary
search. It therefore suffices to show that the expected number of leaves of
the tree generated by the algorithm is of the order of $n^{1/3}$. Letting $L$
denote the tree’s leaf set, we have

$\mathbf{E}\\{|L|\\}\leq\mathbf{E}\big{\\{}\big{|}\big{(}\mathcal{B}^{(1/2)}\big{)}^{c}\big{|}\big{\\}}+\mathbf{E}\big{\\{}\big{|}L\cap\mathcal{B}^{(1/2)}\big{|}\big{\\}}=\mathbf{E}\big{\\{}\big{|}\big{(}\mathcal{B}^{(1/2)}\big{)}^{c}\big{|}\big{\\}}+\sum_{j=0}^{\infty}\sum_{C\in\mathcal{B}^{(1/2)}\cap\mathcal{P}_{j}}\mathbf{E}\big{\\{}\mathbf{1}_{[C\in
L]}\big{\\}}.$

The first term is $O(n^{1/3})$ by lemma 7 and the second is $O(1)$ by the
proof of lemma 12.

## References

  * [1] G. Alsmeyer.  Galton–Watson Processes.  Course notes at the University of Münster, 2008.
  * [2] L. Anderlini.  Density estimation trees as fast non-parametric modelling tools.  arXiv, 1607.06635v1, 2016.
  * [3] K. B. Athreya and P. E. Ney.  Branching Processes.  Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972.
  * [4] A. C. Berry.  The accuracy of the gaussian approximation to the sum of independent variates.  Transactions of the American Mathematical Society, 49:122–136, 1941.
  * [5] L. Birgé.  Approximation dans les espaces métriques et théorie de l’estimation.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, pages 181–237, 1983.
  * [6] L. Devroye.  A Course in Density Estimation.  Boston, Birkhäuser Verlag, 1987.
  * [7] L. Devroye and G. Biau.  Cellular tree classifiers.  Electronic Journal of Statistics, 7:1875–1912, 2013.
  * [8] L. Devroye and L. Györfi.  Nonparametric Density Estimation: The L1 View.  Wiley series in probability and mathematical statistics. New York, John Wiley, 1985.
  * [9] L. Devroye and T. Reddad.  Discrete minimax estimation with trees.  Electronic Journal of Statistics, 13:2595–2623, 2019.
  * [10] W. Feller.  An Introduction to Probability Theory and Its Applications.  Wiley, 1950.
  * [11] U. Grenander.  On the theory of mortality measurement.  Skandinavisk Aktuarietidskrift, (2):125–153, 1956.
  * [12] P. Groeneboom.  Estimating a monotone density.  Proceedings of the Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer, 2:539–555, 1985.
  * [13] G. H. Hardy, J. E. Littlewood, and G. Pólya.  Inequalities.  Cambridge University Press, 1988.
  * [14] W. Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, 1963.
  * [15] V. F. Kolchin.  Random Mappings.  Translation Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York, 1986.
  * [16] G. Lugosi, P. Massart, and S. Boucheron.  Concentration Inequalities. A Nonasymptotic Theory of Independence.  Oxford University Press, 2013.
  * [17] R. Lyons and Y. Peres.  Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York, 2016.
  * [18] V. V. Petrov.  Sums of Independent Random Variables.  Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin, Heidelberg, 1975.
  * [19] P. Ram and A. G. Gray.  Density estimation trees.  Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, pages 627–635, 2011.
  * [20] G. Schmidberger.  Tree-based Density Estimation: Algorithms and Applications.  PhD thesis, University of Waikato, New Zealand, 2009.


Search for lepton-flavor-violating decays of the tau lepton
at a future muon collider

Gholamhossein Haghighat1, Mojtaba Mohammadi Najafabadi1

1 School of Particles and Accelerators, Institute for Research in Fundamental
Sciences (IPM),

P.O. Box 19395-5531, Tehran, Iran

*<EMAIL_ADDRESS>
16th International Workshop on Tau Lepton Physics (TAU2021),
September 27 – October 1, 2021 10.21468/SciPostPhysProc.?

## Abstract

Tau leptons can have lepton-flavor-violating (LFV) couplings to a muon or an
electron and an Axion-Like Particle (ALP). ALPs are pseudo Nambu-Goldstone
bosons associated with spontaneously broken global U(1) symmetries. LFV ALPs
have been of a great interest in the last several decades as they can address
some of the SM long-lasting problems. Assuming a future muon collider proposed
by the Muon Accelerator Program (MAP), we search for LFV decays
$\tau\rightarrow\ell a$ ($\ell=e,\mu$) of one of the tau leptons produced in
the muon-anti muon annihilation. The ALP mass is assumed to be in the range
100 eV to 1 MeV and three different chiral structures are considered for the
LFV coupling. Using a multivariate technique and performing a parameterized
simulation based on the ideal target performance, we obtain expected 95$\%$
confidence level upper limits on the LFV couplings tau-electron-ALP and tau-
muon-ALP. Limits are computed assuming the center-of-mass energies of 126, 350
and 1500 GeV which the future muon collider is supposed to operate at. We
study the two cases of unpolarized and polarized muon beams and show that
taking advantage of tau polarization-induced effects, the main background
$\tau\rightarrow e/\mu+\nu\bar{\nu}$ can be significantly reduced. Results
indicate that current limits on the LFV couplings can be improved by roughly
one order of magnitude using the present analysis.

###### Contents

  1. 1 Introduction
  2. 2 ALP production in LFV tau decays
  3. 3 Event generation and analysis
  4. 4 Prospects for limits on the LFV tau couplings
  5. 5 Conclusion

##  1 Introduction

The neutrino oscillations [2] verified by experimental data suggest the
possibility of charged lepton-flavor-violating (LFV) decays. These decays are
strongly suppressed in the Standard Model (SM) providing a strong motivation
for searching for beyond SM (BSM) LFV processes. Axion-Like Particles (ALPs),
on the other hand, are pseudo Nambu-Goldstone bosons associated with
spontaneously broken U(1) symmetries [3] and can have flavor-violating
couplings to the SM charged leptons. Such particles have found numerous
applications in many areas of physics as they can address some of the SM
problems such as the strong CP problem, baryon asymmetry problem, Dark Matter,
etc. The parameter space of LFV ALPs has been probed by many experiments [4]
in the recent decades. Collider searches for the tau decay $\tau\rightarrow
e/\mu+a$, where $a$ denotes an ALP, have constrained the ALP-tau-electron and
ALP-tau-muon couplings [5]. ALPs with $\leq 1$ MeV masses decay predominantly
to photons. However, they leave the detector before the decay and thus their
existence can be revealed by missing energy signals. In such searches, the
signal is mainly overwhelmed by the decay $\tau\rightarrow
e/\mu+\nu\bar{\nu}$. In this work, we provide a procedure for separating the
signal from this background using tau polarization-induced effects and show
that this method can improve the obtained sensitivity significantly. Assuming
a future muon collider proposed by the Muon Accelerator Program (MAP) [6], we
study both the tau decay final states $e^{\pm}+a$ and $\mu^{\pm}+a$ and
provide the expected limits on the couplings ALP-tau-muon and ALP-tau-electron
for ALPs with $m_{a}\leq 1$ MeV.

##  2 ALP production in LFV tau decays

The LFV coupling of the ALP to the SM charged leptons can be described by the
effective Lagrangian [4]

$\displaystyle\mathcal{L}_{\rm eff}=\sum_{i\neq
j}\frac{\partial_{\mu}a}{2f_{a}}\,\bar{\ell}_{i}\gamma^{\mu}(c^{V}_{\ell_{i}\ell_{j}}+c^{A}_{\ell_{i}\ell_{j}}\gamma_{5})\ell_{j}\,,$
(1)

where $c^{V,A}_{\ell_{i}\ell_{j}}$ are hermitian matrices, $f_{a}$ is the
symmetry breaking scale of the model and $\ell_{i}=e,\mu,\tau$. We assume the
chiral structures V+A, V$-$A and V/A. The V+A and V$-$A cases respectively
correspond to the $c_{\ell_{i}\ell_{j}}\equiv
c^{V}_{\ell_{i}\ell_{j}}=c^{A}_{\ell_{i}\ell_{j}}$ and
$c_{\ell_{i}\ell_{j}}\equiv
c^{V}_{\ell_{i}\ell_{j}}=-c^{A}_{\ell_{i}\ell_{j}}$ conditions. The V/A case
assumes that one of the $c^{V,A}_{\ell_{i}\ell_{j}}$ couplings vanishes, i.e.
either $c_{\ell_{i}\ell_{j}}\equiv c^{V}_{\ell_{i}\ell_{j}}\neq
0,c^{A}_{\ell_{i}\ell_{j}}=0$ or $c_{\ell_{i}\ell_{j}}\equiv
c^{A}_{\ell_{i}\ell_{j}}\neq 0,c^{V}_{\ell_{i}\ell_{j}}=0$. According to the
above Lagrangian, the ALP can be produced in the tau decays
$\tau^{\pm}\rightarrow e^{\pm}\,a$ and $\tau^{\pm}\rightarrow\mu^{\pm}\,a$.
The ALP mass is assumed to be in the range $m_{a}\leq 1$ MeV in this study.
Such light ALPs can only decay into a pair of photons and have a decay length
many orders of magnitude larger than the typical size of a detector. The
majority of them, therefore, manifest themselves as missing energy.

We assume the process $\mu^{-}\mu^{+}\rightarrow\tau^{-}\tau^{+}$ with the
subsequent decay of one of the tau leptons into $e/\mu+a$. The remaining tau
lepton experiences a SM decay. A future muon collider proposed by the Muon
Accelerator Program (MAP) operating at the center-of-mass energies 126, 350
and 1500 GeV is assumed. In the limit $m_{a}\ll m_{\tau}$, the final lepton in
the decay $\tau\rightarrow\ell\,a$ ($\ell=e,\mu$) has an energy of
$E_{\ell}\simeq m_{\tau}/2$. Neglecting the final state lepton mass in this
decay, the rest frame differential decay width for the three assumed chiral
structures are found to be [4]

$\displaystyle\frac{\text{d}\Gamma(\tau^{\pm}\to\ell^{\pm}\,a)}{\text{d}\cos\theta}=\frac{m_{\tau}^{3}}{128\pi
f_{a}^{2}}\left(1-\frac{m_{a}^{2}}{m_{\tau}^{2}}\right)^{2}\times\left\\{\begin{array}[]{ll}\vskip
6.0pt plus 2.0pt minus
2.0pt2c_{\tau\ell}^{2}\left(1\mp\mathcal{P}_{\tau}\cos\theta\,\right)\,\,\,\,\,\,\,\mathrm{V\\!+\\!A}\\\
\vskip 6.0pt plus 2.0pt minus
2.0pt2c_{\tau\ell}^{2}\left(1\pm\mathcal{P}_{\tau}\cos\theta\,\right)\,\,\,\,\,\,\,\mathrm{V\\!-\\!A}\\\
c_{\tau\ell}^{2}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathrm{V/A}\\\ \end{array}\right.,$ (5)

where $\theta$ is the angle between the polarization vector of the decaying
tau and the direction of the final state lepton and $\mathcal{P}_{\tau}$ is
the degree of polarization of tau leptons. As seen, the angular distribution
of the final lepton depends on the assumed chiral structure. Despite the final
lepton in the LFV tau decay which is monoenergetic regardless of its
direction, in the SM decay $\tau\rightarrow e/\mu+\nu\bar{\nu}$, the energy of
the final lepton depends on its angular orientation. To be more specific,
final leptons $\ell^{-}$ ($\ell^{+}$) emitted forwardly (backwardly) with
respect to the polarization of the decaying tau are less energetic than those
emitted in other directions and are mostly separated from the leptons
resulting from the LFV tau decay. The difference between the polarization-
induced effects in these processes is utilized in this study to separate the
LFV signal from the main SM background. In addition to the main SM background,
other background processes, i.e. the production of $W^{-}W^{+}$, $t\bar{t}$,
$ZZ$, $Z\gamma$, $hZ$, $q\bar{q}$ ($q=u,d,c,s,b$) and
$e^{-}e^{+}/\mu^{-}\mu^{+}$ are also considered in this analysis. At high
enough center-of-mass energies, the SM vector boson fusion (VBF) processes
become important and should be considered in any analysis. However, at the
(relatively low) center-of-mass energies assumed in this study, the cross
section of the VBF processes is so small that the contribution of these
processes to the background can be safely neglected [7].

##  3 Event generation and analysis

Generation of events is performed using the packages FeynRules [8],
MadGraph5_aMC@NLO [9], Pythia 8.2.43 [10], Delphes 3.4.2 [11] with the muon
collider delphes card
111https://github.com/delphes/delphes/blob/master/cards/delphes˙card˙MuonColliderDet.tcl
and FastJet 3.3.2 [12]. The center-of-mass energies 126, 350 and 1500 GeV
corresponding to the integrated luminosities of 2.5, 189.2 and 394.2 fb-1 are
assumed and the event generation is performed separately for the cases of
unpolarized muon beams and polarized muon beams with $+0.8$ ($-0.8$)
polarization for the $\mu^{-}$ ($\mu^{+}$) beam. The ALP mass is assumed to
vary in the range 100 eV to 1 MeV. In the event generation, $f_{a}$ is set to
10 TeV. The two cases of $c_{\tau\mu}\neq 0$ and $c_{\tau e}\neq 0$ are
analyzed independently. Appropriate event selection criteria regarding the
number and type of the reconstructed objects in the events are performed.
$\tau$-tagged jets should satisfy the kinematical conditions $p_{T}>30$ GeV
and $|\eta|<2.5$. Moreover, they should include exactly three charged hadrons,
and at most one photon. Isolated muons, electrons and photons are required to
pass the conditions $p_{T}>10$ GeV and $|\eta|<2.5$. Events should either have
exactly one electron-muon pair or exactly one lepton (electron or muon) along
with one $\tau$-tagged jet. Using the momentum direction of the tau leptons,
the space is divided into two hemispheres, one on the side of the tau lepton
undergoing the LFV decay and one on the side of the tau lepton undergoing the
SM decay. There can be at most one photon on either side. Events passing the
selection cuts are analyzed to compute a proper set of discriminating
variables. A multivariate technique using the Boosted Decision Trees (BDT)
algorithm [13] is deployed to better discriminate between the signal and
background. The BDT output is used to constrain the ratios $c_{\tau e}/f_{a}$
and $c_{\tau\mu}/f_{a}$.

The cartoon in Fig. 1 shows the decaying tau leptons in the ALP production
process.

Figure 1: The decaying tau leptons in the ALP production process. $\tau_{1}$
and $\tau_{2}$ respectively undergo the LFV and SM decays. $V$ is either a
lepton ($e,\mu$) or a system of hadrons identified as a $\tau$-jet, and
$X_{\nu}$ is a system of neutrinos.

The momenta of the decaying tau leptons cannot be exactly determined because
of the invisible ALP and neutrinos. Using the conservation of momentum, one
finds the system of equations

$\displaystyle\hat{v}_{1}.\,\vec{p}_{\ell}=\frac{2E_{\tau_{1}}E_{\ell}+m_{a}^{2}-m_{\tau}^{2}-m_{\ell}^{2}}{2\,\sqrt{E_{\tau_{1}}^{2}-m_{\tau}^{2}}}\,,\,\
\ \ \ \ \
\hat{v}_{1}.\,\vec{p}_{V}=-\,\frac{2E_{\tau_{2}}E_{V}-m_{\tau}^{2}-m_{V}^{2}}{2\,\sqrt{E_{\tau_{2}}^{2}-m_{\tau}^{2}}}\,,\,\
\ \ \ \ \ |\hat{v}_{1}|=1\,,$ (6)

where the unit vector $\hat{v}_{1}$ denotes the momentum direction of
$\tau_{1}$. $E_{\tau_{1}}$ and $E_{\tau_{2}}$ can be estimated, ignoring the
radiative emissions and using the conservation of energy, to be half of the
center-of-mass energy of the experiment, i.e.
$E_{\tau_{1}}=E_{\tau_{2}}=\sqrt{s}/2$. This system of equations has two
solutions for $\hat{v}_{1}$. We take the average of the solutions as
$\hat{v}_{1}$ and reconstruct the momenta of the decaying tau leptons
$\vec{p}_{\tau_{1}}$ and $\vec{p}_{\tau_{2}}$, using the obtained momentum
direction. Furthermore, we reconstruct the momentum of the invisible ALP
($E_{a},\vec{p}_{a}$).

The discriminating variables used by the BDT algorithm are provided below. The
frame in which a variable is measured is the laboratory frame unless stated
otherwise.

  * •

Missing transverse energy $\not{E}_{T}$.

  * •

Transverse momenta and pseudorapidities of the isolated lepton $\ell$ and the
$V$ system.

  * •

Invariant mass of the the ALP and the isolated lepton $\ell$.

  * •

Angle between the momentum of the $V$ system and the momentum of the lepton
$\ell$.

  * •

Angle between the momenta of the lepton $\ell$ and the ALP in the $\tau_{1}$
rest frame.

  * •

Angle between the momentum of $\tau_{1}$ in the laboratory frame and the
momentum of the lepton $\ell$ in the $\tau_{1}$ rest frame.

  * •

Energy fraction of the lepton $\ell$ in the $\tau_{1}$ rest frame,
$x_{\ell}^{\tau_{1}\mathrm{RF}}=2E_{\ell}^{\tau_{1}\mathrm{RF}}/m_{\tau}$.

A comparison shows that the signal-background discrimination using the above
variables is significantly improved in the polarized muon beams case compared
with the unpolarized case.

##  4 Prospects for limits on the LFV tau couplings

Using the BDT output, we obtain expected $95\%$ confidence level (CL) limits
on the couplings $c_{\tau e}/f_{a}$ and $c_{\tau\mu}/f_{a}$. We assume a
$10\%$ systematic uncertainty on the event selection efficiency of each
process. Results indicate that the most stringent limits belong to the center-
of-mass energy of 350 GeV, and that different ALP mass scenarios below 1 MeV
result in similar limits. Fig. 2 shows the limits obtained at $\sqrt{s}=350$
GeV against the ALP mass for the three assumed chiral structures and the two
muon polarization cases. Also shown are the present limits derived from
searches at the ARGUS experiment [5] as well as future prospects at Belle-II
[14].

(a)

(b)

Figure 2: Obtained $95\%$ CL expected limits at $\sqrt{s}=350$ GeV, current
limits and future prospects of the limits on a) $c_{\tau e}/f_{a}$ and b)
$c_{\tau\mu}/f_{a}$ against the ALP mass. The green, blue and red solid
(dotted) lines respectively show the expected limits in the V/A, V$-$A and V+A
cases with unpolarized (polarized) beams. The pink dashed (dash-dotted) line
shows the present limit in the V+A/V$-$A (V/A) case obtained in ARGUS
searches. The cyan dashed (dash-dotted) line shows the Belle-II future
prospects for the V+A/V$-$A (V/A) structure assuming an integrated luminosity
of 50 $ab^{-1}$.

It is seen that both the obtained unpolarized and polarized limits are
significantly stronger than the present limits. Assuming an ALP mass of 1 MeV,
the most stringent limits on $c_{\tau e}/f_{a}$ ($c_{\tau\mu}/f_{a}$) in the
V+A, V$-$A and V/A cases belong to the polarized muon beams case and are
respectively $2.48\times 10^{-5}$ ($2.27\times 10^{-5}$), $4.90\times 10^{-5}$
($4.68\times 10^{-5}$) and $4.37\times 10^{-5}$ ($3.92\times 10^{-5}$)
$\mathrm{TeV}^{-1}$. Our recast of the limits derived from ARGUS searches in
the V+A/V$-$A (V/A) case are $c_{\tau e}/f_{a}<3.3\times 10^{-4}$ ($c_{\tau
e}/f_{a}<4.7\times 10^{-4}$) and $c_{\tau\mu}/f_{a}<4.3\times 10^{-4}$
($c_{\tau\mu}/f_{a}<6.1\times 10^{-4}$) TeV-1. A comparison shows that the
presented analysis can improve the current limits by roughly one order of
magnitude. Results also indicate that the obtained limits in the unpolarized
case are slightly weaker than the prospects at Belle-II. In the polarized
case, however, the obtained limits for the V+A and V/A chiral structures are
slightly stronger than the prospects at Belle-II.

##  5 Conclusion

We studied the LFV decays of the tau lepton into an electron (or a muon) and
an ALP assuming a future muon collider operating at $\sqrt{s}=$ 126, 350 and
1500 GeV. The chiral structures V+A, V$-$A and V/A for the LFV tau decay, and
the two cases of unpolarized and polarized muon beams were studied separately
and expected $95\%$ CL limits on the LFV couplings $c_{\tau e}/f_{a}$ and
$c_{\tau\mu}/f_{a}$ for ALP masses $m_{a}\leq 1$ MeV were obtained. The most
stringent limits were obtained at the center-of-mass energy of 350 GeV. It is
seen that, if producing the polarized muon beams assumed in this work becomes
possible, the present experimental limits derived from ARGUS searches can be
improved by roughly one order of magnitude with the help of this analysis. The
improvement in the experimental limits using the present analysis with
unpolarized muon beams can be about half an order of magnitude. A comparison
shows that the limits obtained in the polarized case assuming the V+A and V/A
chiral structures are slightly stronger than the prospects at Belle-II
assuming an integrated luminosity of 50 $ab^{-1}$. Other obtained polarized
and unpolarized limits are, however, slightly weaker than the prospects at
Belle-II. It is seen that the limits get worse as the center-of-mass energy
increases from 350 GeV to 1.5 TeV. Both the signal and background cross
sections decrease as the energy grows. The reduction in the background,
however, doesn’t compensate for the reduction in the signal giving rise to
looser constraints. At high enough energies, the vector boson fusion (VBF)
processes become important. Such processes may further degrade the limits at
high energies since they can contribute to the background.

## References

  * [1]
  * [2] P. Lipari, doi:10.5170/CERN-2003-003.115, url:https://cds.cern.ch/record/677618.
  * [3] R. D. Peccei and H. R. Quinn, Phys. Rev. Lett. 38, 1440 (1977). doi:10.1103/PhysRevLett.38.1440
  * [4] L. Calibbi, D. Redigolo, R. Ziegler and J. Zupan, [arXiv:2006.04795 [hep-ph]].
  * [5] H. Albrecht, T. Hamacher et al. Z. Phys. C - Particles and Fields 68, 25–28 (1995) doi:10.1007/BF01579801
  * [6] M. Boscolo, J. P. Delahaye and M. Palmer, Rev. Accel. Sci. Tech. 10, no.01, 189-214 (2019) doi:10.1142/9789811209604_0010 [arXiv:1808.01858 [physics.acc-ph]].
  * [7] A. Costantini, F. De Lillo, F. Maltoni, L. Mantani, O. Mattelaer, R. Ruiz and X. Zhao, JHEP 09, 080 (2020) doi:10.1007/JHEP09(2020)080 [arXiv:2005.10289 [hep-ph]].
  * [8] A. Alloul, N. D. Christensen, C. Degrande, C. Duhr and B. Fuks, Comput. Phys. Commun. 185, 2250 (2014) doi:10.1016/j.cpc.2014.04.012 [arXiv:1310.1921 [hep-ph]].
  * [9] J. Alwall, M. Herquet, F. Maltoni, O. Mattelaer and T. Stelzer, JHEP 1106, 128 (2011) doi:10.1007/JHEP06(2011)128 [arXiv:1106.0522 [hep-ph]].
  * [10] T. Sjostrand, S. Mrenna and P. Z. Skands, JHEP 0605, 026 (2006) doi:10.1088/1126-6708/2006/05/026 [hep-ph/0603175].
  * [11] J. de Favereau et al. [DELPHES 3 Collaboration], JHEP 1402, 057 (2014) doi:10.1007/JHEP02(2014)057 [arXiv:1307.6346 [hep-ex]].
  * [12] M. Cacciari, G. P. Salam and G. Soyez, Eur. Phys. J. C 72, 1896 (2012) doi:10.1140/epjc/s10052-012-1896-2 [arXiv:1111.6097 [hep-ph]].
  * [13] A. Hocker et al., PoS ACAT , 040 (2007) [physics/0703039 [PHYSICS]].
  * [14] E. Kou et al. [Belle-II], PTEP 2019, no.12, 123C01 (2019) [erratum: PTEP 2020, no.2, 029201 (2020)] doi:10.1093/ptep/ptz106 [arXiv:1808.10567 [hep-ex]].