\section{Introduction}\label{sec:intro}
A sequential algorithm transforms an input sequence $t_1,t_2,\ldots$
into an output sequence $x_1,x_2,\ldots$ where, for
all $n\in\bN$, $x_{n+1}$ depends on $x_n$ and $t_{n+1}$ only.
Typically, the output variables are elements of some
combinatorial family $\bF$, each $x\in\bF$ has a size parameter
$\phi
(x)\in\bN$ and $x_n$ is an element of the set
$\bF_n:=\{x\in\bF\dvtx \phi(x)=n\}$ of objects of size $n$. In the
probabilistic analysis of such algorithms, one
starts with a stochastic model for the input sequence and is interested
in certain aspects of the output sequence. The
standard input model assumes that the $t_i$'s are the values of a
sequence $\eta_1,\eta_2,\ldots$ of independent and
identically distributed random variables. For random input of this
type, the output sequence then is the path of a Markov
chain $X=(X_n)_{n\in\bN}$ that is adapted to the family $\bF$ in the
sense that
\begin{equation}
\label{eq:time-space} P(X_n\in\bF_n) = 1 \qquad\mbox{for all } n\in
\bN.
\end{equation}
Clearly, $X$ is highly transient---no state can be visited twice.

The special case we are interested in, and which we will use to
demonstrate an approach that is generally applicable in
the situation described above, is that of binary search trees and two
standard algorithms, known by their acronyms BST
(binary search tree) and DST (digital search tree). These are discussed
in detail in the many excellent texts in this area,
for example in \cite{Knuth3,Mahmoud1} and \cite{Drmota09}.
Various functionals of the search trees, such as the
height \cite{Dev86}, the path length \cite{RegnierQS,RoeQS}, the node depth
profile \cite{J-H2001,CDJ2001,CR2004,CKMR2005,FHN2006,DJN2008},
the subtree size profile \cite{Fu2008,DeGr3}, the Wiener index \cite{Nein02} and the
silhouette \cite{GrSilh} have been studied, with methods spanning the
wide range from generatingfunctionology to
martingale methods to contraction arguments on metric spaces of
probability distributions (neither of these lists is
complete). Many of the results are asymptotic in nature, where the
convergence obtained as $n\to\infty$ may refer to the
distributions or to the random variables themselves. As far as strong
limit theorems are concerned, a significant step
toward a unifying approach was made in the recent paper \cite{EGW},
where methods from discrete potential theory were
used to obtain limit results on the level of the combinatorial
structures themselves: In a suitable extension
of the state space $\bF$, the random variables $X_n$ converge almost
surely as $n\to\infty$, and the limit generates the
tail $\sigma$-field of the Markov chain. The results in \cite{EGW}
cover a wide variety of structures; search trees are
a special case. It should also be mentioned here that the use of
boundary theory has a venerable tradition in connection
with random walks; see \cite{KaimVersh} and~\cite{Woess1}.

Our aims in the present paper are the following. First, we use the
algorithmic background for a direct proof of the
convergence of the BST variables $X_n$, as $n\to\infty$, to a limit
object $X_\infty$, and we obtain a representation
of $X_\infty$ in terms of the input sequence $(\eta_i)_{i\in\bN}$.
Second, we introduce the subtree size metric on
finite binary trees. This leads to a reinterpretation of the above
convergence in terms of metric trees. We also
introduce a family of weighted variants of this metric, with parameter
$\rho\ge1$, and then identify the critical
value $\rho_0$ with the property that the metric trees converge for
$\rho<\rho_0$ and do not converge if $\rho>
\rho_0$. The value $\rho_0$ turns out to also be the threshold for
compactness of the limit tree. Third, we use
convergence at the tree level to (re)obtain strong limit theorems for
three tree functionals---the path length, the
Wiener index and a metric version of the silhouette.

These topics are treated in the next three sections, where each has its
own introductory remarks.

