Some Properties of the Cantor Distribution (original) (raw)

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 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.1 Random series

The Cantor distribution with parameter J(0<J�1/2) was introduced in [5] by the random series where the X i are independent with the distribution Pr[X _i_=0]=Pr[X _i_=1]=1/2, andJ=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_1_w_2��� over the alphabet {0,1} and a map value, defined by

1.2 Moments of the distribution

We abbreviate a _n_=E[X n_]. The aim is to solve the recursion formula (from [5]) Let us introduce the exponential generating function A(z)=�_n � 0 a n z n/n!. The functional equation involving A(z), once solved by iteration, gives 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 _n_]=a _n_=F(log | n)n | | ���� | 1+ O | ���� | ���� | ���� | . | | ----------------------------- | ------- | | ---- | ------ | ---- | ---- | ---- | - |

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

1.3 Order statistics

Let us consider n random independent variables Y_1,...,Y n from a Cantor distribution. The average value E[min(Y_1,...,Y n)] of the smallest value among them is denoted by a n. The coefficients a n obey the following recursion Considering now not exactly the Poisson generating function_A(z)=�_k_� 0_a n z n/n! but rather a simpler equation can be obtained. Indeed, one has The coefficients a_^_n can be extracted directly from this equation (equating coefficients of z n/n! on both sides). Going back to the original coefficients_a_ n, we have the explicit solution 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 | | | ( | G(-log2 J) z(-log2 J) +d(log2 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+2denoting the (m+2)th Fibonacci number. As an example, consider the classical Cantor case withJ=1/3 and _m_=3. Then the values

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, Note that

2.2 Moments of the Cantor-Fibonacci distribution

Let us consider the generating functions

| G n(z):= | | ( | value (w) | ) | _z_|w|, | | -------------- | | - | ----------- | - | ---------- |

where |w| denotes the length of the Fibonacci word w. The quantity is the n_th 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

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)= | | ���� | n _z_+ _z_2 | | | n_-i J2_i 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'') Therefore we have the following theorem

Theorem 1 The moments of the Cantor-Fibonacci distribution fulfill the following recursion: _M 0 =0 and for _n � 1

2.3 The asymptotic behaviour of the moments

A rough estimate shows that M n � l_n_. We might infer that l=J+lJ2, so thatl=1/1+J. It is not rigourous but we can set

m n:=M n � (1+J)n

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/n! need to be considered. Finally the Poisson transformed function_m_^ (z)=_e_-z m(z) obeys the functional equation 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 _n th moment _M n of the Cantor-Fibonacci distribution has for _n � � the following asymptotic behaviour

| _M n = | �� | 1+ | �� | F(- log | _n)n | | ���� | 1+O | ���� | ���� | ���� | , | | ------------- | ---- | ---- | ---- | ----------- | ------ | | ------ | ----- | ------ | ------ | ------ | --- |

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

Note that here, e_-J_z/a_m_^(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_n.

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 F ibonacci numbers, 1998. -- To appear.

This document was translated from LATEX byH E V E A.