\documentstyle[12pt] {amsart}

\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   

\newcommand {\QQ}  {{\bf Q}}
\newcommand {\RR}  {\mathbb{R}}
\newcommand {\ZZ}  {{\bf Z}}
\newcommand {\CC}  {{\bf C}}
\newcommand {\pp}  {{\bf p}}
\newcommand {\OO}  {{\cal O}}
\newcommand {\NN}  {{\rm N}}
\newcommand {\VV}  {\mathbb{V}}
\newcommand {\EE}  {\mathbb{E}}
\newcommand {\FF}  {{\cal F}}
\newcommand {\xx} {{\bf x}}
\newcommand {\yy} {{\bf y}}
\newcommand {\uu} {{\bf u}}
\newcommand {\kk} {{\bf k}}
\newcommand {\XX} {{\bf X}}
\newcommand {\tT} {{\bf t}}
\newcommand {\ovl} {\overline}
%\newcommand {\mod} {\mbox{\,{\rm mod}\,}}

\newtheorem {Def}{Definition}
\newtheorem {Th}{Theorem}
\newtheorem {Cor}{Corollary}
\newtheorem {Pro}{Proposition}
\newtheorem {Le}{Lemma}
\newtheorem {Ru}{Rule}
\newtheorem {Appl}{Application}

\begin{document}


\font\sevenbf=cmbx7
\font\fivebf=cmbx5
\scriptfont\bffam=\sevenbf
\scriptscriptfont\bffam=\fivebf


\title[The Height of ${q}$-Binary Search Trees]{
The Height of $\boldsymbol{q}$-Binary Search Trees}

\author{Michael Drmota and Helmut Prodinger}   

\address{
Department of Geometry, %\newline
Technical University of Vienna, %\newline
Wiedner Hauptstrasse 8--10, %\newline
A-1040 Vienna, %\newline
Austria }
\email{michael.drmota@@tuwien.ac.at}

\address{
The John Knopfmacher Centre for Applicable Analysis and Number
Theory, School of Mathematics, University of the Witwatersrand, P.\;O.
Wits, 2050 Johannesburg, South Africa} 
\email{helmut@@gauss.cam.wits.ac.za}

\keywords{Binary search tree, $q$--analog, height}
%\subjclass{}






 
\begin{abstract}
$q$--binary search trees are obtained from words, equipped
with the geometric distribution instead of permutations.
The average and variance of the height are computated, 
based on random words of length $n$, as well as a 
Gaussian limit law.
\end{abstract}

\maketitle

\section{Introduction}

The paper \cite{prodinger01} introduces for the first time
a meaningful $q$--model of binary search trees: Instead of
binary search trees, one considers tournament trees, which
differ only marginally from binary search trees; if one
starts from a permutation 
$\left(\begin{smallmatrix}
1&2&\cdots& n \\ \pi_1&\pi_2&\cdots &\pi_n
\end{smallmatrix}\right)$, then one inserts the number $i$
instead of the number $\pi_i$. 
Thus, traversing the tree in inorder, we might think
of the associated permutation as
$\rho1\sigma$, where 1 goes into the root, 
and $\rho $ resp. $\sigma$ form 
(recursively) the left resp. right subtree. 

Now instead of considering permutations $\pi_1\pi_2\cdots \pi_n$, 
we consider words over the alphabet $\{1,2,3,\dots\}$, and
(geometric) probabilities attached to the letters, i.\;e.
the probability of letter $i$ is $pq^{i-1}$, with $p+q=1$.
The binary search tree is then constructed by writing a 
nonempty word $w$ as $w=xay$, where $a$ is the smallest letter
occurring, and $x\in\{a+1,a+2,\dots\}^*$ and
$y\in\{a,a+1,\dots\}^*$. The letter $a$ goes into the root 
and $x$ resp. $y$ form the left resp. right subtree.

