Some Properties of the Cantor Distribution

Some Properties of the Cantor Distribution

Helmut Prodinger

Technische Universität Wien, Austria

Algorithms Seminar

December 9, 1996

[summary by Julien Clément]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract

The Cantor distribution is defined as a random series

1-J

J

å

i³1
X_iJⁱ,
where J is a parameter and the X_i are random variables that take the values 0 and 1 with probability 1/2. The moments and order statistics are discussed, as well as a ``Fibonacci'' variation. Connections to certain trees and splitting processes are also mentioned.

1 Cantor distribution

1.1 Random series

The Cantor distribution with parameter J (0<J£1/2) was introduced in [5] by the random series

i ³ 1

X_i Jⁱ,

where the X_i are independent with the distribution Pr[X_i=0]=Pr[X_i=1]=1/2, and J=1-J. The name stems from the special case J=1/3, since then this process gives exactly those numbers from the interval [0,1] that have a ternary expansion solely consisting of the digits 0 and 2. We might alternatively consider an infinite (random) word w₁w₂··· over the alphabet {0,1} and a map value, defined by

value(w₁ w₂ ···)=

i ³ 1

w_i Jⁱ.

1.2 Moments of the distribution

We abbreviate a_n=E[Xⁿ]. The aim is to solve the recursion formula (from [5])

a_n=

2(1-Jⁿ)

n-1

k=0

æ
è

ö
ø

^n-k J^k a_k, a₀=1.

Let us introduce the exponential generating function A(z)=å_{n ³ 0} a_n zⁿ/n!. The functional equation involving A(z), once solved by iteration, gives

A(z)=

k ³ 0

1+e

J^k z

In order to derive an asymptotic equivalent of a_n, the Poisson generating function B(z)=e^-z A(z) has to be considered. Using ``Mellin'' techniques to derive an asymptotic expansion of log B(z) when z tends to infinity and a ``de-poissonization'' argument which suggests the approximation a_n ~ B(n), one gets

E[Xⁿ]=a_n= F(log

1/J

n)n

-log

1/J

æ
ç
ç
è

1+ O

æ
ç
ç
è

ö
÷
÷
ø

The function F(x) is periodic of period 1 and has known Fourier coefficients. The mean of F(x) is for instance

2log J

ó
õ

k ³ 1

1+e

J^k z

log

1/J

2 -1

dx.

1.3 Order statistics

Let us consider n random independent variables Y₁,...,Y_n from a Cantor distribution. The average value E[min(Y₁,...,Y_n)] of the smallest value among them is denoted by a_n. The coefficients a_n obey the following recursion

(2ⁿ-2J)a_n=

+ J

n-1

k=1

æ
è

ö
ø

J a_k.

Considering now not exactly the Poisson generating function A(z)=å_{k³ 0}a_n zⁿ/n! but rather

(z)=

e^z -1

A(z)=

n ³ 0

zⁿ

a simpler equation can be obtained. Indeed, one has

(2z)= J

(z)+

e^z+1

The coefficients a^{^}_n can be extracted directly from this equation (equating coefficients of zⁿ/n! on both sides). Going back to the original coefficients a_n, we have the explicit solution

a_n=-

n-1

k=0

æ
è

ö
ø

B_k+1

k+1

2^k+1-1

2^k-J

where B_n denotes a Bernoulli number. An approach based on Rice's method finally gives an asymptotic equivalent of a_n

a_n ~ n

log₂ J

2 J -1

J log 2

(

G(-log₂ J) z(-log₂ J) + d(log₂ n)

)

where z(s), G(s) and d(s) denote respectively the Riemann's zeta function, the gamma function and a periodic function with period 1 and a very small amplitude (provided J is not too close to 0).

2 Cantor-Fibonacci distribution

2.1 Fibonacci restriction

