THE CANTOR—FIBONACCI DISTRIBUTION

HELMUT PRODINGER

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.

1. Introduction

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

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

where the X_{i} are independent with the distribution

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

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.

We might of course alternatively think of an infinite (random) word w_{1}w_{2} … over the alphabet {0, 1} and a mapping value, defined by

value(w_{1}w_{2} …) = \frac{ϑ̄}{ϑ} ∑_{i≥1} w_{i}ϑ^{i} .  (3)

Observe the recursion formula

value(0w) = ϑ · value(w)
value(1w) = ϑ̄ + ϑ · value(w) .

(4)

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

Compare some of the papers of the author for that [8, 9, 10].

The set of (finite) Fibonacci words F (no two adjacent letters ‘1’) is given by

F = {0, 10}^{∗}{ε + 1};  (5)

Date: May 9, 1996.

This research was partly done while the author was visiting the CRM (Centre de Recerca Matemàtica, Institut d’Estudis Catalans).

here, ‘∗’ means arbitrary repetitions and ‘ε’ the empty word. There is also the recurrence

F = ε + 1 + {0, 10}F .  (6)

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 ϑ = \frac{1}{3} and m = 3. Then the values

\begin{matrix}2(0 · \frac{1}{3} + 0 · \frac{1}{9} + 0 · \frac{1}{27}) = 0 \\ 2(0 · \frac{1}{3} + 0 · \frac{1}{9} + 1 · \frac{1}{27}) = \frac{2}{27} \\ 2(0 · \frac{1}{3} + 1 · \frac{1}{9} + 0 · \frac{1}{27}) = \frac{2}{9} \\ 2(1 · \frac{1}{3} + 0 · \frac{1}{9} + 0 · \frac{1}{27}) = \frac{2}{3} \\ 2(1 · \frac{1}{3} + 0 · \frac{1}{9} + 1 · \frac{1}{27}) = \frac{20}{27} \end{matrix}  (7)

appear, each with probability \frac{1}{5}.

It is also useful to have F (z), the generating function of Fibonacci words, according to their lengths. From (5) and general principles we get it as

F (z) = \frac{1 + z}{1 − z − z^{2}} = ∑_{m≥0} F_{m+2}z^{m} ;  (8)

note that

F_{n} = \frac{1}{\sqrt{5}}(α^{n} − β^{n}) with α = \frac{1 + \sqrt{5}}{2} and β = \frac{1 − \sqrt{5}}{2} .  (9)

2. The Moments

Lad and Taylor in their original paper [5] have considered the nth moment of the Cantor distribution. They obtained a recursion for them, which was analyzed by Grabner and the author in [2]. Other papers dealing with the Cantor distribution are [3] and [4].

In this paper, we want to analyze the nth moments of the Cantor–Fibonacci distribution. We do this by considering the generating functions

G_{n}(z) := ∑_{w∈F} (value(w))^{n} z^{|w|} ;  (10)

where |w| denotes the length of the Fibonacci word w. The quantity

\frac{[z^{m}]G_{n}(z)}{[z^{m}]F (z)}  (11)

is then the nth moment, when considering words of length m; finally we consider the limit of this for m → ∞ and call it M_{n}.

We rewrite the recursion for value, when restricted to Fibonacci words;

value(0w) = ϑ · value(w)
value(10w) = ϑ̄ + ϑ^{2} · value(w) .

(12)

Note also that value(ε) = 0 and value(1) = ϑ̄. Using the recursion F = ε + 1 + {0, 10}F, we find for n ≥ 1

\begin{aligned}G_{n}(z) & = ϑ̄^{n}z + ϑ^{n}zG_{n}(z) + ∑_{w∈F} (ϑ̄ + ϑ^{2}value(w))^{n}z^{2+|w|} \\ & = ϑ̄^{n}z + ϑ^{n}zG_{n}(z) + z^{2} ∑_{i=0}^{n} \binom{n}{i}ϑ̄^{n−i}ϑ^{2i} G_{i}(z) . \end{aligned}  (13)

This recursion can be made explicit by rewriting it as