\section{Binary search trees
\label{sec:BSTDoob--Martin}

We first introduce some notation, mostly specific to binary trees, then
discuss the two search algorithms and the associated
Markov chains and finally recall the results from \cite{EGW} related to
these structures, including an alternative proof
of the main limit theorem.

\subsection{Some notation}\label{subsec:notation}
We write $\cL(X)$ for the distribution of a random variable $X$ and
$\cL
(X|Y=k)$, $\cL(X|Y)$, $\cL(X|\cF)$ for the
various versions of the conditional distribution of $X$ given (the
value of) a random variable $Y$ or a $\sigma$-field
$\cF$. Further, $\delta_c$ is the one-point mass at $c$, $1_A$ is the
indicator function of the set $A$ [so that
$1_A(c)=\delta_c(A)$], $\Bin(n,p)$ denotes the binomial distribution
with parameters $n\in\bN$ and $p\in(0,1)$,
$\Beta(\alpha,\beta)$ is the beta distribution with parameters
$\alpha
,\beta>0$ and $\unif(0,1)=\Beta(1,1)$ is the
uniform distribution on the unit interval. We also write $\unif(M)=(\#
M)^{-1}\sum_{c\in M} \delta_c$ for the uniform
distribution on a finite set $M$.

With $\bN_0=\{0,1,2,\ldots\}$ let
\[
\bV_k:= \{0,1\}^k,\qquad \bV:=\bigsqcup
_{k\in\bN_0}\bV_k,\qquad \partial\bV:= \{0,1\}^\infty
\]
be the set of 0--1 sequences of length $k$, $k\in\bN_0$, the set of all
finite 0--1 sequences and the set of all infinite
0--1 sequences, respectively. The set $\bV_0$ has $\varnothing$, the
``empty sequence,'' as its only element, and $|u|$ is the
length of $u\in\bV$, that is, $|u|=k$ if $u\in\bV_k$. For each node
$u=(u_1,\ldots,u_k)\in\bV$ we use
\begin{eqnarray*}
u0&:=&(u_1,\ldots,u_k,0),
\\
u1&:=&(u_1,\ldots,u_k,1),
\\
\bar u&:=&(u_1,\ldots,u_{k-1})\qquad \mbox{if } k\ge1,
\end{eqnarray*}
to denote its left and right direct descendant (child) and its direct
ancestor (parent). We write $u\le v$ for
$u=(u_1,\ldots,u_k)\in\bV$, $v=(v_1,\ldots,v_l)\in\bV$ if $k\le
l$ and
$u_j=v_j$ for $j=1,\ldots,k$, that is, if $u$ is a
prefix of $v$; the extension to $v\in\partial\bV$ is obvious. The
prefix order is a partial order only, but there exists
a unique minimum $u\wedge v$ to any two nodes $u,v\in\bV$, their last
common ancestor; again, this can be extended to
elements of $\partial\bV$. Another ordering on $\bV$ can be obtained
via the function $\beta\dvtx\bV\to[0,1]$,
\begin{equation}
\label{eq:defbeta} \beta(u):= \frac{1}{2} + \sum_{j=1}^k
\frac
{2u_j-1}{2^{j+1}}, \qquad u\in\bV.
\end{equation}
This will be useful in various proofs, and also in connection with
illustrations.

By a \emph{binary tree} we mean a subset $x$ of the set $\bV$ of nodes
that is prefix stable in the sense that $u\in x$ and
$v\le u$ implies that $v\in x$. Informally, we regard the components
$u_1,\ldots,u_k$ of $u$ as a routing instruction
leading to the vertex $u$, where~0 means a move to the left, 1 a move
to the right and the empty sequence is the root
node. The edges of the tree $x$ are the pairs $(\bar u,u)$, $u\in x,
u\neq\varnothing$. A node is external to
a tree if it is not one of its elements, but its direct ancestor is; we
write $\partial x:=\{u\in\bV\dvtx \bar u\in x,
u\notin x\}$ for the set of external nodes of $x$. Finally,
\begin{equation}
\label{eq:sts} \sigma(x,u):= \#\{v\in x\dvtx u\le v\}
\end{equation}
is the size of the subtree of $x$ rooted at $u$ (or the number of
descendants of $u$ in $x$, including $u$).

Let $\bB$ denote the (countable) set of finite binary trees, $\bB
_n:=\{
x\in\bB\dvtx \#x=n\}$ those of size (number of
nodes) $n$. The single element of $\bB_1$ is $\{\varnothing\}$, the tree
that consists of the root node only.

\subsection{Search algorithms and Markov chains}\label{subsec:AlgMC}
Let $(t_i)_{i\in\bN}$ be a sequence of pairwise distinct real numbers.
The BST (binary search tree) algorithm stores
these sequentially into labeled binary trees $(x_n,L_n)$, $n\in\bN$,
with $x_n\in\bB_n$ and
$L_n\dvtx x_n\to\{t_1,\ldots,t_n\}$. For $n=1$ we have $x_1=\{
\varnothing\}$
and $L_1(\varnothing)=t_1$. Given $(x_n,L_n)$, we
construct $(x_{n+1},L_{n+1})$ as follows: Starting at the root node we
compare the next input value $t_{n+1}$ to the
value $L_n(u)$ attached to the node $u$ under consideration, and move
to $u0$ if $t_{n+1}<L_n(u)$ and to $u1$
otherwise, until an ``empty'' node $u$ (necessarily an external node of
$x_n$) is found. Then $x_{n+1}:=x_n\cup\{u\}$ and
$L_{n+1}(u):=t_{n+1}$, $L_{n+1}(v):=L_n(v)$ for all $v\in x_n$.

Now let $(\eta_i)_{i\in\bN}$ be a sequence of independent random
variables with $\cL(\eta_i)=\unif(0,1)$ for all
$i\in\bN$, and let $X_n$ be the random binary tree associated with the
first $n$ of these. By construction, the label
functions $L_n$ are monotone with respect to the $\beta$-order of the
tree nodes, that is, with $\beta$ as
in \eqref{eq:defbeta},
\begin{equation}
\label{eq:orderpropBST} \beta(u)\le\beta(v) \Rightarrow L_n(u)\le
L_n(v)\qquad \mbox{for all } n \mbox{ with }\{u,v\}\subset
X_n.
\end{equation}
In particular, if we number the external nodes of $X_n$ from the left
to the right, then the number of the node that
receives $\eta_{n+1}$ is the rank of this value among $\{\eta
_1,\ldots
,\eta_n\}$, hence uniformly distributed on
$\{1,\ldots,n+1\}$. This shows that the (deterministic) BST algorithm,
when applied to the (random) input
$(\eta_i)_{i\in\bN}$, results in a Markov chain $(X_n)_{n\in\bN}$ with
state space $\bB$, start at $X_1\equiv
\{\varnothing\}$ and transition probabilities
\begin{equation}
\label{eq:transBST} Q \bigl(x,x\cup\{u\} \bigr) =
\cases{1/(1+\# x), &\quad $\mbox{if }u\in\partial x$,\vspace*{2pt}
\cr
0, & \quad $\mbox{otherwise}$.}
\end{equation}
In words: We obtain $X_{n+1}$ by choosing one of the $n+1$ external nodes
of $X_n$ uniformly at random and joining it to the tree. We refer to
this construction as the
\emph{BST chain}.

For the DST (digital search tree) algorithm, the input values are
infinite 0--1 sequences, that is, elements of $\partial
\bV$. Given $t_1,t_2,\ldots\in\partial\bV$ we again obtain a sequence
$x_1,x_2,\ldots$ of labeled binary trees, but now
we use the components $t_{n+1,k}$, $k\in\bN$, of the next input value
$t_{n+1}$ as a routing instruction through $x_n$,
moving to $u0$ from an occupied node $u\in\bV_k$ if $t_{n+1,k+1}=0$ and
to $u1$ otherwise. As in the BST case we assume
that the $t_i$'s are the values of a sequence of independent and
identically distributed random variables $\eta_i$,
where the distribution of the $\eta_i$'s is now a probability measure
$\mu$ on the measurable space
$(\partial\bV,\cB(\partial\bV))$, with $\cB(\partial\bV)$ the
$\sigma
$-field generated by the projections on the
sequence elements, $\partial\bV\ni t=(t_k)_{k\in\bN}\mapsto t_i$,
$i\in
\bN$. This $\sigma$-field is also generated by
the sets
\begin{equation}
\label{eq:defA} A_u:= \{v\in\partial\bV\dvtx v\ge u \}, \qquad u\in\bV.
\end{equation}
It is easy to check that the intersection of two such sets is either
empty or again of this form. This implies that
$\mu$ is completely specified by its values $\mu(A_u)$, $u\in\bV$, and
the DST analogue of \eqref{eq:transBST} then is
\begin{equation}
\label{eq:transDST} Q \bigl(x,x\cup\{u\} \bigr) =
\cases{\mu(A_u), &\quad $\mbox{if } u\in\partial x$,\vspace*{2pt}
\cr
0, & \quad $\mbox{otherwise}$.}
\end{equation}
By the \emph{DST chain with driving distribution $\mu$} we mean a
Markov chain $(X_n)_{n\in\bN}$ with state space $\bB$,
start at $\{\varnothing\}$ and transition mechanism given by \eqref
{eq:transDST}.

\subsection{Doob--Martin compactification}\label{subsec:DM}
We refer the reader to Doob's seminal paper \cite{Doob1959} and to the
recent textbook \cite{Woess2} for the main
results of, background on and further references for the boundary
theory for transient Markov chains. For the BST chain
the Doob--Martin\vspace*{1pt} compactification has recently been obtained in \cite{EGW}: It can be described as the closure $\bar\bB$
of the embedding of $\bB$ into the compact space $[0,1]^{\bV}$, endowed
with pointwise convergence, that is given by the
standardized \emph{subtree size functional}
\[
\bB\ni x \mapsto \biggl(\bV\ni u\mapsto\frac{\sigma(x,u)}{\# x} \biggr)
\]
with $\sigma$ as defined in \eqref{eq:sts}. Further, the elements of
the boundary $\partial\bB$ may be represented by
probability measures $\mu$ on $(\partial\bV,\cB(\partial\bV))$, with
convergence $x_n\to\mu$ of a sequence
$(x_n)_{n\in\bN}$ in $\bB$ meaning that
\[
\mu(A_u) = \lim_{n\to\infty} \frac{\sigma(x_n,u)}{\# x_n} \qquad\mbox{for all } u\in\bV,
\]
and $\mu_n(A_u)\to\mu(A_u)$ for all $u\in\bV$ if we have a sequence
$(\mu_n)_{n\in\bN}$ of elements of $\partial\bB$
instead.

The general theory implies that $X_n$ converges almost surely to a
limit $X_\infty$ with values in $\partial\bB$;
\cite{EGW} also contains a description of $\cL(X_\infty)$. The proof
given there does not make use of the algorithmic
background, but takes the transition mechanism \eqref{eq:transBST} as
its starting point. We now show that this
background leads to a direct proof of $X_n\to X_\infty$, and to a
representation of $X_\infty$ in terms of the input
sequence.

We need some more notation. On $\bV$ we define a metric $d_\bV$ by
\begin{equation}
\label{eq:defdV} d_\bV(u,v):= 2^{-|u\wedge v|}-\tfrac{1}{2}
\bigl(2^{-|u|}+2^{-|v|} \bigr),\qquad u,v\in\bV.
\end{equation}
On $\bV$ itself this gives the discrete topology, and the completion of
$\bV$ with respect to $d_\bV$ leads to $\bar
\bV:=\bV\cup\partial\bV$, a compact and separable metric space.
This is
also the ends compactification if we regard
$\bV$ as the complete rooted binary tree. We extend the $A_u$'s to
$\bar\bV$ by
\[
\bar A_u:= \{ v\in\bar\bV\dvtx v\ge u\}, \qquad u\in\bV.
\]
Because of
\[
\bar A_u:= \bigl\{ v\in\bar\bV\dvtx d_\bV(u,v)<2^{-|u|}
\bigr\} = \bigl\{ v\in\bar\bV\dvtx d_\bV(u,v)\le2^{-|u|-1}
\bigr\}
\]
these sets are open and closed. Further,
\[
\{u\} = \bar A_u\setminus(\bar A_{u0}\cup\bar
A_{u1}), \qquad \bar A_u\cap\bar A_v=
\cases{ \bar A_u, &\quad $\mbox{if } u\le v$,\vspace*{2pt}
\cr
\bar
A_v, &\quad $\mbox{if } u\ge v$,\vspace*{2pt}
\cr
\varnothing, &\quad $
\mbox{otherwise,}$}
\]
hence $\{\bar A_u\dvtx u\in\bV\}$ is a $\pi$-system that generates
$\cB
(\bar\bV)$. Together these facts imply that
weak convergence of probability measures $\mu_n$ to a probability
measure $\mu$ on $(\bar\bV,\cB(\bar\bV))$
is equivalent to
\begin{equation}
\label{eq:wconvT} \lim_{n\to\infty} \mu_n(\bar
A_u) = \mu(\bar A_u)\qquad \mbox{for all } u\in\bV.
\end{equation}
In view of
\[
\frac{1}{n} \sigma(X_n,u) = \unif(X_n) (\bar
A_u)
\]
and $X_\infty(\bV)=0$ convergence in the Doob--Martin topology is
therefore equivalent to the weak convergence of
probability measures on the metric space $(\bar\bV,d_\bV)$ if we
represent finite subsets $M$ of $\bV$ by the uniform
distribution $\unif(M)$ on $(\bar\bV,\cB(\bar\bV))$.

Moreover, any sequence $(\mu_n)_{n\in\bN}$ of probability measures on
$(\bar\bV,\cB(\bar\bV))$ is tight, as $\bar\bV$
is compact, and therefore has a limit point by Prohorov's theorem
\cite{Bill68}, page~37. If $(\mu_n(\bar A_u))_{n\in\bN}$
is a convergent sequence for each $u\in\bV$, then there is only one
such limit point, which means that $\mu_n$
converges weakly to some probability measure $\mu$ and that \eqref
{eq:wconvT} holds.
Finally, let
\begin{equation}
\label{eq:deftau} \tau(u):=\inf\{n\in\bN\dvtx X_n\ni u\}, \qquad u\in\bV,
\end{equation}
be the time that the node $u$ becomes an element of the BST sequence.
It is easy to see that the $\tau(u)$'s are finite
with probability 1.

\begin{theorem}\label{thm:DMconv}
Let $(X_n)_{n\in\bN}$ be the sequence of binary trees generated by the
BST algorithm with input a sequence
$(\eta_i)_{i\in\bN}$ of independent and identically distributed random
variables with $\cL(\eta_1)=\unif(0,1)$.

\begin{longlist}[(a)]
\item[(a)] With probability 1 the sequence $\unif(X_n)$ converges
weakly to a random probability measure $X_\infty$ on
$(\partial\bV,\cB(\partial\bV))$ as $n\to\infty$.

\item[(b)] For each $u\in\bV$, $u\neq\varnothing$, with $i:=\tau(u)-1$,
$\tau$ as in \eqref{eq:deftau},
and
\[
0=:\eta_{(i:0)} <\eta_{(i:1)}<\cdots<\eta_{(i:i)}<
\eta_{(i:i+1)}:=1
\]
the augmented order statistics associated with $\eta_1,\ldots,\eta_i$,
we have
\[
X_\infty(A_u) = \eta_{(i:j+1)} -\eta_{(i:j)}\qquad
\mbox{with } \eta_{(i:j)} <\eta_{i+1}<\eta_{(i:j+1)}.
\]

\item[(c)]
The random variables
\[
\xi_u:= \frac{X_\infty(A_{u0})}{X_\infty(A_u)},\qquad  u\in\bV,
\]
are independent, and $\cL(\xi_u)=\unif(0,1)$ for all $u\in\bV$.
\end{longlist}
\end{theorem}

\begin{pf}
Let $u$, $\tau(u)$, $i$ and $\eta_{(i:j)}$, $j=0,\ldots,i+1$, be as in
part (b) of the theorem.
The order property \eqref{eq:orderpropBST} of the labeled binary
search trees implies that for a node $v$ with label
$\eta_k$, $k>i$, the relation $v\ge u$ is equivalent to $\eta_{(i:j)}
<\eta_{k}<\eta_{(i:j+1)}$. Hence, by the law of
large numbers,
\begin{eqnarray*}
\lim_{n\to\infty} \unif(X_n) (\bar A_u) &=&
\lim_{n\to\infty} \frac{\#\{v\in X_n\dvtx v\ge u\}}{n}
\\
&=& \lim_{n\to\infty} \frac{\#\{i < k\le n\dvtx\eta_k\in(\eta
_{(i:j)}, \eta_{(i:j+1)})\}}{n}
\\
&=& \eta_{(i:j+1)} -\eta_{(i:j)}
\end{eqnarray*}
with probability 1 for every $u\in\bV$. In view of
\[
\{u\}= \bigl\{v\in\bar\bV\dvtx d(u,v)<2^{-|u|-1} \bigr\}\qquad \mbox{for all }
u \in\bV,
\]
the one-point sets with elements from $\bV$ are open in the topology on
$\bar\bV$. As $\unif(X_n)$ assigns at most the
value $1/n$ to such a set, it follows with the portmanteau theorem
\cite{Bill68}, page 11, that any limit point of this
sequence is concentrated on $\partial\bV$. Parts (a) and (b) of the
theorem now follow with the above general remarks
on weak convergence of probability measures on $(\bar\bV,\cB(\bar
\bV))$.

For the proof of (c) we use the following well-known fact: The
conditional distribution of $\eta_{i+1}$, given
$\eta_1,\ldots,\eta_i$ and given that the value lands in an interval
$I=(\eta_{(i:j)},\eta_{(i:j+1)})$ of the augmented
order statistics, is the uniform distribution on $I$, which implies
that $\unif(0,1)$ is the distribution of the normalized
distance $\xi_{u}$ to the left endpoint of $I$. For different $\eta
$-values these relative insertion positions
are independent, hence $\xi_u$, $u\in\bV$, are independent and
uniformly distributed on the unit interval.
\end{pf}

We note the following consequence of the representation in part (c) of
the theorem: For a fixed $u\in\bV$ let
\[
\varnothing=u(0)<u(1)<\cdots<u(k)=u
\]
with $|u(j)|=j$ for $j=0,\ldots,k$ be the path that connects $u$ to the
root node. We then have
\begin{eqnarray}
\label{eq:prodXinfty} X_\infty(A_u) = \prod
_{j=0}^{k-1}\tilde\xi_{u(j)}
\nonumber
\\[-8pt]
\\[-8pt]
\eqntext{\displaystyle\mbox{with }
\tilde\xi_{u(j)}:=
\cases{ \xi_{u(j)}, &\quad $\mbox{if
}u(j+1)=u(j)0$, \vspace*{2pt}
\cr
1-\xi_{u(j)}, &\quad $\mbox{if
}u(j+1)=u(j)1$.}}
\end{eqnarray}
Note that the factors $\tilde\xi_{u(j)}$, $j=0,\ldots,k-1$, are
independent and that they all have
distribution $\unif(0,1)$.

Theorem \ref{thm:DMconv} confirms the view expressed in \cite{Woess2}, pages 191
and 218, that in specific cases embeddings
(or boundaries) can generally be obtained directly on using the then
available additional structure; here this turns out to
be the algorithmic representation of the Markov chain. However, there
are two additional benefits of the general theory:
First, because of the space--time property \eqref{eq:time-space} the
limit $X_\infty$ generates the tail $\sigma$-field
\[
\cT:= \bigcap_{n=1}^\infty\sigma \bigl(
\{X_m\dvtx m\ge n\} \bigr)
\]
associated with the sequence $(X_n)_{n\in\bN}$. This may serve as a
starting point for the unification of strong limit
theorems for functionals $(Y_n)_{n\in\bN}$, $Y_n=\Psi(X_n)$ of the
discrete structures: If $Y_n$ converges to $Y_\infty$
in a ``reasonable'' space, then the limit~$Y_\infty$, which is $\cT
$-measurable, must be a function of $X_\infty$; see, for example,
\cite{Kall}, Lemma 1.13. The second general result is extremely useful in
the context of the calculations that
arise in specific applications of the theory: The conditional
distribution of the chain $(X_n)_{n\in\bN}$ given the
value of $X_\infty$ is again a Markov chain, where the new transition
probabilities can be obtained from the limit value
and the old transition probabilities by a procedure that is known as
Doob's $h$-transform. In the present situation it
turns out that the conditional distribution of the BST chain, given
$X_\infty=\mu$, is the same as that of the DST chain
driven by $\mu$. We refer the reader to \cite{EGW} for details; the
last statement appears there only for a specific~$\mu$, but the generalization to an arbitrary probability measure $\mu$
in the boundary is straightforward. Roughly, the
embedded jump chains at the individual nodes are P\'olya urns; for
these the boundary has been obtained
in \cite{BK1964}, and from the general construction of the Doob--Martin
boundary it is clear that the outcome is
unaffected by the step from a Markov chain to its embedded jump chain.
We collect some consequences in the following
proposition, where
\begin{equation}
\label{eq:natFilt} \cF_n:= \sigma(X_1,\ldots,X_n),\qquad
n\in\bN,
\end{equation}
are the elements of the natural filtration of the BST chain.

\begin{proposition}\label{prop:conddistrnodes}
With the notation and assumptions as in Theorem \ref{thm:DMconv},
\begin{equation}
\label{eq:nodeBin} \cL \bigl(\sigma(X_n,u0) | \sigma(X_n,u)=k,
\xi_u=p \bigr) = \Bin(k-1,p) \qquad\mbox{if } k>0,
\end{equation}
and, for all $i,j\in\bN_0$,
\begin{equation}
\label{eq:nodeBeta} \cL \bigl(\xi_u | \sigma(X_n,u0)=i,
\sigma(X_n,u1)=j \bigr) = \Beta(i+1,j+1).
\end{equation}
Further, the variables $(\xi_u)_{u\in\bV}$ are conditionally
independent given $\cF_n$.
\end{proposition}

\section{Metric aspects}\label{sec:results}
All trees in this paper are subgraphs of the complete binary tree,
which has $\bV$ as its set of nodes and
$\{(\bar u,u)\dvtx u\neq \varnothing\}$ as its set of edges; in
particular, our trees are specified by their
node sets $x$. In a tree metric $d $ the distance of any two nodes
$u,v$ is the sum of the distances between
successive nodes on the unique path from $u$ to $v$, which means that
such a metric is given by
its values $d(\bar u,u)$, $u\in x$, $u \neq\varnothing$. For example,
the metric $d_\bV$ in
Section~\ref{subsec:DM} has $d_\bV(\bar u,u)=2^{-|u|-1}$, and the
canonical tree distance $d_{\mathrm{can}}$
is given by $d_{\mathrm{can}}(\bar u,u)=1$. For our trees the
prefix order further leads to
\begin{equation}
\label{eq:distviamin} d(u,v) = d(u,\varnothing) + d(v,\varnothing) - 2 d(u\wedge v,
\varnothing) \qquad\mbox{for all } u,v\in x.
\end{equation}
Metric trees may also be interpreted as graphs with edge weight, where
the edge $(\bar u,u)$ receives the weight
$d(\bar u,u)$.

Our aim in this section is to rephrase the convergence of the BST
sequence as a convergence of metric trees,
and to show that this view leads to convergence with respect to
stronger topologies. The situation here is
much simpler than for Aldous's continuum random tree where the
Gromov--Hausdorff convergence
of equivalence classes of metric trees is used; see \cite{EvansSF} and
the references given there. In fact,
the search trees considered here have node sets that grow monotonically
to the full $\bV$, so we may define
convergence of a sequence $((x_n,d_n))_{n\in\bN}$ of metric binary
trees to $(\bV,d_\infty)$ to mean that
\begin{equation}
\label{eq:treeconvweak} \lim_{n\to\infty} d_n(u,v) =
d_\infty(u,v) \qquad\mbox{for all } u,v\in\bV,
\end{equation}
which of course is equivalent to $ \lim_{n\to\infty} d_n(\bar u,u) =
d_\infty(\bar u,u)$ for all $u\in\bV$,
$u\neq\varnothing$. Note that $d_\bV$ and $d_{\mathrm{can}}$ are
both local metrics in the sense that $d(u,v)$ does
not depend on the tree $x$ as long as $u,v\in x$.

Motivated by the view in Section~\ref{subsec:DM} of finite and
infinite binary trees as probability measures $\mu$ on $(\bar\bV,\cB
(\bar\bV))$, we now introduce the (relative)
\emph{subtree size metric}, which assigns $\mu(\bar A_u)$ to the
distance of $\bar u$ and $u$, that is,
\[
d_x(\bar u,u) = \frac{\sigma(x,u)}{\sigma(x,\varnothing)} \qquad\mbox{for all } u\in x, u\neq
\varnothing,
\]
if $x\in\bB$, and
\[
d_\mu(\bar u,u) = \mu(A_u) \qquad\mbox{for all } u\in\bV, u
\neq\varnothing
\]
for the complete tree and a probability measure $\mu$ on $(\partial
\bV
,\cB(\partial\bV))$, where we assume that
$\mu(A_u)>0$ for all $u\in\bV$. Again, there is an algorithmic
motivation: In terms of the BST mechanism, the weight of
an edge $(\bar u,u)$ is the (relative) number of times this edge has
been traversed in the construction of the
tree. These metrics depend on their tree in a global manner.

With this terminology in place we may now rephrase the convergence in
Theorem \ref{thm:DMconv} as the
convergence in the sense of \eqref{eq:treeconvweak} of the finite
metric trees $(X_n,d_{X_n})$ to the infinite metric
tree $(\bV, d_{X_\infty})$, almost surely and as $n\to\infty$.

By construction the Doob--Martin compactification is the weakest
topology that allows for a continuous extension of the
functions $\bB\ni x\mapsto\sigma(x,u)/\break \sigma(x,\varnothing)$,
$u\in\bV$.
For the analysis of tree functionals stronger
modes of convergence turn out to be useful; for example, do we have
uniform convergence in \eqref{eq:treeconvweak}?
Also, subtree sizes decrease along paths leading away from the root
node, so we may consider a weight factor for the
distance of a node to its parent that depends on the depth of the node:
For all $\rho\ge1$, we define the
\emph{weighted subtree size metric} with \emph{weight parameter}
$\rho$ by
\[
d_{x,\rho}(\bar u,u):= \rho^{|u|}d_{x}(\bar u,u),\qquad
d_{\mu,\rho
}(\bar u,u):= \rho^{|u|}d_{\mu}(\bar u,u),
\]
in the finite and infinite case, respectively. Of course, with $\rho=1$
the subtree size metric reappears.

\begin{theorem}\label{thm:Hconv}
Let $\rho_0=1.26107\cdots$ be the smaller of the two roots of the
equation $ 2e\log(\rho)=\rho$, $\rho>0$.
Let $X_n$, $n\in\bN$ and $X_\infty$ be as in Theorem \ref{thm:DMconv}.
\begin{longlist}[(a)]
\item[(a)] For $\rho<\rho_0$, the metric space $(\bV,d_{X_\infty
,\rho
})$ is compact with probability 1.

\item[(b)] For $\rho> \rho_0$, the metric space $(\bV,d_{X_\infty
,\rho
})$ has infinite diameter with probability 1.

\item[(c)] For $\rho<\rho_0$, the metric spaces $(X_n,d_{X_n,\rho})$
converge uniformly to\break  $(\bV,d_{X_\infty,\rho})$
as $n\to\infty$ in the sense of
\begin{equation}
\label{eq:supconv}  \sup_{u,v\in X_n} \bigl| d_{X_n,\rho
}(u,v)-d_{X_\infty,\rho}(u,v)
\bigr| \to0 \qquad\mbox{ almost surely and in mean}.\hspace*{-35pt}
\end{equation}

\item[(d)] For $\rho> \rho_0$, and with $ d_{X_n,\rho}(\bar u,u):=0$
for $u\notin X_n$,
\[
\sup_{u,v\in\bV} \bigl| d_{X_n,\rho}(u,v)-d_{X_\infty,\rho}(u,v) \bigr| =
\infty\qquad\mbox{with probability 1}.
\]
\end{longlist}
\end{theorem}

\begin{pf}
We embed the metric trees into the linear space $\bL(0)$ of all
functions $f\dvtx\bV\setminus\{\varnothing\}\to\bR$ via
\[
x \mapsto f:= \bigl(u\mapsto d_x(\bar u,u) \bigr),\qquad  x\in\bB;
\]
probability measures $\mu$ on $(\bar\bV,\cB(\bar\bV))$ become elements
of $\bL(0)$ by identifying~$\mu$ with the function $u\mapsto\mu(A_u)$. In particular, we now
write $X_\infty(u)$ instead of $X_\infty(A_u)$.
For $\rho\ge1$ let $\bL(\rho)$ be the set of all $f\in\bL(0)$ with
\[
\|f\|_\rho:= \sum_{k=1}^\infty
\rho^k \max_{|u|=k} \bigl|f(u)\bigr| < \infty.
\]
Clearly, this gives a family of nested separable Banach spaces, with
\[
\bB\hookrightarrow\bL(\gamma)\subset\bL(\rho)\subset\bL(0) \qquad\mbox{for } 1\le
\rho<\gamma.
\]
We now show that, with the above identification,
\begin{eqnarray}
E \|X_\infty\|_\rho&< & \infty\qquad\mbox{if } \rho<
\rho_0, \label{eq:XinfinL1}
\\
P \Bigl( \sup_{u\in\bV} \rho^{|u|} X_\infty(u)=
\infty \Bigr) &= & 1 \qquad\mbox{if } \rho>\rho_0 \label{eq:XinfinL2}
\end{eqnarray}
and that, for $\rho<\rho_0$ and as $n\to\infty$,
\begin{equation}
\label{eq:liminL} \|X_n-X_\infty\|_\rho\to0 \qquad\mbox{almost surely and in mean.}
\end{equation}
Clearly, \eqref{eq:XinfinL1} implies that $X_\infty\in\bL(\rho)$ with
probability 1 if $\rho<\rho_0$.

The basis for our proof of \eqref{eq:XinfinL1} and \eqref{eq:XinfinL2}
is the connection of BST trees to branching
random walks, a connection that has previously been used by several
authors, especially for the analysis of the height
of search trees; see the survey \cite{DevGelbesBuch} and the references
given there. Let $u(k,j)$, $j=1,\ldots,2^k$, be
a numbering of the nodes from $\bV_k$ such that
\[
\beta \bigl(u(k,1) \bigr)<\beta \bigl(u(k,2) \bigr)<\cdots< \beta \bigl(u
\bigl(k,2^k \bigr) \bigr),
\]
with $\beta$ as defined in \eqref{eq:defbeta}. The key observation is
that the variables
\[
Y_{k,j}:= -\log X_\infty \bigl(u(k,j) \bigr), \qquad j=1,
\ldots,2^k,
\]
are the positions of the members of the $k$th generation in a branching
random walk
with offspring distribution $\delta_2$ and with
\[
Z:= \delta_{-\log\xi} +\delta_{-\log(1-\xi)},\qquad  \cL(\xi)=\unif(0,1)
\]
for the point process of the positions of the children relative to
their parent. Biggins~\cite{Biggins}
obtained several general results for such processes that we now
specialize to the present
offspring distribution and point process of relative positions. Let
\[
m(\theta):= E \biggl(\int e^{-\theta t} Z(dt) \biggr) = \frac
{2}{1+\theta}
\]
and
\begin{equation}
\label{eq:mudef} \tilde m(a):= \inf \bigl\{e^{\theta a} m(\theta )\dvtx\theta
\ge0 \bigr\} = 2ae^{1-a}.
\end{equation}
Note that
\begin{equation}
\label{eq:thetaopt} \tilde m(a) = m \bigl(\theta(a) \bigr)\qquad \mbox{with } \theta(a)=
\frac{1}{a}-1,
\end{equation}
and that, by definition of $\rho_0$,
\begin{equation}
\label{eq:rho2a} \rho<\rho_0\quad \Longleftrightarrow\quad \tilde m(\log\rho)<1.
\end{equation}
Finally, let $Z^{(k)}(t)$ be the number of particles in generation $k$
that are located to the left of $t$.

Now suppose that $\rho<\rho_0$. Let $\alpha:=(\rho+\rho_0)/2$ and
$\eta
:=\log(\alpha)$.
We adapt the upper bound argument in \cite{Biggins} to our present
needs: For all $\theta>0$
and $C > 1$, with $\gamma:=\log(C)$,
\begin{eqnarray*}
P \Bigl(\alpha^{k} \max_{|u|=k} X_\infty(u)>C
\Bigr) &=& P \Bigl( \min_{1\le j \le2^k} Y_{k,j} \le k\eta-\gamma
\Bigr)
\\
&\le& EZ^{(k)} \biggl(k \biggl(\eta-\frac{\gamma}{k} \biggr) \biggr)
\\
&\le&\exp \biggl(k \biggl(\eta-\frac{\gamma}{k} \biggr)\theta \biggr) m(
\theta)^k
\\
&=& C^{-\theta} \bigl(e^{\eta\theta}m(\theta) \bigr)^k.
\end{eqnarray*}
By \eqref{eq:rho2a}, $\tilde m(\eta)<1$. Choosing the optimal $\theta
=\theta(\eta)$, which
with \eqref{eq:thetaopt} is easily seen to be greater than $1$, leads to
\begin{eqnarray*}
E \Bigl(\alpha^{k} \max_{|u|=k} X_\infty(u)
\Bigr) &\le&1 + \int_1^\infty P \Bigl(
\alpha^{k} \max_{|u|=k} X_\infty(u)>x \Bigr)
\,dx
\\
&\le&1 + \tilde m(\eta)^k \int_1^\infty
x^{-\theta(\eta)} \,dx \le c,
\end{eqnarray*}
with a finite constant $c$ that does not depend on $k$. Hence
\[
\sum_{k=1}^\infty\rho^k E \Bigl(
\max_{|u|=k} X_\infty(u) \Bigr) \le c \sum
_{k=1}^\infty \biggl(\frac{\rho}{\alpha}
\biggr)^k < \infty,
\]
which in turn implies \eqref{eq:XinfinL1} by monotone convergence.

Suppose now that $\rho>\rho_0$, so that $\tilde m(\eta)>1$ by \eqref
{eq:rho2a} for $\eta:=\log\rho$.
By \cite{Biggins}, Theorem 2,
\[
\lim_{k\to\infty}\frac{1}{k} \log \bigl(\# \bigl\{1\le j
\le2^k\dvtx Y_{k,j}\le k \eta \bigr\} \bigr) = \log\tilde m(
\eta) > 0
\]
with probability 1. In particular, and again with probability 1,
\[
\exists k_0\ \forall k\ge k_0\ \exists u\in
\bV_k\qquad -\log X_\infty(u)\le k \log\rho.
\]
Clearly, this implies \eqref{eq:XinfinL2}.

For the proof of \eqref{eq:liminL} we first consider the random
variables $\sigma(X_n,u)$, $n\in\bN$, for some fixed
$u\in\bV$. We wish to relate these to $E[X_\infty(u)|\cF_n]$, with
$\cF
_n$ as in \eqref{eq:natFilt}. For this, we use
the representation of $X_\infty$ in terms of $(\xi_u)_{u\in\bV}$ given
in Section~\ref{subsec:DM}, together with
Proposition \ref{prop:conddistrnodes}. We may assume that $k:=|u|>0$.

The representation \eqref{eq:prodXinfty}, the conditional independence
of the $\tilde\xi$-variables given~$\cF_n$, and
the well-known formula for the first moment of beta distributions
together lead to
\[
E \bigl[X_\infty(u)|\cF_n \bigr] = \prod
_{j=0}^{k-1}E[\tilde\xi_{u(j)}|
\cF_n] = \prod_{j=0}^{k-1}
\frac{\sigma(X_n,u(j+1))+1}{\sigma(X_n,u(j)0) +
\sigma(X_n,u(j)1)+2}.
\]
In view of
\[
\sigma(x,u0)+ \sigma(x,u1)+1 =
\cases{ \sigma(x,u), &\quad $\mbox{if } u
\in x$, \vspace*{2pt}
\cr
1, &\quad $\mbox{if } u\notin x$,}
\]
the product telescopes to
\begin{equation}
\label{eq:telescprod2} E \bigl[X_\infty(u)|\cF_n \bigr] =
\frac{\sigma(X_n, u) +1}{n+1}\qquad \mbox{for all } u\in X_n.
\end{equation}
We now introduce
\[
Z_n\dvtx\bV\to\bR,\qquad  u\mapsto E \bigl[X_\infty(u)|
\cF_n \bigr].
\]
Then $(Z_n,\cF_n)_{n\in\bN}$ is a vector-valued martingale. For
$\rho
<\rho_0$ we have by part (a) of the theorem that
$X_\infty\in\bL(\rho)$ with probability 1 and that $E\|X_\infty\|
_\rho
<\infty$, hence $ Z_n\to X_\infty$ almost surely
and in mean in $\bL(\rho)$ by Proposition V-2-6 in \cite{NeveuMart}.

In our present representation of trees as functions on $\bV$ we have
\[
X_n(u) =
\cases{ \displaystyle\frac{n+1}{n} Z_n(u)-
\frac{1}{n}, &\quad $\mbox{if } u\in X_n$,\vspace*{2pt}
\cr
0, &\quad $
\mbox{if } u\notin X_n$,}
\]
which implies that $0\le X_n\le(1+n^{-1})Z_n$ for all $n\in\bN$. As
$X_n\to X_\infty$ pointwise with probability 1 by
Theorem \ref{thm:DMconv}
we can now use a suitable version of the dominated convergence theorem,
such as that given in \cite{Kall}, Theorem 1.21,
to obtain that $X_n$ converges to $X_\infty$ in $\bL(\rho)$ as $n\to
\infty$, again almost surely and in mean.

It remains to show that the tree statements in the theorem follow from
the linear space statements \eqref{eq:XinfinL1},
\eqref{eq:XinfinL2} and \eqref{eq:liminL}.

For (a) we prove that the limiting metric space is totally bounded.
From \eqref{eq:XinfinL1} and the definition of the
norm we obtain for any given $\varepsilon>0$ a $k=k(\varepsilon)\in
\bN$ such that
\[
\sum_{j=k}^\infty\rho^j \max
_{|u|=j} X_\infty(u) < \varepsilon,
\]
which by the definition of the weighted subtree size metric means that
all nodes $v$ with
$|v|\ge k$ have a distance from their predecessor at level $k$ that is
less than $\varepsilon$. As there are only
finitely many nodes of level less than $k$ this shows that the whole of
$\bar\bV$ may be covered by a finite
number of $\varepsilon$-balls. Of course, this argument is meant to be
applied to each element of a suitable set
of probability 1 separately.

For (b) we simply note that \eqref{eq:XinfinL2} implies that, with
probability 1,
\[
\sup_{u\in\bV,u\neq\varnothing} d_{X_\infty,\rho}(\bar u,u)=\infty
\]
if $\rho>\rho_0$. This also gives (d).\vadjust{\goodbreak}

Finally, for all $u\in\bV$, $u\neq\varnothing$,
\begin{eqnarray*}
\bigl| d_{X_n,\rho}(u,\varnothing)-d_{X_\infty,\rho}(u,\varnothing)\bigr | &\le&\sum
_{\varnothing\neq v\le u} \bigl| d_{X_n,\rho}(\bar v,v)-d_{X_\infty,\rho}(
\bar v,v) \bigr|
\\
&\le&\sum_{k=1}^{|u|} \rho^k \max
_{|v|=k} \bigl|X_n(v)-X_{\infty} (v)\bigr |
\\
&\le&\|X_n-X_\infty\|_\rho.
\end{eqnarray*}
The upper bound does not depend on $u$, hence (c) follows on
using \eqref{eq:distviamin}.
\end{pf}

We note that the convergence of metric trees considered in Theorem \ref
{thm:Hconv} implies the convergence with respect
to the Gromov--Hausdorff distance of the corresponding equivalence
classes of metric trees; see \cite{Burago}, Section~7.3.3.

\begin{figure}

\includegraphics{948f01.eps}

\caption{The metric tree for the odd (upper part) and even (lower part)
$\pi$-data,
for $n=50$ (left) and $n=100$ (right), respectively; see text for
details.}\label{fig:pitrees}
\end{figure}

The subtree size metric also leads to a visualization of search trees:
We use the function $\beta$ defined
in \eqref{eq:defbeta} to map nodes to points in the unit interval, and
above the $x$-coordinate $\beta(u)$ we draw a
line parallel to the $y$-axis from $d_{X_n}(\bar u,\varnothing)$ to
$d_{X_n}(u,\varnothing)$. In order to obtain a visually
more pleasing result we may add lines that run parallel to the
$x$-axis, connecting nodes with the same parent. In
Figure~\ref{fig:pitrees} we have carried this out for the trees arising
from two separate input sequences for the BST
algorithm, with the data obtained from alternating blocks of length 10
of digits in the decimal expansion of
$\pi-3$. The upper part refers to the odd and the lower to the even
numbered blocks. In both cases we have given the trees
for $n=50$ and $n=100$, and with $\rho=1$. Vertically, the trees are
from the same distribution; moving horizontally to
the right, we have almost sure convergence.

\section{Tree functionals}\label{sec:application}
In this section we show how the above results can be used in connection
with the asymptotic analysis of tree functionals. Here is the recipe:
We start with a functional $Y_n=\Psi _n(X_n)$ of the trees, with
(deterministic) functions $\Psi_n$ on $\bB_n$ that have values in some
separable Banach space $(\bL,\|\cdot\|)$. We suspect that $Y_n$
converges almost surely to some limit variable $Y_\infty$ as $n\to
\infty $. We know that if this is the case, then
$Y_\infty=\Psi(X_\infty)$ for some $\Psi$ defined on $\partial\bB $ (as
always, almost surely). We do not know what $\Psi$ is, but if we manage
to rewrite the $\Psi_n$'s in terms of subtree sizes, then Theorem
\ref{thm:DMconv} may lead to an educated guess. On that basis we next
consider $\Phi_n(X_n)=E[\Psi(X_\infty)|\cF_n]$, assuming that $E\|\Psi
(X_\infty )\|<\infty$. This gives an $\bL$-valued martingale. By the
associated convergence theorem we then have that $\tilde
Y_n:=\Phi_n(X_n)$ converges to $Y_\infty$ almost surely and in mean.
Finally, a simple inspection of $\Phi _n-\Psi _n$ may reveal that
$\tilde Y_n-Y_n$ is asymptotically negligible---indeed, if $Y_n$
converges to $Y_\infty$, then $\tilde Y_n-Y_n$ \emph{must} tend to 0.

In the first three subsections we work out the details of the above
strategy for path lengths, for a tree index and for
an infinite dimensional tree functional. The final subsection is a
collection of remarks on other functionals and
related tree structures, indicating further applications of the method,
but also its limitations. The potential-theoretic
approach can provide additional insight; for example, we will relate a
martingale introduced in connection with tree
profiles to Doob's $h$-transform.

Throughout this section we abbreviate $X_\infty(A_u)$ to
$X_\infty(u)$.\newpage

\subsection{Path length}\label{subsec:PL}
The first tree functional we consider is the \emph{internal path length},
\begin{equation}
\label{eq:IPLa} \IPL(x):=\sum_{u\in x} |u|, \qquad x\in\bB,
\end{equation}
which may be rewritten as
\begin{equation}
\label{eq:IPLb} \IPL(x) =\sum_{u\in x,u\neq\varnothing} \sigma (x,u) =
\sum_{u\in x} \sigma(x,u) - \# x.
\end{equation}
Let
\[
H(0):=0,\qquad  H(n):=\sum_{i=1}^n
\frac{1}{i}\qquad \mbox{for all } n\in\bN,
\]
be the harmonic numbers. It is well known that
\[
\lim_{n\to\infty} \bigl( H(n) - \log n \bigr) =\gamma,
\]
where $\gamma\approx0.57722$ is Euler's constant.
We need two auxiliary statements; we omit the (easy) proofs.

\begin{lemma}\label{lem:intformula}
For all $i,j\in\bN_0$,
\[
\frac{\Gamma(i+j+2)}{\Gamma(i+1)\Gamma(j+1)}\int_0^1
x^i(1-x)^j \log(x) \,dx = H(i)-H(i+j+1).
\]
\end{lemma}

For a random variable
$\eta$ with distribution $\Beta(i+1,j+1)$ Lemma \ref{lem:intformula}
leads to
\begin{equation}
\label{eq:expxlogx} E \bigl(\eta\log(\eta) \bigr) = \frac
{i+1}{i+j+2} \bigl(H(i+1) -
H(i+j+2) \bigr).
\end{equation}
The next lemma is a summation by parts formula for binary trees.

\begin{lemma}\label{lem:telescope}
For any function $\psi:\bV\to\bR$,
\[
\sum_{u\in x} \bigl(\psi(u)-\psi(u0)-\psi(u1) \bigr) =
\psi(\varnothing) - \sum_{u\in\partial x} \psi(u) \qquad\mbox{for all
} x \in\bB.
\]
\end{lemma}

Major parts of the following theorem are known; we will give details
later in order to be able to
refer to the proof for a comparison of the methods used. Let
$(X_n)_{n\in\bN}$ be the BST chain, and
let $X_\infty$ be its limit, as in Theorem~\ref{thm:Hconv}.

\begin{theorem}\label{thm:IPL}
Let $C\dvtx(0,1)\to\bR$ be defined by
\[
C(s):= 1 + 2 \bigl( s\log(s) + (1-s)\log(1-s) \bigr).\vspace*{-9pt}
\]
\begin{longlist}[(a)]
\item[(a)] The limit
\[
Y_\infty:= \sum_{u\in\bV}X_\infty(u) C
\biggl(\frac{X_\infty
(u0)}{X_\infty(u)} \biggr)
\]
exists almost surely and in quadratic mean.

\item[(b)] As $n\to\infty$,
\begin{equation}
\label{eq:convIPL} \frac{1}{n} \IPL(X_n)-2\log n \to2\gamma- 4 +
Y_\infty,
\end{equation}
almost surely and in quadratic mean.
\end{longlist}
\end{theorem}

\begin{pf}
From the representation of $X_\infty$ given in Section~\ref{subsec:DM}, we know that the random variables
\[
\xi_u:=\frac{X_\infty(u0)}{X_\infty(u)},\qquad  u\in\bV,
\]
are independent and uniformly distributed on the unit interval, and
that $X_\infty(u)$ is a function of the $\xi_v$'s
with $v<u$. In particular, for all nodes $u$, the two factors in the
sum appearing in the definition of $Y_\infty$ are
independent. Let $\cG_k$ be the $\sigma$-field generated by the $\xi
_u$'s with $|u|\le k$, and put
\[
Y_k:= \sum_{u\in\bV, |u|\le k} X_\infty(u) C
\biggl(\frac
{X_\infty(u0)}{X_\infty(u)} \biggr),\qquad  k\in\bN.
\]
Then these properties lead to
\begin{eqnarray*}
E[Y_{k+1}| \cG_k] &=& Y_k + E \biggl[ \sum
_{|u|=k+1}X_\infty(u) C \biggl(\frac{X_\infty(u0)}{X_\infty(u)}
\biggr)\Big | \cG_k \biggr]
\\
&=& Y_k + \sum_{|u|= k+1} X_\infty(u)
EC(\xi_u)
\\
&=& Y_k,
\end{eqnarray*}
where we have used the fact that $EC(\xi_u)=0$. Further, with the same
arguments,
\begin{eqnarray*}
E \bigl[(Y_{k+1}-Y_k)^2| \cG_k
\bigr] &= &E \biggl[ \biggl( \sum_{|u|=k+1}
X_\infty(u) C(\xi_u) \biggr)^2 \Big|
\cG_k \biggr]
\\
&=& \sum_{|u|=k+1} X_\infty(u)^2 EC(
\xi_u)^2,
\end{eqnarray*}
so that
\[
E(Y_{k+1}-Y_k)^2 = \sum
_{|u|=k+1} EX_\infty(u)^2 EC(
\xi_u)^2.
\]
We also have $\kappa:=EC(\xi_u)^2<\infty$, and using \eqref
{eq:prodXinfty} we get
\[
EX_\infty(u)^2 = \bigl(E\xi_\varnothing^2
\bigr)^k = 3^{-k},
\]
so that
\begin{equation}
\label{eq:tailY} E(Y_{k+1}-Y_k)^2 =
2^k3^{-k} \kappa\qquad\mbox{for all } k\in\bN.
\end{equation}
Taken together these calculations show that $(Y_k,\cG_k)_{k\in\bN}$ is
an $L^2$-bounded martingale,
and an appeal to the corresponding martingale limit theorem completes
the proof of (a).
In particular, $Y_\infty$ is well defined, and even has finite second moment.

For the proof of (b) let $Z_n:=E[Y_\infty|\cF_n]$,
$n\in\bN$, so that $(Z_n,\cF_n)_{n\in\bN}$ is again a martingale
bounded in $L^2$. Our plan is to show that $Z_n$ is
sufficiently close to the transformed internal path length that appears
in \eqref{eq:convIPL}.

Using again the stochastic structure of $X_\infty$ we are thus led to
consider the conditional expectations
$E[X_\infty(u)|\cF_n]$ and $E[ C(\xi_u)|\cF_n]$, $u\in\bV$ and
$n\in\bN
$. From Proposition \ref{prop:conddistrnodes} we
know that, for all $u\in X_n$,
\[
\cL(\xi_u|\cF_n) = \Beta \bigl(\sigma(X_n,u0)+1,
\sigma(X_n,u1)+1 \bigr) ,
\]
and that the $\xi_u$'s are conditionally independent given $\cF_n$.
Hence Lemma \ref{lem:intformula}
can be applied [see also \eqref{eq:expxlogx}], resulting in
\begin{eqnarray}
\label{eq:condexpC}
E \bigl[C(\xi_u)|\cF_n
\bigr] &=& 1 + \frac{2\tau(X_n,u0)+2\tau
(X_n,u1)}{\sigma(X_n,u0)+\sigma(X_n,u1)+2}
\nonumber
\\[-8pt]
\\[-8pt]
\nonumber
&&{}-2 H \bigl(\sigma(X_n,u0)+\sigma(X_n,u1)+2
\bigr),
\end{eqnarray}
where the function $\tau:\bB\times\bV\to\bR$ is given by
\[
\tau(x,u):= \bigl(\sigma(x,u)+1 \bigr) H \bigl(\sigma(x,u)+1 \bigr).
\]
For each fixed $n\in\bN$, almost sure convergence of $E[Y_k|\cF_n]$ to
$E[Y_\infty|\cF_n]$ as $k\to\infty$ follows
from
\[
\bigl\| E[Y_k|\cF_n]-E[Y_\infty|\cF_n]
\bigr\|_2 \le\| Y_k-Y_\infty \|_2,
\]
the upper bound in \eqref{eq:tailY} and the Borel--Cantelli lemma.
Together with the conditional independence of $X_\infty(u)$ and $C(\xi
_u)$ given $\cF_n$, this leads to
\begin{equation}
\label{eq:sumrepr} Z_n = \sum_{u\in\bV} E
\bigl[X_\infty(u) |\cF_n \bigr] E \bigl[C(\xi_u)|
\cF_n \bigr].
\end{equation}
From \eqref{eq:condexpC} we obtain $E[C(\xi_u)|\cF_n]=0$ for
$u\notin
X_n$, and, clearly,
\begin{equation}
\label{eq:splitnodes} \sigma(X_n,u0) + \sigma(X_n,u1) +1 =
\sigma(X_n,u)\qquad \mbox{for all } u\in X_n.
\end{equation}
Taken together, \eqref{eq:telescprod2}, \eqref{eq:condexpC}, \eqref
{eq:sumrepr} and \eqref{eq:splitnodes}
lead to
\[
Z_n = \sum_{u\in X_n}\frac{\sigma(X_n,u)+1}{n+1}
\biggl(1 + \frac{2\tau(X_n,u0)+2\tau(X_n,u1)}{\sigma(X_n,u)+1} -2 H \bigl(\sigma(X_n,u)+1 \bigr)
\biggr),
\]
which in turn gives
\[
Z_n = \frac{1}{n+1} \bigl(\IPL(X_n)+2n \bigr) -
\frac{2}{n+1} \sum_{u\in X_n} \bigl(
\tau(X_n,u)-\tau(X_n,u0)-\tau(X_n,u1) \bigr).
\]
Lemma \ref{lem:telescope} can be applied to the second sum, and the
assertion finally follows from
$\tau(X_n,\varnothing)=(n+1)H(n+1)$ and $\tau(X_n,u)=1$ for $u\in
\partial X_n$.
\end{pf}

Almost sure convergence of the standardized internal path length for
the BST sequence has been obtained
in \cite{RegnierQS}, and convergence in distribution, together with a
fixed point relation for the limit distribution,
in \cite{RoeQS}. Our method may been seen as an amalgamation of R\'
egnier's martingale approach and R\"osler's
approach, where the latter has come to be known as the contraction
method in the analysis of algorithms: We obtain
a strong limit, but we do not need to ``find the martingale'' (a task
familiar to many an applied probabilist).
The approach suggested in the present paper, to look at convergence of
the full objects via a suitable
completion of the state space of the underlying combinatorial Markov
chain, leads to a representation of the almost sure
limit. This gives the martingale by projection via conditional
expectations, and from the representation one can also read
off a fixed point relation for the distribution of the limit.

\subsection{The Wiener index}\label{subsec:WI}
The canonical graph distance $d_{\mathrm{can}} (u,v)$ of any two
nodes $u$ and $v$ in a finite connected graph $G$
with node set $V$ is the minimum length of a path (sequence of edges)
that connects $u$ and $v$ in $G$. The sum of these
distances is the \emph{Wiener index} of the graph,
\begin{equation}
\label{eq:WI} \WI(G):= \frac{1}{2}\sum_{(u,v)\in V\times V}
d_{\mathrm{can}} (u,v),
\end{equation}
introduced by the chemist H. Wiener. Some background together with
pointers to the literature is given in \cite{Nein02},
which is also our main reference in this subsection. Among other
results it is shown in \cite{Nein02} that for the BST
sequence $(X_n)_{n\in\bN}$ the rescaled Wiener indices,
\[
W_n:= \frac{1}{n^2} \WI(X_n) -2\log n,
\]
converge in distribution as $n\to\infty$.

Again, we project a suitable functional $\Psi(X_\infty)$ of the limit
tree $X_\infty$ to a function
$E[\Psi(X_\infty)|\cF_n]$ of $X_n$ that is sufficiently close to $W_n$.
This will give a strong limit theorem,
that is, it turns out that the rescaled Wiener indices in fact converge
almost surely for the random binary trees generated
by the BST algorithm for i.i.d. input, and it will also lead to a
representation of the limit $W_\infty$ as a function
of $X_\infty$.

We begin by rewriting the Wiener index in terms of subtree sizes,
similar to the transition from \eqref{eq:IPLa}
to \eqref{eq:IPLb} in the analysis of the internal path length. For a
binary tree $x$,
\begin{equation}
\label{eq:WIa} \sum_{(u,v)\in x\times x} |u\wedge v| = \sum
_{u\in x} \sigma(x,u)^2.
\end{equation}
This may be proved by induction, using the left and right subtrees in
the induction step;
see \cite{DennDiss}, page 70. Using \eqref{eq:distviamin}, \eqref
{eq:IPLb}, \eqref{eq:WI} and \eqref{eq:WIa}
we now obtain
\begin{equation}
\label{eq:WIrepr} \WI(X_n) = n \IPL(X_n) + n^2
- \sum_{u\in X_n} \sigma(X_n,u)^2.
\end{equation}
It is a benefit of working with
almost sure convergence that we can deal with the constituents on the
right-hand side of \eqref{eq:WIrepr}
separately (which means that we can make use of Theorem \ref{thm:IPL}),
whereas in connection with convergence
in distribution one needs to consider the joint distribution of $\IPL
(X_n)$ and $\WI(X_n)$; see \cite{Nein02}.

\begin{theorem}\label{thm:WI}
The series
\begin{equation}
\label{eq:defYinfty} Z_\infty:= \sum_{u\in\bV}X_\infty(u)^2
\end{equation}
converges almost surely and in quadratic mean, and, as $n\to\infty$,
\begin{equation}
\label{eq:thmWI} \frac{1}{n^2} \WI(X_n) -2\log n \to
W_\infty
\end{equation}
again almost surely and in quadratic mean, where the limit is given by
\begin{equation}
\label{eq:thmWIrepr} W_\infty:= 2\gamma-3 + Y_\infty-
Z_\infty,
\end{equation}
with $Y_\infty$ as in Theorem \ref{thm:IPL}.
\end{theorem}

\begin{pf}
Almost sure convergence in \eqref{eq:defYinfty} follows with
Theorem \ref{thm:Hconv}, and the moment calculations below
show that $EZ_\infty^2<\infty$. In particular,
\[
Z_n:= E[Z_\infty|\cF_n] \to Z_\infty
\]
almost surely and in quadratic mean. Again, the Markov property implies
that $Z_n$ can be written as a function of
$X_n$. In order to obtain this function we first consider a fixed node
$u\in\bV$.

From \eqref{eq:prodXinfty} we get
\[
X_\infty(u)^2 = \prod_{j=0}^{k-1}
\tilde\xi_{u(j)}^{ 2}.
\]
From \eqref{eq:nodeBeta} and the known formula for the second moment of
beta distributions we obtain,
considering the cases $u(j+1)=u(j)0$ and $u(j+1)=u(j)1$ separately,
\begin{eqnarray*}
&& E \bigl[\tilde\xi_{u(j)}^{ 2}|\cF_n \bigr]\\
&&\qquad =
\frac{(\sigma(X_n, u(j+1)) +1) (\sigma(X_n, u(j+1)) +2)} {
(\sigma(X_n, u(j)0) +\sigma(X_n, u(j)1) +2) (\sigma(X_n, u(j)0)
+\sigma(X_n, u(j)1) +3) }.
\end{eqnarray*}
Using the conditional independence statement in Proposition \ref
{prop:conddistrnodes}, we see that we have a
telescoping product again, so that
\[
E \bigl[X_\infty(u)^2|\cF_n \bigr] =
\frac{(\sigma(X_n, u) +1) (\sigma(X_n, u) +2)}{(n+1)(n+2)}
\qquad\mbox{for all } u\in X_n\cup\partial
X_n.
\]
The set $\bV\setminus X_n$ can be written as the disjoint union of the
subtrees rooted at the $n+1$ external nodes
of $X_n$, and we have
\[
E \bigl[\xi_u^2|\cF_n \bigr] = E \bigl[(1-
\xi_u)^2|\cF_n \bigr] = \tfrac{1}{3}\qquad
\mbox{for all } u\notin X_n.
\]
Therefore,
\begin{eqnarray*}
&&\sum_{u\notin X_n} E \bigl[X_\infty(u)^2|
\cF_n \bigr]
\\
&&\qquad= \frac{1}{(n+1)(n+2)}\sum_{u\in\partial X_n} \bigl(\sigma
(X_n,u)+1 \bigr) \bigl(\sigma(X_n,u)+2 \bigr) \sum
_{v\in\bV,v\ge u} \biggl(\frac{1}{3}
\biggr)^{|v|-|u|}
\\
&&\qquad= \frac{2}{(n+1)(n+2)}\sum_{u\in\partial X_n} \sum
_{k=0}^\infty2^k \biggl(\frac{1}{3}
\biggr)^k
\\
&&\qquad= \frac{6}{n+2}
\end{eqnarray*}
in view of $\sigma(X_n,u)=0$ for $u\in\partial X_n$. Taken together
this gives
\[
Z_n = \frac{1}{(n+1)(n+2)}\sum_{u\in X_n}
\bigl(\sigma(X_n,u)+1 \bigr) \bigl(\sigma(X_n,u)+2 \bigr)
+ \frac{6}{n+2}.
\]
Using \eqref{eq:IPLb} we get
\[
\sum_{u\in X_n} \bigl(\sigma(X_n,u)+1 \bigr)
\bigl(\sigma(X_n,u)+2 \bigr) = \sum_{u\in X_n}
\sigma(X_n,u)^2 + 3\cdot\IPL(X_n) + 5n
\]
so that, with \eqref{eq:WIrepr},
\[
\frac{1}{(n+1)(n+2)} \WI(X_n) = \frac{n}{(n+1)(n+2)} \IPL
(X_n) + \frac{n^2}{(n+1)(n+2)} - Z_n + R_n,
\]
where $R_n$ tends to 0 almost surely and in quadratic mean. From
Theorem \ref{thm:IPL} we know that
\[
\frac{1}{n} \IPL(X_n) - 2\log n \to2\gamma- 4 +
Y_\infty
\]
in the same sense. Combining the last two statements we obtain \eqref
{eq:thmWI}, with $W_\infty$ as in \eqref{eq:thmWIrepr}.
\end{pf}

\subsection{Metric silhouette}
In our third application we consider an infinite-dimensional tree functional.

Each element $v=(v_k)_{k\in\bN}$ of $\partial\bV$ defines a path
through a binary tree via the sequence
$(v(k))_{k\in\bN}$ of nodes given by $v(k)=(v_1,\ldots,v_k)$, $k\in
\bN
$. In \cite{GrSilh} the ``silhouette''
$\Sil(x)$ of $x\in\bB$ was introduced in an attempt to obtain a search
tree analogue of the famous Harris encoding of
simply generated trees: with each path $v$, we record its exit level
when passing through $x$, that is,
\[
\Sil(x) (v):= \min \bigl\{k\in\bN: v(k)\notin x \bigr\}, \qquad v\in \partial\bV.
\]
The tree silhouette can be visualized as a function on the unit
interval via the binary expansion
\begin{equation}
\label{eq:Phidef} \Phi\dvtx[0,1)\to\partial\bV, \qquad t\mapsto (v_k)_{k\in\bN}
\qquad\mbox{with } v_k:= \bigl\lceil2^{k+1}t \bigr\rceil- 2 \bigl
\lceil2^{k}t \bigr\rceil.
\end{equation}
It was shown in \cite{GrSilh} that for the BST chain $(X_n)_{n\in\bN}$
some smoothing is necessary to obtain an
interesting limit for the stochastic processes\break  $ (\Sil(X_n)(\Phi
(t)) )_{0\le t<1}$ as $n\to\infty$.

We have seen in the previous sections that for search trees it makes
sense to replace the canonical tree distance
implicit in the above definition of $\Sil(x)$ by the subtree size
metric. A corresponding variant
of the silhouette is the \emph{metric silhouette},
\[
\mSil(x) (v):= \sum_{k=1}^\infty\sigma
\bigl(x,v(k) \bigr),\qquad  v\in\partial\bV.
\]
Again, our aim is to obtain a strong limit theorem in the BST
situation, together with a representation of the limit as
a function of $X_\infty$. In addition, and going beyond the individual
arguments $v\in\partial\bV$, we regard
$\mSil(X_n)$ as a random function on $\partial\bV$. With $d_{\bV}$ as
in \eqref{eq:defdV} this is a compact and separable
metric space ($\bV$ is open in the completion $\bar\bV$ that we
introduced in Section~\ref{subsec:DM}). We write
$C(\partial\bV,d_{\bV})$ for the space of continuous functions
$f\dvtx\partial\bV\to\bR$. Together with
\[
\| f\|_\infty:= \sup_{v\in\partial\bV}\bigl |f(v)\bigr|,
\]
this is a separable Banach space.

Remember that the values of $X_\infty$ are probability measures on
$(\partial\bV,\cB(\partial\bV))$. Let
$\Sigma_\infty:\partial\bV\to[0,\infty]$ be defined by
\[
\Sigma_\infty(v):= -\int_{\partial\bV} \log_2
\bigl(d_{\bV}(u,v) \bigr) X_\infty(du),\qquad  v\in\partial\bV.
\]
This is the logarithmic potential of the random measure $X_\infty$ with
respect to $d_{\bV}$; see \cite{Woess1}, page 62.
Finally, we recall that a real function $f$ on the metric space
$(\partial\bV,d_{\bV})$ is said to be (globally) H\"older
continuous with exponent $\alpha$ if there exists a constant $C<\infty$
such that
\[
\bigl|f(u)-f(v)\bigr| \le C d_{\bV}(u,v)^\alpha\qquad\mbox{for all }u,v\in
\partial\bV.
\]

\begin{theorem}\label{thm:mSil}
Let $\alpha_0:= \log_2\rho_0=0.33464\ldots$ with $\rho_0$ as in
Theorem \ref{thm:Hconv}.
\begin{longlist}[(a)]
\item[(a)] $E \|\Sigma_\infty\|_\infty<\infty$.
\item[(b)] With probability 1, $\Sigma_\infty$ is H\"older continuous
with exponent $\alpha$ for all $\alpha<\alpha_0$.
\item[(c)] As $n\to\infty$,
\[
\biggl\| \frac{1}{n} \mSil(X_n) - \Sigma_\infty
\biggr\|_\infty\to0 \qquad\mbox{almost surely and in mean}.
\]
\end{longlist}
\end{theorem}

\begin{pf}
Because of $d_\bV(u,v)=2^{-|u\wedge v|}$ for all $u,v\in\partial\bV
$ we
have\break  $-\log_2 d_\bV(u,v)\in\bN_0$ and
\[
-\log_2 d_\bV(u,v) \ge k\quad \Longleftrightarrow\quad u\in
A_{v(k)}
\]
for all $k\in\bN$ so that
\begin{equation}
\label{eq:Sigma} \Sigma_\infty(v) = \sum_{k=1}^\infty
X_\infty \bigl(v(k) \bigr) \qquad\mbox{for all } v\in\partial\bV.
\end{equation}

Now let $\alpha$ be as in the statement of the theorem; we may assume
that \mbox{$\alpha>0$}. Let $\rho:=2^\alpha$. By
Theorem \ref{thm:Hconv} there exists a set of probability 1 such that
for all~$\omega$ in this set,
$C(\omega):=\|X_\infty(\omega)\|_\rho< \infty$. We fix such an
$\omega
$ and drop it from the notation. Because of
$X_\infty(u)\le C\rho^{|u|}$ for all $u\in\bV$ and \eqref
{eq:Sigma}, we
then have
$\Sigma_\infty(v)\le C\sum_{k=1}^\infty\rho^{-k}$ for all $v\in
\partial
\bV$,
which implies
\[
\|\Sigma_\infty\|_\infty\le\frac{1}{\rho-1} \|
X_\infty\|_\rho.
\]
In particular, $E\|\Sigma_\infty\|_\infty<\infty$ by \eqref
{eq:XinfinL1} in the proof of Theorem \ref{thm:Hconv}.

Similarly, if $u,v\in\partial\bV$ are such that $|u\wedge v|=k$, then
\begin{eqnarray*}
\bigl| \Sigma_\infty(u)-\Sigma_\infty(v)\bigr | &=& \sum
_{j=k+1}^\infty X_\infty \bigl(u(j) \bigr) + \sum
_{j=k+1}^\infty X_\infty \bigl(v(j)
\bigr)
\\
&\le&2 C \sum_{j=k+1}^\infty
\rho^{-j} = \frac{2C\rho^{-k}}{\rho-1} \le\frac{2C}{\rho-1}
d_{\bV}(u,v)^\alpha
\end{eqnarray*}
by definition of $\rho$. This proves (b).

For the proof of (c) we first consider the random functions $\Sigma_n$
defined by
\[
\Sigma_n(v):= E \bigl[\Sigma_\infty(v)|\cF_n
\bigr],\qquad v\in\partial\bV.
\]
With $J:=\Sil(X_n)(v)$ we get, using monotone convergence
for conditional expectations and $\cF_n$-measurability of $J$,
\begin{eqnarray*}
\Sigma_n(v) &=& \sum_{k=1}^J E
\bigl[X_\infty \bigl(v(k) \bigr)|\cF_n \bigr] + \sum
_{k=J+1}^\infty E \bigl[X_\infty \bigl(v(k)
\bigr)| \cF_n \bigr]
\\
&= &\sum_{k=1}^J \frac{\sigma(X_n,v(k))+1}{n+1} +
\frac{\sigma(X_n,v(J))+1}{n+1} \sum_{k=J+1}^\infty \biggl(
\frac{1}{2} \biggr)^{k-J}
\\
&= &\frac{1}{n+1} \bigl( \mSil(X_n) (v)+J \bigr) +
\frac{1}{n+1}.
\end{eqnarray*}
Here we have used our formula \eqref{eq:telescprod2} for $E[\Sigma
_\infty(u)|\cF_n]$ and its extension
to nodes outside $X_n$ that can be obtained as in the proof of
Theorem \ref{thm:WI}.

Let $h(x)=\max\{|u|: u\in x\}$ be the height of $x\in\bB$. Taking the
supremum over $v\in\partial\bV$ we get
\[
\biggl\| \Sigma_n - \frac{1}{n+1} \mSil(X_n)
\biggr\|_\infty\le\frac{h(X_n)+1}{n+1}.
\]
It is easy to show that the right-hand side converges to 0 with
probability 1 (see \cite{Dev86} for techniques and
results on the height),
so it remains to prove that $\Sigma_n$ converges almost surely and in
mean to $\Sigma_\infty$ in the separable
Banach space $ (C(\partial\bV,d_{\bV}),\|\cdot\|_\infty)$.
This, however, is again immediate
from the vector-valued martingale convergence theorem given in
\cite{NeveuMart}, page 104.
\end{pf}

\begin{figure

\includegraphics{948f02.eps}

\caption{The metric silhouette for the odd (left) and even (right)
$\pi$-data,
with $n=50$ (blue) and $n=100$ (black).}
\label{fig:metrSilh}
\end{figure}

Figure~\ref{fig:metrSilh} shows the metric silhouette for the trees in
Figure~\ref{fig:pitrees}. Note that the
continuity in Theorem \ref{thm:mSil} refers to the space $(\partial
\bV
,d_{\bV})$; for example,
$(t_n)_{n\in\bN}$ with $t_n=\frac{1}{2}+(-1)^n\frac{1}{n}$ for all $n
\in\bN$ is a Cauchy sequence with respect to
euclidean distance, but its inverse under the function $\Phi$ defined
in \eqref{eq:Phidef} that we used for the
illustration is not a Cauchy sequence in $(\partial\bV,d_{\bV})$.
Loosely speaking, the function~$\beta$ ``flattens''
the node set $\bV$.

\subsection{Other functionals and tree structures}\label{subsec:otherfunc}
The fill (or saturation) level $F(x)$ and height $H(x)$ of a tree $x\in
\bB$ are defined by
\[
F(x)=\max \bigl\{k\in\bN_0\dvtx\{0,1\}^k\subset x \bigr
\}, \qquad H(x)=\max\bigl\{|u|: u\in x \bigr\},
\]
respectively. For these tree functionals, the following asymptotic
results are well known:
\begin{equation}
\label{eq:fillheightconstants} \frac{F(X_n)}{\log n}\to\alpha_-,\qquad
 \frac{H(X_n)}{\log n}\to\alpha_+\qquad
\mbox{as } n\to\infty,
\end{equation}
both almost surely. Here $\alpha_-=0.373\ldots$ and $\alpha
_+=4.311\ldots$ are the two solutions of the equation
$x\log(2e/x)=1$. The survey \cite{DevGelbesBuch} gives details and
references, and explains the relation to branching
processes.

In situations such as these, where the almost sure limit is a constant,
projection on the sub-$\sigma$-fields
$\cF_n$ would simply return the constant, hence no simplification arises.

Both the fill level and height of a tree as well as its path length
(see Section~\ref{subsec:PL}) can be written as functionals
of the tree's node profile. Recall that $|u|$ denotes the length of
$u\in\bV$. Let
\[
v(x,k):= \# \bigl\{u\in\partial x\dvtx|u|=k \bigr\}, \qquad
w(x,k):= \#\bigl \{u\in x\dvtx|u|=k \bigr\}
\]
be the number of external (resp., internal) nodes of $x\in\bB$ at
depth $k$.
Applied to the BST sequence $(X_n)_{n\in\bN}$, this gives sequences
$(V_n)_{n\in\bN}$ and $(W_n)_{n\in\bN}$ of random
functions on the nonnegative integers via $V_n(k)=v(X_n,k)$ and
$W_n(k)=w(X_n,k)$, the external and internal node
profile of the binary search tree. Clearly,
\begin{eqnarray*}
F(X_n) &=& \min \bigl\{k\in\bN: V_n(k)>0 \bigr\} - 1,
\\
H(X_n) &=& \max \bigl\{k\in\bN: W_n(k)>0 \bigr\}
\end{eqnarray*}
and
\[
\IPL(X_n) = \sum_{k=1}^\infty
k W_n(k),
\]
so such profiles go some way toward a unifying approach to tree
functionals and indeed, they have been studied
extensively; see \cite{J-H2001,CDJ2001,CR2004,CKMR2005,FHN2006,DJN2008}.
A~crucial role
in \cite{J-H2001,CDJ2001,CR2004,CKMR2005} is played by a parametrized
family of martingales introduced in \cite{J-H2001}.
In order to connect this to the point of view of the present paper we
rephrase the basic idea using our terminology and
notation.

Fix some $z\in\bR_+$. The external profile $V_n$ of $X_n$ can be
regarded as the counting density of a
random finite measure on $\bN$ with total mass $n+1$ and value
\[
Y_n:= \sum_{k=1}^\infty
V_n(k) z^k = \sum_{u\in\partial
X_n}
z^{|u|}
\]
at $z$ of its generating function.
Let $v$ be the random node that is added to $X_n$ to obtain $X_{n+1}$.
It is easy to see that
\[
Y_{n+1} = Y_n + z^{|v|}(2z-1).
\]
In the BST mechanism the node $v$ is chosen uniformly at random from
the $n+1$ external nodes of $X_n$, hence
\begin{eqnarray*}
E[Y_{n+1}|\cF_n] &= & E \biggl[\sum
_{v\in\partial X_n} \bigl(Y_n+z^{|v|}(2z-1) \bigr)
1_{\{X_{n+1}=X_n\cup\{v\}\}} \Big|\cF_n \biggr]
\\
&=& Y_n E \biggl[\sum_{v\in\partial X_n}1_{\{X_{n+1}=X_n\cup\{v\}\}
}
\Big|\cF_n \biggr]
\\
&&{} + (2z-1) E \biggl[\sum_{v\in\partial X_n} z^{|v|}
1_{\{X_{n+1}=X_n\cup\{v\}\} }\Big |\cF_n \biggr]
\\
&= & Y_n + \frac{2z-1}{n+1}\sum_{v\in\partial X_n}
z^{|v|}
\\
&=& \frac{n+2z}{n+1} Y_n,
\end{eqnarray*}
which means that $(M_n,\cF_n)_{n\in\bN}$ with
\[
M_n:= C(n) Y_n, \qquad C(n):=\prod
_{k=1}^{n-1} \frac{k+1}{k+2z} \mbox{ for all } n\in
\bN,
\]
is a martingale. Obviously, the martingale is strictly positive
whenever $z>0$. Because of the space--time property
it can therefore be written as $M_n=h(X_n)$ with some positive harmonic
function $h$ on $\bB$, which depends on $z>0$,
and which in the present context is given by
\[
h(x) = C(\# x)\sum_{u\in\partial x}z^{|u|}.
\]
Moreover, the distribution $P^h$ of the corresponding $h$-transform,
which is the Markov chain with transition probabilities
\[
p^h(x,y) = \frac{1}{h(x)} p(x,y) h(y),\qquad  x,y\in\bB,
\]
is such that for all $n\in\bN$ the restriction $P^h_{\cF_n}$ of $P^h$
to $\cF_n$ has density
\[
\frac{dP^h_{\cF_n}}{dP_{\cF_n}} = \frac{1}{2z} h(X_n)
\]
with respect to the restriction $P_{\cF_n}$ to $\cF_n$ of the
distribution $P$ of the original BST chain.
Here we have used that both chains start with the tree $X_1=\{
\varnothing
\}$, and that $h(\{\varnothing\})=2z$.
A straightforward calculation yields
\begin{equation}
\label{eq:tiltedMC} p^h \bigl(x,x\cup\{v\} \bigr) = \frac{1}{n+2z}
\frac{\sum_{u\in\partial
x}z^{|u|} + z^{|v|}(2z-1)}{\sum_{u\in\partial x}z^{|u|}}
\end{equation}
for all $x\in\bB$, $v\in\partial x$.
Note that this agrees with the transition mechanism of the BST chain if
$z=1/2$ or $z=1$. For general $z>0$
a corresponding chain may be constructed by a marking mechanism that
makes use of an additional spine
variable. This idea was introduced in the context of branching
processes; for search trees it has been
used in \cite{CKMR2005}, to which paper we refer for more details. The
following direct construction of a
Markov chain with transitions as in \eqref{eq:tiltedMC} may be of
interest: Given $X_n$, we choose an external
node $u$ with probability proportional to~$z^{|u|}$. With probability
$(2z)/(n+2z)$ we then accept $u$ as the node
$v$ to be added to $X_n$; if $u$ is rejected, then $v$ is chosen
uniformly at random from the other $n$
external nodes of $X_n$.

In the first three subsections of the present section we began our
analysis by relating the functionals in question to
the subtree sizes. As the latter fully describe the tree this must also
be possible in the profile context.
For $x\in\bB$, $z>0$ let
\[
\Psi_z(x):= \sum_{u\in x} \sigma(x,u)
z^{|u|}.
\]
Each $v\in\bV_{k+1}$ with $\bar v\in x$ is either an internal or an
external node of $x$, which means that $v(x,k+1)=2
w(x,k) - w(x,k+1)$. Also, the number of internal nodes with depth at
least $k$ is the sum of all subtree sizes of the
nodes with level exactly equal to $k$, that is, $\sum_{u\in x,
|u|=k}\sigma(x,u)=\sum_{j=k}^\infty w(x,j)$. Taken together,
this gives
\[
\sum_{k=1}^\infty v(x,k) z^k =
\biggl(2z-3+\frac{1}{z} \biggr) \Psi_z(x) + \biggl(2-
\frac{1}{z} \biggr) \#x + 1,
\]
which leads to
\[
Y_n = \biggl(2z-3+\frac{1}{z} \biggr) \Psi_z(X_n)
+ \biggl(2-\frac{1}{z} \biggr) n + 1
\]
(note that the bracketed term vanishes for $z=1/2$ and $z=1$). This
could serve as the basis for an analysis along the
lines of the first three subsections. We do not pursue this here but
show instead that the general theory can be used
to obtain an interpretation of the function that represents the limit
of Jabbour's martingale in terms of the
Doob--Martin limit of the BST sequence: Recall that $M_n/(2z)$ is the
density associated with the change of measure from
$P_{\cF_n}$ to $P^h_{\cF_n}$. If the convergence $M_n\to M_\infty$ is
in $L^1$ (see below), then $M_\infty/(2z)$ is a
density of $P^h$ with respect to $P$. Thus we have $M_\infty=2z\Psi
(X_\infty)$, with $\Psi$ a density of the
distribution of $X_\infty$ under the transformed measure $P^h$ with
respect to the distribution of $X_\infty$ under the
original $P$.

It is shown in \cite{CKMR2005} that $L^1$-convergence holds if and only
if the parameter $z$ is inside a
specific bounded interval $I=(c_-,c_+)$, that $M_\infty\equiv0$ if
$z\notin I$, and that, with $\alpha_+,\alpha_-$ as
in \eqref{eq:fillheightconstants}, $c_-=\alpha_-/2$ and $c_+=\alpha
_+/2$. These two phase transitions are related to the
asymptotics of the maximum and minimum node size respectively at a
specific level of the limit $X_\infty$: If $z$ is too
small, then nodes close to the root are favored too much by $p^h$; if
$z$ is too large, then too much weight is given to nodes
far away from the root. In both cases $P^h$ is then singular with
respect to $P$. For the weighted subtree size
metric considered in Section~\ref{sec:results} only one of these
caveats matters in that node sizes must not be inflated
too much. Hence there is only one such phase transition, which should
be related to the height constant, and indeed, a
straightforward calculation shows that $\rho_0=(2e)/\alpha_+$.

Finally, let us mention that the approach toward strong asymptotics of
dynamic data structures that we have developed
in detail for binary search trees should be applicable in many related
situations. The necessary modifications may be
minor, such as for the discounted path length that appears in \cite
{GrSilh}, or straightforward, as for the random
recursive trees that are often treated in parallel with binary trees
(see, e.g., \cite{Nein02} for the Wiener index), or
they may be challenging, for example, when we wish to amplify the weak
convergence results for node depth profiles
obtained in \cite{DJN2008} for a wide class of trees to strong limit
theorems as we have done for the Wiener index in
Section~\ref{subsec:WI}. Of course, convergence in distribution and
convergence along paths are rather different
phenomena; see Figures~\ref{fig:pitrees} and \ref{fig:metrSilh}. It is
interesting that for a given dynamical structure
we may have a strong limit theorem (with nontrivial limit) for some
aspects (functionals), but not for others;
see \cite{DeGr3} for such results in connection with the subtree size
profile of binary search trees.

\section*{Acknowledgment}
I thank the referee for the stimulating comments,
and for
providing several valuable references.


\section{Introduction}
Spectropolarimetry in the neutral helium multiplets at 1083.0~nm and 587.6~nm ($D_3$ line) is one of the most valuable tools (and one of the few available) for the quantitative investigation of the magnetic properties of plasma structures embedded in the chromosphere and corona, such as spicules and prominences \citep{landi_d3_82,querfeld85,bommier94,casini03,lopezariste_casini05,ramelli06_2,ramelli06, harvey_hall71,ruedi96,lin98,trujillo_nature02,Lagg04,trujillo_merenda05,socas_elmore05,merenda06,centeno+10}.
The linear polarization signals in both multiplets are generated by the joint action of the transversal Zeeman effect and scattering polarization modified by the Hanle effect \citep[e.g.,][]{trujillo_asensio07}.
However, the circular polarization signal of the 1083.0~nm multiplet is always dominated by the longitudinal Zeeman effect alone, producing characteristic antisymmetric profiles, whereas in $D_3$ it has an important contribution from the alignment-to-orientation conversion mechanism \citep[A-O mechanism;][]{kemp84,landi_landolfi04}, which generates a significant amount of net circular polarization (NCP) in the line \citep{landi_d3_82}.
The A-O mechanism operates when the Larmor frequency corresponding to the magnetic field is of the order of the energy separation (in frequency units) between the fine structure levels of a given spectral term.
In the D$_3$ line this occurs for magnetic fields stronger than 10~G; in the 1083.0~nm line, it is negligible for fields below 300~G \citep[see, e.g., Figure 3~of][]{asensio_trujillo_hazel08}.
Therefore, for the magnetic fields of up to a few hundreds of Gauss characteristic of spicules and prominences, the Stokes $V$ profiles in the 1083.0~nm line are expected to be mainly antisymmetric.

\begin{figure*}
\centering
\includegraphics[width=0.49\textwidth]{mapas_2.eps}
\includegraphics[width=0.49\textwidth]{inversiones_2.eps}
\caption{Left: Stokes parameters $I$, $Q$, $U$, and $V$ (top to bottom) along the slit at positions 10.8'$''$ (leftmost) and 15.0$''$ (rightmost) in the first and second scan in Figure~3. Dashed yellow lines mark the position of the solar limb (disk, below; off-limb, above).
The intensity scale on-disk has been highly attenuated for representation purposes.
Right: line intensity and polarization (dots) at the two positions marked ``a'' and ``b'', and best-fit profiles from inversions with one (red) or two (blue) components along the LOS, in the absence (solid) or presence (dashed) of atomic orientation. The physical parameters of the models are given in Table~1, labeled as $1$ and $2$ for the one-component inversion, in the last case including an ad-hoc orientation of the radiation field, and 3 and 4 for the two-components inversions without and with orientation of the radiation field.
}
\label{fig:mapas_slit1}
\end{figure*}

We report full-Stokes observations of the 1083.0~nm multiplet of \ion{He}{1} in solar spicules and a prominence in a quiet region.
The observations display anomalous single-lobed Stokes $V$ profiles in the spicular material.
We show, after a detailed analysis of possible instrumental sources of error, that these profiles are not artifacts, but of solar origin.
We argue that these profiles are the result of several components along the line of sight (LOS) and that they might also be a signature of atomic orientation.

\section{Observations}
The data analyzed  consist of full Stokes vector spectropolarimetry at the 1083.0~nm spectral region, containing the photospheric \ion{Si}{1} 1082.71~nm line and the chromospheric \ion{He}{1} 1083.0~nm multiplet.
They were obtained on April 24th, 2011 with the upgraded Tenerife Infrared Polarimeter \citep[TIP-{\sc II};][]{collados_tipII07} instrument attached to the Vacuum Tower Telescope at the Observatorio del Teide.
We scanned a quiet region at the east limb (90$^\circ$E, 40$^\circ$S), with the slit inclined by about $45^\circ$ with respect to the limb. We simultaneously recorded part of the
solar disk, the spicular material, and a prominence.
The scanned area was 70$'' \times 42''$ along the slit and in the scan direction,
respectively. The pixel size was 0\farcs32$\times 0\farcs6$. The time span between
two consecutive slit positions was approximately 30 s and the spectral resolution was 4.5 pm. The
noise level in polarization was about 10$^{-3}$ in units of the
maximum intensity, $I_{max}$. The seeing conditions were very good and the adaptive
optics system worked efficiently for the whole observation run. This resulted in a spatial
resolution  of $\sim 0.6''$ and made it possible that we could scan the same region four times.

To avoid the appearance of spurious signals we have been extremely careful in the data reduction process.
From the original raw data, we removed the bias level, applied the flatfield correction, and demodulated the data to obtain the four Stokes parameters using the standard software package available for TIP-II users.
The flatfield correction removed most of the polarized interference fringes, leaving a residual pattern with amplitudes below 10$^{-4}$ $I_{max}$.

Despite the good seeing conditions and the image stability offered by the adaptive optics system, some occasional image motion is unavoidable within the $4\times 250$~ms of the modulation process which yields spurious polarization \citep[seeing-induced crosstalk, e.g.,][]{lites_87}.
Normally this effect is minimized by the spatio-temporal demodulation scheme \citep{collados99}.
However, close to the limb observations are extremely sensitive to this effect because of the steep intensity gradients.
As a result, thin stripes of spurious positive and/or negative polarization signal parallel to the limb were apparent in the observations.
At this point, the observational procedure with the slit crossing the limb proved to be very helpful.
The spurious polarization signal along the slit can be modeled as a combination of the first and second derivatives of the intensity, while the actual coefficients of the combination depend on the particular image motion during the observation.
Assuming that the continuum is unpolarized  because linear polarization due to Rayleigh scattering is negligible at such long wavelengths, we fitted the variation of the spurious polarization signals in the continuum along the slit to the first and second spatial derivatives of the intensity, and subtracted the fit.
This correction was applied to all wavelengths using the same coefficients but the intensity derivatives calculated at each wavelength.
This process was able to remove most of the artifacts but within a very small stripe ($\leq 1''$) around the limb.
As an additional benefit, this procedure further diminished the residual patterns left after flat field correction.

\begin{figure*}
\centering
\includegraphics[width=0.49\textwidth]{mapas_1.eps}
\includegraphics[width=0.49\textwidth]{inversiones_1.eps}
\caption{Same as Figure \ref{fig:mapas_slit1} but for slit positions 23.4$''$ and 13.2$''$ in the third and first scan in Figure 3.}
\label{fig:mapas_slit2}
\end{figure*}

Stray light is also an issue when observing across the limb \citep{beck_11}.
At some far off-limb positions with no apparent emission from the prominence a residual absorption spectrum from the integrated disk could be noticed.
From the average of several such pixels we built a stray light spectrum.
The amount of stray light contamination along the slit was then found through correlation with this spectrum, using the telluric line at 1083.2 nm and smoothing the ensuing correlation coefficient maps.
We then subtracted the average off-limb stray light profile times the smoothed correlation coefficient from the Stokes $I$ profiles. This approach proved to be quite effective in removing off-limb stray light.

Figures \ref{fig:mapas_slit1} and \ref{fig:mapas_slit2} display the Stokes profiles of the 1083.0~nm
triplet at four different positions. The intensity profile
appears in emission above the solar limb, both in the spicules and in the
prominence (at about $25''$ above the limb).
The \ion{He}{1} multiplet shows characteristic signatures associated to scattering processes
and the Hanle effect inside and outside the disk in Stokes $Q$ and $U$. The
Stokes $V$ signals are very faint on the disk but show clearly antisymmetric
profiles in the prominence (profile d), as expected for this multiplet when the Stokes $V$
signal is dominated by the Zeeman effect.
However, unexpectedly, we detect single-lobed Stokes $V$
profiles off-limb in the spicular material.

Firstly, we note that the single-lobed $V$ profiles were already apparent after the standard data reduction process; the thorough analysis described above just served to enhance their presence by eliminating artifacts.
Additional reasons why we think these single-lobed Stokes
$V$ profiles are of solar origin are:
1) we do not observe any off-limb polarization signal in the telluric line \citep[see Sect. 3.3 in][]{beck_11},
2) we also observe Zeeman-like signals at the same slit position, 3) they are located
in patches that are spatially coherent during more than 135 minutes. It seems extremely unlikely that seeing-induced signals appear at the same location in the solar structure during all the observational runs. Figure \ref{fig:mapas_int_ncp} displays the net circular polarization (the Stokes $V$ signal integrated along the 1083.0~nm triplet)
normalized to its maximum in the field of view (FOV) for pixels with
circular polarization signals above the noise level.
Extremely asymmetric Stokes $V$ profiles are quite common in spicules forming patches that are persistent for more than 2 hours of observation.

Regular Stokes $V$ profiles (mostly antisymmetric and similar to profile d) pervade the prominence. They are also found in the spicules, although they have a large degree of asymmetry. Figure \ref{fig:mapas_slit2} shows two examples of antisymmetric profiles. As can be seen, the Stokes $V$ profile belonging to the spicular material is asymmetric (both in area and in amplitude). Moreover, both Stokes $Q$ and $V$ profiles show two peaks and are broader than Stokes $I$, indicating the existence of at least two atmospheric components along the line of sight.

\begin{figure}
\centering
\includegraphics[width=\columnwidth,bb=15 30 500 296]{ncp_6.eps}\\
\includegraphics[width=\columnwidth,bb=15 30 500 255]{ncp_7.eps}\\
\includegraphics[width=\columnwidth,bb=15 30 500 255]{ncp_10.eps}\\
\includegraphics[width=\columnwidth,bb=15 30 500 290]{ncp_12.eps}
\vspace{0.3cm}
\caption{Four consecutive scans (horizontal slit; scanning direction from bottom to top) of the observed FOV including spicules and a prominence.
The start time of each scan is displayed at the bottom right corner of the corresponding panel.
The background images show the maximum intensity of the \ion{He}{1} multiplet. The NCP of Stokes $V$ profiles (normalized to its maximum
in the field-of-view) with signals above the noise level is overplotted in a color code.
The dashed lines mark the solar limb and, roughly, the highest altitude of observed spicular material. White circles mark the position of the profiles shown in Figures ~\ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}.}
\label{fig:mapas_int_ncp}
\end{figure}

\section{Inversion of the data}

We carried out inversions of the profiles shown in Figures~\ref{fig:mapas_slit1} and \ref{fig:mapas_slit2} with the inversion code HAZEL \citep[HAnle and ZEeman Light, see][]{asensio_trujillo_hazel08} assuming a slab of constant properties, characterized by the optical depth of the red component of the multiplet, $\tau_{\rm red}$, the thermal width, $v_\mathrm{th}$, the macroscopic velocity along the LOS, $v_\parallel$, and the damping constant. Each slab is permeated by a magnetic field with strength, $B$, inclination relative to the vertical, $\theta_B$, and
azimuth, $\chi_B$. The radiation field is assumed to be given by the continuum
illumination at the wavelengths of all transitions considered in the 5-level \ion{He}{1}
atomic model. The center-to-limb variation tabulated by \cite{cox00} is used to compute
the anisotropy of the radiation field. This simple model let us fit regular profiles as d) in Figure~\ref{fig:mapas_slit2} and recover the physical conditions there (see model d in Table~1), but it is clearly unable to reproduce the $V$ profiles at positions a, b, and c (cf. solid red lines in Figures~\ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}, corresponding to models a$_1$, b$_1$, and c$_1$ in Table~1). In general, the Stokes $V$ profiles in the prominence are similar to profile d) in Figure~\ref{fig:mapas_slit2}, implying that a single magnetic component would be sufficient to fit the observations of a prominence at our spatial resolution and spectropolarimetric accuracy.

