Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Novel Characteristics of Split Trees by use of Renewal Theory   We investigate characteristics of random split trees introduced by Devroye;
split trees include for example binary search trees, $m$-ary search trees,
quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search
trees. More precisely: We introduce the use of renewal theory in the studies of
split trees, and use this theory to prove several results about split trees. A
split tree of cardinality $n$ is constructed by distributing $n$ "balls" (which
often represent "key numbers") in a subset of vertices of an infinite tree. One
of our main results is to give a relation between the deterministic number of
balls $n$ and the random number of vertices $N$. Devroye has found a central
limit law for the depth of the last inserted ball so that most vertices are
close to $\frac{\ln n}{\mu}+\mathcal{O}\Big(\sqrt{\ln n}\Big)$, where $\mu$ is
some constant depending on the type of split tree; we sharpen this result by
finding an upper bound for the expected number of vertices with depths
$\geq\frac{\ln n}{\mu}+\ln^{0.5+\epsilon} n$ or depths $\leq\frac{\ln
n}{\mu}+\ln^{0.5+\epsilon} n$ for any choice of $\epsilon>0$. We also find the
first asymptotic of the variances of the depths of the balls in the tree.

20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin
19
The categories of this paper are: eess
22
The categories of this paper are: chao-dyn
33
The categories of this paper are: plasm-ph
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
25
The categories of this paper are: patt-sol
4
The categories of this paper are: cond-mat
34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
23
The categories of this paper are: solv-int