The paper \cite{prodinger01} dealt with the path length;
here we consider the height. The height of a binary search
tree (and thus of the trees in our model) is defined to be
the largest number of nodes in a path from the root to a leaf;
the empty tree (related to the empty word) has height 0.

We will prove that the expected
height, when considering random words of length $n$, is
asymptotic to $pn$; the variance will also be computed
as well as a Gaussian limit law. (The letter $p$ will always
denote $1-q$ in this paper.) Recall that the result for
traditional binary search trees is $\sim c\log n$ with
$c=4.31107$, see \cite{DevR}; 
unfortunately we do not get that result as
the limit $q\to1$ as it so happened for the path length. 
However, nothing is wrong here, since the limit 
$q\to1$ in $pn$ simply tells us that the average height should
be less than linear. Although this original hope of
getting the classical result as a corollary did not work
out, we nevertheless think that the results presented here
are of independent interest. Note also that $pn$ is the expected
number of letters 1 in a (random) string of length $n$.
In our asymmetric model, they must all lie on one path.

\smallskip
In more detail, we will obtain the following results:


Let $H_n$ denote the height of $q$--binary search trees
with $n$ (internal) nodes (this is a random variable, 
defined on words of length $n$). 


\begin{Th}\label{Th1}
For every positive $q<1$ the height $H_n$ of
 $q$--binary search trees
with $n$ (internal) nodes satifies a central limit theorem
of the form
\begin{equation}\label{Th11}
\sup_{x\in{\RR}} \left|\,{\bf Pr}\{ H_n \le x \} - 
\Phi\left( \frac {x-pn}{\sqrt{npq}}\right) \,\right|
= \OO(n^{-1/2}),
\end{equation}
where $\Phi(x)$ denotes the normal distribution function
\[
\Phi(x) = \frac 1{\sqrt{2\pi}} \int_{-\infty}^x
e^{-t^2/2}\,dt.
\]
The expected value is given by
\begin{equation}\label{eqTh12}
{\EE}\, H_n = p n + \OO\left( \frac 1p\right),
\end{equation}
in which the $\OO$-constant is uniform for $0<q<1$.
The variance can be estimated by
\begin{equation}\label{eqTh13}
{\VV}\, H_n = pq n + \OO_q\left( n^{1/2} \log^2 n\right).
\end{equation}
\end{Th}
The $\OO$-constant in the error term of the variance is not
uniform for $0<q<1$. The dependency on $q$
 has not been worked out since the
order of magnitude of the error term is surely not optimal. However, 
although the error term for the expected value is uniform, 
this theorem cannot
be used to cover the case $q\to 1$ where it is known that 
the expected value is given by  
\[
{\EE}\, H_n = c\log n + \OO\left( \log\log n\right)
\]
(with $c = 4.31107\cdots$, see \cite{DevR}) and the variance is bounded:
\[
{\VV}\, H_n = \OO(1)
\]
(see \cite{Drm2,DR2}).

\section{Weak Convergence}

\begin{Le}\label{Le1}
Let $y_k(x)$ denote the generating function
\[
y_k(x) = \sum_{n\ge 0} {\bf Pr}\{ H_n \le k \} x^n.
\]
Then we have $y_k(0) = 1$ and 
\begin{equation}\label{eqLe1}
y_{k+1}(x)  = pxy_k(x)y_k(qx)+ y_{k+1}(qx).
\end{equation}
\end{Le}

{\it Proof.}
The proof is a straight forward translation of the 
basic decomposition $w=xay$: If $a=1$ (described by $px$), 
then the left
subtree consists only of letters  in $\{2,3,\dots\}$, 
described by $y_k(qx)$, but the right subtree can have
any letters, which is described by $y_k(x)$. However, if
$a>1$, we get the term $y_{k+1}(qx)$ (we might then think
of all letters being reduced by 1).
 $\qed$