G_{n}(z) = \frac{1}{1 − ϑ^{n}z − ϑ^{2n}z^{2}} [ϑ̄^{n}z + z^{2} ∑_{i=0}^{n−1} \binom{n}{i}ϑ̄^{n−i}ϑ^{2i} G_{i}(z)]  (14)

Note the special instance G_{0}(z) = F (z) and

G_{1}(z) = \frac{1}{1 − ϑz − ϑ^{2}z^{2}} [ϑ̄z + z^{2}ϑ̄F (z)] = \frac{ϑ̄z}{(1 − ϑz − ϑ^{2}z^{2})(1 − z − z^{2})} .  (15)

From this we could get (by partial fraction decomposition) the coefficient of z^{m} explicitly. However, since we only consider the limit for m → ∞, life is easier. Both, G_{1}(z) and

F (z) have the dominant singularity at z = 1/α, and it is a simple pole. Consequently,

[z^{m}]G_{1}(z) ∼ Aα^{m},  with A = lim_{z→1/α}(1 − zα)G_{1}(z)  (16)

and

[z^{m}]F (z) ∼ Bα^{m},  with B = lim_{z→1/α}(1 − zα)F (z)  (17)

Therefore

lim_{m→∞} \frac{[z^{m}]G_{1}(z)}{[z^{m}]F (z)} = \frac{A}{B} ,  (18)

which we can compute as

lim_{z→1/α} \frac{\frac{ϑ̄z}{1−ϑz−ϑ^{2}z^{2}}}{1 + z} = \frac{ϑ̄}{α^{2} − αϑ − ϑ^{2}} .  (19)

The fact that z = 1/α 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/α in the rest, to obtain the nth moment M_{n} as

M_{n} = \frac{1}{1 − ϑ^{n}/α − ϑ^{2n}/α^{2}} [\frac{1}{α^{2}} ∑_{k=0}^{n−1} \binom{n}{k}ϑ̄^{n−k}ϑ^{2k}M_{k}] .  (20)

Theorem 1. The moments of the Cantor–Fibonacci distribution fulfill the following recursion: M_{0} = 1 and for n ≥ 1

M_{n} = \frac{1}{α^{2} − αϑ^{n} − ϑ^{2n}} ∑_{k=0}^{n−1} \binom{n}{k}ϑ̄^{n−k}ϑ^{2k}M_{k} .  (21)

For instance

M_{1} = \frac{ϑ̄}{α^{2} − αϑ − ϑ^{2}} ,
M_{2} = \frac{ϑ̄^{2}(α^{2} − αϑ + ϑ^{2})}{(α^{2} − αϑ^{2} − ϑ^{4})(α^{2} − αϑ − ϑ^{2})} ,
Variance = M_{2} − M_{1}^{2} = \frac{ϑ̄^{4}α^{3}}{(α^{2} − αϑ^{2} − ϑ^{4})(α^{2} − αϑ − ϑ^{2})^{2}} .

(22)

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 (= non–Fibonacci) case was done in [2].

A rough estimation shows us that the moments decrease exponentially. Indeed, if we set M_{n} ≈ λ^{n}, we might infer that λ = ϑ̄ + λϑ^{2}, or

λ = \frac{1}{1 + ϑ} .  (23)

This is not rigorous, but we can set

m_{n} := M_{n} · (1 + ϑ)^{n}  (24)

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

m_{n} = \frac{1}{α^{2} − αϑ^{n} − ϑ^{2n}} ∑_{k=0}^{n−1} \binom{n}{k}(1 − ϑ^{2})^{n−k}ϑ^{2k}m_{k} .  (25)

To study this sequence further, we rewrite it as

m_{n}(α^{2} − αϑ^{n} − ϑ^{2n}) = ∑_{k=0}^{n} \binom{n}{k}(1 − ϑ^{2})^{n−k}ϑ^{2k}m_{k} − ϑ^{2n}m_{n}  (26)

or

m_{n}(α^{2} − αϑ^{n}) = ∑_{k=0}^{n} \binom{n}{k}(1 − ϑ^{2})^{n−k}ϑ^{2k}m_{k}  (27)

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!}  (28)

