\documentstyle[12pt]{report}
\setlength{\topmargin}{.5cm}
\setlength{\textheight}{22cm}
\setlength{\oddsidemargin}{.3cm}
\setlength{\textwidth}{16cm}
\setlength{\parskip}{8mm}
\setlength{\parindent}{0mm}
\setlength{\baselineskip}{8mm}
\newcommand{\un}{\underline}
\def\de{\delta}
\def\dsy{\displaystyle}
\def\bmZ{\mbox{\boldmath $Z$}}
\def\({\left(}
\def\){\right)}
\def\bc{\begin{center}}
\def\ec{\end{center}}
\def\ft{\footnotesize}
\def\ph{\phantom}
\def\nh{\null\hspace{.6cm}}
\def\G{\Gamma}
%\pagestyle{empty}
\renewcommand{\baselinestretch}{1.2}

\begin{document}
\bc{\large{\bf Explicit and asymptotic formulae for the expected values
of the order statistics of the Cantor distribution}}

 Arnold Knopfmacher$^{\ft{\rm a}}$, Helmut Prodinger$^{\ft{\rm b}}$

{\em{\scriptsize${}^{{\rm a}}$Department of Computational \& Applied
Mathematics, Witwatersrand University, 2050, South Africa\\
${}^{\rm b}$Department of Algebra and Discrete Mathematics, Technical
University of Vienna, A-1040 Vienna, Austria}}\ec

\hrule