If we write this in the form
\begin{equation*}   
\frac{y_{k+1}(x)-y_{k+1}(qx)}{(1-q)x}=y_{k}(qx)y_{k}(x),
\end{equation*}
then the limit $q\to1$ gives
\begin{equation*}   
y^\prime_{k+1}(x)=y^2_{k}(x),
\end{equation*}
the usual recursion in the instance of binary search trees.
(Recall that $\frac{f(x)-f(qx)}{(1-q)x}=:(D_q\,f)(x)$, and $D_q$ is called
the $q$--difference operator.)
Also, if we write
\begin{equation*}   
y_k(x)=\sum_{0\le j<2^k}a_{k,j}x^j,
\end{equation*}
then we get, by comparing coefficients, 
\begin{equation*}   
a_{k+1,j}=\frac{p}{1-q^j}\sum_{0\le i<j}a_{k,i}\,a_{k,j-1-i}\,q^i
\qquad \text{for $j\ge1$},
\end{equation*}
and $a_{k,0}=1$ for all $k\ge0$.


\begin{Le}\label{Le2}
The generating functions $y_k(x)$ are bounded above by
\begin{equation}\label{eqLe21}
y_k(x) \le \frac 1{1-x} - \frac x{1-x} \left( \frac{px}{1-qx}
\right)^{k+1}.
\end{equation}
Furthermore, this inequality is also true on the level of coefficients,
 i.\;e.
\begin{align}\label{eqLe22}
\begin{split}
{\bf Pr}\{ H_n \le k \} &= [x^n] y_k(x) \\
&\le  1 - [x^n] \frac x{1-x} \left( \frac{px}{1-qx} \right)^{k+1} \\
& =   \sum_{l=0}^k {n-1\choose l} p^l q^{n-1-l}. 
\end{split}
\end{align}
\end{Le}

Note that this upper bound is an exact binomial distribution function
which is asymptotically normal with mean $p(n-1)$ and
variance $pq(n-1)$. 

{\it Proof.}
Since $y_k(x) \le 1/(1-x)$ we get from (\ref{eqLe1}) that
\[
y_{k+1}(x)\le \frac{px}{1-qx} y_k(x) + \frac 1{1-qx}.
\]
Thus, (\ref{eqLe21}) follows by induction. Note that any step in
these calculations is also true on the level of coefficients.
Thus, 
\[
{\bf Pr}\{ H_n \le k \} \le 1 - [x^n] \frac x{1-x} \left( 
\frac{px}{1-qx}\right)^{k+1}.
\]
Set
\[
Y_k(x) =  \frac 1{1-x} - \frac x{1-x} \left( \frac{px}{1-qx} \right)^{k+1}
\]
and
$$
\Delta_k(x) = Y_k(x) - Y_{k-1}(x) 
= \frac 1p \left( \frac{px}{1-qx} \right)^{k+1}.
$$
Since
\[
[x^n] \Delta_k(x) =  {n-1\choose k} p^k q^{n-1-k},
\]
(\ref{eqLe22}) follows immediately.
$\qed$

\begin{Le}\label{Le3}
The generating functions $y_k(x)$ are bounded below by
\begin{align}\label{eqLe31}
\begin{split}
y_k(x) &\ge  \frac 1{1-x} - \frac x{1-x} \left( \frac{px}{1-qx}
\right)^{k+1}\\
        &-   \frac{(qx)^2}{1-qx} \frac {\left( \frac{px}{1-qx} \right)^{k}
- (qx)^k}
              { \frac{px}{1-qx}  - qx } \\
        &-   \frac{qx}{1-x} \left( \frac{px}{1-qx} \right)
              \frac {\left( \frac{px}{1-qx} \right)^{k} - (qx)^k}
              {\frac{px}{1-qx}  - qx } \\
       &+   \frac{qx^2}{1-x} \left( \frac{px}{1-qx} \right)^{k+1}
             \frac{1-(qx)^k}{1-qx}.
\end{split}
\end{align}
Furthermore, this inequality is also true on the level of coefficients.
\end{Le}

