\documentclass[12pt,reqno]{amsart}%{article}
     %\usepackage{a4ams}
     \usepackage{amsfonts,amsmath,amssymb}

     \topmargin 0 pt
     \textheight 46\baselineskip
     \advance\textheight by \topskip
     %\setlength{\parindent}{0pt}
     \setlength{\parskip}{2pt plus 2pt minus 1pt}
     \setlength{\textwidth}{155mm}
     \setlength{\oddsidemargin}{5.6mm}
     \setlength{\evensidemargin}{5.6mm}

     \def\al{\alpha}

     \newtheorem{theorem}{Theorem}

     \newtheorem{lemma}{Lemma}

     \newtheorem{prop}{Proposition}
     \numberwithin{equation}{section}

     \def\P{{\mathbb {P}}}
     \def\t{\vartheta}\def\tt{\bar{\vartheta}}
     \def\v{\textsf{value}}
     \def\mm{\widehat m}
     \def\ma{\widehat a}
     \def\Card{\mathit{Card}}
\def\d{\mathsf{d}}
\def\i{\mathrm{i}}

     % other useful commands
     \newcommand{\Leaf}{\qedsymbol}

     \title[$(q,\delta)$-numeration systems with  missing digits]
     {${\boldsymbol{(q,\delta)}}$-numeration systems with missing digits}

     \author[F.~Bassino]{Fr\'ed\'erique Bassino$^\dag{}$}
     \address{Fr\'ed\'erique Bassino\\ Institut Gaspard Monge\\
     Unversit\'e de Marne-la-Vall\'ee\\
     77454 Marne-la-Vall\'ee Cedex 2\\ France}
     \email{bassino@univ-mlv.fr}
     \thanks{$^\dag{}$This author was supported by
     the CNRS/NRF-project $n^o$10959}
     \thanks{ 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}

     \author[H.~Prodinger]{Helmut Prodinger$^\dag{}$}
     \address{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}
     \email{helmut@staff.ms.wits.ac.za}

     \date{\today}
     \subjclass{Primary: 11A63, 11K16; Secondary: 60C05}
     \keywords{Digits, Depoissonization, Mellin Transform, Asymptotic Expansion, Moments}

     \begin{document}
     \begin{abstract}
     We consider the
     $(q,\delta)$ numeration system,
     with basis $q\ge2$ and
     the set of digits $\{\delta, \delta+1, \ldots, q+\delta-1\}$
     where $-(q-1)\le \delta\le 0$.
     We study properties of numbers
     where some digits \emph{do not occur}. This is analogous to the
     Cantor set $\big\{0.a_1a_2\dots\mid a_i\in\{0,2\}\big\}$.

     We compute an asymptotic equivalent of the $n$th moment of
     the ``Cantor $(q,D)$--distribution'' which can be described
     as the numbers $0.w_1w_2\dots$ with $w_i\in D\subseteq
     \{\delta,  \ldots, q+\delta-1\}$, and each such letter can
     occur with the same probability $1/\Card D$.

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

     \end{abstract}

     \maketitle

     \section{Introduction}
     \label{sec:intro}

     We consider the $(q,\delta)$ numeration system, with basis $q\ge2$ and
     the set of digits $\{\delta, \delta+1, \ldots, q+\delta-1\}$ where
     $-(q-1)\le \delta\le 0$.\footnote{Often, the letter $d$ is used
     instead of $\delta$. In this paper, however, we need the letter $d$
     for other purposes.} Every real number $x$ has an essentially
     unique\footnote{Some numbers have two representations, which is the
     analogue of $1=0.999\dots\;$.} representation
     \begin{equation*}
     x=\sum_{k\le n}a_kq^k
     \end{equation*}
     with $a_k\in\{\delta, \delta+1, \ldots, q+\delta-1\}$.  In particular,
     we are interested in properties of numbers where some digits \emph{do
     not occur}. This is analogous to the Cantor set, which can be
     described as
     \begin{equation*}
     \big\{0.a_1a_2\dots\mid a_i\in\{0,2\}\big\}.
     \end{equation*}

     The Cantor distribution with parameter $\t$, $0<\t\le\frac{1}{2}$, was
     introduced in \cite{LadTay92} by the random series
     \begin{equation*}
     \frac{\tt}{\t}\sum_{i\ge1}X_i\t ^i~,
     \end{equation*}
     where the $X_i$ are independent with the distribution
     \begin{equation*}
     \P\{X_i=0\}=\P\{X_i=1\}=\frac{1}{2}~,
     \end{equation*}
     and $\tt=1-\t$. The name stems from the instance $\t=\frac13$, 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 \cite{LadTay92},
     and, more recently in \cite{GraPro94}, where an asymptotic formula for
     the $n$th 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 $\{\delta, \delta+1,
     \ldots, q+\delta-1\}$; we set $\d=\Card D$ and $D=\{d_1<d_2  <\ldots<
     d_{\d}\}$.

     We consider infinite (random) words $w_1w_2\dots$ over the alphabet
     $D=\{d_1, d_2, \ldots, d_{\d}\} $ and a mapping \v, defined by
     \begin{equation*}
     \v(w_1w_2\dots)=\sum_{i\ge1}w_i q^{-i}~.
     \end{equation*}
     Each letter can appear with probability $\frac{1}{\d}$.

     In this way we obtain a probability distribution on the interval
     $[\delta/(q-1), \delta/(q-1)+1]$, which we will call the
     Cantor--$(q,D)$ distribution.  In Section~\ref{sec:moments} we
     study its moments.

     \medskip

     Another interesting topic related to the Cantor distribution was
     introduced in \cite{Hosking94}; one assumes that $n$ (independent)
     elements are drawn according to the Cantor distribution. One is
     interested in the expected value of the \emph{minimum\/} of
     them. Hosking gave a recursion for these expectations, which was
     eventually solved in \cite{KnoPro94}, 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
     \emph{Rice's method\/} \cite{FlSe95}.

     In Section~\ref{sec:minimum} we are going to solve the analogous
     question in our model of the $(q,\delta)$--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 \cite{JaSz98} and \cite{spa01}; the present approach is modelled
     after the analysis in \cite{KiPrSz96}, which is also covered in
     \cite{JaSz98} and \cite{spa01}.

     \section{The Moments}\label{sec:moments}

     Observe the recursion formula, valid
     for all $i \in \{1, \ldots, \d\}$
     \begin{align}\begin{split}
     \v(d_iw)&=d_i\cdot q^{-1}+q^{-1}\cdot\v(w)~.
     \end{split}\end{align}
     %
     Here, $dw$ is the concatentation of the digit $d$  and the
     infinite string $w$; denote the set of all infinite strings by
$\mathcal{W}$. From the self--similarity of the measure, we can derive
a recursion for the moments $M_n$ as follows:
\begin{align*}
M_n&=\sum_{w\in\mathcal{W}}\big(\v(w)\big)^n\\
&=\frac1{\d q^n}\sum_{i=0}^\d\sum_{w\in\mathcal{W}}\big(d_i+\v(w)\big)^n\\
&=\frac1{\d q^n}\sum_{i=0}^\d\sum_{j=0}^n\binom nj d_i^{n-j}M_j.
\end{align*}
It can be made explicit by isolating the term $M_n$:
     \begin{equation*}
     M_n= \frac{\d^{-1}q^{-n}}{1-q^{-n}}\sum_{i=1}^\d \sum_{j=0}^{n-1}
     d_i^{n-j} \binom{n}{j}M_j .
     \end{equation*}
This recursion could be used to compute  a list of the first few moments.
     \begin{theorem}
     The moments of the Cantor--$(q,D)$ distribution satisfy the following
     recursion: $M_0=1$ and for $n\ge1$
     \begin{equation*}
     M_n= \frac{1}{{\d}(q^n-1)} \sum_{j=0}^{n-1} \sum_{i=1}^\d d_i^{n-j}
     \binom njM_j  .
     \end{equation*}
     \end{theorem}
     For instance
     \begin{align}\begin{split}
     M_1&=\frac{1}{\d(q-1)}\sum_{i=1}^\d d_i  ,\\
     M_2&=\frac{1}{\d(q^2-1)}\sum_{i=1}^\d d_i^2+\frac{1}{\d^2(q-1)^2(q+1)}
\bigg(\sum_{i=1}^\d
     d_i\bigg)^2, \\
     \textsf{Variance}&=M_2-M_1^2=
     \frac{1}{\d(q^2-1)}\sum_{i=1}^\d d_i^2-\frac{q}{\d^2(q-1)^2(q+1)}
\bigg(\sum_{i=1}^\d
     d_i\bigg)^2 .
     \end{split}\end{align}

     \section{The Asymptotic Behaviour of the Moments}

     The next problem is to investigate the asymptotic behaviour of the moments
     $M_n$, as $n\to\infty$. Remember that this investigation for the classical
     case was done in \cite{GraPro94}.

     A rough estimation shows us that the moments decrease
     exponentially. Indeed, if we set $M_n\approx \lambda^{-n}$, we might infer
     that $\lambda=(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
     \begin{equation*}
     m_n:=M_n\cdot \lambda^{n}
     \end{equation*}
     and show that this sequence has nicer properties. It satisfies the
     \emph{modified recurrence}
     \begin{equation*}
     m_n= \frac{1}{\d(q^n-1)} \sum_{i=1}^\d \sum_{j=0}^{n-1}\binom nj(\lambda
     d_i)^{n-j} m_j \ .
     \end{equation*}
     To study this sequence further, we rewrite it as
     \begin{equation*}
     m_n\cdot \d(q^n-1)=
     \sum_{i=1}^\d \bigg(\sum_{j=0}^{n}\binom nj(\lambda d_i)^{n-j} m_j -m_n
     \bigg)
     \end{equation*}
     or
     \begin{equation*}
     m_n =
     \frac{1}{\d q^n}
     \sum_{i=1}^\d \sum_{j=0}^{n}\binom nj(\lambda d_i)^{n-j} m_j
     \end{equation*}
     and note that this holds for all $n \ge 0$. Then we introduce the
     \emph{exponential generating function}
     \begin{equation*}
     m(z)=\sum_{n\ge0}m_n\frac{z^n}{n!}
     \end{equation*}
     and get
     \begin{equation*}
     m(z)= \frac{1}{\d} \sum_{i=1}^\d  e^{d_i \lambda \frac{z}{q}}
     \;m\Big(\frac{z}{q}\Big)
     =\prod_{k\ge1}\frac{
     \sum_{i=1}^\d e^{{z} d_i \lambda /{q^k}}}{\d}.
     \end{equation*}
     As in \cite{GraPro94}, we have to consider the \emph{Poisson transformed
     function\/} $\mm(z)=e^{-z}m(z)$, which satisfies the functional equation
     \begin{equation}\label{eq:star}
     \mm(z) = \frac{1}{\d} \sum_{i=1}^\d e^{\frac{z}{q} (d_i \lambda +1-q)}
     \;\mm\Big(\frac{z}{q}\Big) \ .
     \end{equation}
     This functional equation~(\ref{eq:star}) can also
     be solved by iteration:
     \begin{equation*}
     \mm(z)=\prod_{k\ge1}\frac{
     \sum_{i=1}^\d e^{{z} (d_i \lambda +1-q)/{q^k}}}{\d}.
     \end{equation*}
     %
     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 $\mm(z)$ for $z\to \infty$.
     The reason is that $m_n\sim \mm(n)$. The justification for this is a
     technique called \emph{depoissonization}.

     The general  references for that are
     \cite{JaSz98} and \cite{spa01}. We follow \cite{GraPro94},
     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} \sum_{i
     \neq M} e^{\frac{z}{q} (d_i \lambda +1-q)} \mm\big(\frac{z}{q}\big)$ and consider
     it to be an auxiliary (and \emph{known\/}) function;
     \begin{equation}\label{m:eq}
     \mm(z)
     =\frac1{\d}\mm\Big(\frac{z}{q}\Big)+R(z)\  .
     \end{equation}
     We compute the \emph{Mellin transform\/} of (\ref{m:eq})\ \ (see
     \cite{FlGoDu95} for definitions and properties);
     \begin{equation*}
     \mm^\ast(s)
     =\frac{q^s}{\d}\mm^\ast(s)+R^\ast(s)=\frac{R^\ast(s)}{1-\frac{q^s}{\d}}\ .
     \end{equation*}
     The  function $m(z)$ can be recovered from this by
     \emph{Mellin's inversion formula},
     \begin{equation*}
     \mm(z)=\frac{1}{2\pi \i}\int_{c-\i\infty}^{c+\i\infty}
     \frac{R^\ast(s)}{1-\frac{q^s}{\d}}\,z^{-s}\,ds\ ,
     \end{equation*}
     where $0<c<\log_q\d$. By shifting the integral to the right and taking the
     \emph{negative residues\/} into account, we get the desired asymptotic
     behaviour of $\mm(z)$.  There are simple poles at $s=\log_q\d+\frac{2k\pi
     \i}{\log q}$, $k\in\mathbb Z$.  The negative residue there is
     \begin{equation*}
     \frac{1}{\log q}R^\ast\Big(\log_q\d+\frac{2k\pi \i}{\log q}\Big)\,z^{-\log_q
     \d-\frac{2k\pi \i}{\log q}}\ .
     \end{equation*}
     The value for $k=0$ is of special interest; it is, to make it more
     explicit,
     \begin{equation*}
     \frac{1}{\log q} z^{-\log_q \d} \int_0^\infty \frac{1}{\d} \sum_{i \neq M}
     e^{\frac{z}{q} (d_i \lambda +1-q)}\; \mm\Big(\frac{z}{q}\Big)\; z^{\log_q\d-1} \,dz\ .
     \end{equation*}
     Traditionally, one collects all the terms into a periodic function.

     \begin{theorem}
     The $n$th moment $M_n$
     of the Cantor--$(q,D)$ distribution has for $n\to\infty$ the following
     asymptotic behaviour
     \begin{equation*}
     M_n=\bigg(\frac{d_M}{q-1}\bigg)^{n}\Phi(-\log_q n)\,n^{-\log_q \d}\bigg(1+O\Big(\frac
     1n\Big)\bigg)\ ,
     \end{equation*}
     where $\Phi(x)$ is a periodic function with period 1 and known Fourier
     coefficients. The mean (zeroth Fourier coefficient) is given by
     \begin{equation*}
     \frac{1}{\log q} \int_0^\infty \frac{1}{\d} \sum_{i \neq M} e^{\frac{z}{q}
     (d_i \lambda +1-q)}\; \mm\Big(\frac{z}{q}\Big)\; z^{\log_q\d-1} \,dz\ .
     \end{equation*}

     \end{theorem}

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

     \textbf{Example.} We consider $q=5$ and $D=\{-1,1,3\}$, so $\d=3$,
     $d_M=3$, and $\lambda=\frac 43$. Then
     \begin{equation*}
     m_n= \frac{1}{3(5^n-1)} \sum_{j=0}^{n-1}\binom nj
     \Big((-\tfrac43 )^{n-j}+(\tfrac43 )^{n-j}+4^{n-j}\Big) m_j \ .
     \end{equation*}
     %
     So we replace $R(z)$ by
     \begin{equation*}
     R^{\text{approx}}=
     \frac13\Big(e^{-16z/15}+e^{-8z/15}\Big)\;e^{-z/5}\;
     \Big(
     1+\tfrac1{20}z+{\tfrac {1}{288}}{z}^{2}+{\tfrac {19}{144000}}{z}^{3}+{
     \tfrac {5887}{1347840000}}{z}^{4}
     +\dots\Big)
     \end{equation*}
     and compute
     \begin{equation*}
     \frac1{\log 5}\int_0^\infty
     R^{\text{approx}}\; z^{\log3/\log5-1}\;dz=
     0.59896\dots\;.
     \end{equation*}
     We find $M_{100}\;(\tfrac43)^{100}\; 100^{\log3/\log5}\approx
     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 $\infty$; 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.

     \bigskip

     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 \cite{JaSz98} and in
     \cite{spa01}, 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 \pi \i}\int_{|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 \pi \i}
\int_{|z|=n, \Re z \geq 0}\frac{m(z)}{z^{n+1}}dz
     +(-1)^n \frac{1}{2 \pi \i}\int_{|z|=n, \Re z \geq 0}\frac{m(-z)}{z^{n+1}}dz.\]
     We now use the fact that the saddle point in the integral
     \[\frac{n!}{2 \pi i}\int_{{\mathcal 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 \cite{debruijn} or to \cite{Odl95}.
     As $m(z)=e^z (e^{-z}m(z))$ where
     \[e^{-z}m(z)=\prod_{k \ge 1}\frac{
     \sum_{i=1}^\d e^{{z} (d_i \lambda +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 \pi \i}\int_{|z|=n, \Re z \geq 0}\frac{m(z)}{z^{n+1}}dz \sim
     e^{-n}m(n)\bigg(1+O\Big(\frac{1}{n}\Big)\bigg),\]
     and similarly
     \[\frac{n!}{2 \pi \i}\int_{|z|=n, \Re z \geq 0}\frac{m(-z)}{z^{n+1}}dz\sim
     e^{-n}m(-n)\bigg(1+O\Big(\frac{1}{n}\Big)\bigg).\]
     Compare \cite{Grabner93} for such an approach.

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

     \begin{theorem} In the instance of two dominant digits $d_1$, $d_{\d}$, with
     $-d_1=d_{\d}=d_M$,
     the $n$th moment $M_n$
     of the Cantor--$(q,D)$ distribution has for $n\to\infty$ the following
     asymptotic behaviour
     \begin{equation*}
     M_n=\bigg(\frac{d_M}{q-1}\bigg)^{n}\Big[\Phi_1(-\log_q n)
     +(-1)^n\Phi_2(-\log_q n)\Big]
     \,n^{-\log_q \d}\bigg(1+O\Big(\frac
     1n\Big)\bigg)\ ,
     \end{equation*}
     where $\Phi_1(x)$ and $\Phi_2(x) $ are periodic functions with period 1 and known
     Fourier
     coefficients. The means (zeroth Fourier coefficients) are given by
     \begin{align*}
     &\frac{1}{\log q} \int_0^\infty \frac{1}{\d} \sum_{i \neq d} e^{\frac{z}{q}
     (d_i \lambda +1-q)}\; e^{-z/q}\;m\Big(\frac{z}{q}\Big)\; z^{\log_q\d-1} \,dz , \\
     &\frac{1}{\log q} \int_0^\infty \frac{1}{\d} \sum_{i \neq 1} e^{\frac{z}{q}
     (-d_i \lambda +1-q)}\; e^{-z/q}\;m\Big(\frac{-z}{q}\Big)\; z^{\log_q\d-1} \,dz , \\
     \end{align*}
     respectively.
     \end{theorem}
     While the even moments are always positive, the sign of the odd ones
     depends on the largest (in modulus) digit $d_i \in D$ such that not
     both $d_i$ and $-d_i$ are in $D$.

     \textbf{Example.} We consider $q=7$ and $D=\{-3,2,3\}$, so $\d=3$,
     $d_M=3$, and $\lambda=2$. Then
     \begin{equation*}
     m_n= \frac{1}{3(7^n-1)} \sum_{j=0}^{n-1}\binom nj
     \Big((-6 )^{n-j}+4^{n-j}+6^{n-j}\Big) m_j \ .
     \end{equation*}
     %
     So we replace $R(z)$ by
     \begin{equation*}
     R^{\text{approx}}=
     \frac13\Big(e^{-12z/7}+e^{-2z/7}\Big)\;e^{-z/7}\;
     \Big(
     1+\tfrac1{63}z+{\tfrac {101}{63504}}{z}^{2}+{\tfrac {251}{32577552}}{z}^{3}
     +\dots\Big)
     \end{equation*}
     and compute
     \begin{equation*}
     \frac1{\log 7}\int_0^\infty
     R^{\text{approx}}\; z^{\log3/\log7-1}\;dz=
     0.63967\dots\;.
     \end{equation*}
     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
     \begin{equation*}
     R^{\text{approx}}=
     \frac13\Big(e^{-12z/7}+e^{-10z/7}\Big)\;e^{-z/7}\;
     \Big(
     1-\tfrac1{63}z+{\tfrac {101}{63504}}{z}^{2}-{\tfrac {251}{32577552}}{z}^{3}
     +\dots\Big)
     \end{equation*}
     and find
     \begin{equation*}
     \frac1{\log 7}\int_0^\infty
     R^{\text{approx}}\; z^{\log3/\log7-1}\;dz=
     0.39769\dots\;.
     \end{equation*}
     This is the second contribution; call it $C_2$.

     We find $M_{100}\;2^{100}\; 100^{\log3/\log7}\approx
     1.04057$; this is close to $C_1+C_2=1.03737$. On the other hand,
     $M_{99}\;2^{99}\; 99^{\log3/\log7}\approx 0.26770$;
     this is to be compared with $C_1-C_2=0.24197$.

     \section{Expected value of the minimum order statistic of the
     $(q,D)$--distribution}
     \label{sec:minimum}

     We consider {\em random strings} $c_1\,c_2\,c_3\ldots$ where the $c_i$'s
     $\in D=\{d_1  < d_2  < \cdots  < d_{\d}\}$ are equally likely.  We then consider
     the random variable $\v$ that maps $c_1\,c_2\,c_3\ldots$ to the real number
     $$
     \v(c_1\,c_2\,c_3\ldots)=\sum_{i\geq1}c_iq^{-i}\;
     \in\Big[ \frac{d_1}{q-1},   \frac{d_\d}{q-1}\Big]\;.
     $$
     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<c^{\prime}_1\,c^{\prime}_2\,c^{\prime}_3\ldots$
     iff there is a $k$ such that $c_i=c^{\prime}_i$ for $i=1,\ldots, k-1$ and
     $c_k  < c^{\prime}_k$.  It thus makes sense to speak of order statistics for
     strings.  Suppose that $n$ independent random strings $w_1,\ldots, w_n$ are
     produced.  We denote by $a_n$ the average value of the
     minimum of the $n$ real numbers $\v(w_1),\ldots, \v(w_n)$.
     We derive the following recursion for the expected minimum

     $$
     a_n=\frac{1}{q\d^n}\bigg[\sum_{i=1}^{\d-1} \bigg( \sum_{k=1}^n \binom{n}{k}
     (\d-i)^{n-k} (d_i+a_k)\bigg) + d_{\d}  + a_n  \bigg]
     \;,\quad n\geq 1\;,
     $$
     or
     $$
     (\d^nq-\d)a_n= \sum_{i=1}^{\d} \Big[(\d-i+1)^n - (\d-i)^n\Big] d_i +
     \sum_{k=1}^{n-1} \sum_{i=1}^{\d-1} \binom{n}{k} (\d-i)^{n-k}a_k\;,\quad n\geq
     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_1d_1d_1\dots$ 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 $\al_n:=a_n-\frac{d_1}{q-1}$ and rewrite the recursion:

     $$
     (\d^nq-\d)\Big(\al_n+\frac{d_1}{q-1}\Big)
     = \sum_{i=1}^{\d} \Big[(\d-i+1)^n - (\d-i)^n\Big] d_i +
     \sum_{k=1}^{n-1} \sum_{i=1}^{\d-1} \binom{n}{k} (\d-i)^{n-k}
     \Big(\al_k+\frac{d_1}{q-1}\Big)
     $$
     or
     $$
     (\d^nq-\d)\al_n
     = -(\d-1)^nd_1+\sum_{i=2}^{\d} \Big[(\d-i+1)^n - (\d-i)^n\Big] d_i +
     \sum_{k=1}^{n-1} \sum_{i=1}^{\d-1} \binom{n}{k} (\d-i)^{n-k}
     \al_k.
     $$

     Then we introduce the \emph{exponential generating
     function} (with $\al_0:=0$)
     \begin{equation*}
     a(z)=\sum_{n\ge0}\al_n\frac{z^n}{n!}
     \end{equation*}
     and get
     \begin{equation*}
     qa(\d z)-\d a(z)= (1-e^{(\d-1)z})d_1+\sum_{i=2}^\d 
\Big( e^{(\d-i+1)z} - e^{(\d-i)z} \Big)
     d_i +
     \sum_{i=1}^{\d-1} \Big(e^{(\d-i)z} -1 \Big) a(z),
     \end{equation*}
     or
     \begin{equation*}
     a(\d z)= \frac{1}{q} \Big(\frac{1-e^{\d z}}{1-e^z}\Big) a(z) +
     \frac{d_1}{q}(1-e^{(\d-1)z})+
     \frac{1}{q}
     \sum_{i=1}^\d \Big( e^{(\d-i+1)z} - e^{(\d-i)z} \Big) d_i.
     \end{equation*}
     We have to consider the \emph{Poisson transformed function\/}
     $\ma(z)=e^{-z}a(z)$, which satisfies the functional equation
     \begin{equation*}
     \ma(\d z) = \frac{1}{q} \Big(\frac{1-e^{-\d z}}{1-e^{-z}}\Big) \ma(z)
     +\frac{d_1}{q}(e^{-\d z}-e^{-z})+
     \frac{1}{q} (e^{z}-1) \sum_{i=2}^\d e^{-iz}d_i \ .
     \end{equation*}

     The next step is to consider the behaviour of $\ma(z)$ for $z\to \infty$.
     The reason is that $\al_n\sim \ma(n)$. The justification for this is
     again the technique of  \emph{depoissonization}. We set
     $$
     b(z)= \frac{1-e^{-\d z}}{1-e^{-z}}\qquad\text{and} \qquad
     \phi(z)= \prod_{j=0}^{\infty}b(z\d^j)=\frac1{1-e^{-z}}
     $$
     and
     $$
     c(z)=\frac{d_1}{q}(e^{-z}-e^{-z/\d})+
     \frac{1}{q} (e^{z/\d}-1) \sum_{i=2}^\d e^{-iz/\d}d_i.
     $$
     We then get
     \begin{equation*}
     \ma(z)
     = \sum_{n=0}^{\infty}q^{-n}\,c(q^{-n}z) \prod_{k=1}^n b(q^{-k}z)  .
     \end{equation*}
     As $\ma(0)=0$, we finally obtain
     \begin{equation}\label{a:eq}
     \ma(z) \phi(z)
     = \sum_{n=0}^{\infty}q^{-n}\,c(\d^{-n}z)\, \phi(\d^{-n}z)  .
     \end{equation}
     %
     We compute the \emph{Mellin transform\/} of (\ref{a:eq}); since it is
     a harmonic sum (see \cite{FlGoDu95} for more background), we obtain
     \begin{equation*}
     \big(\ma(z) \phi(z)\big)^\ast(s) =\sum_{n \geq 0} q^{-n}\,\d^{ns}\,
     \big(c(z)\phi(z)\big)^\ast(s)=
     \frac{1}{1-\frac{\d^s}{q}}\big(c(z) \phi(z)\big)^\ast(s) .
     \end{equation*}
(The Mellin transform
\begin{equation*}
\big(c(z) \phi(z)\big)^\ast(s)=\int_0^\infty\bigg[
\frac{d_1}{q}(e^{-z}-e^{-z/\d})+
     \frac{1}{q} (e^{z/\d}-1) \sum_{i=2}^\d e^{-iz/\d}d_i\bigg]
\frac{e^z}{e^z-1}z^{s-1}dz
\end{equation*}
can be expressed by Hurwitz' zeta functions: Recall that the
 Hurwitz zeta function is defined as
$$\zeta(s,a)=\sum_{k=0}^{\infty}\frac{1}{(k+a)^s}$$
for $\Re(s) >1$ and $a \geq 0$. The classical formula

$$\Gamma(s) \zeta(s,a) = \int_{0}^{\infty}
z^{s-1}\frac{e^{-az}}{1-e^{-z}}dz$$
eventually gives us
$$
\big(c(z)\phi(z)\big)^*=\Gamma(s) \bigg(\frac{d_1}{q}\Big(\zeta\big(s,1\big)-
\zeta\big(s,\frac{1}{\d}\big)\Big) +\frac{1}{q}\sum_{i=2}^{\d} \Big( \zeta\big(s,\frac{i-1}{\d}\big)-
\zeta\big(s,\frac{i}{\d}\big)\Big) d_i \bigg).
$$
 This can be used for
numerical calculations.)






     %
     The function $\ma(z)$ can be recovered from this by
     \emph{Mellin's inversion formula},
     \begin{equation*}
     \ma(z) \phi(z)=\frac{1}{2\pi \i}\int_{c-\i\infty}^{c+\i\infty}
     \frac{\big(c(z)\phi(z)\big)^\ast(s)}{1-\frac{\d^s}{q}}\,z^{-s}\,ds\ ,
     \end{equation*}
     where $0<c<\log_{\d} q$. By shifting the integral to the right and taking the
     \emph{negative residues\/} into account, we get the desired asymptotic
     behaviour of $\ma(z)$.  There are simple poles at $s=\log_{\d} q+\frac{2k\pi
     \i}{\log \d}$, $k\in\mathbb Z$.  The negative residue there is
     \begin{equation*}
     \frac{1}{\log \d}\big(c(z) \phi(z)\big)^\ast\Big(\log_{\d}q+
     \frac{2k\pi \i}{\log \d}\Big)\,z^{-\log_\d q -\frac{2k\pi \i}{\log \d}} .
     \end{equation*}
     The value for $k=0$ is of special interest; it is, to make it more
     explicit,
     \begin{equation*}
     \frac{1}{\log \d} z^{-\log_{\d} q} \int_0^\infty c(z) \phi(z)\, 
z^{\log_{\d} q-1}
     \,dz .
     \end{equation*}
     Moreover $\phi(z) \sim 1$ as $z\to\infty$.
     One collects all the terms into a periodic function.

     \begin{theorem}
     The expected value of the minimum order statistics of the
     Cantor--$(q,D)$ distribution has for $n\to\infty$ the following
     asymptotic behaviour
     \begin{equation*}
     a_n= \frac{d_1}{q-1}
     +\Phi(-\log_{\d} q)\,n^{-\log_{\d} q}\bigg(1+O\Big(\frac 1n\Big)\bigg) ,
     \end{equation*}
     where $\Phi(x)$ is a periodic function with period 1 and known Fourier
     coefficients. The \textsf{mean\/} (zeroth Fourier coefficient) is given by
     \begin{equation*}
     \frac{1}{\log \d}
     \int_0^\infty
     c(z) \phi(z) \, z^{\log_{\d} q-1} \,dz .
     \end{equation*}

     \end{theorem}

     As before, the integral can be  computed numerically.

     \textbf{Example.}
     We consider again the example $q=5$ with $D=\{-1,1,3\}$ and $\d=3$.
     Then $a_{100}+\frac{1}{4}\approx0 .00205441$. Further,
     \begin{equation*}
     c(z)=\frac15\big(-4{e^{-z}}+2{e^{-z/3}}+2{e^{-2z/3}}\,\big),
     \end{equation*}
     and
     \begin{equation*}
     \frac{1}{\log 3}
     \int_0^\infty
     c(z) \phi(z) \, z^{\log5/\log3-1} \,dz \approx
     1.77099.
     \end{equation*}
     %
     Eventually, $1.77099\cdot100^{\log5/\log3}\approx0.00208$.




     \bibliographystyle{plain}

     %\bibliography{pro_bib}

     \begin{thebibliography}{10}

     \bibitem{debruijn}
     N.~G. de Bruijn.
     \newblock {\em Asymptotic Method in Analysis}.
     \newblock North Holland, Amsterdam, The Netherlands, 1961.

     \bibitem{FlGoDu95}
     P.~Flajolet, X.~Gourdon, and P.~Dumas.
     \newblock Mellin transforms and asymptotics: {H}armonic sums.
     \newblock {\em Theoret. Comput. Sci.}, 144:3--58, 1995.

     \bibitem{FlSe95}
     P. Flajolet and R. Sedgewick.
     \newblock Mellin Transforms and Asymptotics : Finite Differences and Rice's
     Integrals.
     \newblock {\em Theoret. Comput. Sci.}, 144:101--124, 1995.

     \bibitem{Grabner93}
     P. Grabner.
     \newblock Searching for losers.
     \newblock {\em Random Structures and Algorithms}, 4:99--110, 1993.

     \bibitem{GraPro94}
     P.~Grabner and H.~{P}rodinger.
     \newblock Asymptotic analysis of the moments of the {C}antor distribution.
     \newblock {\em Statistics and Probability Letters}, 26:243--248, 1996.

     \bibitem{Hosking94}
     J.~R.~M. Hosking.
     \newblock Moments of order statistics of the {C}antor distribution.
     \newblock {\em Statistics and Probability Letters}, 19:161--165, 1994.

     \bibitem{JaSz98}
     P. Jacquet and W. Szpankowski.
     \newblock Analytical depoissonization and its applications.
     \newblock {\em Theoret. Comput. Sci.}, 201:1--62, 1998.

     \bibitem{KiPrSz96}
     P. Kirschenhofer, H. Prodinger and W. Szpankowski.
     \newblock Analysis of a splitting process arising
     in probabilistic counting and other related algorithms.
     \newblock {\em Random Structures and Algorithms}, 9:379--401, 1996.

     \bibitem{KnoPro94}
     A.~Knopfmacher and H.~{P}rodinger.
     \newblock Exact and asymptotic formul{\ae}\ for average values of order
      statistics of the {C}antor distribution.
     \newblock {\em Statistics and Probability Letters},  27:189--194, 1996.

     \bibitem{Odl95}
     A.~M. Odlyzko.
     \newblock Asymptotic enumeration methods.
     \newblock In {\em Handbook of Combinatorics}, vol. 2,
     1063--1229, R. L. Graham, M. Groetschel, and L. Lovasz, eds.,
     Elsevier, 1995.

     \bibitem{LadTay92}
     F.~R. Lad and W.~F.~C. Taylor.
     \newblock The moments of the {C}antor distribution.
     \newblock {\em Statistics and Probability Letters}, 13:307--310, 1992.

     \bibitem{Pro98}
     H. Prodinger.
     \newblock The Cantor-Fibonacci distribution.
     \newblock  Proceedings {\em ``Applications of
     Fibonacci Numbers''}, vol. 7, 311--318, Kluwer, 1998.

     \bibitem{spa01}
     W. Szpankowski.
     \newblock {\em Average Case Analysis of Algorithms on Sequences}.
     \newblock John Wiley {\&} Sons, New York, 2001.

     %\bibitem{RaJaSz93}
     %B.~Rais, P.~Jacquet, and W.~Szpankowski.
     %\newblock Limiting distribution for the depth in {P}atricia tries.
     %\newblock {\em SIAM Journal on Discrete Mathematics}, 6:197--213, 1993.

     \end{thebibliography}

     \end{document}