(q, δ)-NUMERATION SYSTEMS WITH MISSING DIGITS

FRÉDÉRIQUE BASSINO^{†} AND HELMUT PRODINGER^{†}

Abstract. We consider the (q, δ) numeration system, with basis q ≥ 2 and the set of digits {δ, δ + 1, …, q + δ − 1} where −(q − 1) ≤ δ ≤ 0. We study properties of numbers where some digits do not occur. This is analogous to the Cantor set {0.a_{1}a_{2} ⋯ | a_{i} ∈ {0, 2}}.

We compute an asymptotic equivalent of the nth moment of the “Cantor (q, D)– distribution” which can be described as the numbers 0.w_{1}w_{2} … with w_{i} ∈ D ⊆ {δ, …, q +δ −1}, and each such letter can occur with the same probability 1/CardD.

Furthermore, we consider n random strings according to this distribution and the expected minimum of them. We find a recursion which we solve asymptotically.

1. Introduction

We consider the (q, δ) numeration system, with basis q ≥ 2 and the set of digits {δ, δ + 1, …, q + δ − 1} where −(q − 1) ≤ δ ≤ 0.^{1} Every real number x has an essentially unique^{2} representation

x = ∑_{k≤n} a_{k}q^{k}

with a_{k} ∈ {δ, δ + 1, …, q + δ − 1}. In particular, we are interested in properties of numbers where some digits do not occur. This is analogous to the Cantor set, which can be described as

{0.a_{1}a_{2} ⋯ | a_{i} ∈ {0, 2}}.

The Cantor distribution with parameter ϑ, 0 < ϑ ≤ \frac{1}{2}, was introduced in [11] by the random series

\frac{ϑ̄}{ϑ} ∑_{i≥1} X_{i}ϑ^{i} ,

where the X_{i} are independent with the distribution

ℙ\{X_{i} = 0\} = ℙ\{X_{i} = 1\} = \frac{1}{2} ,

Date: November 6, 2002. 1991 Mathematics Subject Classification. Primary: 11A63, 11K16; Secondary: 60C05. Key words and phrases. Digits, Depoissonization, Mellin Transform, Asymptotic Expansion,

Moments.

†This author was supported by the CNRS/NRF-project n^{o}10959. Part of this work was done during the first author’s visit to the John Knopfmacher Centre for

Applicable Analysis and Number Theory at the University of the Witwatersrand, Johannesburg, South Africa.

1Often, the letter d is used instead of δ. In this paper, however, we need the letter d for other purposes.

2Some numbers have two representations, which is the analogue of 1 = 0.999 ….

and ϑ̄ = 1 − ϑ. The name stems from the instance ϑ = \frac{1}{3}, since then exactly those numbers from the interval [0, 1] appear that have a ternary expansion solely consisting of the digits 0 and 2.

The moments of this distribution where considered in [11], and, more recently in [5], where an asymptotic formula for the nth moment was derived using a combination of analytic techniques, notably depoissonization (“de-Poissonization”) and Mellin transforms.

In the first part of the present paper we derive analogous results: Let D be a (given) subset of the set of digits {δ, δ + 1, …, q + δ − 1}; we set d = CardD and D = {d_{1} < d_{2} < … < d_{d}}.

We consider infinite (random) words w_{1}w_{2} … over the alphabet D = {d_{1}, d_{2}, …, d_{d}} and a mapping value, defined by

value(w_{1}w_{2} …) = ∑_{i≥1} w_{i}q^{−i} .

Each letter can appear with probability \frac{1}{d}.

In this way we obtain a probability distribution on the interval [δ/(q−1), δ/(q−1)+1], which we will call the Cantor–(q, D) distribution. In Section 2 we study its moments.

Another interesting topic related to the Cantor distribution was introduced in [6]; one assumes that n (independent) elements are drawn according to the Cantor distribution. One is interested in the expected value of the minimum of them. Hosking gave a recursion for these expectations, which was eventually solved in [9], both exactly and asymptotically. For the exact solution (involving Bernoulli numbers) a neat trick of Knuth’s was essential; for the asymptotics one could then rely on Rice’s method [3].