{\it Proof.}
First we use the trivial lower bound
\[
y_k(x) \ge \frac {1-x^{k+1}}{1-x}
\]
and the upper bound (\ref{eqLe21}) to obtain the inequality
\begin{align*}
y_{k+1}(x) &=   pxy_k(x)y_k(qx) + y_{k+1}(qx) \\
&\ge  x(1-q)y_k(x) \left( \frac 1{1-qx} - \frac {(qx)^{k+1}}{1-qx} \right) 
+ \frac 1{1-qx} - \frac {(qx)^{k+2}}{1-qx} \\
&\ge  \frac{px}{1-qx} y_k(x) + \frac 1{1-qx} \\
 & - px\frac {(qx)^{k+1}}{1-qx}  
\left( \frac 1{1-x} - \frac x{1-x} \left( \frac{px}{1-qx} \right)^{k+1}
\right)
-\frac {(qx)^{k+2}}{1-qx} .
\end{align*}
Now (\ref{eqLe31}) follows by induction. As in the proof of Lemma~\ref{Le2} it
can be observed that (\ref{eqLe31}) is also true on the level of coefficients.
$\qed$


In order to obtain proper error terms for the lower bound for
${\bf Pr}\{ H_n \le k \}$ which may derived from Lemma \ref{Le3}
we make use of the following lemma.

\begin{Le}\label{Le4}
Let $0<q<1$ be given and
let $F(x)$ be a function which is analytic for $|x|< 1+ \varepsilon$
for some $\varepsilon>0$. Then there exist $c>0$ and $\eta>0$
such that 
\begin{equation}\label{eqLe41}
[x^n] F(x) \left( \frac{px}{1-qx} \right)^k =
\OO\left( n^{- 1/2}
\exp\left( - \frac cn \bigl(k-pn\bigr)^2
\right)\right)
\end{equation}
and
\begin{equation}\label{eqLe42}
[x^n] F(x) \frac {\left( \frac{px}{1-qx} \right)^{k} - (qx)^k}
              {\frac{px}{1-qx}  - qx } =
\OO\left( n^{- 1/2}
\exp\left( - \frac cn \bigl(k-pn\bigr)^2 
\right)\right) + \OO(q^k)
\end{equation}
uniformly for $|k-pn|\le \eta n$ as $n\to\infty$.
\end{Le}

{\it Proof.}
By using  standard saddle point asymptotics (compare with \cite{Drm1})
it follows that
\begin{align*}
[x^n] F(x) \left( \frac{px}{1-qx} \right)^k &=
\frac 1{2\pi i}
\int\limits_{|z|=x_0}  F(z) \left( \frac{pz}{1-qz} \right)^k
\frac{dz}{z^{n+1}}\\ 
&=  \OO\left( n^{- 1/2} x_0^{-n}\left(
\frac{px_0}{1-qx_0} \right)^k
\right),
\end{align*}
where the saddle point $x=x_0=\left( 1- \frac kn \right)/q$ 
is determined by the equation
\[
\frac{x \frac {d}{dx}\left( \frac{px}{1-qx} \right)}
{\frac{px}{1-qx}} = \frac nk.
\]
In particular we have $x_0 =1$ if $k/n =p$. Finally a local
expansion of 
\[
x_0^{-n}\left( \frac{px_0}{1-qx_0} \right)^k =
\frac {q^{n-k}p^k}
{\left( 1- \frac kn\right)^{n-k}  \left( \frac kn\right)^{k} }
\]
completes the proof of (\ref{eqLe41}).