Obviously, the Zeeman effect alone is unable to reproduce Stokes $V$ profiles with NCP but several known mechanisms are able to generate it. First, the presence of correlations between velocity and magnetic field gradients along the LOS \citep[][]{illing75} has often been proposed (in photospheric lines) to explain the asymmetries in Stokes $V$ induced by the Zeeman effect
around magnetic flux concentrations \citep{solanki88,grossman_doerth88,sanchez_almeida89,solanki93}.
This effect might be of some importance when observing spicules or prominences close to and off the limb, because
the LOS potentially crosses many structures with different velocities and magnetic fields \citep[e.g. the multi-thread prominence models described in][and references therein]{labrosse_10, mackay_10}.
A property of the asymmetric profiles is that the width of the remaining single-lobed Stokes
$V$ profile should be roughly half the width of the Stokes $I$ profile. In our case,
the observed single-lobed Stokes $V$ profile is roughly of the same width as Stokes
$I$, and in some cases even larger.

Atomic orientation, i.e., the presence of population imbalances and quantum coherence between the $+M$ and the corresponding $-M$ magnetic sublevels of a given level \citep[][]{fano57}, is in itself a direct source of NCP through imbalanced emission or absorption of $\sigma^\pm$ components. To fit the profiles, we have considered the possible presence of atomic orientation (models a$_{2}$, b$_{2}$, c$_{2}$ in Table 1 and dashed red lines in Figures \ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}). The way to introduce this atomic orientation in the HAZEL code is by an ad-hoc amount of orientation of the incident radiation field (i.e., $J^1_0 / J^0_0$).
We only took into account orientation in this multiplet. This is justified because the 1083.0~nm multiplet can be relatively well approximated by a two-term system. We have nonetheless tested that
the presence of atomic orientation in the other transitions of the model does not
modify our results. With the approximation of a single component and atomic orientation, we obtained an acceptable fit for the position c (although the double peak of Stokes $Q$ is not reproduced), but it was impossible to reproduce the other profiles.