In Section 4 we are going to solve the analogous question in our model of the (q, δ)– system with allowed set of digits D. Unfortunately, the nice trick does no longer work in this more general case, and we thus have to use the technique of depoissonization; for more details about this technique, one can refer to [7] and [13]; the present approach is modelled after the analysis in [8], which is also covered in [7] and [13].

2. The Moments

Observe the recursion formula, valid for all i ∈ {1, …, d}

value(d_{i}w) = d_{i} · q^{−1} + q^{−1} · value(w) .  (2.1)

Here, dw is the concatentation of the digit d and the infinite string w; denote the set of all infinite strings by W. From the self–similarity of the measure, we can derive a recursion for the moments M_{n} as follows:

M_{n} = ∑_{w∈W} (value(w))^{n}

= \frac{1}{dq^{n}} ∑_{i=0}^{d} ∑_{w∈W} (d_{i} + value(w))^{n}

= \frac{1}{dq^{n}} ∑_{i=0}^{d} ∑_{j=0}^{n} \binom{n}{j}d_{i}^{n−j}M_{j}.

It can be made explicit by isolating the term M_{n}:

M_{n} = \frac{d^{−1}q^{−n}}{1 − q^{−n}} ∑_{i=1}^{d} ∑_{j=0}^{n−1} d_{i}^{n−j}\binom{n}{j}M_{j}.

This recursion could be used to compute a list of the first few moments.

Theorem 1. The moments of the Cantor–(q, D) distribution satisfy the following recursion: M_{0} = 1 and for n ≥ 1

M_{n} = \frac{1}{d(q^{n} − 1)} ∑_{j=0}^{n−1} ∑_{i=1}^{d} d_{i}^{n−j}\binom{n}{j}M_{j}.

For instance

M_{1} = \frac{1}{d(q − 1)} ∑_{i=1}^{d} d_{i},

M_{2} = \frac{1}{d(q^{2} − 1)} ∑_{i=1}^{d} d_{i}^{2} + \frac{1}{d^{2}(q − 1)^{2}(q + 1)}( ∑_{i=1}^{d} d_{i})^{2},

Variance = M_{2} − M_{1}^{2} = \frac{1}{d(q^{2} − 1)} ∑_{i=1}^{d} d_{i}^{2} − \frac{q}{d^{2}(q − 1)^{2}(q + 1)}( ∑_{i=1}^{d} d_{i})^{2}.

(2.2)

3. The Asymptotic Behaviour of the Moments

The next problem is to investigate the asymptotic behaviour of the moments M_{n}, as n → ∞. Remember that this investigation for the classical case was done in [5].

A rough estimation shows us that the moments decrease exponentially. Indeed, if we set M_{n} ≈ λ^{−n}, we might infer that λ = (q − 1)/d_{M}, where d_{M} is the digit of maximal modulus in D.

First, we assume that there is only one digit of maximal modulus; without loss of generality we may further assume that it is positive, since otherwise we would have simply to multiply the moments by (−1)^{n} and work with the set of digits −D instead.

We set

m_{n} := M_{n} · λ^{n}

and show that this sequence has nicer properties. It satisfies the modified recurrence

m_{n} = \frac{1}{d(q^{n} − 1)} ∑_{i=1}^{d} ∑_{j=0}^{n−1} \binom{n}{j}(λd_{i})^{n−j}m_{j} .

To study this sequence further, we rewrite it as

m_{n} · d(q^{n} − 1) = ∑_{i=1}^{d} ( ∑_{j=0}^{n} \binom{n}{j}(λd_{i})^{n−j}m_{j} − m_{n})

or

m_{n} = \frac{1}{dq^{n}} ∑_{i=1}^{d} ∑_{j=0}^{n} \binom{n}{j}(λd_{i})^{n−j}m_{j}

and note that this holds for all n ≥ 0. Then we introduce the exponential generating function

m(z) = ∑_{n≥0} m_{n} \frac{z^{n}}{n!}

and get

m(z) = \frac{1}{d} ∑_{i=1}^{d} e^{d_{i}λ \frac{z}{q}} m(\frac{z}{q} ) = ∏_{k≥1} \frac{∑_{i=1}^{d} e^{zd_{i}λ/q^{k}}}{d} .

