Explicit and asymptotic formulae for the expected values of the order statistics of the Cantor distribution

Arnold Knopfmacher^{a}, Helmut Prodinger^{b}

aDepartment of Computational & Applied Mathematics, Witwatersrand University, 2050, South Africa bDepartment of Algebra and Discrete Mathematics, Technical University of Vienna, A-1040 Vienna, Austria

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.

Key words: order statistics, alternating sums, Bernoulli numbers, Rice’s method

1. Introduction

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.

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.

Rather than speaking of the Cantor distribution we will interpret the recursion in terms of random strings c_{1} c_{2} c_{3} … where the

c_{i}’s ∈ {0, 1} are independently obtained by flips of a fair coin. Given a parameter ϕ with 0 < ϕ ≤ \frac{1}{2} we then consider the random variable T that maps c_{1} c_{2} c_{3} … to the real number

T (c_{1} c_{2} c_{3} …) = \frac{1 − ϕ}{ϕ} ∑_{i≥1} c_{i}ϕ^{i} ∈ [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} … < d_{1} d_{2} d_{3} … iff there is a k such that c_{i} = d_{i} for i = 1, …, 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}, …, 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}), …, T (w_{n}). Similarly let a_{n}^{(k)} denote the average value of the kth smallest number, 1 ≤ k ≤ n, with a_{n}^{(1)} ≡ a_{n}. The particular choice ϕ = \frac{1}{3} produces real numbers T (w_{i}) that belong to the Cantor set, hence the choice of name for the distributions.

Hosking (1994, equation 5) derives the following recursion for the expected minimum

(2^{n} − 2ϕ)a_{n} = 1 − ϕ + ϕ ∑_{k=1}^{n−1} \binom{n}{k} a_{k} , n ≥ 1 .  (1.1)

It is convenient to set a_{0} = 0.

To solve this recursion exactly, we follow the approach of Knuth (1973). Let A(z) = ∑_{n≥0} 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ϕA(z) = (1 − ϕ)(e^{z} − 1) + ϕ(e^{z}A(z) − A(z))

or

A(2z) = ϕ(1 + e^{z})A(z) + (1 − ϕ)(e^{z} − 1) .

Now introduce

Â(z) = \frac{1}{e^{z} − 1} A(z) = ∑_{n≥0} â_{n} z^{n}/n!

where we obtain the simpler equation

Â(2z) = ϕÂ(z) + \frac{1 − ϕ}{e^{z} + 1} .

Equating coefficients of \frac{z^{n}}{n!} on both sides leads to (Abramowitz and Stegun (1972, pp. 804-5))

2^{n}â_{n} = ϕâ_{n} − (1 − ϕ) \frac{B_{n+1}}{n + 1} (2^{n+1} − 1)

where B_{n} denotes a Bernoulli number defined by

∑_{n≥0} B_{n} z^{n}/n! = \frac{z}{e^{z} − 1} .

Therefore

â_{n} = −(1 − ϕ) \frac{B_{n+1}}{n + 1} \frac{2^{n+1} − 1}{2^{n} − ϕ} .

Now from the relation A(z) = (e^{z} − 1)Â(z) we obtain

a_{n} = ∑_{k=0}^{n−1} \binom{n}{k} â_{k} , n ≥ 1 ,

which yields the explicit formula

a_{n} = −(1 − ϕ) ∑_{k=0}^{n−1} \binom{n}{k} \frac{B_{k+1}}{k + 1} \frac{2^{k+1} − 1}{2^{k} − ϕ} .

It is convenient to rewrite this solution to Hosking’s recurrence in the form

a_{n} = −\frac{1 − ϕ}{n + 1} ∑_{k=1}^{n} \binom{n + 1}{k} B_{k} \frac{2^{k} − 1}{2^{k−1} − ϕ} .  (1.2)

It is interesting to note that in the limiting case ϕ = \frac{1}{2} this simplifies to

a_{n} = −\frac{1}{n + 1} ∑_{k=1}^{n} \binom{n + 1}{k} B_{k} = \frac{1}{n + 1} , n ≥ 1 ,

using the recurrence for the Bernoulli numbers

B_{n+1} = ∑_{k=0}^{n+1} \binom{n + 1}{k} B_{k} , B_{0} = 1 .

In the other limiting case ϕ = 0 we obtain from (1.2) (or immediately from (1.1)) the solution

a_{n} = \frac{1}{2^{n}} , n ≥ 1 .

2. Asymptotics

For the general case 0 < ϕ < \frac{1}{2}, (1.2) does not simplify further. Instead we show how to obtain an asymptotic expression for a_{n}. Consider the sum

S_{n} = ∑_{k=1}^{n−1} \binom{n}{k} B_{k} \frac{2^{k} − 1}{2^{k−1} − ϕ}

and note that a_{n} = −\frac{1−ϕ}{n+1} S_{n+1}. We express this sum as a contour integral (see e.g. Flajolet and Sedgewick (1994))

S_{n} = \frac{1}{2πi} ∫_{C} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)} (−zζ(1 − z)) \frac{2^{z} − 1}{2^{z−1} − ϕ} dz

where ζ(s) denotes Riemann’s zeta function and where C denotes a positively oriented curve that encircles the poles 1, 2, …, n−1 of the integrand and no other poles. The choice of integrand here is motivated in part by the result B_{k} = −kζ(1 − k)(−1)^{k} , k ≥ 1. 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{aligned}\frac{(−1)^{n−1}n!}{z(z − 1) ⋯ (z − n)} & = & \frac{Γ(n + 1)Γ(−z)}{Γ(n + 1 − z)} \\ & = & n^{z}Γ(−z) (1 + O (\frac{1}{n})) \end{aligned}

to produce the alternative representation,

