
\documentclass[12pt]{amsart}
\usepackage{a4wide,graphicx,bbm,amssymb,ifthen,url}


\allowdisplaybreaks

\newcommand{\eps}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\numberwithin{equation}{section}

\newcommand{\klammern}[4][]%
{\ifthenelse{\equal{#1}{}}{\left#2}{\csname#1\endcsname#2}%
#4\ifthenelse{\equal{#1}{}}{\right#3}{\csname#1\endcsname#3}}

\newcommand{\betrag}[2][]{\klammern[#1]{\lvert}{\rvert}{#2}}
\newcommand{\fl}[2][]{\klammern[#1]{\lfloor}{\rfloor}{#2}}
\newcommand{\ceil}[2][]{\klammern[#1]{\lceil}{\rceil}{#2}}
\newcommand{\cond}[2][]{\klammern[#1]{[}{]}{#2}}
\newcommand{\fractional}[2][]{\klammern[#1]{\{}{\}}{#2}}

\newcommand{\seq}[1]{\mathbf{#1}}
\newcommand{\Rmin}{R_{\mathrm{min}}}
\newcommand{\Rmax}{R_{\mathrm{max}}}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\val}{\mathsf{value}}
\newcommand{\bigunion}{\bigcup}

\newcommand{\bigOh}{\mathcal{O}}
\newcommand{\smallOh}{o}


\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem*{remark}{Remark}
\theoremstyle{definition}
\newtheorem*{ackn}{Acknowledgement}
\begin{document}

\title[Subblock occurrences]
{Subblock occurrences in signed digit representations}
\author[P. J. Grabner]{Peter J. Grabner$^\dag$}
\address[P. Grabner]{Institut f\"ur Mathematik A,
Technische Universit\"at Graz,
Steyrergasse 30,
8010 Graz,
Austria}
\email{peter.grabner@tugraz.at}
\thanks{\dag{} This author is supported by the 
 START-project Y96-MAT of the
  Austrian Science Fund.}

\author[C. Heuberger]{Clemens Heuberger$^\ddag$}
\address[C. Heuberger]{Institut f\"ur Mathematik B,
Technische Universit\"at Graz,
Steyrergasse 30,
8010 Graz,
Austria}
\email{clemens.heuberger@tugraz.at}
\thanks{\ddag{} This author is supported by grant S8307-MAT of the Austrian
  Science Fund.}

\author[H. Prodinger]{Helmut Prodinger}
\address[H. 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}

\keywords{Digit representation, subblock occurrence, Mellin-Perron formula}
\subjclass{Primary:11K16 ; Secondary:11A63, 11M41}
\date{\today}
\begin{abstract}
Signed digit representations with base $q$ and digits
$-\frac q2,\dots,\frac q2$ (and uniqueness being enforced
by applying a special rule which decides whether $-q/2$
or $q/2$ should be taken) are considered with respect to
counting the occurrences of a given (contiguous) subblock
of length $r$. The average number of occurrences amongst
the numbers $0,\dots,n-1$ turns out to be 
$\mathit{const}\cdot\log_qn+\delta(\log_qn)+\smallOh(1)$, with a constant
and a periodic function of period one depending on the given
subblock; they are explicitly described. Furthermore, we use probabilistic
techniques to prove a central limit theorem for the number of occurrences of a
given subblock.
\end{abstract}

\maketitle


\section{Introduction}\label{intro}

If we write $10^6$ in binary we obtain $11110100001001000000$. This 
\textit{word\/}  contains the (contiguous) substring $100$ three times. In this
paper we are concerned with counting occurrences of a given substring 
(or block) (like $100$) 
in representations of numbers. Since this is typically somewhat erratic,
we are interested in an average
\begin{equation*}
\frac1N\sum_{0\le n<N}(\textsf{number of occurrences of a given block $w$
in the representation of $n$}).
\end{equation*}
This is a generalisation of counting the frequency of digits. 

For the instance of the $q$--ary representation of numbers this average was
investigated by Kirschenhofer in \cite{Kirschenhofer:1983:subbl}; the more
exotic $(q,d)$--ary representation of numbers with base $q$ and digits
$d,d+1,\dots, d+q-1$ was treated in \cite{Kirschenhofer-Prodinger:1984}. The
technique in these papers was an extension of Delange's method
\cite{Delange:1975:chiffres}. However, in
\cite{Flajolet-Grabner-Kirschenhofer-Prodinger:1994:mellin} a novel method,
based on the Mellin--Perron summation formula was introduced, and it was
indicated how it works for such subblock counting problems. We will use this
technique in the present paper. (A Delange type analysis would be feasible but
very messy.)

Recently, Heuberger and Prodinger \cite{Heuberger-Prodinger:2001:minim-expan}
have considered a symmetric system
\begin{equation*}
  n=\sum_{j=0}^\infty \eps_j q^j
\end{equation*}
with an even base $q$ and digits $\eps_j\in \{-\frac q2,\dots,\frac q2\}$. Such
a system is a priori redundant because of the existence of both $\pm \frac q2$
but can be made unique by the condition that $\betrag{\eps_j}=q/2$ implies
$0\le \sign(\eps_j)\eps_{j+1}<q/2$  (Equivalent conditions where discussed in
\cite{Heuberger-Prodinger:2001:minim-expan}).  We call this expansion the
\emph{symmetric signed digit expansion} of $n$ and denote it by
$(\dots\eps_2(n)\eps_1(n)\eps_0(n))$.  For $q=2$, this system was already
considered by Reitwiesner in a computer science context in
\cite{Reitwiesner:1960}.

In this paper we are addressing the subblock counting problem
in such symmetric   signed digit expansions.

Before we announce our principal findings, we need some
notation.
\medskip

If a block $\seq b=(b_s,\dots ,b_0)$ is given, we denote its
\emph{value\/} by
$\val(\seq b)=\sum_\ell b_\ell q^\ell$. 

We also use Iverson's notation, popularized in
\cite{Graham-Knuth-Patashnik:1994}: $[P]$
is defined to be 1 if condition $P$ is true, and
0 otherwise. With this notation we can count the number of 
subblock occurrences of $\seq b$ in (the symmetric signed digit expansions
of) $n$ via
\begin{equation}
s_{\mathbf{b}}(n)=\sum_{k=0}^\infty
\cond{(\eps_{k+r-1}(n),\ldots,\eps_{k}(n))=\seq b}.\label{eq:freya}
\end{equation}

We only consider \emph{admissible\/} blocks $\seq b$: these blocks
represent the number $\val(\seq b)$ in the
symmetric   signed digit expansion. For interest we note
that there are 
\begin{equation*}
\frac{2+q}{1+q}q^r-\frac{1}{1+q}(-1)^r
\end{equation*}
admissible blocks of length $r$; this was implicitly proved in
\cite{Heuberger-Prodinger:2001:carry-propag}.

We also use the decomposition of a real number $x$ as
$x=\fl x+\{x\}$ with the \emph{fractional part\/} $\{ x\}$ satisfying
$0\le\{x\}<1$.

As said before, we are going to study   the quantity
\begin{equation}\label{eq:Sb}
S_{\seq b}(N)=\sum_{n<N}\sum_{k=0}^\infty
\cond{(\eps_{k+r-1}(n),\ldots,\eps_{k}(n))=\seq b}.
\end{equation}
We will prove the following theorem.


\begin{theorem}\label{thm1}
  Let $q\geq2$ be an even integer and $r\geq1$. For an admissible block $\seq
  b=(b_{r-1},\ldots,b_0)$ with $|b_{r-1}|<\frac q2$ and $\seq b\neq0^r$ the
  number of occurrences of the block $\seq b$ in the symmetric signed digit
  expansions of the positive integers less than $N$ satisfies
\begin{equation}\label{eq:erda}
S_{\seq b}(N)=\frac{Q(b_0)}{q^r(q+1)}N\log_qN+h_0(\seq b)N+
NH_{\seq b}(\log_qN)+\smallOh(N),
\end{equation}
where
\begin{align}
Q(\eta)=&q+
\begin{cases}
2&\text{for }\eta=0,\\
0&\text{for }\eta=\pm\frac q2,\\
1&\text{else,}\\
\end{cases}\\
H_{\seq b}(x)=&\sum_{k\in\Z\setminus\{0\}}h_k(\seq b)e^{2k\pi ix},\notag\\
h_k(\seq b)=&\frac{\log q}{2k\pi i(\log q+2k\pi i)}
\Biggl(\zeta\left(\frac{2k\pi i}{\log q},\cond{\val(\seq b)<0}+q^{-r}\val(\seq
  b)+
  \frac{\Rmin(b_0)}{q^r(q+1)}\right)\notag\\*
&\qquad-\zeta\left(\frac{2k\pi i}{\log q},\cond{\val(\seq b)<0}+q^{-r}\val(\seq
  b)+
  \frac{\Rmax(b_0)}{q^r(q+1)}\right)\Biggr)\text{ for $k\neq 0$},\notag\\
h_0(\seq b)=&\log_q\Gamma\left(\cond{\val(\seq b)<0}+q^{-r}\val(\seq b)+
  \frac{\Rmin(b_0)}{q^r(q+1)}\right)\notag\\
&-\log_q\Gamma\left(\cond{\val(\seq b)<0}+q^{-r}\val(\seq b)+
  \frac{\Rmax(b_0)}{q^r(q+1)}\right)\notag\\
&-\frac{Q(b_0)}{q^r(q+1)}\left(r+\frac12+\frac1{\log q}-\frac 1{q+1}\right)+
\frac1{q^{r-1}(q+1)},\notag\\
\Rmin(\eta)=&-\frac q2-\cond{(\eta-1)\bmod q\geq\frac q2},
\label{eq:Rmin-Rmax-def}\\
\Rmax(\eta)=&\frac q2+\cond{\eta\bmod q<\frac q2}.
\end{align}
The function $H_{\seq b}(x)$ is a periodic continuous function of period $1$
and mean $0$. As usual $\zeta(s,x)$ denotes the Hurwitz $\zeta$-function.
\end{theorem}

\begin{remark}
The case of blocks $\seq b$ with most significant digit $b_{r-1}=\pm\frac q2$
can be reduced to Theorem~\ref{thm1} by using the following simple observation
\begin{equation*}
S_{\seq b}(N)=
\begin{cases}
\displaystyle\sum_{\eta=-\frac q2+1}^0\!\!\!\!\!S_{\eta\seq b}(N)&
\text{for }b_{r-1}=-\frac q2,\\ 
\displaystyle\sum_{\eta=0}^{\frac q2-1}S_{\eta\seq b}(N)&
\text{for }b_{r-1}=\frac q2.
\end{cases}
\end{equation*}
The main term in this case is $\frac12\frac{Q(b_0)}{q^r(q+1)}N\log_qN$.
\end{remark}

The instance $r=1$ (counting digits) was discussed in
\cite{Heuberger-Prodinger:2001:minim-expan}, although without mentioning the
periodic fluctuations in explicit form.  Thuswaldner \cite{thuswaldner:1999}
has used Dirichlet series and the Mellin-Perron summation formula to exhibit
this fluctuating behaviour in the case $q=2$ and $r=1$.

The limit distribution of digital functions of various kinds has been
investigated by several authors. Especially, we mention the work of M.~Drmota
and J.~Gajdosik \cite{Drmota_Gajdosik1998:distribution} for local and central
limit theorems for the sum-of-digits function with respect to recurrence based
numeration systems.  Furthermore, central limit theorems for digital functions
in polynomial subsequences of the integers have been studied by N.~L.~Bassily
and I.~Katai \cite{Bassily1994:distribution,Bassily_Katai1995:distribution}.

We will prove the following central limit theorem for $s_{\mathbf{b}}(n)$.

\begin{theorem}\label{thm2}
Let $s_{\mathbf{b}}(n)$ denote the number of occurrences of the block
$\mathbf{b}$ in the symmetric signed digit expansion of $n$ defined in
\eqref{eq:freya}. Then $s_{\mathbf{b}}$ satisfies
\begin{equation}\label{eq:central}
\lim_{N\to\infty}\frac1N\#\left\{n<N\mid s_{\mathbf{b}}(n)<
\frac{Q(b_0)}{q^r(q+1)}\log_qN+x\sqrt{V_{\mathbf{b}}\log_qN}\right\}=
\frac1{\sqrt{2\pi}}\int\limits_{-\infty}^xe^{-\frac{t^2}2}\,dt,
\end{equation}
where
\begin{multline}\label{eq:Vb}
V_{\mathbf{b}}=\frac{Q(b_0)}{q^r(q+1)}
\Biggl(1+2\sum_{t=1}^{r-1}\cond{b_t=b_0,\ldots,b_{r-1}=b_{r-1-t}}\frac1{q^t}\\
+2\frac q{q^r(q+1)}\left(1-\frac{Q(b_0)}{q+1}\right)
-(2r-1)\frac{Q(b_0)}{q^r(q+1)} \Biggr).
\end{multline}
\end{theorem}


\section{Explicit formul{\ae}}

In \cite{Heuberger-Prodinger:2001:minim-expan} we were able to give
an explicit formula for the $k$-th digit of the 
symmetric signed digit expansion of $n$. 
The problem in this section is to combine this information for
each individual digit of a given admissible block $\seq b$ in
a manageable way.

\smallskip

Theorem~5 of \cite{Heuberger-Prodinger:2001:minim-expan} asserts that the
digits of the symmetric signed digit expansion can be computed by
\begin{equation}\label{eq:digit-formula}
  \eps_k(n)=\sum_{s=0}^{q^2-1}c_s\fl{\frac{n}{q^{k+2}}+\xi_s},
\end{equation}
where $k\ge 0$ and
\begin{align*}
  \xi_s&:=\frac{s(q+1)+q/2+\cond{s\bmod q<q/2}}{q^2(q+1)},\\
  c_s&:=
  \begin{cases}
    -(q-1)&\text{ if $s\bmod q = q/2-\cond{\fl{s/q}\ge q/2}$},\\
    1     &\text{ otherwise}
  \end{cases}
\end{align*}
for $0\le s <q^2$.

It will be convenient to extend \eqref{eq:digit-formula} to arbitrary reals $x$
(instead of the integer $n$) and arbitrary integers $k$. We now show that this
indeed defines a digit expansion for every real $x$.

In the proof of
Theorem~5 in \cite{Heuberger-Prodinger:2001:minim-expan},
\eqref{eq:digit-formula} has been rewritten to
\begin{equation*}
  \eps_k(x)=\sum_{j=0}^{q-1}\left(\fl{\frac{x}{q^{k+1}}+\frac jq +
    \frac{q/2+\cond{j<q/2}}{q(q+1)}}
    -q\fl{\frac{x}{q^{k+2}}+\frac jq +
    \frac{q/2+\cond{j<q/2}}{q(q+1)}}
\right).
\end{equation*}
It is clear that $\eps_k(x)=0$ for sufficiently large $k$. Therefore, we obtain
\begin{equation*}
  \sum_{k=-L}^\infty \eps_k(x)q^k=\sum_{j=0}^{q-1}q^{-L}
  \fl{xq^{L-1}+\frac jq + \frac{q/2+\cond{j<q/2}}{q(q+1)}}=
  x+\bigOh(q^{-L}).
\end{equation*}
This implies $\sum_{k\in\Z} \eps_k(x)q^k=x$ for all $x\in\R$.

Furthermore, the proof of Theorem~5 in
\cite{Heuberger-Prodinger:2001:minim-expan} shows that
$\betrag{\eps_k(x)}\leq\frac q2$ and that $\betrag{\eps_k(x)}=\frac q2$ implies
$0\leq\sign(\eps_k(x))\eps_{k+1}(x)\leq\frac q2-1$.

We also state \eqref{eq:digit-formula} in an alternative way:
\begin{lemma}\label{le:ziffern-formel}
  Let $k\in\Z$, $x\in\R$ and let $\xi_{-1}:=0$ and $\xi_{q^2}:=1$. Then 
  the $\xi_\ell$ are increasing. Choose $0\le s\le q^2$ such that
  \begin{equation}\label{eq:le:ziffern-formel:s-definition}
    \xi_{s-1}\le \fractional{\frac{x}{q^{k+2}}}<\xi_s.
  \end{equation}
  Write $s=mq+j$ where $0\le m$ and $0\le j<q$.

  Then the $k$th digit $\eps_k(n)$ of $n$ can be expressed as
  \begin{equation}\label{eq:le:ziffern-formel:formel}
    \eps_k(n)= \eps_0(s)=
    \begin{cases}
      j&\text{ if }j<q/2,\\
      j-q&\text{ if }j>q/2,\\
      q/2&\text{ if }j=q/2 \text{ and }m<q/2,\\
      -q/2&\text{ if }j=q/2 \text{ and }m\ge q/2.\\
    \end{cases}
  \end{equation}
\end{lemma}
\begin{proof}
  It can easily be checked that the $\xi_\ell$ are increasing.  Since
  $\sum_{\ell=0}^{q^2-1}c_\ell=0$ and since $\xi_\ell+\xi_{q^2-1-\ell}=1$ for
  $-1\le \ell\le q^2$, we can rewrite \eqref{eq:digit-formula} as
\begin{equation*}
  \eps_k(x)=\sum_{\ell=0}^{q^2-1}c_\ell\fl{y+ 1-\xi_{q^2-1-\ell}},
\end{equation*}
where $y=\fractional{x q^{-(k+2)}}$. By the monotonicity of the $\xi_\ell$,
relation \eqref{eq:le:ziffern-formel:s-definition} implies
$\fl{y+1-\xi_\ell}=\cond{\ell\le s-1}$. Therefore, we have
\begin{equation*}
  \eps_k(x)=\sum_{\ell=0}^{s-1}c_\ell
  =\sum_{t=0}^{m-1}\sum_{\ell=0}^q c_{tq+\ell}+\sum_{\ell=0}^{j-1}c_{mq+\ell}.
\end{equation*}
By definition, $\sum_{\ell=0}^q c_{tq+\ell}=0$ for all $0\le t\le q-1$. This
implies that
\begin{equation*}
  \eps_k(x)=\sum_{\ell=0}^{j-1}c_{mq+\ell}=
  j-q\cond{j-1\geq q/2-\cond{m\ge q/2}}.
\end{equation*}
This proves the first equation in \eqref{eq:le:ziffern-formel:formel}. The
second equation in~\eqref{eq:le:ziffern-formel:formel} is Lemma~3 in
\cite{Heuberger-Prodinger:2001:minim-expan}.
\end{proof}
We will now find out how the block $(\eps_{k+r-1}(n),\dots,\eps_k(n))$ can be
calculated from the knowledge of $\fractional{n/q^{k+r+1}}$. To this aim, we
fix some $r\ge 1$, $k\ge 0$ and some $1\le j\le q^{r+1}(q+1)$. We consider an
integer $n$ such that
\begin{equation}\label{eq:n-j-condition}
  \fractional{\frac{n}{q^{k+r+1}}}\in\left[ \frac{j-1}{q^{r+1}(q+1)},
\frac{j}{q^{r+1}(q+1)}\right).
\end{equation}
This implies that
\begin{equation*}
  \frac{(j-1)/q^\ell}{q^2(q+1)}\le \frac{n}{q^{k+\ell+2}}-uq^{r-\ell-1}
  < \frac{j/q^\ell}{q^2(q+1)}
\end{equation*}
for some integer $u$ and all $0\le \ell\le r-1$. By
Lemma~\ref{le:ziffern-formel}, the digit $\eps_{k+\ell}(n)$ depends on $j$ and
$\ell$ only, and not on $n$: If $-1\le s_\ell\le q^2$ is chosen such that
\begin{equation*}
  \xi_{s_\ell-1}\le \fractional{\frac{j-1}{q^{\ell+2}(q+1)}} < \xi_{s_\ell},
\end{equation*}
then
\begin{equation*}
  \eps_{k+\ell}(n)=\eps_0(s_\ell).
\end{equation*}
Using Lemma~\ref{le:ziffern-formel} once more, we get
\begin{equation}\label{eq:j-b-condition}
  \eps_{k+\ell}(n)=\eps_\ell\left(\frac{j-1}{q+1}\right).
\end{equation}
Therefore, we study the digit expansion of real numbers in more detail.

\begin{lemma}\label{lem2}
For all $x\in\R$ there exist unique  $u\in\Z$ and $v\in\R$ with $x=u+v$ such
that 
\begin{equation}\label{eq:lem2:vbound}
  -\frac{q/2+\cond{(\eps_0(u)-1)\bmod q\ge q/2}}{q+1}\le v<
  \frac{q/2+\cond{\eps_0(u)\bmod q< q/2}}{q+1}.
\end{equation}
Furthermore $\eps_\ell(x)=\eps_\ell(u)$ for $\ell\ge 0$.
\end{lemma}
\begin{proof}
Since
\begin{equation*}
\frac{q/2+\cond{\eps_0(u)\bmod q< q/2}}{q+1}=1-
\frac{q/2+\cond{(\eps_0(u+1)-1)\bmod q\ge q/2}}{q+1}
\end{equation*}
existence and uniqueness of $u$ and $v$ follows.

We consider first the case $\ell=0$. By Lemma~\ref{le:ziffern-formel}, there is
some $s$ with $\eps_0(u)=\eps_0(s)$ and $\xi_{s-1}\le
\fractional{u/q^2}<\xi_s$. We assume first $1\le s<q^2$. By definition, we have
\begin{equation*}
  (s-1)+\frac{q/2+\cond{(s-1)\bmod q<q/2}}{q+1}\le
  u-mq^2<s+\frac{q/2+\cond{s\bmod q<q/2}}{q+1}
\end{equation*}
for some integer $m$. Since $u$ is an integer, we conclude that
\begin{equation*}
  (s-1)+\ceil{\frac{q/2+\cond{(s-1)\bmod q<q/2}}{q+1}}\le
  u-mq^2\le s+\ceil{\frac{q/2+\cond{s\bmod q<q/2}}{q+1}}-1.
\end{equation*}
Since the values of the ceiling functions equal $1$, we can rewrite this as
\begin{equation}\label{eq:lem2:ubound}
  \xi_{s-1}+\frac{q/2+\cond{(s-1)\bmod q\ge q/2}}{q^2(q+1)}\le \frac{u}{q^2}-m
  \le 
\xi_s-\frac{q/2+\cond{s\bmod q< q/2}}{q^2(q+1)}.
\end{equation}
Combining this with \eqref{eq:lem2:vbound} yields
\begin{equation*}
  \xi_{s-1}\le \frac{u+v}{q^2}-m<\xi_s,
\end{equation*}
which is equivalent to $\eps_0(u+v)=\eps_0(s)=\eps_0(u)$.

For $s=0$ and $s=q^2$ we have to do some extra work. We only show what happens
for $s=0$: we still have the upper bound as in \eqref{eq:lem2:ubound}. Thus the
only problem occurs, if $\frac{u+v}{q^2}-m<0$. But then 
\begin{equation*}
\xi_{q^2}=1>\frac{u+v}{q^2}-m+1\geq1-\frac{\frac q2+1}{q^2(q+1)}=\xi_{q^2-1}
\end{equation*}
by \eqref{eq:lem2:vbound}. This also implies $\eps_0(x)=\eps_0(u)$ as
requested.

In order to deal with $\ell\geq1$ we consider 
\begin{equation*}
  \sum_{k\ge 0}(\eps_k(x)-\eps_k(u))q^k=
  v-\sum_{k<0} \eps_k(x)q^k.
\end{equation*}
The left hand side is an integer which is divisible by $q$ by the above
discussion. The absolute value of the right hand side is at most
\begin{equation*}
  \frac{q/2+1}{q+1}+\frac q2\sum_{k\ge 1}q^{-k}<2\le q,
\end{equation*}
which implies that both sides vanish. This means that
$\sum_{k\ge 0}\eps_k(x)q^k=\sum_{k\ge 0}\eps_k(u)q^k$.  Since both sides are
symmetric signed digit expansions of the same integer, the digits have to be
equal. 
\end{proof}

\section{Counting blocks}\label{sec:block}

Let $\seq b=(b_{r-1},\ldots,b_0)$ be an admissible block. We want to count the
number of occurrences of the block $\seq b$ as a subblock of the digit
expansions of the integers $0,\ldots,N-1$. In order to avoid technical problems
arising from leading zeros we exclude the block $\seq b=0^r$. Furthermore,
we can exclude blocks $\seq b$ with most significant digit
$b_{r-1}\in\{\pm\frac q2\}$. This ensures that $\eps_\ell(wq^r+\val(\seq
b))=b_\ell$ for $0\le\ell\le r-1$ and $w\in\Z$, because Algorithm~2 of
\cite{Heuberger-Prodinger:2001:minim-expan} does not consider $w$ when
computing the first $r$ digits in that case. For blocks starting with zeros, 
it makes sense to tacitly assume that any number has a sufficient number
of leading zeros. 

Let $\seq b$, $n\ge 1$ and $k\ge 0$ be fixed. 
By \eqref{eq:n-j-condition} and \eqref{eq:j-b-condition}, we have
$(\eps_{k+r-1(n)}, \dots, \eps_{k}(n))=\seq b$ if and only if 
\begin{equation*}
  \fractional{\frac n{q^{k+r+1}}}\in \bigunion_{j\in J(\seq b)}\left[
  \frac{j-1}{q^{r+1}(q+1)}, \frac{j}{q^{r+1}(q+1)}\right),
\end{equation*}
where 
\begin{equation}\label{eq:Jb-definition}
J(\seq b)=\left\{1\le j\le q^{r+1}(q+1): 
\left(\eps_{r-1}\left(\frac{j-1}{q+1}\right),\ldots,
\eps_0\left(\frac{j-1}{q+1}\right)\right)=\seq b\right\}.
\end{equation}

In order to describe the set $J(\seq b)$, 
we write $j-1=(q+1)u+R$ with $\Rmin(\eps_0(u))\leq R<\Rmax(\eps_0(u))$ with
$\Rmin$ and $\Rmax$ defined in \eqref{eq:Rmin-Rmax-def}.  Then by
Lemma~\ref{lem2} we have $\eps_\ell(\frac{j-1}{q+1})=\eps_\ell(u)$ for
$\ell\geq0$ and can rewrite \eqref{eq:Jb-definition} as
\begin{multline*}
J(\seq b)=\bigl\{ j=(q+1)u+R+1: u\in \Z,  1\leq j\le q^{r+1}(q+1),\\
  \Rmin(\eps_0(u))\le R < \Rmax(\eps_0(u)),
  \text{ and } \left(\eps_{r-1}(u),\ldots,\eps_0(u)\right)=\seq b \bigr\}.
\end{multline*}
Under our assumptions on the block $\seq b$ we can write the numbers $u$
satisfying the last condition as $u=wq^r+\val(\seq b)$ with $w\in\Z$. Thus we
arrive at
\begin{multline*}
J(\seq b)=\bigl\{j=(q+1)(wq^r+\val(\seq b))+R+1: w \in \Z, 
  1\le j \le q^{r+1}(q+1), \text{ and } \\
  \Rmin(b_0)\le R < \Rmax(b_0) \bigr\}.
\end{multline*}
Inserting the definition of $j$ in the range given for $j$, we get the
following condition on $w$:
\begin{equation*}
-\fl{q^{-r}\left(\val(\seq b)+\frac R{q+1}\right)}\le w
<q-\fl{q^{-r}\left(\val(\seq b)+\frac R{q+1}\right)}.
\end{equation*}
By \eqref{eq:Rmin-Rmax-def} we have
$\sign(\val(\seq b)+\frac R{q+1})=\sign \val(\seq b)\neq0$ and therefore
\begin{equation*}
0<(\sign \val(\seq b))\left(\val(\seq b)+\frac R{q+1}\right)<q^r.
\end{equation*}
Summing up this gives
\begin{equation*}
\fl{q^{-r}\left(\val(\seq b)+\frac R{q+1}\right)}=-\cond{\val(\seq b)<0}.
\end{equation*}

Thus we reach the following explicit characterization:
\begin{proposition}\label{prop1}
  Let $0^r\neq \seq b$ an admissible block with $\betrag{b_{r-1}}<q/2$, $n$ be
  a positive integer and $k\ge 0$. Let
  \begin{align*}
    I_{\seq b}:=&\bigunion_{\cond{\val(\seq b)<0}\le w < q+\cond{\val(\seq
    b)<0}} \quad
    \bigunion_{\Rmin(b_0)\le R <\Rmax(b_0)}\\
    & \left[
  \frac{wq^r(q+1)+(q+1)\val(\seq b)+R}{q^{r+1}(q+1)},
  \frac{wq^r(q+1)+(q+1)\val(\seq b)+R+1}{q^{r+1}(q+1)}\right).
  \end{align*}
  Then $((\eps_{k+r-1}(n),\dots,\eps_k(n))=\seq b$ if and only if
  \begin{equation*}
    \fractional{\frac{n}{q^{k+r+1}}}\in I_{\seq b}.
  \end{equation*}
\end{proposition}

We now study the sum \eqref{eq:Sb}. We denote the interval
$[\frac{j-1}{q^{r+1}(q+1)},\frac j{q^{r+1}(q+1)})$ by $I_j$ and its
characteristic function by $\mathbbm{1}_{I_j}$. The above proposition shows
that
\begin{equation}\label{eq:Sbjfinal}
S_{\seq b}(N)=\sum_{w=\cond{\val(\seq b)<0}}^{q+\cond{\val(\seq b)<0}-1}
\sum_{R=\Rmin(b_0)}^{\Rmax(b_0)-1}S_{wq^r(q+1)+(q+1)\val(\seq b)+R+1}(N),
\end{equation}
where
\begin{equation}\label{eq:Sjdef}
  S_j(N)=\sum_{n<N}\sum_{k=0}^\infty
\mathbbm{1}_{I_j}\left(\fractional{\frac n{q^{k+r+1}}}\right).
\end{equation}
We note that $(q+1)(wq^r+\val(\seq b))+R+1\geq2$ by \eqref{eq:Rmin-Rmax-def}.



\section{Dirichlet series}\label{dirichlet}
In this section, we study the asymptotic behaviour of the sum $S_j(N)$ defined
in \eqref{eq:Sjdef}, where $1<j\leq q^{r+1}(q+1)$ using Dirichlet generating
functions and the Mellin-Perron summation formula.  

We rewrite $S_j(N)$ as
\begin{equation}\label{eq:abel}
S_j(N)=\sum_{n=1}^N (N-n)\sum_{k=0}^\infty
\left(\mathbbm{1}_{I_j}(\{nq^{-k-r-1}\})-\mathbbm{1}_{I_j}(\{(n-1)q^{-k-r-1}\})
\right)
\end{equation}
using Abel summation. It is clear that the difference in \eqref{eq:abel} only
takes values in $\{0,\pm 1\}$. We now discuss for which $n$ the non-zero values
are taken.

The first term in the difference equals $1$, if
\begin{equation*}
n\equiv u\mod q^{k+r+1}\quad\text{for some }
u\in\left\{\left\lceil\frac{(j-1)q^k}{q+1}\right\rceil,\ldots,
\left\lceil\frac{jq^k}{q+1}\right\rceil-1\right\}.
\end{equation*}
Using a similar expression for the second term in the difference, we obtain
\begin{multline*}
\mathbbm{1}_{I_j}(\{nq^{-k-r-1}\})-\mathbbm{1}_{I_j}(\{(n-1)q^{-k-r-1}\})=\\
\left[n\equiv\left\lceil\frac{(j-1)q^k}{q+1}\right\rceil\mod q^{k+r+1}\right]-
\left[n\equiv\left\lceil\frac{jq^k}{q+1}\right\rceil\mod q^{k+r+1}\right].
\end{multline*}

Now we can write the Dirichlet generating function of
$$\sum_{k=0}^\infty
\left(\mathbbm{1}_{I_j}(\{nq^{-k-r-1}\})-\mathbbm{1}_{I_j}(\{(n-1)q^{-k-r-1}\})
\right)$$
as
\begin{multline}\label{eq:phij}
\sum_{n=1}^\infty\frac1{n^s}\sum_{k=0}^\infty
\left(\mathbbm{1}_{I_j}(\{nq^{-k-r-1}\})-\mathbbm{1}_{I_j}(\{(n-1)q^{-k-r-1}\})
\right)\\*
=\sum_{k=0}^\infty\sum_{n=0}^\infty
\frac1{\left(q^{k+r+1}n+\left\lceil\frac{(j-1)q^k}{q+1}\right\rceil\right)^s}-
\sum_{k=0}^\infty\sum_{n=0}^\infty
\frac1{\left(q^{k+r+1}n+\left\lceil\frac{jq^k}{q+1}\right\rceil\right)^s}.
\end{multline}

It is clearly enough to study functions $\psi_j(s)$ defined by
\begin{equation*}
\psi_j(s)=\sum_{k=0}^\infty\sum_{n=0}^\infty
\frac1{\left(q^{k+r+1}n+\left\lceil\frac{jq^k}{q+1}\right\rceil\right)^s}=
\sum_{n=1}^\infty\frac{\lambda_j(n)}{n^s}=
\sum_{n=1}^\infty\frac{\lambda_j^{(0)}(n)}{n^s}+
\sum_{n=1}^\infty\frac{\lambda_j^{(1)}(n)}{n^s},
\end{equation*}
where $\lambda_j^{(\ell)}(n)$ denotes the contribution originating from the
terms $k\equiv\ell\mod2$ ($\ell=0,1$) in the first sum. The splitting of the
sum is motivated by
\begin{equation*}
\left\lceil\frac{jq^k}{q+1}\right\rceil=\frac{jq^k}{q+1}+
\frac{j(-1)^{k+1}\bmod (q+1)}{q+1}.
\end{equation*}
This leads us to studying  the functions
\begin{equation}\label{eq:dir}
\sum_{n=1}^\infty\frac{\lambda_j^{(\ell)}(n)}{(n-\alpha_j^{(\ell)})^s}=
\sum_{\substack{k\geq0\\k\equiv\ell\bmod2}}\sum_{n=0}^\infty
\frac1{\left(q^{k+r+1}n+\frac{jq^k}{q+1}\right)^s}=
\frac{q^{-(r+\ell-1)s}}{q^{2s}-1}\zeta\left(s,\frac j{(q+1)q^{r+1}}\right),
\end{equation}
where $\alpha_j^{(\ell)}=\frac{j(-1)^{\ell+1}\bmod (q+1)}{q+1}$.

We will use the Mellin-Perron summation formula (cf.~\cite{Tenenbaum:1995}) in
the form
\begin{equation}\label{eq:mel-per}
\sum_{n<N}(N-n)a_n=\frac1{2\pi i}\int\limits_{c-i\infty}^{c+i\infty}
\sum_{n=1}^\infty\frac{a_n}{(n-\alpha)^s}(N-\alpha)^{s+1}\frac{ds}{s(s+1)},
\end{equation}
where $0\leq\alpha<1$ and $c$ is in the half-plane of absolute convergence of
the Dirichlet series. In the sequel we will write $\int_{(c)}$ for the contour
integral over the vertical line $\Re s=c$.  The usefulness of this in the
context of digital counting was described (for $\alpha=0$) in the survey
\cite{Flajolet-Grabner-Kirschenhofer-Prodinger:1994:mellin} and in the slightly
more general situation $0\leq\alpha<1$ in
\cite{Grabner-Kirschenhofer-Prodinger:1998}. Without this version with the
parameter $\alpha$, one could still proceed successfully, as in
\cite{thuswaldner:1999}, but that would be considerably more cumbersome and
less elegant.

Applying \eqref{eq:mel-per} to the two functions in \eqref{eq:dir} separately
with the two values of $\alpha_j^{(\ell)}$ we obtain
\begin{equation}\label{eq:sumlambda}
\begin{aligned}
\sum_{n<N}(N-n)\lambda_j(n)&=\sum_{n<N}(N-n)\lambda_j^{(0)}(n)+
\sum_{n<N}(N-n)\lambda_j^{(1)}(n)\\
&=\frac1{2\pi i}\int\limits_{(2)}
\frac{q^{-(r-1)s}}{q^{2s}-1}\zeta(s,\beta_j)
(N-\alpha_j^{(0)})^{s+1}\frac{ds}{s(s+1)}\\
&+\frac1{2\pi i}\int\limits_{(2)}
\frac{q^{-rs}}{q^{2s}-1}\zeta(s,\beta_j)
(N-\alpha_j^{(1)})^{s+1}\frac{ds}{s(s+1)},
\end{aligned}
\end{equation}
where $\beta_j=\frac j{(q+1)q^{r+1}}$ We now notice that
$\zeta(\sigma+it,\alpha)=\bigOh(|t|^{\frac12-\sigma})$ for $\sigma\leq0$
(cf.~\cite{Tenenbaum:1995}). Thus we can shift the line of integration to
$\Re s=-\frac14$ by taking residues at the poles in $s=1$ and
$s=\frac{k\pi i}{\log q}=:\chi_k$ into account to obtain 
\begin{equation}\label{eq:asymp}
\begin{aligned}
  \sum_{n<N}(N-n)\lambda_j(n)&=
  \frac{q^{-(r-1)}}{2(q^2-1)}(N-\alpha_j^{(0)})^2+
  \frac{q^{-r}}{2(q^2-1)}(N-\alpha_j^{(1)})^2\\
  &+\frac{1-2\beta_j}4(N-\alpha_j^{(0)})\log_q(N-\alpha_j^{(0)})+
  \frac{1-2\beta_j}4(N-\alpha_j^{(1)})\log_q(N-\alpha_j^{(1)})\\
  &-\frac{1-2\beta_j}4\left(r+\frac1{\log q}\right)(N-\alpha_j^{(0)})-
  \frac{1-2\beta_j}4\left(r+1+\frac1{\log q}\right)(N-\alpha_j^{(1)})\\
  &+\frac1{2\log q}\zeta'(0,\beta_j)(2N-\alpha_j^{(0)}-\alpha_j^{(1)})\\
  &+(N-\alpha_j^{(0)})\sum_{k\in\mathbb{Z}\setminus\{0\}}
  \frac{(-1)^{k(r-1)}}{2\log q}
  \frac{\zeta(\chi_k,\beta_j)}{\chi_k(\chi_k+1)}(N-\alpha_j^{(0)})^{\chi_k}\\
  &+(N-\alpha_j^{(1)})\sum_{k\in\mathbb{Z}\setminus\{0\}}\frac{(-1)^{kr}}{2\log
    q}
  \frac{\zeta(\chi_k,\beta_j)}{\chi_k(\chi_k+1)}(N-\alpha_j^{(1)})^{\chi_k}\\
  &+\frac1{2\pi i}\int\limits_{(-\frac14)}\cdots ds+ \frac1{2\pi
    i}\int\limits_{(-\frac14)}\cdots ds.
\end{aligned}
\end{equation}
It is clear from the absolute convergence of the two integrals that they are
bounded by $\bigOh(N^{\frac34})$.


Similarly to the cases studied in
\cite{Flajolet-Grabner-Kirschenhofer-Prodinger:1994:mellin} and
\cite{Grabner-Kirschenhofer-Prodinger:1998} the above integrals could be
computed by writing $\frac1{q^{2s}-1}$ as a geometric series and shifting the
line of integration back to $\Re s=2$. Since the resulting formul\ae{} are
highly unpleasant, we restrict ourselves to the two asymptotic main
terms.


% In order to derive more precise
% information on their value, we proceed as follows:
% We compute
% \begin{multline}\label{eq:geom-sum}
% \frac1{2\pi i}\int\limits_{(-\frac14)}\frac{q^{-(r+\ell-1)s}}{q^{2s}-1}
% \zeta(s,\beta_j)(N-\alpha_j^{(\ell)})^{s+1}\frac{ds}{s(s+1)}=\\
% -\sum_{k=1}^\infty q^{-2k+\ell}\frac1{2\pi i}\int\limits_{(-\frac14)}
% \zeta(s,\beta_j)\left(q^{(2k-\ell)}(N-\alpha_j^{(\ell)})\right)^{s+1}
% \frac{ds}{s(s+1)}.
% \end{multline}
% Thus we only have to compute the integral in the sum
% This done by shifting the line of integration back to $\Re s=2$ and using
% \eqref{eq:mel-per} (note that
% $q^{2k-\ell}(N-\alpha_j^{(\ell)})-\beta_j\in\mathbb{N}$ by definition):
% \begin{align*}
% &\frac1{2\pi i}\int\limits_{(-\frac14)}
% \zeta(s,\beta_j)\left(q^{(2k-\ell)}(N-\alpha_j^{(\ell)})\right)^{s+1}
% \frac{ds}{s(s+1)}\\
% =&-q^{2k-\ell}(N-\alpha_j^{(\ell)})\left(\frac12-\beta_j\right)-
% \frac12q^{4k-2\ell}(N-\alpha_j^{(\ell)})^2\\
% &+\frac1{2\pi i}\int\limits_{(2)}
% \zeta(s,\beta_j)\left(q^{(2k-\ell)}(N-\alpha_j^{(\ell)})\right)^{s+1}
% \frac{ds}{s(s+1)}\\
% =&-q^{2k-\ell}(N-\alpha_j^{(\ell)})\left(\frac12-\beta_j\right)-
% \frac12q^{4k-2\ell}(N-\alpha_j^{(\ell)})^2\\
% &+\sum_{n=0}^{q^{2k-\ell}(N-\alpha_j^{(\ell)})-\beta_j}
% \left(q^{2k-\ell}(N-\alpha_j^{(\ell)})-\beta_j-n\right)\\
% &=-\frac12\beta_j(1-\beta_j).
% \end{align*}
% Inserting this into \eqref{eq:geom-sum} yields
% \begin{multline*}
% \frac1{2\pi i}\int\limits_{(-\frac14)}\frac{q^{2s}}{q^{2s}-1}
% \zeta(s,\beta_j)(N-\alpha_j^{(0)})^{s+1}\frac{ds}{s(s+1)}\\
% +\frac1{2\pi i}\int\limits_{(-\frac14)}\frac{q^s}{q^{2s}-1}
% \zeta(s,\beta_j)(N-\alpha_j^{(1)})^{s+1}\frac{ds}{s(s+1)}=
% \frac12\beta_j(1-\beta_j)\frac1{q-1}
% \end{multline*}

% This computation shows that there holds an exact formula for
% $\sum(N-n)\lambda_j(n)$ which involves powers of $N$, evaluations of the
% logarithm at $(N-\alpha_j^{(\ell)})$ and periodic functions of period $2$
% evaluated at $\log_q(N-\alpha_j^{(\ell)})$. Since the complexity of this exact
% formula would still increase by collecting all further terms, we will now only
% consider the asymptotic main terms of this formula.

Thus we have
\begin{multline}\label{eq:lambda-sum}
\sum_{n<N}(N-n)\lambda_j(n)=\frac12\frac 1{q^r(q-1)}N^2+
\left(\frac12-\beta_j\right)N\log_qN\\*
+\left(\log_q\Gamma(\beta_j)-
\frac12\log_q2\pi-
\left(\frac12-\beta_j\right)\left(\frac1{\log q}+\frac12+r\right)-
\frac{q\alpha_j^{(0)}+\alpha_j^{(1)}}{q^r(q^2-1)}\right)N\\
+N\left(F_j(\log_qN)+F_j(\log_qN+1)\right)+\bigOh(\log N)+
\bigOh\bigg(N\omega\Big(F_j,\frac1N\Big)\bigg),
\end{multline}
where the periodic function $F_j$ of period $2$  is given by its absolutely
convergent Fourier series
\begin{equation*}
F_j(x)=\sum_{k\in\mathbb{Z}\setminus\{0\}}\frac{(-1)^{kr}}{2\log q}
\frac{\zeta(\chi_k,\beta_j)}{\chi_k(\chi_k+1)}e^{k\pi i x}
\end{equation*}
and $\omega(F_j,\delta)$ denotes the modulus of continuity of $F_j$. Clearly, 
$G_j(x)=F_j(x)+F_j(x+1)$ is a periodic function of period $1$ with Fourier
series
\begin{equation*}
G_j(x)=\sum_{k\in\mathbb{Z}\setminus\{0\}}\frac1{\log q}
\frac{\zeta(\chi_{2k},\beta_j)}{\chi_{2k}(\chi_{2k}+1)}e^{2k\pi i x}.
\end{equation*}

Putting everything together we obtain
\begin{equation}\label{eq:SN-asymp}
\begin{aligned}
S_j(N)=&\sum_{n<N}(N-n)(\lambda_{j-1}(n)-\lambda_j(n))\\
=&\frac1{(q+1)q^{r+1}}N\log_qN\\
&+\Biggl(\log_q\frac{\Gamma(\beta_{j-1})}{\Gamma(\beta_j)}-
\frac1{(q+1)q^{r+1}}\left(\frac1{\log q}+\frac12+r\right)-
\frac 1{q^r(q+1)^2}\\
&\qquad+\frac{q[j\equiv1\bmod(q+1)]-[j\equiv0\bmod(q+1)]}{q^r(q^2-1)}
\Biggr)N\\
&+N\left(G_{j-1}(\log_qN)-G_j(\log_qN)\right)+\smallOh(N).
\end{aligned}
\end{equation}

In order to obtain an asymptotic expression for $S_{\seq b}(N)$ stated in
Theorem~\ref{thm1} we have to
combine the equations \eqref{eq:Sbjfinal} and \eqref{eq:SN-asymp}. For this
purpose we need two identities:
\begin{align*}
&\sum_{w=0}^{q-1}\log_q\Gamma\left(x+\frac wq\right)=\frac{q-1}2\log_q2\pi
+\frac12-qx+\log_q\Gamma(qx)\quad\text{for }q\geq2\quad
\text{(cf.~\cite{Magnus-Oberhettinger-Soni:1966})},\\
&\sum_{w=0}^{q-1}\zeta\left(s,\frac wq+x\right)=
q^s\sum_{n=0}^\infty\sum_{w=0}^{q-1}\frac1{(nq+w+qx)^s}=q^s\zeta(s,qx)
\quad\text{for }x>0.
\end{align*}
Furthermore, we notice that $[\val(\seq b)<0]+q^{-r}\val(\seq
b)+\frac{\Rmin(b_0)}{q^{r}(q+1)}>0$. This yields \eqref{eq:erda}.

\section{A central limit theorem}\label{sec:centr-limit-theor}
In this section we will sketch a proof of Theorem~\ref{thm2}. 

We first construct a probability space (Kubilius model, cf.~\cite{Elliott:1979:probab}),
which will be used to approximate the values of $s_{\mathbf{b}}(n)$ by random
variables. For this purpose we consider the infinite product space
\begin{equation*}
\Omega=\left\{-\frac q2,\ldots,\frac q2\right\}^{\mathbb{N}_0}
\end{equation*}
equipped with a probability measure $\mu$ given on cylinder sets by
\begin{equation*}
\mu\left(\{(\omega_j)_{j\geq0}\mid \omega_j=a_j\text{ for }j\leq k-1\}\right)=
\lim_{N\to\infty}\frac1{N}\#\left\{n<N\mid \eps_{k-1}(n)=a_{k-1},\ldots,
\eps_0(n)=a_0\right\}.
\end{equation*}
The limit exists, since the subsets of $\mathbb{N}$ given by fixing a finite
number of digits correspond to residue classes modulo a power of $q$ by
Proposition~\ref{prop1}. From this fact it also follows that (for
$j_0<j_1<\cdots<j_s$)
\begin{multline}\label{eq:myapprox}
\frac1{N}\#\left\{n<N\mid \eps_{j_s}(n)=a_{j_s},\ldots,
\eps_{j_0}(n)=a_{j_0}\right\}=\\
\mu\left(\left\{(\omega_j)_{j\geq0}\mid \omega_{j_s}=a_{j_s},\ldots,
\omega_{j_0}=a_{j_0}\right\}\right)+\mathcal{O}\left(\frac{q^{j_s}}N\right).
\end{multline}

We define random variables
\begin{equation*}
X_k(\omega)=[(\omega_{k+r-1},\ldots,\omega_k)=\mathbf{b}].
\end{equation*}
From the definition of $\mu$ and Proposition~\ref{prop1} it follows that
\begin{equation}\label{eq:myX_k}
\mu\left(X_k=1\right)=\frac{Q(b_0)}{q^r(q+1)}+\frac{(-1)^k}{q^{k+r}}
\left(1-\frac{Q(b_0)}{q+1}\right),
\end{equation}
which shows that the random variables $X_k$ are not quite identically
distributed. Furthermore, we compute the joint distribution of $X_k$ and
$X_{k+t}$ for $t>r$:
\begin{multline}\label{eq:myX_kX_k+t}
\mu\left(X_k=1\wedge X_{k+t}=1\right)=\\
\mu\left(X_k=1\right)
\left(\mu\left(X_{k+t}=1\right)+
\frac{(-1)^{t+r}}{q^t}\left(1-\frac{(-1)^{k+r}}{q^{k+r}}\right)
\left(1-\frac{Q(b_0)}{q+1}\right)\right),
\end{multline}
which shows that the random variables $X_k$ and $X_{k+t}$ are not independent.
The probabilities in the case $t\leq r$ depend on the self-overlapping
structure of $\mathbf{b}$ and can be computed using \eqref{eq:myX_k}. The
variance of $\sum_{k=0}^KX_k$ can be computed
\begin{multline}\label{eq:var}
\mathbb{V}\left(\sum_{k=0}^KX_k\right)=K\frac{Q(b_0)}{q^r(q+1)}
\Biggl(1+2\sum_{t=1}^{r-1}\cond{b_t=b_0,\ldots,b_{r-1}=b_{r-1-t}}\frac1{q^t}\\
+2\frac q{q^r(q+1)}\left(1-\frac{Q(b_0)}{q+1}\right)
-(2r-1)\frac{Q(b_0)}{q^r(q+1)} \Biggr)+\mathcal{O}(1)
=V_{\mathbf{b}}K+\mathcal{O}(1).
\end{multline}
Equation \eqref{eq:myX_kX_k+t} shows that the random variables $X_k$ are
$\varphi$-mixing in the sense of \cite{Philipp:1971:mixin} with
$\varphi(t)=\mathcal{O}(q^{-t})$. An application of
\cite[Theorem~1.2.3]{Philipp:1971:mixin} yields the central limit theorem for
$X_k$
\begin{equation}\label{eq:philipp}
\lim_{K\to\infty}\mu\left(\sum_{k=0}^KX_k<\frac{Q(b_0)}{q^r(q+1)}K+
x\sqrt{KV_{\mathbf{b}}}\right)=
\frac1{\sqrt{2\pi}}\int\limits_{-\infty}^xe^{-\frac{t^2}2}\,dt.
\end{equation}

For technical reasons we replace the function $s_{\mathbf{b}}(n)$ by
\begin{equation*}
\tilde s_{\mathbf{b}}(n)=\sum_{k\leq\log_qN-\log^{\frac13}N}
\cond{(\eps_{k+r-1}(n),\ldots,\eps_{k}(n))=\seq b}
\end{equation*}
and notice that
$s_{\seq b}(n)-\tilde s_{\seq b}(n)=\mathcal{O}(\log^{\frac13}N)$. From
\eqref{eq:myapprox} it follows that the normalized moments of
$\tilde s_{\seq b}(n)$ converge to the same limit as the corresponding moments
of $\sum_{k\leq\log_qN-\log^{\frac13}N}X_k$. Since \eqref{eq:philipp} holds the
convergence of moments implies
\begin{equation*}
\lim_{N\to\infty}\frac1N\#\left\{n<N\mid \tilde s_{\seq b}(n)<
\frac{Q(b_0)}{q^r(q+1)}\log_qN+x\sqrt{V_{\mathbf{b}}\log_qN}\right\}=
\frac1{\sqrt{2\pi}}\int\limits_{-\infty}^xe^{-\frac{t^2}2}\,dt
\end{equation*}
by the Fr\'echet-Shohat theorem (cf.~\cite[Lemma~1.43]{Elliott:1979:probab}).
\begin{ackn}
The authors thank an anonymous referee for pointing out the possiblity to prove
a central limit theorem.
\end{ackn}

\bibliographystyle{plain}
\providecommand{\etc}{\emph{etc.}}\providecommand{\etc}{\emph{etc.}}
\def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{Bassily1994:distribution}
N.~L. Bassily.
\newblock Distribution of {$q$}-ary digits in some sequences of integers.
\newblock {\em Ann. Univ. Sci. Budapest. Sect. Comput.}, 14:13--22, 1994.
\newblock Festschrift for the 50th birthday of Karl-Heinz Indlekofer.

\bibitem{Bassily_Katai1995:distribution}
N.~L. Bassily and I.~K{\'a}tai.
\newblock Distribution of the values of {$q$}-additive functions on polynomial
  sequences.
\newblock {\em Acta Math. Hungar.}, 68:353--361, 1995.

\bibitem{Delange:1975:chiffres}
H.~Delange.
\newblock Sur la fonction sommatoire de la fonction``somme des chiffres''.
\newblock {\em Enseignement Math. (2)}, 21(1):31--47, 1975.

\bibitem{Drmota_Gajdosik1998:distribution}
M.~Drmota and J.~Gajdosik.
\newblock The distribution of the sum-of-digits function.
\newblock {\em J. Th\'eor. Nombres Bordeaux}, 10:17--32, 1998.

\bibitem{Elliott:1979:probab}
P.~D. T.~A. Elliott.
\newblock {\em Probabilistic number theory. {I}, {M}ean-value theorems}, volume
  239 of {\em Grundlehren der Mathematischen Wissenschaften}.
\newblock Springer-Verlag, New York, 1979.

\bibitem{Flajolet-Grabner-Kirschenhofer-Prodinger:1994:mellin}
Ph. Flajolet, P.~J. Grabner, P.~Kirschenhofer, H.~Prodinger, and R.~F. Tichy.
\newblock Mellin transforms and asymptotics: digital sums.
\newblock {\em Theoret. Comput. Sci.}, 123:291--314, 1994.

\bibitem{Grabner-Kirschenhofer-Prodinger:1998}
P.~J. Grabner, P.~Kirschenhofer, and H.~Prodinger.
\newblock The sum-of-digits function for complex bases.
\newblock {\em J. London Math. Soc. (2)}, 57(1):20--40, 1998.

\bibitem{Graham-Knuth-Patashnik:1994}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete mathematics. {A} foundation for computer science}.
\newblock Addison-Wesley, second edition, 1994.

\bibitem{Heuberger-Prodinger:2001:carry-propag}
C.~Heuberger and H.~Prodinger.
\newblock Carry propagation in signed digit representations.
\newblock Preprint. Available at
  \url{http://www.opt.math.tu-graz.ac.at/~cheub/publications/carry.ps}.

\bibitem{Heuberger-Prodinger:2001:minim-expan}
C.~Heuberger and H.~Prodinger.
\newblock On minimal expansions in redundant number systems: Algorithms and
  quantitative analysis.
\newblock {\em Computing}, 66:377--393, 2001.

\bibitem{Kirschenhofer:1983:subbl}
P.~Kirschenhofer.
\newblock Subblock occurrences in the $q$-ary representation of $n$.
\newblock {\em SIAM J. Algebraic Discrete Methods}, 4(2):231--236, 1983.

\bibitem{Kirschenhofer-Prodinger:1984}
P.~Kirschenhofer and H.~Prodinger.
\newblock Subblock occurrences in positional number systems and {G}ray code
  representation.
\newblock {\em J. Inform. Optim. Sci.}, 5(1):29--42, 1984.

\bibitem{Magnus-Oberhettinger-Soni:1966}
W.~Magnus, F.~Oberhettinger, and R.~P. Soni.
\newblock {\em Formulas and Theorems for the Special Functions of Mathematical
  Physics}.
\newblock Springer, Berlin, New York, 1966.

\bibitem{Philipp:1971:mixin}
W.~Philipp.
\newblock {\em Mixing sequences of random variables and probabilistic number
  theory}.
\newblock Number 114 in Memoirs of the American Mathematical Society. American
  Mathematical Society, Providence, R. I., 1971.

\bibitem{Reitwiesner:1960}
G.~W. Reitwiesner.
\newblock Binary arithmetic.
\newblock In {\em Advances in computers}, volume~1, pages 231--308. Academic
  Press, New York, 1960.

\bibitem{Tenenbaum:1995}
G.~Tenenbaum.
\newblock {\em Introduction to analytic and probabilistic number theory}.
\newblock Cambridge University Press, Cambridge, 1995.

\bibitem{thuswaldner:1999}
J.~M. Thuswaldner.
\newblock Summatory functions of digital sums occurring in cryptography.
\newblock {\em Period. Math. Hungar.}, 38:111--130, 1999.

\end{thebibliography}


%\bibliography{Signed_Block}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