The proof of (\ref{eqLe42}) runs along similar lines. However,
we have to be a little bit more careful. The reason is that
the denominator
\[
\frac{pz}{1-qz}  - qz 
\]
is singular for $z_1=0$ and for $z_2=(-1+2q)/q^2$. Nevertheless the whole part
\[
\frac {\left( \frac{pz}{1-qz} \right)^{k} - (qz)^k}
              {\frac{pz}{1-qz}  - qz }
\]
is regular for $|z|<1/q$. Note that $|z_2|>1$ for $0<q<\sqrt 2-1$ and
that $|z_2|<1$ for $\sqrt 2-1<q<1$. Thus, if $q\ne \sqrt 2-1$ 
we get similarly to the above
\begin{align*}
[x^n]& F(x) \frac {\left( \frac{px}{1-qx} \right)^{k} - (qx)^k}
              {\frac{px}{1-qx}  - qx } =
\frac 1{2\pi i}
\int\limits_{|z|=x_0}  F(z) 
\frac {\left( \frac{pz}{1-qz} \right)^{k} - (qz)^k}
              {\frac{pz}{1-qz}  - qz }
\,\frac{dz}{z^{n+1}}\\ 
& =\frac 1{2\pi i}
\int\limits_{|z|=x_0}  F(z) \frac {\left( \frac{pz}{1-qz} \right)^{k}}
              {\frac{pz}{1-qz}  - qz } 
\,\frac{dz}{z^{n+1}} -\frac 1{2\pi i}
\int\limits_{|z|=x_0}  F(z) \frac {(qz)^k}
              {\frac{pz}{1-qz}  - qz }
\,\frac{dz}{z^{n+1}}\\ 
& =\frac 1{2\pi i}
\int\limits_{|z|=x_0}  F(z) \frac {\left( \frac{pz}{1-qz} \right)^{k}}
              {\frac{pz}{1-qz}  - qz } 
\,\frac{dz}{z^{n+1}}-\frac 1{2\pi i}
\int\limits_{|z|=1}  F(z) \frac {(qz)^k}
              {\frac{pz}{1-qz}  - qz }
\,\frac{dz}{z^{n+1}}\\ 
& = \OO\left( n^{-1/2} x_0^{-n}\left(
\frac{px_0}{1-qx_0} \right)^k\right) + \OO(q^k).
\end{align*}
Note that we just shifted the paths of integration in regions
of analyticity if $\eta$ is chosen sufficiently small such that
$|x_0-1|< |1-z_2|$. 

If $q = \sqrt 2-1$ then there are polar singularities at $z_2=-1$
after splitting the integral. However, the residues of the functions
involved (at $z=-1$) are both of order
\[
O\big((\sqrt 2-1)^k\big) = O(q^k),
\]
which implies that we get the same error term as in the case $q \ne \sqrt 2-1$.
$\qed$

\medskip

Note further
that (with a little bit more effort) we could have been much
more precise. However, the bound given by Lemma \ref{Le4} is 
sufficient for our purposes.

\begin{Le}\label{Le5}
For every $0<q<1$ there exist  $c>0$ and $\eta>0$
such that 
\begin{equation}\label{eqLe51}
\left|\, {\bf Pr}\{ H_n \le k \} - 
\sum_{l=0}^k {n-1\choose l} p^l q^{n-1-l}\, \right| 
= \OO\left( n^{-1/2}
\exp\left( - \frac cn \bigl(k-pn\bigr)^2
\right)\right)
\end{equation}
uniformly for $|k-pn|\le \eta n$  and
\begin{equation}\label{eqLe52}
\big|\, {\bf Pr}\{ |H_n - pn| \ge m \} \big| 
= \OO\left( 
\exp\Big( - c\frac {m^2}n \Big)\right)
\end{equation}
uniformly for $|m|\le \eta n$ as $n\to\infty$.
\end{Le}

{\it Proof.}
First we note that Lemma \ref{Le4} applies to the function
\[
\frac{(qx)^2}{1-qx} \frac{\left( \frac{px}{1-qx} \right)^{k} -(qx)^k}
 {\frac{px}{1-qx}  - qx }.
\]
The remaining error term
will  now be treated in the same way as in the proof of 
Lemma~\ref{Le4}:
\begin{align*} &[x^n] \Biggl(\frac{qx}{1-x} \left(
\frac{px}{1-qx} \right)
              \frac {\left( \frac{px)}{1-qx} \right)^{k} - (qx)^k}
              {\frac{px}{1-qx}  - qx } 
        + \frac{qx^2}{1-x} 