As in [5], we have to consider the Poisson transformed function m̂(z) = e^{−z}m(z), which satisfies the functional equation

m̂(z) = \frac{1}{d} ∑_{i=1}^{d} e^{\frac{z}{q} (d_{i}λ+1−q)} m̂(\frac{z}{q} ) .  (3.1)

This functional equation (3.1) can also be solved by iteration:

m̂(z) = ∏_{k≥1} \frac{∑_{i=1}^{d} e^{z(d_{i}λ+1−q)/q^{k}}}{d} .

However, this product is not too useful, and we have to go back to the functional equation.

The next step is to consider the behaviour of m̂(z) for z → ∞. The reason is that m_{n} ∼ m̂(n). The justification for this is a technique called depoissonization.

The general references for that are [7] and [13]. We follow [5], where the technique is explained in more detail. The idea is roughly as follows: One extracts the coefficients m_{n} of m(z) via Cauchy’s integral formula taking a circle of radius n and uses Stirling’s formula for the approximation of the quantity n!/n^{n} which occurs.

It is suggestive to use a new name R(z) for \frac{1}{d} ∑_{i≠M} e^{\frac{z}{q} (d_{i}λ+1−q)}m̂(\frac{z}{q}) and consider it to be an auxiliary (and known) function;

m̂(z) = \frac{1}{d}m̂(\frac{z}{q} ) + R(z) .  (3.2)

We compute the Mellin transform of (3.2) (see [2] for definitions and properties);

m̂^{∗}(s) = \frac{q^{s}}{d} m̂^{∗}(s) + R^{∗}(s) = \frac{R^{∗}(s)}{1 − \frac{q^{s}}{d}} .

The function m(z) can be recovered from this by Mellin’s inversion formula,

m̂(z) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} \frac{R^{∗}(s)}{1 − \frac{q^{s}}{d}} z^{−s} ds ,

where 0 < c < log_{q} d. By shifting the integral to the right and taking the negative residues into account, we get the desired asymptotic behaviour of m̂(z). There are simple poles at s = log_{q} d + \frac{2kπi}{log q}, k ∈ ℤ. The negative residue there is

\frac{1}{log q} R^{∗}( log_{q} d + \frac{2kπi}{log q}) z^{− log_{q} d− \frac{2kπi}{log q}} .

The value for k = 0 is of special interest; it is, to make it more explicit,

\frac{1}{log q} z^{− log_{q} d} ∫_{0}^{∞} \frac{1}{d} ∑_{i≠M} e^{\frac{z}{q} (d_{i}λ+1−q)} m̂(\frac{z}{q} ) z^{log_{q} d−1} dz .

Traditionally, one collects all the terms into a periodic function.

Theorem 2. The nth moment M_{n} of the Cantor–(q, D) distribution has for n → ∞ the following asymptotic behaviour

M_{n} = (\frac{d_{M}}{q − 1})^{n}Φ(− log_{q} n) n^{− log_{q} d}(1 + O(\frac{1}{n})) ,

where Φ(x) is a periodic function with period 1 and known Fourier coefficients. The mean (zeroth Fourier coefficient) is given by

\frac{1}{log q} ∫_{0}^{∞} \frac{1}{d} ∑_{i≠M} e^{\frac{z}{q} (d_{i}λ+1−q)} m̂(\frac{z}{q} ) z^{log_{q} d−1} dz .

This integral can be computed numerically by replacing m̂(\frac{z}{q}) by the first few values of its Taylor expansion, which can be obtained by iterating the recurrence for the numbers m_{n}.

Example. We consider q = 5 and D = \{−1, 1, 3\}, so d = 3, d_{M} = 3, and λ = \frac{4}{3}. Then

m_{n} = \frac{1}{3(5^{n} − 1)} ∑_{j=0}^{n−1} \binom{n}{j}((−\frac{4}{3})^{n−j} + (\frac{4}{3})^{n−j} + 4^{n−j})m_{j} .

So we replace R(z) by

R^{approx} = \frac{1}{3}(e^{−16z/15} + e^{−8z/15}) e^{−z/5} (1 + \frac{1}{20}z + \frac{1}{288}z^{2} + \frac{19}{144000}z^{3} + \frac{5887}{1347840000}z^{4} + …)