We then performed inversions considering two components along the LOS, each one with different values of the physical parameters and a relative macroscopic velocity between them (models a$_{3}$, b$_{3}$, c$_{3}$ in Table 1 and solid blue lines in Figures \ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}).
Finally, we also allowed for an ad-hoc amount of orientation in the two-component model (models a$_{4}$, b$_{4}$, c$_{4}$ in Table 1 and dashed blue lines in Figures \ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}).
With this modelling we fit fairly well the remaining profiles. The inferred physical parameters are reasonable for these kind of structures: the doppler broadening and the optical thickness have larger values in the spicules than in the prominence, as well as the magnetic field strength (see Table 1). However, the exact magnetic field vector is subject to some known ambiguities whose discussion is beyond the scope of this paper.

In spicules, regular antisymmetric Stokes $V$ profiles are rare; most of them exhibit noticeable NCP and often
show evidence for the presence of (at least) two components. We detect either two peaks in the Stokes $V$ lobes and/or Stokes $Q$ and $U$ that are not compatible with Stokes $V$ with a single configuration of the magnetic field. To fit polarization profiles of solar spicules one therefore needs more complex models than that of a single component. Probably, one should think on a modeling that takes into account the transfer of polarized radiation and a source not only of atomic alignment (hence $J^2_0/J^0_0$) but of atomic orientation (hence $J^1_0/J^0_0$).