The Cantor distribution might be viewed as a mapping value over a set of random words over a binary alphabet. We might also think about restricted words, according to the Fibonacci restriction, that two adjacent letters `1' are not allowed. The set of (finite) Fibonacci words F is given by

F={0,01}^* {e+1}.

In the original setting (Cantor distribution) probabilities are simply introduced by saying that each letter of {0,1} can appear with probability 1/2. Here the situation is more complicated. We say that each word of Fibonacci of length m is equally likely. There are F_m+2 such words, with F_m+2 denoting the (m+2)th Fibonacci number. As an example, consider the classical Cantor case with J=1/3 and m=3. Then the values

value(000)=0, value(001)=

, value(010)=

, value(100)=

, value(101)=

appear, each with probability 1/5. The generating function F(z) of Fibonacci words, according to their lengths is easily derived from the definition of F above,

F(z)=

1+z

1-z-z²

m³ 0

F_m+2z^m.

Note that

F_n=

(5)^1/2

(

aⁿ-bⁿ

)

with a=

1+(5)^1/2

and b=

1-(5)^1/2

2.2 Moments of the Cantor-Fibonacci distribution

Let us consider the generating functions

G_n(z):=

w Î F

(

value (w)

)

z^|w|,

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

[z^m]G_n(z)

[z^m]F(z)

is the nth moment, when considering words of length m. Then we let m tend to infinity to get a limit called M_n (note that taking limits wasn't necessary for the independent original case). The recursion for value, when restricted to Fibonacci words, is

value(0w)

=J · value(w)

value(10w)

+J²· value(w).

These formulae translate almost directly to generating functions according to the recursive definition F=e + 1 +{0,10} F. Thus it gives an explicit recursion formula for the functions G_n(z)

G_n(z)=

ⁿ z-J²ⁿ z²

é
ê
ê
ë

ⁿ z+ z²

n-1

i=0

æ
è

ö
ø

^n-i J²ⁱG_i(z)

ù
ú
ú
û

Since we only consider the limit for m ® ¥, we can get the asymptotic behaviour noting that both F(z) and G_n(z) have the same dominant singularity at z=1/a and also that it is a simple pole. Consequently, we have (due to a ``pole cancellation'')

M_n=

lim

m ® ¥

[z^m] Gⁿ(z)

[z^m]F(z)

lim

z ® 1/a

G_n(z)

F(z)

Therefore we have the following theorem

Theorem 1 The moments of the Cantor-Fibonacci distribution fulfill the following recursion: M₀=0 and for n ³ 1

M_n=

a²-a Jⁿ-J²ⁿ

i=1

æ
è

ö
ø

^n-i J²ⁱM_i.

2.3 The asymptotic behaviour of the moments

A rough estimate shows that M_n » lⁿ. We might infer that l=J+lJ², so that l=1/1+J. It is not rigourous but we can set

m_n:=M_n · (1+J)ⁿ

anyway and show that this sequence has nicer properties. As before the recurrence on the coefficients m_n and then the exponential generating function m(z)=å_n m_n zⁿ/n! need to be considered. Finally the Poisson transformed function m^{^} (z)=e^-z m(z) obeys the functional equation

(z)=

(J z)+

a²

(J²z).

Because m_n ~ m^{^}(n), the next step considers the behaviour of m^{^}(z) for z ® ¥. Using the Mellin transform (and the Mellin inversion formula), we have the following theorem

Theorem 2 The nth moment M_n of the Cantor-Fibonacci distribution has for n ® ¥ the following asymptotic behaviour

M_n=

æ
è

ö
ø

-n

F(-log

n) n

log

æ
ç
ç
è

1+O

æ
ç
ç
è

ö
÷
÷
ø

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

log J

ó
õ

(J z) z

-log

a -1

dz.

Note that here, e^-Jz/am^{^}(J z) is merely considered as an auxiliary function. This integral can be computed numerically by replacing m^{^}(J z) by the first few values of its Taylor expansion, which can be obtained through the recursion formula on the coefficient m_n. As an example, the classical case J=1/3 gives (apart from small fluctuations),

M_n ~ .6160498 n^-.4380178 0.75ⁿ.

The fact that in an asymptotic formula the generating function itself, evaluated at a certain point, appears is not at all uncommon in combinatorial analysis.

References

[1]: Flajolet (Philippe), Gourdon (Xavier), and Dumas (Philippe). -- Mellin transforms and asymptotics: harmonic sums. Theoretical Computer Science, vol. 144, n°1-2, 1995, pp. 3--58. -- Special volume on mathematical analysis of algorithms.
[2]: Flajolet (Philippe) and Sedgewick (Robert). -- Mellin transforms and asymptotics: finite differences and Rice's integrals. Theoretical Computer Science, vol. 144, n°1-2, 1995, pp. 101--124. -- Special volume on mathematical analysis of algorithms.
[3]: Grabner (P. J.) and Prodinger (H.). -- Asymptotic analysis of the moments of the Cantor distribution. Statistics & Probability Letters, vol. 26, n°3, 1996, pp. 243--248.
[4]: Knopfmacher (Arnold) and Prodinger (Helmut). -- Explicit and asymptotic formulae for the expected values of the order statistics of the Cantor distribution. Statistics & Probability Letters, vol. 27, n°2, 1996, pp. 189--194.
[5]: Lad (F. R.) and Taylor (W. F. C.). -- The moments of the Cantor distribution. Statistics & Probability Letters, vol. 13, n°4, 1992, pp. 307--310.
[6]: Prodinger (H.). -- The Cantor-Fibonacci distribution. Applications of Fibonacci numbers, 1998. -- To appear.

This document was translated from L^AT_EX by H^EV^EA.