\left( \frac{px}{1-qx}\right)^{k+1}
             \frac{1-(qx)^k}{1-qx}\Biggr)\\
&=\frac 1{2\pi i}
\int\limits_{|z|=1-\varepsilon}\Biggl( \frac{qz}{1-z} 
\left( \frac{pz}{1-qz}
\right)              \frac {\left( \frac{pz}{1-qz} \right)^{k} - (qz)^k}
              {\frac{pz}{1-qz}  - qz }
-   \frac{qz^2}{1-z} \left( \frac{pz}{1-qz}
\right)^{k+1}  \frac{1-(qz)^k}{1-qz}\Biggr)
\,\frac{dz}{z^{n+1}} \\
&=\frac 1{2\pi i} \int\limits_{|z|=x_0}
\Biggl( \frac{qz}{1-z} \left( \frac{pz}{1-qz} \right)
              \frac {1}
              {\frac{pz}{1-qz}  - qz } 
  -  \frac{qz^2}{1-z}  \frac{pz}{1-qz}
\frac{1}{1-qz}\Biggr) \left( \frac{pz}{1-qz}\right)^{k}
\,\frac{dz}{z^{n+1}}\\
&\quad - \frac 1{2\pi i} \int\limits_{|z|=1-k^{-1}} 
\frac{qz}{1-z} \left( \frac{pz}{1-qz}
\right) \frac {(qz)^k}
              {\frac{pz}{1-qz}  - qz }
\,\frac{dz}{z^{n+1}} 
\\&\quad + \frac 1{2\pi i} \int\limits_{|z|=1-k^{-1}} 
 \frac{qz^2}{1-z} \left( \frac{pz}{1-qz}
\right)^{k+1}  \frac{(qz)^k}{1-qz}
\,\frac{dz}{z^{n+1}} \\
& =  \OO\left( n^{-1/2} x_0^{-n}\left(
\frac{px_0}{1-qx_0} \right)^k\right) + \OO(kq^k).
\end{align*}
Here we used the estimates 
\[
\max_{|z|=1-k^{-1}} \left| z^{k} \right| = \OO(1) 
\]
and
\[
\max_{|z|=1-k^{-1}} \left| \frac{pz}{1-qz} \right| = \OO(1).
\]
Finally observe that in the range $|k-pn|\le \eta n$ we surely have
\[
kq^k = \OO\left( n^{-1/2}
\exp\left( - \frac cn \bigl(k-pn\bigr)^2 
\right)\right)
\]
which completes the proof of (\ref{eqLe51}).

The proof of (\ref{eqLe52}) is now easy. We just have to combine a
proper tail estimate for the binomal distribution, i.\;e.
\[
\sum_{|l-pn|\ge m} {n-1\choose l} p^l q^{n-1-l} =
\OO\left( 
\exp\Big( - c\frac {m^2}n \Big)\right),
\]
with (\ref{eqLe51}).
$\qed$

\medskip

We are now able to complete the first part of
Theorem \ref{Th1}. It is well known that the distribution function of
the binomial distribution can be estimated by the distribution function
of the normal distribution up to a uniform error of order 
$\OO(n^{-1/2})$, i.\;e., as $n\to\infty$,
\begin{equation}\label{eq54}
\sup_{x\in{\RR}} \left|\, \sum_{l\le x} {n-1\choose l} p^l
q^{n-1-l}  - \Phi\left( \frac {l-pn}{\sqrt{pqn}} \right)\right|
= \OO(n^{-1/2}),
\end{equation}
compare with \cite[p.\ 542]{Fell}.