\begin{table}
\caption{Inferred physical parameters of the inversion models}
\centering
\begin{tabular}{clrrrrcc}
\hline\hline
model & $\tau_{\rm red}$ & $B$ & $\theta_B$ & $\chi_B$ & $v_{\rm th}$ & $v_\parallel$ & $v$ \\
 & & (G) & $(^\circ)$ & $(^\circ)$ & \multicolumn{2}{c}{(km s$^{-1}$)} & \\
\hline
a$_1$ & 0.83 & 18  &  93 &  58 & 11.0  & -1.5  &      \\
a$_2$ & 0.83 & 11  & 87  & 57  & 11.0  & -1.5  & 0.05     \\
a$_3$ & 0.78  & 79  & 38  & 4  & 9.0  & -0.8  &      \\
          & 0.54 & 179 &  94 &  109  & 10.4  & -2.7  &       \\
a$_4$ & 0.78  & 57  & 36  & 3  & 9.0  &  -0.5 &   0.013   \\
          &  0.54 &  93 & 93  &  119  & 10.4  &  -4.4  &   0.013    \\
 \hline
b$_1$ & 1.5  & 7  & 92  & 46  & 11.5  & -1.5  &      \\
b$_2$ & 1.5  & 5  & 92  & 46  & 11.5  & -1.5  & 0.01     \\
b$_3$ & 1.0  & 38  & 41  & 7  & 8.4  &  0.3 &      \\
          &  0.7 &  60 &  88 &  131 &  10.3 &  -4.7 &       \\