and compute

\frac{1}{log 5} ∫_{0}^{∞} R^{approx} z^{log 3/ log 5−1} dz = 0.59896 ….

We find M_{100} (\frac{4}{3})^{100} 100^{log 3/ log 5} ≈ 0.60351. The reason that this works is as follows: The radius of convergence of m(z) is infinity, so we replace it by its Taylor series. It is multiplied by terms of the form e^{−z} and integrated from 0 to ∞; to have any degree of accuracy, we can integrate from 0 to K, say, and throw in enough terms of the Taylor series. Maple evaluates the integral as a finite sum of Gamma functions.

The case when −d_{1} = d_{d} requires special care. If one has e. g. a symmetric set of digits D, then all odd moments vanish. A similar phenomenon occurs if the largest positive and negative digits coincide. Depoissonization, as it is described in [7] and in [13], does not cover this instance. But one could just extract coefficients n![z^{n}]m(z) via Cauchy’s integral formula using as the path of integration a circle of radius n. We have

n![z^{n}]m(z) = \frac{1}{2πi} ∫_{|z|=n} \frac{m(z)}{z^{n+1}}dz.

After a separation of the integral between positive and negative half plane and a change of variable in the second term of the sum, we get

n![z^{n}]m(z) = \frac{n!}{2πi} ∫_{|z|=n,ℜz≥0} \frac{m(z)}{z^{n+1}}dz + (−1)^{n} \frac{1}{2πi} ∫_{|z|=n,ℜz≥0} \frac{m(−z)}{z^{n+1}}dz.

We now use the fact that the saddle point in the integral

\frac{n!}{2πi} ∫_{C} \frac{e^{z}}{z^{n+1}} dz = 1

lies at z = n + O(1). For more details about the saddle point method, one can refer to [1] or to [10]. As m(z) = e^{z}(e^{−z}m(z)) where

e^{−z}m(z) = ∏_{k≥1} \frac{∑_{i=1}^{d} e^{z(d_{i}λ+1−q)/q^{k}}}{d}

is bounded, the previous saddle point is asymptotically not affected by multiplying e^{z} by this infinite product. Thus we get

\frac{n!}{2πi} ∫_{|z|=n,ℜz≥0} \frac{m(z)}{z^{n+1}}dz ∼ e^{−n}m(n)(1 + O(\frac{1}{n})),

and similarly

\frac{n!}{2πi} ∫_{|z|=n,ℜz≥0} \frac{m(−z)}{z^{n+1}}dz ∼ e^{−n}m(−n)(1 + O(\frac{1}{n})).

Compare [4] for such an approach.

We next study both terms of the sum by making use of the Mellin transform as in the previous instance.

Theorem 3. In the instance of two dominant digits d_{1}, d_{d}, with −d_{1} = d_{d} = d_{M}, the nth moment M_{n} of the Cantor–(q, D) distribution has for n → ∞ the following asymptotic behaviour

M_{n} = (\frac{d_{M}}{q − 1})^{n}[Φ_{1}(− log_{q} n) + (−1)^{n}Φ_{2}(− log_{q} n)] n^{− log_{q} d}(1 + O(\frac{1}{n})) ,

where Φ_{1}(x) and Φ_{2}(x) are periodic functions with period 1 and known Fourier coefficients. The means (zeroth Fourier coefficients) are given by

\frac{1}{log q} ∫_{0}^{∞} \frac{1}{d} ∑_{i≠d} e^{\frac{z}{q} (d_{i}λ+1−q)} e^{−z/q} m(\frac{z}{q} ) z^{log_{q} d−1} dz,

\frac{1}{log q} ∫_{0}^{∞} \frac{1}{d} ∑_{i≠1} e^{\frac{z}{q} (−d_{i}λ+1−q)} e^{−z/q} m(\frac{−z}{q} ) z^{log_{q} d−1} dz,

respectively.

While the even moments are always positive, the sign of the odd ones depends on the largest (in modulus) digit d_{i} ∈ D such that not both d_{i} and −d_{i} are in D.

Example. We consider q = 7 and D = {−3, 2, 3}, so d = 3, d_{M} = 3, and λ = 2. Then