and get

α^{2}m(z) − αm(ϑz) = e^{(1−ϑ^{2})z}m(ϑ^{2}z).  (29)

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

m̂(z) = \frac{e^{−ϑ̄z}}{α} m̂(ϑz) + \frac{1}{α^{2}} m̂(ϑ^{2}z) .  (30)

This functional equation can – at least in principle – be solved by iteration. Even though it is hard to write down the explicit solution, we can consider it to be a known function.

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 de–Poissonization. A preliminary reference for that is [11]. 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 [2], where the technique is explained in more detail.

It might be suggestive to use a new name R(z) for \frac{e^{−ϑ̄z}}{α} m̂(ϑz) and consider it to be an auxiliary (and known) function;

m̂(z) = \frac{1}{α^{2}} m̂(ϑ^{2}z) + R(z) .  (31)

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

m̂^{∗}(s) = \frac{1}{α^{2}} ϑ^{−2s}m̂^{∗}(s) + R^{∗}(s) = \frac{R^{∗}(s)}{1 − α^{−2}ϑ^{−2s}} .  (32)

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 − α^{−2}ϑ^{−2s}} z^{−s} ds ,  (33)

where 0 < c < − log_{ϑ} α. 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_{ϑ} α + \frac{2kπi}{log ϑ}, k ∈ ℤ. The negative residue there is

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

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

−\frac{1}{2 log ϑ}z^{log_{ϑ} α} ∫_{0}^{∞} \frac{e^{−ϑ̄z}}{α} m̂(ϑz) z^{− log_{ϑ} α−1} dz .  (35)

Traditionally, one collects all the terms into a periodic function. Theorem 2. The nth moment M_{n} of the Cantor–Fibonacci distribution has for n → ∞ the following asymptotic behaviour

M_{n} = (1 + ϑ)^{−n}Φ(− log_{ϑ} n) n^{log_{ϑ} α}(1 + O(\frac{1}{n})) ,  (36)

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

−\frac{1}{2 log ϑ} ∫_{0}^{∞} \frac{e^{−ϑ̄z}}{α} m̂(ϑz) z^{− log_{ϑ} α−1} dz .  (37)

This integral can be computed numerically by replacing m̂(ϑ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 ϑ = \frac{1}{3}. Then (apart from small fluctuations),

M_{n} ∼ .6160498 · n^{−.4380178} · 0.75^{n}.  (38)

This is consistent with the actual values; the reader is encouraged to check it. It is fun!!

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 [7], [6].

Acknowledgement. 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 Centre de Recerca Matemâtica, Institut d’Estudis Catalans, Barcelona. I am thankful for the hospitality encountered there.

References

[1] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoretical Computer Science, 144:3–58, 1995.

[2] P. Grabner and H. Prodinger. Asymptotic analysis of the moments of the Cantor distribution. Statistics and Probability Letters (to appear), 1994.

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

[4] A. Knopfmacher and H. Prodinger. Exact and asymptotic formulæ for average values of order statistics of the Cantor distribution. Statistics and Probability Letters (to appear), 1994.

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

[6] R. Otter. The number of trees. Ann. Math., 49:583–599, 19348.

[7] G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68:145–254, 1937.

[8] H. Prodinger. On the number of Fibonacci partitions of a set. The Fibonacci Quarterly, 19:463–466, 1981.

[9] H. Prodinger. Ordered Fibonacci partitions. Canadian Mathematical Bulletin, 26:312–316, 1983.

[10] H. Prodinger. Über längste 1-Teilfolgen in 0-1–Folgen. In E. Hlawka, editor, Zahlentheoretische Analysis II, volume 1262 of Lecture Notes in Mathematics, pages 124–133, 1987.

[11] B. Rais, P. Jaquet, and W. Szpankowski. Limiting distribution for the depth in Patricia tries. SIAM Journal on Discrete Mathematics, 6:197–213, 1993.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

 E-mail address: Helmut.Prodinger@tuwien.ac.at