b$_4$ & 0.9  & 35  & 41  & 6  & 9.2  & 0.3  &    0.006  \\
          &  0.6 & 71  &  88 &  130 &  11.0 &  -4.8 &   0.006   \\
\hline
c$_1$ & 3.0  & 19  & 40  & 3  & 10.5  & -0.6  &      \\
c$_2$ &  3.0 & 21  & 40  & 3  & 10.9  & -0.6  & -0.004     \\
c$_3$ & 1.7  & 29  & 93  & 85  & 10.0  & -0.1  &      \\
          &  1.3 &  23  &  86 &  31 &  12.3 &   &  -0.1     \\
c$_4$ & 1.4  & 75  & 14  & 25  & 10.1  & -0.7  & -0.006     \\
          &  1.2  &  22 &  65 &  30 &  13.0 &  -0.6 &  -0.006    \\
\hline
d        &  1.6 & 28  & 44  & 3  & 5.5  & -1.8  &      \\
\hline \hline
\end{tabular}
\end{table}

\section{Generation of atomic orientation}

As stated in Sect.\,1, the A-O mechanism can generate a very small amount of atomic orientation that is already taken into account in the modeling by HAZEL. Likewise, the generation of a sufficient amount of atomic orientation through the presence of electric fields \citep{favati87} as suggested by \cite{lopezariste_halpha05} \citep[see also][]{casini_rafa_06, casini_rafa_08} for the H$\alpha$ line in solar prominences can also be discarded for this multiplet since it is not hydrogenic.