m_{n} = \frac{1}{3(7^{n} − 1)} ∑_{j=0}^{n−1} \binom{n}{j}((−6)^{n−j} + 4^{n−j} + 6^{n−j})m_{j} .

So we replace R(z) by

R^{approx} = \frac{1}{3}(e^{−12z/7} + e^{−2z/7}) e^{−z/7} (1 + \frac{1}{63}z + \frac{101}{63504}z^{2} + \frac{251}{32577552}z^{3} + …)

and compute

\frac{1}{log 7} ∫_{0}^{∞} R^{approx} z^{log 3/ log 7−1} dz = 0.63967 ….

This is the first contribution; call it C_{1}. Now we do the same for the set of digits −D = {−3, −2, 3}. Then we use

R^{approx} = \frac{1}{3}(e^{−12z/7} + e^{−10z/7}) e^{−z/7} (1 − \frac{1}{63}z + \frac{101}{63504}z^{2} − \frac{251}{32577552}z^{3} + …)

and find

\frac{1}{log 7} ∫_{0}^{∞} R^{approx} z^{log 3/ log 7−1} dz = 0.39769 ….

This is the second contribution; call it C_{2}.

We find M_{100} 2^{100} 100^{log 3/ log 7} ≈ 1.04057; this is close to C_{1} + C_{2} = 1.03737. On the other hand, M_{99} 2^{99} 99^{log 3/ log 7} ≈ 0.26770; this is to be compared with C_{1} − C_{2} = 0.24197.

4. Expected value of the minimum order statistic of the (q, D)–distribution

We consider random strings c_{1} c_{2} c_{3} … where the c_{i}’s ∈ D = {d_{1} < d_{2} < ⋯ < d_{d}} are equally likely. We then consider the random variable value that maps c_{1} c_{2} c_{3} … to the real number