S_{n} = \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞} n^{z}Γ(1 − z)ζ(1 − z) \frac{2^{z} − 1}{2^{z−1} − ϕ} dz · (1 + O (\frac{1}{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} − ϕ = 0

are candidates for poles. They are

z = 1 + log_{2} ϕ + χ_{k} , k ∈ Z with χ_{k} = \frac{2kπi}{log 2} .

The residue at such a point is

n^{1+log_{2} ϕ+χ_{k}}Γ(− log_{2} ϕ + χ_{k})ζ(− log_{2} ϕ + χ_{k}) \frac{2ϕ − 1}{ϕ log 2} .

Now note that

n^{χ_{k}} = e^{2kπi log_{2} n}

and define

δ(x) = ∑_{k≠0} Γ(− log_{2} ϕ + χ_{k})ζ(− log_{2} ϕ + χ_{k})e^{2kπix} .

This is a periodic function of x with period 1, mean 0 and a very small amplitude provided that ϕ is not too close to 0. Then for our sum S_{n} we have the asymptotic estimate

S_{n} = n^{1+log_{2} ϕ} \frac{2ϕ − 1}{ϕ log 2} \{Γ(− log_{2} ϕ)ζ(− log_{2} ϕ) + δ(log_{2} n)\} · (1 + O (\frac{1}{n}))

and consequently

a_{n} = n^{log_{2} ϕ} \frac{(1 − ϕ)(1 − 2ϕ)}{ϕ log 2}\{Γ(− log_{2} ϕ)ζ(− log_{2} ϕ) + δ(log_{2} n)\} (1 + O (\frac{1}{n})) . (2.1)

If we disregard the numerically small fluctuating term we can write

a_{n} ∼ n^{log_{2} ϕ} \frac{(1 − ϕ)(1 − 2ϕ)}{ϕ log 2} Γ(− log_{2} ϕ)ζ(− log_{2} ϕ) .  (2.2)

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 ϕ = \frac{1}{3} for which a_{n} ∼ \frac{c}{n^{log_{2} 3}} where c = 2\frac{Γ(log_{2} 3)ζ(log_{2} 3)}{3 log 2} = 1.99670497 ….

\begin{matrix}n & a_{n} & a_{n}(n + 1)^{log_{2} 3} \\ 20 & 0.0156734 & 1.95358 \\ 40 & 0.0054856 & 1.97436 \\ 60 & 0.00293339 & 1.98176 \\ 80 & 0.00187479 & 1.98532 \\ 100 & 0.001312296 & 1.98756 \\ 120 & 0.000994329 & 1.98915 \\ 140 & 0.000780667 & 1.9902 \\ 160 & 0.000632884 & 1.99095 \\ 180 & 0.000525843 & 1.99155 \\ 200 & 0.00044548 & 1.99208 \end{matrix}

Figure 1: Graph of a_{n} versus n in decreasing orders of magnitude for ϕ = 0.5, 0.4, 0.3, 0.2 and 0.1.

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} = \frac{1 − ϕ}{n + 1} \{2 + \frac{1 − 2ϕ}{ϕ} ∑_{k=1}^{n} \binom{n + 1}{k} \frac{B_{k}}{ϕ^{−1}2^{k−1} − 1}\}

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.

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)

na_{n−1}^{(k)} = (n − k)a_{n}^{(k)} + ka_{n}^{(k+1)} .

For example we have

\begin{matrix}a_{n}^{(2)} & = & a_{n} + n(a_{n−1} − a_{n}) = na_{n−1} − (n + 1)a_{n} + 2a_{n} \\ & = & −(1 − ϕ) ∑_{k=1}^{n−1} \binom{n}{k} B_{k} \frac{2^{k} − 1}{2^{k−1} − ϕ} + (1 − ϕ) ∑_{k=1}^{n} \binom{n + 1}{k} B_{k} \frac{2^{k} − 1}{2^{k−1} − ϕ} + 2a_{n} . \end{matrix} (2.3)

More generally David (1981, p.48) provides the exact formula

a_{n}^{(k)} = ∑_{j=0}^{k−1} \binom{n − j − 1}{n − k} \binom{n}{j} (−1)^{k−j−1}a_{n−j} .  (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)} ∼ c(k)a_{n} .

where

c(k) = ∏_{m=1}^{k−1} (1 − \frac{log_{2} ϕ}{m}) .

In the limiting case ϕ = \frac{1}{2}, we find by (2.4) and Vandermonde’s formula that

a_{n}^{(k)} = \frac{k}{n + 1} ,

which is intuitively clear, since ϕ = \frac{1}{2} 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 \frac{1}{n+1} .

The other limiting case ϕ = 0 means that we may choose only the points 0 or 1, both with probability \frac{1}{2}. We find

a_{n}^{(k)} = 2^{−n} ∑_{i=0}^{k−1} \binom{n}{i} ,

which can easily be proved from (2.4) by induction and has also an obvious interpretation.

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.

References

Abramowitz, M. and I.A. Stegun (1972), Handbook of Mathematical Functions, (Dover,

New York). David, H.A. (1981), Order Statistics (Wiley, New York, 2nd ed.). Flajolet, P. and R. Sedgewick (1994), Mellin transforms and asymptotics: Finite

differences and Rice’s integral, Theoret. Comput. Sci., to appear. Hosking, J.R.M. (1994), Moments of order statistics of the Cantor distribution, Statist.

Prob. Lett. 19, 161-165. Knuth, D.E. (1973), The Art of Computer Programming, Vol III (Addison-Wesley,

Reading MA, 2nd ed.). Prodinger, H. (1993), How to select a loser, Discrete Math. 120, 149-159. Szpankowski, W. (1988), The evaluation of an alternative sum with applications to the

analysis of some data structures, Inform. Proc. Lett. 28, 13-19.