Atomic orientation may be induced by differential excitation of the $\sigma^+$ and $\sigma^-$ components of the transition. This can be achieved by a) illuminating the atomic system with circularly polarized radiation or b) by spectrally splitting the transition components (e.g., in the presence of a magnetic field) and differentially illuminating the $\sigma^\pm$ components.

In the case a), considering a two-level atom with an unpolarized lower level, and assuming complete frequency redistribution (CRD), the atomic orientation generated in the upper level (hence, the NCP of the scattered radiation) is proportional to (Landi Degl'Innocenti \& Landolfi 2004)
\begin{equation}\label{eq_j10}
v= \frac{\bar{J}^1_0}{\bar{J}^0_0}=
\sqrt{\frac{3}{2}} \frac{\int_0^\infty\int_{0}^1 V(\nu,\mu)\mu d\mu \,\phi(\nu) d\nu}{\int_0^\infty\int_{0}^1 I(\nu,\mu) d\mu \; \phi(\nu) d\nu},
\end{equation}
where $\phi(\nu)$ is the line absorption profile.

As a possible scenario for this, consider an ensemble of scatterers in a spicule or a prominence well above the solar surface illuminated from an underlying magnetized photosphere. If the incident Stokes-$V$ profile is antisymmetric and there is no Doppler shift between the radiation field and the atomic system, $v\equiv 0$ and no atomic orientation can be induced.
However, if the scatterers have a collective motion with respect to the surface, the line profiles $\phi$ in Equation~(\ref{eq_j10}) are Doppler shifted with respect to the incoming radiation field ($I$ and $V$) and $v$ does not cancel out in general. Clearly, if the incident radiation has NCP, that contribution adds to $v$.
Figure~\ref{fig:j10} shows the amount of $v$ generated as a function of the velocity, assuming upwards motion, for an illumination with a Gaussian absorption line, using values characteristic of the He~{\sc i} 1083.0~nm line in an active region. The Stokes $V$ incident light has no NCP.

In case b), the uneven pumping of the $\sigma$ components of a two-level atom (unpolarized lower level, CRD), by a spectrally structured radiation field is characterized by the ratio
\begin{equation}\label{eq_phi}
v'=\frac{\int_0^\infty \int^1_0 I(\nu) d\mu \Phi^{10}_0(\nu) d\nu}{\int_0^\infty \int^1_0 I(\nu)  d\mu \Phi^{00}_0(\nu)  d\nu}.
\end{equation}
The frequency integrals are performed over the generalized profiles \citep{landi_landolfi04}
\begin{multline}\label{eq_phi2}
\Phi^{00}_0(\nu)=\sum_{M_uM_\ell}\frac{1}{3}S_q^{J_\ell J_u}(M_\ell M_u) \phi_{M_u M_\ell}(\nu), \\
\Phi^{10}_0(\nu)=\sum_{M_u M_\ell}\frac{M_u}{\sqrt{3J_u(J_u+1)}} S_q^{J_\ell J_u}(M_\ell M_u) \phi_{M_u M_\ell}(\nu),
\end{multline}
where $S_q^{J_\ell J_u}(M_\ell M_u)$ with $q=M_\ell-M_u$ ($q=0, \pm 1$) is the relative strength of the transition between the sublevels $M_u$ and $M_\ell$, and the profile components $\phi_{M_u M_\ell}$ are centered at the frequency $\nu_{M_u M_\ell}=\nu_0+\nu_L(g_u M_u-g_\ell M_\ell)$ ($\nu_L$ is the Larmor frequency and $g_{u, \ell}$ the Land\'e factors of the upper and lower levels, respectively).

As a scenario for this case consider that the underlying photosphere is quiet, but that the scatterers are moving (upwards) in the presence of a magnetic field.
The denominator of Equation (\ref{eq_phi}) is the mean intensity integrated over the line profile taking into account the magnetic splitting of the line components.
The generalized profile $\Phi^{10}_0$ is odd with respect to the central frequency of the transition $\nu_0$ \citep[more generally, $\Phi^{KK'}_0(\nu_0+\Delta)=(-1)^{K+K'}\Phi^{KK'}_0(\nu_0-\Delta)$; see][]{landi_landolfi04}.
Therefore, if the intensity profile of the incident radiation is symmetric around the central frequency $\nu_0$, the integral in the numerator of equation (\ref{eq_phi}) vanishes. If the profiles are Doppler shifted with respect to the incoming intensity, $v'$ varies as in figure \ref{fig:j10} (red curve).

Dynamic generation of atomic orientation has been considered to qualitatively explain asymmetric $V$ profiles in chromospheric lines \citep{trujillo+93}, but its presence in active regions was discarded by \cite{socas_trujillo_ruiz00b}.
Yet, the physical and dynamical conditions to be expected in spicules and prominences could be more favorable for the generation of atomic orientation by the processes just described.
First, velocities of the order of 8-10~km~s$^{-1}$ are easily found in our data from Doppler shifts and from H$\alpha$ movies.
Both scenarios require that the He~{\sc i} 1083.0~nm line is formed in the underlying atmosphere.
In our observations the 1083.0~nm line is in absorption within the solar disk in Figures~\ref{fig:mapas_slit1} and \ref{fig:mapas_slit2}.
The large values of $v$ that may be achieved in case a) scenario (see Figure~\ref{fig:j10}) require illumination from underlying relatively strong ($\sim$1~kG), unipolar regions.
However, prominences and filaments form along the neutral line of bipolar active regions, which would yield to cancelations and hence, far smaller values of $v$ and atomic orientation.
More likely is scenario b), in which spicules and low prominence regions are magnetized at the level of $\sim$100~G, values easily found from the inversions.

\section{Conclusions}

We have shown that Stokes $V$ profiles of He\,{\sc i} 1083 nm can have a significant amount of NCP in spicular fields. Surprisingly, this type of signals have not been found in previous spectropolarimetric studies of spicules using this multiplet \citep{socas_elmore05, trujillo_merenda05, centeno+10}.
This may be due to a particularity of the region observed here, or else it could have been that the large values of the NCP might have been mistaken for observational artifacs. To avoid this possible source of confusion, we found our observational strategy of observing with the slit across the limb very advantageous, because it allows a correction for several artifacs caused by image motion or stray light.

These profiles with extreme NCP (mostly single lobed) are explained by the presence of two magnetic components along the LOS (although we expect the reality to be more complex, with a myriad of magnetic and velocity fields crossing the LOS) and perhaps, some amount of atomic orientation ($\sim$ 0.6\%-1\%) generated by dynamic proceses in the presence of magnetic fields.

\begin{figure}
\centering
\includegraphics[width=\columnwidth]{j10.eps}
\caption{Variation of $v$ (blue lines) and $v'$ (red lines) with the adimensional velocity $\omega=v_z \lambda_0/(wc)$ ($v_z$ is the vertical velocity of the upward moving scatterers, $c$ the speed of light, $w$ the width of the incident spectral line).
The incident photospheric radiation field is assumed to be $I=I^0(1-\mu+u\mu)[1-d \exp(-(\lambda-\lambda_0)^2/w^2)]$.
We have considered an absorption ($a=0.3$), limb darkened ($u=0.51$) line, at $\lambda_0$=1083.0~nm, with a width $w=28.9$~pm (corresponding to 8 km~s$^{-1}$).
The parameter $v$ is calculated assuming that the underlying photospheric field is permeated by a uniform 1~kG field; $v'$ is calculated assuming that the scatterers are in the presence of a 100~G field.
The width of the scatterers absorption profiles $\phi$ has been taken to be similar to the incident line.
The solid and dotted lines correspond to opposite magnetic field polarities.
Positive $\omega$ for upward velocities.
As a reference, $\omega=1$ corresponds to $v_z=8$~km~s$^{-1}$.}
\label{fig:j10}
\end{figure}

\begin{acknowledgements}
We thank M. Collados and
J. Trujillo Bueno for useful discussions.
Based on observations in the VTT operated on the island of Tenerife by the KIS in the Spanish Observatorio del Teide of the Instituto de Astrof\' isica de Canarias.
Research supported by the Spanish MEC
under the grants AYA2010-18029 and Consolider-Ingenio 2010 CSD2009-00038.
\end{acknowledgements}