Furthermore, by (\ref{eqLe51}) we get a similar result for 
the distribution of $H_n$:
\begin{equation}\label{eq55}
\sup_{x\in{\RR}} \left|\,{\bf Pr}\{ H_n \le x \} - 
\sum_{l\le x} {n-1\choose l} p^l q^{n-1-l}  \right|
= \OO(n^{-1/2}).
\end{equation}
Note that (\ref{eqLe51}) provides (\ref{eq55}) just for $x$ with
$|x-pn|\le \eta n$. However, by (\ref{eqLe52}) we know that
\[
\big|\, {\bf Pr}\{ |H_n - pn| \ge \eta n \} \big| 
= \OO\left( 
\exp\left( - c\eta^2 n \right)\right).
\]
By the monotonicity of the distribution function this implies
that for $x$ with $|x-pn|\ge \eta n$ we also have
\[
\big|\, {\bf Pr}\{ |H_n - pn| \ge x \} \big| 
= \OO\left( 
\exp\left( - c\eta^2 n \right)\right).
\]
Thus (\ref{eq55}) follows. 

The first part of Theorem \ref{Th1}, i.\;e. (\ref{Th11}), is
now a trivial consequence of  (\ref{eq54}) and (\ref{eq55}).



\section{Convergence of Moments}

Lemmata \ref{Le2} and \ref{Le3}
can be easily used to get quite tight bounds for the expected value.
Note that
\begin{equation}\label{eqEH}
\sum_{n\ge 0} {\EE}\, H_n \, x^n  = 
\sum_{k\ge 0} \left( \frac 1{1-x} - y_k(x) \right)
\end{equation}

\begin{Le}\label{LeEH}
The expected value of $H_n$ can be bounded by
\begin{equation}\label{eqLeEH1}
pn - p \le  {\EE}\, H_n  \le pn + \OO\left( \frac 1p\right).
\end{equation}
\end{Le}

{\it Proof.}
Set 
\[
E(x) = \sum_{k\ge 0} \left( \frac 1{1-x} - y_k(x) \right).
\]
Then by (\ref{eqLe21}) we obtain
\begin{equation*}
E(x) \ge    \frac x{1-x} \sum_{k\ge 0} \left( \frac{px}{1-qx}
\right)^{k+1}=  \frac {px^2}{(1-x)^2},
\end{equation*}
which is also true on the level of coefficients.
Thus, we have
\[
{\EE}\, H_n  \ge p(n-1).
\]
Similarly we get the upper bound. From
\begin{align*}
E(x) &\le   \frac {px^2}{(1-x)^2}  + \frac{(qx)^2}{1-qx} \frac 1
              {\left( \frac{px}{1-qx} \right) - qx } 
\left( \frac 1{1- \frac{px}{1-qx}}  - \frac 1{1-qx} \right) \\
& \quad+ \frac{qx}{1-x} \left( \frac{px}{1-qx} \right)
              \frac 1 {\left( \frac{px}{1-qx} \right) - qx } 
\left( \frac 1{1-\frac{px}{1-qx}} - \frac 1{1-qx} \right) \\
& \quad- \frac{qx^2}{1-x} \frac {\left( \frac{px}{1-qx} \right)}{1-qx}
\left( \frac 1{1- \frac{px}{1-qx}} -  \frac 1{1- \frac{qx^2(1-q)}{1-qx}}
\right) \\
&=  \frac {px^2}{(1-x)^2}  + \frac{(qx)^2}{(1-x)(1-qx)} \\
& \quad+ \frac{pqx^2}{(1-x)^2(1-qx)}  - \frac{pqx^3}{(1-x)^2(1-qx)} + \frac{pqx^3}{(1-x)(1-qx)
\left( 1- \frac {pqx^2}{1-qx} \right) } \\
&=  \frac {px^2}{(1-x)^2}  + \frac{(qx)^2}{(1-x)(1-qx)}  + \frac{pqx^2}{(1-x)(1-qx)}  +\frac{pqx^3}{(1-x)
\left( 1- qx - pqx^2 \right) }
\end{align*}
we directly obtain
\[
{\EE}\, H_n  \le  pn + \OO\left( \frac 1p\right).
\]
This completes the proof of Lemma~\ref{LeEH}.
$\qed$