{\ft{\bf Abstract}

We derive the exact solution to a recurrence relation obtained by
Hosking for the expected value of the minimum order statistic of the
Cantor distribution.  In addition, we indicate how an asymptotic
estimate can be derived for this and similar sums involving binomial
coefficients and Bernoulli numbers.

{\em Key words:}  order statistics, alternating sums, Bernoulli numbers,
Rice's method}\\ [.3cm]

\hrule
\vspace{.5cm}

{\bf 1. Introduction}

\hspace{.6cm}In a recent article Hosking (1994) studied the order
statistics of the Cantor distribution.  In particular he derived a
recurrence relation from which the average values
of the order statistics could be computed step by step.\\
\nh In this paper we derive an explicit solution to this recurence
relation as well as a simple asymptotic approximation to the exact
result.  In doing this we indicate a general approach that could be used
to solve other recurrence relations of a similar nature.\\
\nh Rather than speaking of the Cantor distribution we will interpret
the recursion in terms of {\em random strings} $c_1\,c_2\,c_3\ldots$ where the

$c_i$'s $\in \{0,1\}$ are independently obtained by flips of a fair coin.
Given a parameter $\phi$ with $0<\phi\leq{1\over2}$ we then consider the
random variable $T$ that maps $c_1\,c_2\,c_3\ldots$ to the real number
$$
T(c_1\,c_2\,c_3\ldots)={1-\phi\over\phi}\;\sum_{i\geq1}c_i\phi^i\;
\in[0,1]\;.
$$
The strings now have a natural order from the usual ordering of the real
numbers.  This is easily seen to be equivalent to the lexicographic
ordering of strings, i.e. $c_1\,c_2\,c_3\ldots<d_1\,d_2\,d_3\ldots$ iff
there is a $k$ such that $c_i=d_i$ for $i=1,\ldots, k-1$ and $c_k=0$
while $d_k=1$.  It thus makes sense to speak of order statistics for
strings.  Suppose that $n$ independent random strings $w_1,\ldots, w_n$
are produced by this process.  We denote by $a_n$ the average value of the
 minimum  of
the $n$ real numbers $T(w_1),\ldots, T(w_n)$.  Similarly let $a_n^{(k)}$
denote the average value of the $k$th smallest number, $1\leq k\leq n$,
with $a^{(1)}_n\equiv a_n$.  The particular choice $\phi={1\over 3}$
produces real numbers $T(w_i)$ that belong to the Cantor set, hence the
choice of name for the distributions.\\
\nh Hosking (1994, equation 5) derives the following recursion for the
expected minimum
$$
(2^n-2\phi)a_n=1-\phi+\phi\sum^{n-1}_{k=1}\left({n\atop k}\)a_k\;,\quad
n\geq 1\;.\eqno{(1.1)}
$$
It is convenient to set $a_0=0$.\\
\nh To solve this recursion exactly, we follow the approach of Knuth
(1973).  Let $A(z)=\sum_{n\geq0}a_n z^n/n!$ be the exponential
generating
function of the $a_n$'s.  Then (1.1) translates to the functional
equation
$$
A(2z)-2\phi A(z)=(1-\phi)(e^z-1)+\phi\bigl(e^zA(z)-A(z)\bigr)
$$
or
$$
A(2z)=\phi(1+e^z)A(z)+(1-\phi)(e^z-1)\;.
$$
Now introduce
$$
\hat A(z)={1\over e^z-1}\;A(z)=\sum_{n\geq0}\hat a_n\;z^n/n!
$$
where we obtain the simpler equation
$$
\hat A(2z)=\phi\hat A(z)+{1-\phi\over e^z+1}\;.
$$
Equating coefficients of ${z^n\over n!}$ on both sides leads to
(Abramowitz and Stegun (1972, pp. 804-5))
$$
2^n\hat a_n=\phi\hat a_n-(1-\phi)\;{B_{n+1}\over
n+1}\;\bigl(2^{n+1}-1\bigr)
$$
where $B_n$ denotes a Bernoulli number defined by
$$
\sum_{n\geq0}B_n\;z^n/n!={z\over e^z-1}\;.
$$
Therefore
$$\hat a_n=-(1-\phi)\;{B_{n+1}\over n+1}\;{2^{n+1}-1\over2^n-\phi}\;.
$$
Now from the relation $A(z)=(e^z-1)\hat A(z)$ we obtain
$$
a_n=\sum^{n-1}_{k=0}\({n\atop k}\)\hat a_k\;,\quad n\geq1\;,
$$
which yields the explicit formula
$$
a_n=-(1-\phi)\sum^{n-1}_{k=0}\({n\atop k}\)\;{B_{k+1}\over k+1}\;{2^{k+1}-
1\over 2^k-\phi}\;.
$$
It is convenient to rewrite this solution to Hosking's recurrence in the form
$$
a_n=-{1-\phi\over n+1}\;\sum^n_{k=1}\({n+1\atop
k}\)B_k\;{2^k-1\over2^{k-1} -\phi}\;.\eqno{(1.2)}
$$
It is interesting to note that in the limiting case  $\phi={1\over2}$ this
simplifies to
$$
a_n=-{1\over n+1}\;\sum^n_{k=1}\({n+1\atop k}\)B_k={1\over n+1}\;,\quad
n\geq 1\;,
$$
using the recurrence for the Bernoulli numbers
$$
B_{n+1}=\sum^{n+1}_{k=0}\({n+1\atop k}\)B_k\;,\quad B_0=1\;.
$$
\nh In the other limiting case $\phi=0$ we obtain from (1.2) (or immediately
from (1.1)) the solution
$$
a_n={1\over 2^n}\;,\quad n\geq 1\;.
$$
\vspace{.6cm}

{\bf 2. Asymptotics}

\hspace{.6cm} For the general case $0<\phi<{1\over2}$, (1.2) does not
simplify further.  Instead we show how to obtain an asymptotic expression for
$a_n$.  Consider the sum
$$
S_n=\sum^{n-1}_{k=1}\({n\atop k}\)B_k\;{2^k-1\over2^{k-1}-\phi}
$$
and note that $a_n=-{1-\phi\over n+1}\;S_{n+1}$.  We express this sum as a
contour integral (see e.g. Flajolet and Sedgewick (1994))
$$
S_n={1\over2\pi i}\;\int_{\cal C}\;{(-1)^nn!\over z(z-1)\cdots(z-n)}\;\bigl(
-z\zeta(1-z)\bigr)\;{2^z-1\over2^{z-1}-\phi}\;d z
$$

where $\zeta(s)$ denotes Riemann's zeta function and where $\cal C$ denotes a
positively oriented curve that encircles the poles $1,2,\ldots,n-1$ of
the integrand and no other poles.  The choice of integrand here is
motivated in part by the result $B_k=-k\zeta(1-k)(-1)^k\;,\quad k\geq1$.
The name commonly used for this approach is ``Rice's method''.
Szpankowski (1988) noted that one can change the path of integration
above and in addition use the relation
$$\begin{array}{rcl}
\dsy{(-1)^{n-1}n!\over z(z-1)\cdots(z-n)}&=&\dsy{\G(n+1)\G(-z)\over\G(n+1-z)}
\\
[.5cm]
&=&\dsy n^z\G(-z)\(1+{\it O}\({1\over n}\)\)\end{array}
 $$
to produce the alternative representation,
$$
S_n={1\over2\pi i}\int^{{1\over2}+i\infty}_{{1\over2}-i\infty} n^z\G(1-z)
\zeta(1-z)\;{2^z-1\over2^{z-1}-\phi}\;d z\cdot\(1+{\it O}\({1\over
n}\)\)\;. $$
Shifting the line of integration to the left and collecting the residues
will yield the asymptotic expansion.  The pole of the zeta function at
$z=0$ is cancelled by the factor $2^z-1$, so only the solutions of the
equation
$$
2^{z-1}-\phi=0
$$
are candidates for poles. They are\\ [.3cm]
$$
z=1+\log_2\phi+\chi_k\;,\quad k\in\bmZ\quad
\mbox{with}\quad\chi_k=\dsy{2k\pi i\over\log 2}\;.
$$
The residue at such a point is
$$
n^{1+\log_2\phi+\chi_k}\G(-\log_2\phi+\chi_k)\zeta(-\log_2\phi+\chi_k)\;
{2\phi-1\over\phi\log2}\;.
$$
Now note that
$$
n^{\chi_k}=e^{2k\pi i\log_2n}
$$
and define
$$
\de(x)=\sum_{k\neq0}\G(-\log_2\phi+\chi_k )\zeta(-\log_2\phi+\chi_k )
e^{2k\pi i x}\;.
$$
This is a periodic function of $x$ with period 1, mean 0 and a very small
amplitude  provided that $\phi$ is not too close to 0.  Then for our sum
$S_n$ we have the asymptotic estimate
$$
S_n=n^{1+\log_2\phi}\;{2\phi-1\over\phi\log2}\;\Bigl\{\G(-\log_2\phi)\zeta
(-\log_2\phi)+\de(\log_2n)\Bigr\}\cdot\(1+{\it O}\({1\over n}\)\)
$$
and consequently
$$
a_n=n^{\log_2\phi}\;{(1-\phi)(1-2\phi)\over\phi\log2}\Bigl\{\G(-\log_2\phi)
\zeta(-\log_2\phi)+\de(\log_2n)\Bigr\}\(1+{\it O}\({1\over
n}\)\)\;.\eqno{(2.1)} $$
If we disregard the numerically small fluctuating term we can write
$$
a_n\sim n^{\log_2\phi}\;{(1-\phi)(1-2\phi)\over\phi\log2}\;\G(-\log_2\phi)
\zeta(-\log_2\phi)\;.\eqno{(2.2)}
$$
\nh In the table  below we compare the approximation (2.2) to the
exact value for $a_n$ obtained from the recursion (1.1) in the `classical'
case $\phi={1\over3}$ for which $a_n\sim{c\over n^{\log_23}}$ where
$c=2{\G(\log_23)\zeta(\log_23)\over 3\log 2}=1.99670497\ldots$ .

\bc\begin{tabular}{|r|l|c|}\hline
\multicolumn{1}{|c|}{$n$}&\multicolumn{1}{|c|}{\quad$a_n$\quad}&
$a_n(n+1)^{\log_23}$\\ \hline\hline
20&\quad0.0156734\quad  &1.95358\\
40&\quad0.0054856\quad  &1.97436\\
60&\quad0.00293339\quad &1.98176\\
80&\quad0.00187479\quad &1.98532\\
100&\quad0.001312296\quad&1.98756\\
120&\quad0.000994329\quad&1.98915\\
140&\quad0.000780667\quad&1.9902\ph{6}\\
160&\quad0.000632884\quad&1.99095\\
180&\quad0.000525843\quad&1.99155\\
200&\quad0.00044548\quad&1.99208\\ \hline\end{tabular}\ec
\vspace*{10cm}

\begin{description}
\item[Figure 1:] Graph of $a_n$ versus $n$ in decreasing orders of magnitude
for $\phi=0.5,\;0.4,\;0.3,$ $0.2$ and $0.1$.
\end{description}

\nh Another (possibly more complicated) method of producing this result can
be found in the classical book of Knuth (1973).  In addition by manipulating
the explicit solution (1.2) for $a_n$ we can rewrite it in the form
$$
a_n={1-\phi\over n+1}\;\left\{2+{1-2\phi\over\phi}\;\sum^n_{k=1}\({n+1\atop
k}\)\;{B_k\over\phi^{-1}2^{k-1}-1}\right\}
$$
to which the general result of Prodinger (1993, Theorem 20) is applicable
and again yields (2.2).  However this particular theorem unlike the method
above would not necessarily apply to other similar recursions of this type.\\
\nh It is worthwhile to note that explicit formulas for $a_n^{(k)}$ for $k$
fixed can now be deduced from (1.2) with the aid of the recurrence Hosking
(1994, equation 6)
$$
n a^{(k)}_{n-1}=(n-k)a^{(k)}_n+ka^{(k+1)}_n\;.
$$
For example we have\\ [.5cm]
$\begin{array}{lcl}
a^{(2)}_n&=&a_n+n(a_{n-1}-a_n)=n a_{n-1}-(n+1)a_n+2a_n\\ [.5cm]
&=&\dsy-(1-\phi)\sum^{n-1}_{k=1}\({n\atop k}\)B_k\;
{2^k-1\over 2^{k-1}-\phi}+(1-\phi)\sum^n_{k=1}\({n+1\atop k}\)B_k\;
{2^k-1\over2^{k-1}-\phi}+2a_n\;. \end{array}\hfill (2.3)
$\\ [.5cm]
More generally David (1981, p.48) provides the exact formula
$$
a^{(k)}_n=\sum^{k-1}_{j=0}\({n-j-1\atop n-k}\)\({n\atop j}\)(-1)^{k-j-1}
a_{n-j}\;.\eqno{(2.4)}
$$
Using (2.4), it is possible to obtain asymptotics for $a_n(k)$, for every
fixed $k$, in the same manner as for $a_n$.  We obtain (apart from the
fluctuations)
$$
a_n^{(k)}\sim c(k)a_n\;.
$$
where
$$
c(k)=\prod^{k-1}_{m=1}\(1-{\log_2\phi\over m}\)\;.
$$
\nh In the limiting case $\phi={1\over2}$, we find by (2.4) and {\em
Vandermonde's formula} that
$$
a_n^{(k)}={k\over n+1}\;,
$$
which is intuitively clear, since $\phi={1\over2}$ means that we have the
uniform distribution over $[0,1]$, and a random sample of $n$ points will
typically dissect the interval $[0,1]$ into $n+1$ subintervals of
length ${1\over n+1}\;.$\\
\nh The other limiting case $\phi=0$ means that we may choose only the
points 0 or 1, both with probability ${1\over2}$.  We find
$$
a_n^{(k)}=2^{-n}\sum^{k-1}_{i=0}\({n\atop i}\)\;,
$$
which can easily be proved from (2.4) by induction and has also an obvious
interpretation.
\newpage


{\bf Acknowledgement}

The second author wishes to thank the Centre for
Applicable Analysis and Number Theory, University of Witwatersrand, for the
opportunity to visit in September 1994.  The research for this article was
carried out during this period.\\ [.5cm]

{\bf References}

Abramowitz, M. and I.A. Stegun (1972), {\em Handbook of Mathematical
Functions}, (Dover,\break
\nh New York).\\
David, H.A. (1981), {\em Order Statistics} (Wiley, New York, 2nd ed.).\\
Flajolet, P. and R. Sedgewick (1994), Mellin transforms and asymptotics:
Finite\break
\nh differences and Rice's integral, {\em Theoret. Comput. Sci.,}
to appear.\\
Hosking, J.R.M. (1994), Moments of order statistics of the Cantor
distribution, {\it Statist.\break
\nh Prob. Lett. {\bf19}}, 161-165.\\
Knuth, D.E. (1973), {\em The Art of Computer Programming}, Vol III
(Addison-Wesley,\break
\nh Reading MA, 2nd ed.).\\
Prodinger, H. (1993), How to select a loser, {\em Discrete Math. {\bf120}},
149-159.\\
Szpankowski, W. (1988), The evaluation of an alternative sum with
applications to the\break
\nh analysis of some data structures, {\em Inform.
Proc. Lett. {\bf28}}, 13-19.


\end{document}