value(c_{1} c_{2} c_{3} …) = ∑_{i≥1} c_{i}q^{−i} ∈ [\frac{d_{1}}{q − 1}, \frac{d_{d}}{q − 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} … < c′_{1} c′_{2} c′_{3} … iff there is a k such that c_{i} = c′_{i} for i = 1, …, k − 1 and c_{k} < c′_{k}. It thus makes sense to speak of order statistics for strings. Suppose that n independent random strings w_{1}, …, w_{n} are produced. We denote by a_{n} the average value of the minimum of the n real numbers value(w_{1}), …, value(w_{n}). We derive the following recursion for the expected minimum

a_{n} = \frac{1}{qd^{n}} [ ∑_{i=1}^{d−1} ( ∑_{k=1}^{n} \binom{n}{k}(d − i)^{n−k}(d_{i} + a_{k})) + d_{d} + a_{n}] , n ≥ 1 ,

or

(d^{n}q − d)a_{n} = ∑_{i=1}^{d} [(d − i + 1)^{n} − (d − i)^{n}]d_{i} + ∑_{k=1}^{n−1} ∑_{i=1}^{d−1} \binom{n}{k}(d − i)^{n−k}a_{k} , n ≥ 1 .

This recursion is obtained by considering the smallest digit d_{i} that at least one of the n random strings has in its first position. The minimum value will be one of these, and be determined recursively; the first position adds the quantity \frac{d_{i}}{q} to the recursively determined minimum.

Now, if n is large, it is almost certain that there is a string starting with d_{1}d_{1}d_{1} … among the n random strings, producing the minimal value (in the limit) \frac{d_{1}}{q−1}. Remember that in the classical Cantor case d_{1} = 0, and the question was to analyze how fast a_{n} approaches zero. In order to obtain meaningful results, we define α_{n} := a_{n} − \frac{d_{1}}{q−1} and rewrite the recursion:

(d^{n}q−d)(α_{n}+\frac{d_{1}}{q − 1}) = ∑_{i=1}^{d} [(d−i+1)^{n}−(d−i)^{n}]d_{i}+∑_{k=1}^{n−1} ∑_{i=1}^{d−1} \binom{n}{k}(d−i)^{n−k}(α_{k}+\frac{d_{1}}{q − 1})

or

(d^{n}q − d)α_{n} = −(d − 1)^{n}d_{1} + ∑_{i=2}^{d} [(d − i + 1)^{n} − (d − i)^{n}]d_{i} + ∑_{k=1}^{n−1} ∑_{i=1}^{d−1} \binom{n}{k}(d − i)^{n−k}α_{k}.

Then we introduce the exponential generating function (with α_{0} := 0)

a(z) = ∑_{n≥0} α_{n} \frac{z^{n}}{n!}

and get

qa(dz) − da(z) = (1 − e^{(d−1)z})d_{1} + ∑_{i=2}^{d} (e^{(d−i+1)z} − e^{(d−i)z})d_{i} + ∑_{i=1}^{d−1} (e^{(d−i)z} − 1)a(z),

or

a(dz) = \frac{1}{q}(\frac{1 − e^{dz}}{1 − e^{z}} )a(z) + \frac{d_{1}}{q} (1 − e^{(d−1)z}) + \frac{1}{q} ∑_{i=1}^{d} (e^{(d−i+1)z} − e^{(d−i)z})d_{i}.

We have to consider the Poisson transformed function â(z) = e^{−z}a(z), which satisfies the functional equation

â(dz) = \frac{1}{q}(\frac{1 − e^{−dz}}{1 − e^{−z}} )â(z) + \frac{d_{1}}{q} (e^{−dz} − e^{−z}) + \frac{1}{q}(e^{z} − 1) ∑_{i=2}^{d} e^{−iz}d_{i} .

The next step is to consider the behaviour of â(z) for z → ∞. The reason is that α_{n} ∼ â(n). The justification for this is again the technique of depoissonization. We set

b(z) = \frac{1 − e^{−dz}}{1 − e^{−z}} and ϕ(z) = ∏_{j=0}^{∞} b(zd^{j}) = \frac{1}{1 − e^{−z}}

and

c(z) = \frac{d_{1}}{q} (e^{−z} − e^{−z/d}) + \frac{1}{q}(e^{z/d} − 1) ∑_{i=2}^{d} e^{−iz/d}d_{i}.

We then get

â(z) = ∑_{n=0}^{∞} q^{−n} c(q^{−n}z) ∏_{k=1}^{n} b(q^{−k}z).

As â(0) = 0, we finally obtain

â(z)ϕ(z) = ∑_{n=0}^{∞} q^{−n} c(d^{−n}z) ϕ(d^{−n}z).  (4.1)

We compute the Mellin transform of (4.1); since it is a harmonic sum (see [2] for more background), we obtain

(â(z)ϕ(z))^{∗}(s) = ∑_{n≥0} q^{−n} d^{ns} (c(z)ϕ(z))^{∗}(s) = \frac{1}{1 − \frac{d^{s}}{q}} (c(z)ϕ(z))^{∗}(s).

(The Mellin transform

(c(z)ϕ(z))^{∗}(s) = ∫_{0}^{∞} [\frac{d_{1}}{q} (e^{−z} − e^{−z/d}) + \frac{1}{q}(e^{z/d} − 1) ∑_{i=2}^{d} e^{−iz/d}d_{i}]\frac{e^{z}}{e^{z} − 1}z^{s−1}dz

can be expressed by Hurwitz’ zeta functions: Recall that the Hurwitz zeta function is defined as

ζ(s, a) = ∑_{k=0}^{∞} \frac{1}{(k + a)^{s}}

for ℜ(s) > 1 and a ≥ 0. The classical formula

Γ(s)ζ(s, a) = ∫_{0}^{∞} z^{s−1} \frac{e^{−az}}{1 − e^{−z}} dz

eventually gives us

(c(z)ϕ(z))^{∗} = Γ(s)(\frac{d_{1}}{q} (ζ(s, 1) − ζ(s, \frac{1}{d})) + \frac{1}{q} ∑_{i=2}^{d} (ζ(s, \frac{i − 1}{d}) − ζ(s, \frac{i}{d}))d_{i}).

This can be used for numerical calculations.)

The function â(z) can be recovered from this by Mellin’s inversion formula,

â(z)ϕ(z) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} \frac{(c(z)ϕ(z))^{∗}(s)}{1 − \frac{d^{s}}{q}} z^{−s} ds ,