\medskip

Unfortunately it seems that we cannot prove similarly tight
estimates for the variance. However, we can obtain a
non--trivial result:

\begin{Le}\label{LeVH}
The variance of $H_n$ can be bounded by
\begin{equation}\label{eqLeVH1}
{\VV}\, H_n = pq n + \OO_q\left( n^{1/2} \log^2 n\right).
\end{equation}
\end{Le}

{\it Proof.}
If $F(x) = {\bf Pr}\{X\le x \}$ denotes the distribution function
of a random variable $X$ (of compact support) then the variance of $X$
can be represented by
\[
{\VV}\,X = 2 \int_{-\infty}^{{\EE} X} ({\EE} X - y) F(y)\, dy +
2 \int_{{\EE} X}^{\infty} (y-{\EE} X) (1-F(y))\, dy.
\]
We apply this formula for the height $H_n$ where we have very
precise estimates for ${\EE} H_n$ and its distribution function
$F_n(x) = {\bf Pr}\{H_n\le x \}$, compare with Lemma \ref{Le5}
and Lemma \ref{LeEH}.

Let $u\le \eta \sqrt n$ be a parameter to be defined later.
By applying Lemma \ref{Le5}
and Lemma~\ref{LeEH} we get
\begin{gather*}
2 \int_{0}^{{\EE} H_n - u\sqrt n} ({\EE} H_n - y) F_n(y)\, dy
= \OO\left( n e^{-cu^2} \right),\\
2 \int_{{\EE} H_n - u\sqrt n}^{{\EE} H_n} ({\EE} H_n - y) F_n(y)\, dy
= \frac{pqn}{2} + \OO\left( u^2 \sqrt n\, \right),
\\
2 \int_{{\EE} H_n}^{{\EE} H_n - u\sqrt n} (y-{\EE} H_n)
 (1-F_n(y))\, dy
= \frac{pqn}{2} + \OO\left( u^2 \sqrt n\, \right),\\
\intertext{and}
2 \int_{{\EE} H_n - u\sqrt n}^n (y-{\EE} H_n) (1-F_n(y))\, dy
= \OO\left( n e^{-cu^2} \right).
\end{gather*}
Choosing $u=\log^2 n$ gives the result.
$\qed$


 



\begin{thebibliography}{99}


\bibitem{DevR}  {\sc L.\ Devroye and B.\ Reed}, {\it On the variance 
of the height of random binary search trees\/},  
SIAM J.\ Comput. {\bf 24} (1995), 1157--1162. 

\bibitem{Drm1} {\sc M.\ Drmota}, 
{\it A bivariate asymptotic expansion of coefficients of powers
of generating functions\/},
{\it  Europ.\ J.\ Combinatorics}
{\bf  15}
(1994),
139--152.

\bibitem{Drm2} {\sc M.\ Drmota}, 
{\it The variance of  the  height of binary search trees\/}, 
 Theoret. Comput. Sci., to appear. 

\bibitem{DR2}  {\sc B.\ Reed}, {\it The height of a random
binary search tree\/},  J.\ Assoc.\ Comput.\ Mach., submitted.

\bibitem{Fell} {\sc W.\ Feller}, {\it An Introduction to Probability
Theory and Its Applications, Vol.\ II\/}, 2$^{nd}$ ed., J.\ Wiley, New York, 1971.


\bibitem{prodinger01}  {\sc H. Prodinger}, 
{\it 
A $q$--analogue of the path length of binary 
search trees\/}, Algorithmica, to appear, 2001.


\end{thebibliography}






\end{document}





