
%\documentclass[a4paper]{article}
%\usepackage[centertags,reqno]{amstex}

\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,12pt]{amsart}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter

\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\hfuzz=10pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\theorembodyfont{\slshape}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\def\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}


\RequirePackage{theorem}



\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

\newcommand{\ackno}{\subsection*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}


\begin{document}
\title[The Cantor---Fibonacci Distribution]{The Cantor---Fibonacci Distribution}
\author[ H.~Prodinger]
{ Helmut Prodinger}


\thanks{This research was partly done while the  author
was visiting the CRM (Centre de Recerca Matem\`atica, Institut
d'Estudis Catalans). }




\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{  Helmut.Prodinger@@tuwien.ac.at}



\date{\today}
\begin{abstract} The Cantor--Fibonacci distribution is defined by a random series
where the coefficients are 0 or 1 and no two adjacent 1's are allowed.
A recurrence for the moments is obtained which is then evaluated asymptotically.
\end{abstract} 

\maketitle

\def\P{{\Bbb {P}}}
\def\t{\vartheta}\def\tt{\bar{\vartheta}}
\def\v{\textsf{value}}
\def\F{{\cal {F}}}
\def\eps{\varepsilon}
\def\mm{\widehat m}




\section{Introduction}

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.

We might of course alternatively think of an infinite (random) word 
$w_1w_2\dots$ over the alphabet
$\{0,1\}$ and a mapping \v, defined by
\begin{equation}
\v(w_1w_2\dots)=\frac{\tt}{\t}\sum_{i\ge1}w_i\t ^i~.
\end{equation}
Observe the recursion formula
\begin{align}\begin{split}
\v(0w)&=\t\cdot\v(w)\\
\v(1w)&=\tt+\t\cdot\v(w)~.
\end{split}\end{align}

Whenever we are dealing with words over the alphabet $\{0,1\}$, we might
also think about {\sl restricted words}, according to the
{\sl Fibonacci restriction}, that two adjacent letters `1' are not allowed.

Compare some of the 
%beautiful 
papers of the author for that
\cite{Prodinger81, Prodinger83, Prodinger87}.

The set of (finite) Fibonacci words $\F$ (no two adjacent letters `1') is
given by
\begin{equation}\label{F:eq}
\F=\{0,10\}^\ast\{\eps+1\};
\end{equation}
here, `$\ast$' means arbitrary repetitions and `$\eps$' the empty word.
There is also the recurrence
\begin{equation}
\F=\eps+1+\{0,10\}\F~.
\end{equation}

In the original setting probabilities are simply introduced by saying that each letter can
appear with probability $\frac{1}{2}$. Here, the situation is more complicated.
We say that each Fibonacci word of length $m$ is equally likely. There are $F_{m+2}$ 
such words, with  $F_{m+2}$ denoting the $(m+2)$th Fibonacci number, whence the name.
We will work with finite words, and then letting the length $m$ tend to infinity.
In the independent original case this can be avoided, but here it is necessary.

As an example, consider the classical Cantor case with $\t=\frac13$ and $m=3$.
Then the values
\begin{align}\begin{split}
&2\Big(0\cdot \frac{1}{3}+ 0\cdot \frac{1}{9}+0\cdot \frac{1}{27} \Big)=0\\
&2\Big(0\cdot \frac{1}{3}+ 0\cdot \frac{1}{9}+1\cdot \frac{1}{27} \Big)=\frac{2}{27}\\
&2\Big(0\cdot \frac{1}{3}+ 1\cdot \frac{1}{9}+0\cdot \frac{1}{27} \Big)=\frac{2}{9}\\
&2\Big(1\cdot \frac{1}{3}+ 0\cdot \frac{1}{9}+0\cdot \frac{1}{27} \Big)=\frac{2}{3}\\
&2\Big(1\cdot \frac{1}{3}+ 0\cdot \frac{1}{9}+1\cdot \frac{1}{27} \Big)=\frac{20}{27}
\end{split}\end{align}
appear, each with probability $\frac15$.









It is also useful to have $F(z)$, the generating function of Fibonacci words,
according to their lengths. From (\ref{F:eq}) and general principles we get it as
\begin{equation}
F(z)=\frac{1+z}{1-z-z^2}=\sum_{m\ge0}F_{m+2}z^m~
;
\end{equation}
note that
\begin{equation}
F_n=\frac{1}{\sqrt5}\Big(\alpha^n-\beta^n\Big)\qquad
\text{with}
\quad
\alpha=\frac{1+\sqrt5}{2}\quad\text{and}\quad
\beta=\frac{1-\sqrt5}{2}  \ .
\end{equation}










\section{The Moments}

Lad and Taylor in their original paper \cite{LadTay92} have considered the
$n$th moment of the Cantor distribution. They obtained a recursion for them, which was
analyzed by Grabner and the author in \cite{GraPro94}. Other papers dealing with
the Cantor distribution are \cite{Hosking94} and \cite{KnoPro94}.


In this paper, we want to analyze the
$n$th moments of the Cantor--Fibonacci distribution. We do this by considering the
generating functions
\begin{equation}
G_n(z):=\sum_{w\in\F}\Big(\v(w)\Big)^n\, z^{|w|}~;
\end{equation}
where $|w|$ denotes the length of the Fibonacci word $w$.
The quantity
\begin{equation}
\frac{[z^m]G_n(z)}{[z^m]F(z)}
\end{equation}
is then the $n$th moment, when considering words of length $m$; finally we consider the
limit of this for $m\to\infty$  and call it $M_n$. 

We rewrite the recursion for \v, when restricted to Fibonacci words;
\begin{align}\begin{split}
\v(0w)&=\t\cdot\v(w)\\
\v(10w)&=\tt+\t^2\cdot\v(w)~.
\end{split}\end{align}
Note also that $\v(\eps)=0$ and $\v(1)=\tt$.
Using the recursion $\F=\eps+1+\{0,10\}\F$, we find for $n\ge1$ 
\begin{align}\begin{split}
G_n(z)&=\tt^nz+\t^nzG_n(z)+\sum_{w\in\F}\Big(\tt+\t^2\v(w)\Big)^nz^{2+|w|}\\
&=\tt^nz+\t^nzG_n(z)+z^2\sum_{i=0}^n\binom{n}{i}\tt^{n-i}\t^{2i}\, G_i(z)~.
\end{split}\end{align}
This recursion can be made explicit by rewriting it as
\begin{equation}
G_n(z)=\frac{1}{1-\t^nz-\t^{2n}z^2}\,\bigg[
\tt^nz+z^2\sum_{i=0}^{n-1}\binom{n}{i}\tt^{n-i}\t^{2i}\, G_i(z)
\bigg]
\end{equation}
Note the special instance $G_0(z)=F(z)$
and
\begin{equation}
G_1(z)=\frac{1}{1-\t z-\t^{2}z^2}\,\bigg[\tt z+z^2\tt F(z)\bigg]=
\frac{\tt z}{(1-\t z-\t^{2}z^2)(1-z-z^2)}\ .
\end{equation}

From this we could get (by partial fraction decomposition)  the coefficient of
$z^m$ explicitly.



However, since we only consider the limit for $m\to\infty$, life is easier.
Both, $G_1(z)$
and $F(z)$ have the dominant singularity at $z=1/\alpha$, and it is a simple pole.
Consequently,
\begin{equation}
[z^m]G_1(z)\sim A \alpha^m, \qquad\text{with}\quad A=\lim_{z\to 1/\alpha}(1-z\alpha)G_1(z)
\end{equation}
and
\begin{equation}
[z^m]F(z)\sim B \alpha^m, \qquad\text{with}\quad B=\lim_{z\to 1/\alpha}(1-z\alpha)F(z)
\end{equation}
Therefore
\begin{equation}
\lim_{m\to\infty}\frac{[z^m]G_1(z)}{[z^m]F(z)}=\frac AB\ ,
\end{equation}
which we can compute as
\begin{equation}
\lim_{z\to 1/\alpha}
\frac{\frac{\tt z}{1-\t z-\t^2 z^2}}{1+z}=\frac{\tt}{\alpha^2-\alpha\t-\t^2} \ .
\end{equation}



The fact that $z=1/\alpha$ is a simple pole remains true for all the functions
$G_n(z)$. We can thus divide $G_n(z)$ by
$F(z)$, cancel the pole, and insert $z=1/\alpha$ in the rest, to obtain the
$n$th moment $M_n$ as
\begin{equation}
M_n=
\frac{1}{1-\t^n /\alpha-\t^{2n} /\alpha^2}\bigg[
\frac1{\alpha^2}\sum_{k=0}^{n-1}\binom nk\tt^{n-k}\t^{2k}M_k
\bigg]\ .
\end{equation}

\begin{theorem}
The moments of the Cantor--Fibonacci distribution fulfill the following recursion:
$M_0=1$ and for $n\ge1$
\begin{equation}
M_n=
\frac{1}{\alpha^2-\alpha\t^n -\t^{2n} }
\sum_{k=0}^{n-1}\binom nk\tt^{n-k}\t^{2k}M_k \   .
\end{equation}
\end{theorem}
For instance
\begin{align}\begin{split}
M_1&=\frac{\tt}{\alpha^2-\alpha\t-\t^2} \ ,\\
M_2&=\frac{\tt^2(\alpha^2-\alpha\t+\t^2)}
	{(\alpha^2-\alpha\t^2-\t^4)(\alpha^2-\alpha\t-\t^2)}\ , \\
\text{Variance}&=M_2-M_1^2=\frac{\tt^4\alpha^3}
	{(\alpha^2-\alpha\t^2-\t^4)(\alpha^2-\alpha\t-\t^2)^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 
(= non--Fibonacci)
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=\tt+\lambda\t^2$, or
\begin{equation}
\lambda=\frac{1}{1+\t} \ .
\end{equation}
This is not rigorous, but we can set
\begin{equation}
m_n:=M_n\cdot (1+\t)^n
\end{equation}
anyway and show that this sequence has nicer properties. It fulfills the {\sl modified
recurrence}
\begin{equation}
m_n=
\frac{1}{\alpha^2-\alpha\t^n -\t^{2n} }
\sum_{k=0}^{n-1}\binom nk(1-\t^2)^{n-k}\t^{2k}m_k \ .
\end{equation}
To study this sequence further, we rewrite it as
\begin{equation}
m_n(\alpha^2-\alpha\t^n -\t^{2n})=
\sum_{k=0}^{n}\binom nk(1-\t^2)^{n-k}\t^{2k}m_k -\t^{2n}m_n
\end{equation}
or
\begin{equation}
m_n(\alpha^2-\alpha\t^n )=
\sum_{k=0}^{n}\binom nk(1-\t^2)^{n-k}\t^{2k}m_k 
\end{equation}
and note that  this holds for all $n\ge0$. Then we introduce the {\sl exponential generating
function}
\begin{equation}
m(z)=\sum_{n\ge0}m_n\frac{z^n}{n!}
\end{equation}
and get
\begin{equation}
\alpha^2m(z)-\alpha m(\t z)=e^{(1-\t^2)z}m(\t^2z) .
\end{equation}
As  in \cite{GraPro94}, we have to consider the {\sl Poisson transformed function\/}
$\mm(z)=e^{-z}m(z)$, which fulfills the functional equation
\begin{equation}
\mm(z)
=\frac{e^{-\tt z}}{\alpha}\mm(\t z)+\frac1{\alpha^2}\mm(\t^2z) \ .
\end{equation}
This functional equation can -- at least in principle -- be solved by
{\sl iteration}. Even though it is hard to write down the explicit solution,
we can consider it to be a {\sl known function}.

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 {\sl de--Poissonization}. A preliminary reference for that is
\cite{RaJaSz93}. However, Jacquet and Szpankowski are currently working
on a monography about de--Poissonization, which will be the ultimate
reference for at least the next ten years. We follow \cite{GraPro94},
where the technique is explained in more detail. 

It might be suggestive to
use a new name $R(z)$ for $\frac{e^{-\tt z}}{\alpha}\mm(\t z)$ and consider
it to be an auxiliary (and known) function;
\begin{equation}\label{m:eq}
\mm(z)
=\frac1{\alpha^2}\mm(\t^2z)+R(z)\  .
\end{equation}
We compute the {\sl Mellin transform\/} of (\ref{m:eq})\ \ (see \cite{FlGoDu95} for definitions
and properties);
\begin{equation}
\mm^\ast(s)
=\frac1{\alpha^2}\t^{-2s}\mm^\ast(s)+R^\ast(s)=\frac{R^\ast(s)}{1-\alpha^{-2}\t^{-2s}}\ .
\end{equation}
The  function $m(z)$ can be recovered from this by {\sl 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-\alpha^{-2}\t^{-2s}}\,z^{-s}\,ds\ ,
\end{equation}
where $0<c<-\log_\t\alpha$. By shifting the integral to the right and taking the {\sl negative
residues\/} into account, we get the desired asymptotic behaviour of $\mm(z)$.
There are simple poles at $s=-\log_\t\alpha+\frac{2k\pi i}{\log\t}$, $k\in\Bbb Z$.
The negative residue there is
\begin{equation}
-\frac{1}{2\log\t}R^\ast\Big(-\log_\t\alpha+\frac{2k\pi i}{\log\t}\Big)\,z^{\log_\t\alpha-\frac{2k\pi i}{\log\t}}\ .
\end{equation}
The value for $k=0$ is of special interest; it is, to make it more explicit,
\begin{equation}
-\frac{1}{2\log\t} z^{\log_\t\alpha}
\int_0^\infty     
\frac{e^{-\tt z}}{\alpha}\,\mm(\t z)\, z^{-\log_\t\alpha-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--Fibonacci distribution has for $n\to\infty$ the following
asymptotic behaviour
\begin{equation}
M_n=(1+\t)^{-n}\Phi(-\log_\t n)\,n^{\log_\t\alpha}\Big(1+O\big(\frac 1n\big)\Big)\ ,
\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}{2\log\t} 
\int_0^\infty     
\frac{e^{-\tt z}}{\alpha}\,\mm(\t z)\, z^{-\log_\t\alpha-1}\,dz\ .
\end{equation}

\end{theorem}

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

As an example, we treat the classical case $\t=\frac13$.
Then (apart from small fluctuations), 
\begin{equation}
M_n\sim .6160498 \cdot n^{-.4380178}\cdot 0.75^n .
\end{equation}
This is consistent with the actual values; the reader is encouraged to check it. It is fun!!

\smallskip

The fact that in an asymptotic formula the generating function of the sequence in question,
evaluated at a certain point, appears, is not at all uncommon
in combinatorial analysis. We cite for instance
the classical papers \cite{Polya37}, \cite{Otter48}.

\ackno
This paper was worked out mainly while I was on holiday in Thailand.
I completed it and wrote it up while I was an invited researcher
in the {\sl Centre de Recerca Matem\^atica, Institut d'Estudis Catalans,
Barcelona}. I  am thankful for the hospitality encountered there.
\endackno



\bibliographystyle{plain} 


%\bibliography{pro_bib}

\begin{thebibliography}{10}

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

\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 (to appear)}, 1994.

\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{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 (to appear)}, 1994.

\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{Otter48}
R.~Otter.
\newblock The number of trees.
\newblock {\em Ann. Math.}, 49:583--599, 19348.

\bibitem{Polya37}
G.~P{\'o}lya.
\newblock Kombinatorische {A}nzahlbestimmungen f{\"u}r {G}ruppen, {G}raphen und
  chemische {V}erbindungen.
\newblock {\em Acta Mathematica}, 68:145--254, 1937.

\bibitem{Prodinger81}
H.~Prodinger.
\newblock On the number of {F}ibonacci partitions of a set.
\newblock {\em The Fibonacci Quarterly}, 19:463--466, 1981.

\bibitem{Prodinger83}
H.~Prodinger.
\newblock Ordered {F}ibonacci partitions.
\newblock {\em Canadian Mathematical Bulletin}, 26:312--316, 1983.

\bibitem{Prodinger87}
H.~Prodinger.
\newblock {\"U}ber l{\"a}ngste 1-{T}eilfolgen in 0-1--{F}olgen.
\newblock In E.~Hlawka, editor, {\em Zahlentheoretische Analysis {II}}, volume
  1262 of {\em Lecture Notes in Mathematics}, pages 124--133, 1987.

\bibitem{RaJaSz93}
B.~Rais, P.~Jaquet, 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}