where 0 < c < log_{d} q. By shifting the integral to the right and taking the negative residues into account, we get the desired asymptotic behaviour of â(z). There are simple poles at s = log_{d} q + \frac{2kπi}{log d}, k ∈ ℤ. The negative residue there is

\frac{1}{log d}(c(z)ϕ(z))^{∗}( log_{d} q + \frac{2kπi}{log d}) z^{− log_{d} q− \frac{2kπi}{log d}} .

The value for k = 0 is of special interest; it is, to make it more explicit,

\frac{1}{log d}z^{− log_{d} q} ∫_{0}^{∞} c(z)ϕ(z) z^{log_{d} q−1} dz.

Moreover ϕ(z) ∼ 1 as z → ∞. One collects all the terms into a periodic function.

Theorem 4. The expected value of the minimum order statistics of the Cantor–(q, D) distribution has for n → ∞ the following asymptotic behaviour

a_{n} = \frac{d_{1}}{q − 1} + Φ(− log_{d} q) n^{− log_{d} q}(1 + O(\frac{1}{n})),

where Φ(x) is a periodic function with period 1 and known Fourier coefficients. The mean (zeroth Fourier coefficient) is given by

\frac{1}{log d} ∫_{0}^{∞} c(z)ϕ(z) z^{log_{d} q−1} dz.

As before, the integral can be computed numerically. Example. We consider again the example q = 5 with D = {−1, 1, 3} and d = 3.

Then a_{100} + \frac{1}{4} ≈ 0.00205441. Further,

c(z) = \frac{1}{5}( − 4e^{−z} + 2e^{−z/3} + 2e^{−2z/3} ),

and

\frac{1}{log 3} ∫_{0}^{∞} c(z)ϕ(z) z^{log 5/ log 3−1} dz ≈ 1.77099.

Eventually, 1.77099 · 100^{log 5/ log 3} ≈ 0.00208.

References

[1] N. G. de Bruijn. Asymptotic Method in Analysis. North Holland, Amsterdam, The Netherlands, 1961.

[2] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci., 144:3–58, 1995.

[3] P. Flajolet and R. Sedgewick. Mellin Transforms and Asymptotics : Finite Differences and Rice’s Integrals. Theoret. Comput. Sci., 144:101–124, 1995.

[4] P. Grabner. Searching for losers. Random Structures and Algorithms, 4:99–110, 1993.

[5] P. Grabner and H. Prodinger. Asymptotic analysis of the moments of the Cantor distribution. Statistics and Probability Letters, 26:243–248, 1996.

[6] J. R. M. Hosking. Moments of order statistics of the Cantor distribution. Statistics and Probability Letters, 19:161–165, 1994.

[7] P. Jacquet and W. Szpankowski. Analytical depoissonization and its applications. Theoret. Comput. Sci., 201:1–62, 1998.

[8] P. Kirschenhofer, H. Prodinger and W. Szpankowski. Analysis of a splitting process arising in probabilistic counting and other related algorithms. Random Structures and Algorithms, 9:379– 401, 1996.

[9] A. Knopfmacher and H. Prodinger. Exact and asymptotic formulæ for average values of order statistics of the Cantor distribution. Statistics and Probability Letters, 27:189–194, 1996.

[10] A. M. Odlyzko. Asymptotic enumeration methods. In Handbook of Combinatorics, vol. 2, 1063– 1229, R. L. Graham, M. Groetschel, and L. Lovasz, eds., Elsevier, 1995.

[11] F. R. Lad and W. F. C. Taylor. The moments of the Cantor distribution. Statistics and Probability Letters, 13:307–310, 1992.

[12] H. Prodinger. The Cantor-Fibonacci distribution. Proceedings “Applications of Fibonacci Numbers”, vol. 7, 311–318, Kluwer, 1998.

[13] W. Szpankowski. Average Case Analysis of Algorithms on Sequences. John Wiley & Sons, New York, 2001.

Frédérique Bassino, Institut Gaspard Monge, Unversité de Marne-la-Vallée, 77454 Marne-la-Vallée Cedex 2, France

E-mail address: bassino@univ-mlv.fr

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

E-mail address: helmut@staff.ms.wits.ac.za