Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

336 Combinatorics of Compositions and Words

Using the fact that (1 − a)

≈ e

−a·n

we obtain from (8.13) that

E(X

max

(n)) ≈



h≥1

(1 − exp(−Mn(ρ

∗

)

)withM =

(1 − ρ

∗



(ρ

∗

)

The expression that approximates E(X

max

(n)) is quite well studied (see for

example [67]). Using the results given in Flajolet et al. [67], we obtain that

E(X

max

(n)) ≈ log

1/ρ

∗

n +log

1/ρ

∗

M −

log ρ

∗

+ d(log

1/ρ

∗

nM), (8.16)

where γ = lim

n→∞



i=1

− log n =0.57721566490 ··· and the function

d(x) has period one, mean zero, and small amplitude. For ρ

∗

=1/2and

g(z)=z/(1 − z) we obtain that log

1/ρ

∗

M −

log ρ

∗

=0.3327461773 ···,

giving the desired result. 2

8.4.3 Asymptotics for the number of distinct parts

We now look at a diﬀerent statistic, namely the number of distinct parts in

a random composition.

Deﬁnition 8.40 For a given random composition σ = σ

···σ

of n with

m parts, we denote the number of distinct parts by D

(σ). That is,

(σ)=1+



i=2

{σ

=σ

,j=1,2,...,i−1}

, (8.17)

where I

, the indicator function of the set A equals 1 if A occurs and 0

otherwise.

We present a rather precise result on the asymptotics of E(D

)thatwas

originally obtained by Hwang and Yeh [102] using generating function tech-

niques, but was also derived by Hitczenko and Stengle [97] using a probabilistic

approach. We will summarize the key steps in the probabilistic approach as

these techniques can be used to study the asymptotics of other statistics. The

analysis is based on a reformulation of the notion of a random composition

by exploiting a bijection (mentioned in [10]) between compositions of n and

binary words of length n that end in 1. Speciﬁcally, a composition of n with

m parts is associated with the binary word w

···w

of length n where

=1foralli ∈{σ

,σ

+ σ

,...,σ

+ σ

+ ···+ σ

} and w

=0otherwise.

Example 8.41 The composition 213114 of 12 with six parts corresponds to

the word 011001110001, while the composition 321 of 6 with three parts corre-

sponds to the word 001011. The correspondence is easily visualized as follows:

,-./

(

,-./

(

001

,-./

(

,-./

(

,-./

(

0001

-./

and 001

,-./

(

,-./

(

,-./

Asymptotics for Compositions 337

Note that the number of parts in the composition corresponds to the number

of 1sinthebinaryword.

With this bijection it is easy to see that choosing a composition at random

is equivalent to having a 0 or 1 occur with probability 1/2 at each of the ﬁrst

n −1 positions, with the occurrences at diﬀerent positions being independent

(see Deﬁnition D.5) of each other. In other words, the number of 1s in the ﬁrst

n−1 positions is a binomial random variable (see Deﬁnition D.11) B(n−1, 1/2)

with n −1 trials and success probability 1/2. Thus, the total number of parts

tot

(n) of a random composition of n equals the number of 1s (including the

1 at the rightmost position) in the binary word and therefore,

tot

(n) ∼B(n −1, 1/2) + 1.

The numbers σ

,...,σ

are “waiting times” for the ﬁrst, second,..., and

m-th appearance of a 1. It is well-known and easy to check that in an inﬁnite

sequence of independent Bernoulli trials with success probability p, the waiting

times for successes are independent and identically distributed (i.i.d.) random

variables whose common distribution is that of a geometric random variable

with parameter p (see Deﬁnition D.12). Since we are considering only n − 1

trials, this is no longer true. However, we have the following characterization.

Proposition 8.42 [96, Proposition 1] Let Γ

, Γ

,...,be i.i.d. geometric ran-

dom variables with parameter 1/2(that is, P(Γ

= j)=2

−j

, for all j ≥ 1)

and deﬁne

η =inf{k ≥ 1 | Γ

+Γ

+ ···+Γ

≥ n}.

Then, the distribution of a randomly chosen composition in C

is given by

⎛

⎝

, Γ

,...,Γ

η−1

,n−

η−1



j=1

⎞

⎠

Proposition 8.42 provides an alternative way to create a random compo-

sition, namely sampling geometric random variables, with an adjustment for

the last part (see Appendix F and Exercise 8.11). Using this fact, Hitczenko

and Stengle [97] showed the following result using probabilistic estimates.

Theorem 8.43 [97, page 520] As n →∞,

E(D

) ≈ log

n − 0.6672538227 + d(log

n),

where d is a function with mean zero and period one satisfying |d|≤0.0000016.

Thus, the expected number of distinct parts in a random composition of n

asymptotically behaves like log

n plus a constant plus a small but periodic

oscillation. This behavior is similar to the asymptotic behavior for the average

338 Combinatorics of Compositions and Words

size of the maximal part given in Theorem 8.39. Clearly, the maximal part is

always greater than or equal to the number of distinct parts.

The proof of Theorem 8.43 is split into two parts. It consists of ﬁrst esti-

mating the expected value as an inﬁnite sum of a particular type and then

showing that this type of inﬁnite sum has a certain rate of growth.

Proposition 8.44 [97, Proposition 2.1] As n →∞,

E(D



m≥1



1 −



1 −



(1+o(1))



+ o(1).

Proof We sketch the proof by stating the main steps. Let

(σ)=Γ

(σ)

for all i<η(σ), and

η(σ)

(σ)=n −



η(σ)−1

i=1

(σ) denote the parts of a

randomly chosen composition σ. Clearly,

≤ Γ

. Rewriting (8.17) in terms

of the binary words model leads to

E(D

)=1+E





i=2

{

=

,j=1,2,...,i−1}



or equivalently

E(D

)=1+E



η−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}



+ P(

=Γ

,...,Γ

η−1

). (8.18)

The remainder of the proof consists of estimating each term in (8.18). To

show that the last probability term is negligible we break up the values for η

into those where |η −E(η)|≤t

and those where |η −E(η)| >t

,wheret

(n − 1) log n. To estimate the latter probability, we use that η = X

tot

(n)is

a1+B(n − 1, 1/2) random variable and therefore satisﬁes the bound (using

a large deviation estimate, see Theorem D.14)

P(|η − E(η)|≥t) ≤ 2exp



−2t

n − 1



. (8.19)

Speciﬁcally,



|η − E(η)|≥

(n − 1) log n



≤ 2exp(− 2logn)=

. (8.20)

In order to deal with the values of η where |η − E(η)|≤t

, we deﬁne

= E(η) − t

=(n +1)/2 −

(n − 1) log n (8.21)

and

= E(η)+t

=(n +1)/2+

(n − 1) log n. (8.22)

Asymptotics for Compositions 339

With this deﬁnition of n

and n

we have that

|η − E(η)|≤t

⇐⇒ n

≤ η ≤ n

which we will use repeatedly. Using basic rules of probability and changing

the order of summation results in

=Γ

,...,Γ

η−1

) ≤



j=1

= j, Γ

,...,Γ

η−1

= j)

≤



j=1

P(Γ

≥ j, Γ

,...,Γ

η−1

= j, |η − E(η)|≤t

)

+ nP(|η − E(η)| >t

)

≤



j=1



k=n

P(Γ

≥ j, Γ

,...,Γ

k−1

= j, η = k)+

≤



k=n



j≥1

j−1



1 −



k−1

≤



k=n



∞



1 −

x+1



k−1

dx +

≤



k=n

≤

√

n log n

→ 0,

where the last inequality follows from Exercise 8.10. Now we estimate the

term involving the expectation in (8.18) as

η−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

≤ E



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|≤t

}

+(n − 2)P(|η − E(η)| >t

)

≤ E

η−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|≤t

}

2(n − 2)

, (8.23)

where we have used that I

A∩B

= I

·I

, E(I

)=P(A), and η ≤ n.Sincethe

second term in (8.23) is of order 1/n, we only need to estimate the ﬁrst term.

Translating the condition |η − E(η)|≤t

into values for η, we obtain that

η−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|≤t

}

≤ E



i=2

{Γ

=Γ

,j=1,2,...,i−1}



i=2

P(Γ

=Γ

,j=1, 2,...,i− 1),

340 Combinatorics of Compositions and Words

and similarly,

η−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|≤t

}

≥ E

−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|≤t

}

= E

−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

− E

−1



i=2

{Γ

=Γ

,j=1,2,...,i−1}

{|η−E(η)|>t

}

≥

−1



i=2

P(Γ

=Γ

,j=1, 2,...,i− 1) − (n

− 2)P(|η − E(η)| >t

)

≥

−1



i=2

P(Γ

=Γ

,j=1, 2,...,i− 1) −

n − 3 − 2

(n − 1) log n

Both bounds have the same type of sum which we now estimate. For ﬁxed i,

P(Γ

=Γ

,j=1, 2,...,i−1) =

∞



m=1

P(Γ

= m, Γ

= m, j =1, 2,...,i− 1)

∞



m=1



1 −



i−1

because the Γ

are geometric random variables. Summing over i and perform-

ing some algebraic manipulations leads to



i=2

P(Γ

=Γ

,j=1, 2,...,i−1) =



m≥1

)

1 −



1 −



− 1.

After ignoring terms of order o(1) we obtain that



m≥1



1 −



1 −



−1



≤ ED

≤



m≥1

1 −



1 −



Both bounding sums have powers of the form

(1 + o(1)). Thus the second,

purely analytical step, consists of analyzing the asymptotic behavior of the

inﬁnite sum



m≥1



1 −



1 −



(1+o(1))



Deﬁning

f(x)=



m≥1



1 −



1 −





Asymptotics for Compositions 341

we can apply Proposition A.1 with x =log

(

)andk =log

(

o(1)) to obtain

the result of Theorem 8.43. 2

In fact, Hitczenko and Louchard [93] extended Theorem 8.43 by studying

the poissonized generating function for the probability distribution function

of D

,thatis,

G(z,q)=



n≥0



k≥0

P(D

= k)q

−z

Conditioning on the number of Γ

that are equal to 1 they obtained that

(q)=P(D

= k)q



1ifn =0



n−1

j=0





(q)

if n ≥ 1

Using simple generating function techniques they showed that G(z,q)satisﬁes

the following functional equation:

G(z,q)=G(z/2,q)(e

−z/2

(1 − q)+q).

Then, by nontrivial analysis involving Mellin transforms (see Deﬁnition E.12),

the authors found the variance and higher moments of the random variable

Var(D

) ≈ 1

) ≈−3+2log3=0.1699250014,

) ≈ 10 − 12 log 3 + 6 log 4 = 2.980449991, and

) ≈−45 log 2 + 70 log 3 − 60 log 4 + 24 log 5 = 1.673649353

as n →∞, where the variance does not have a periodic contribution, but the

other moments do. Hitczenko and Louchard also conducted simulations and

investigated additional properties for compositions and Carlitz compositions.

Another generalization of the results given in Proposition 8.44 was investi-

gated by Hitczenko and Savage [95] who studied the probability that a ran-

domly chosen part in a random composition of n has multiplicity k.We

present their result and an outline of the proof.

Deﬁnition 8.45 For a composition σ ∈C

, we deﬁne U

= U

(σ) to be the

set of parts in σ that have multiplicity k,andletU

= U

(σ)=|U

(σ)| be

the number of such parts, given by U

(σ)=



i=1

,where

= {σ

= σ

,j <i and |{>i: σ



= σ

}| = k − 1}

is the event that the i-th part is the ﬁrst occurrence of a new part size with

multiplicity k. Furthermore, let E

denote the event that a randomly chosen

part size of a randomly chosen composition σ ∈C

has multiplicity k.

342 Combinatorics of Compositions and Words

Example 8.46 For σ = 11321325 ∈C

the distinct part sizes are {1, 2, 3, 5}

with respective multiplicities three, two, two, and one and U

(σ)={2, 3}.

The probability that a randomly chosen part size has multiplicity two would be

given by 2/4=U

. If we wanted to compute P(E

) then we would have

to take the average over all such probabilities for σ ∈C

. Thus, in general

P(E

)=E





With this notation, Hitczenko and Savage [95] showed the following result.

Theorem 8.47 [96, Theorem 1] Let k be a ﬁxed integer and let U

and E

be deﬁned as above. Then

(log n)P(E

)=(logn)E





= O(1),

that is, there exist positive constants c

(k) and c

(k) such that for all n ≥ 2,

(k) ≤ (log n)P(E

) ≤ c

(k).

More precisely, as n →∞,

(log n)P(E

+ H

(c log n)+o(1),

where H

is a function of period one with mean zero whose Fourier coeﬃcients

are given by





k −

2πı

log 2



where  =0and ı =

√

−1.

Proof The proof consists of several parts. The ﬁrst part concerns the deriva-

tion of two sequences {

} and {k

} such that both sequences increase to

inﬁnity with lim

n→∞

(

) = 1, and both P(D

≤ 

)andP(D

≥ k

)

tend to zero at a rate faster than log

n. This allows for substitution of either

sequence in the denominator of the expectation that is to be estimated.

Let S

(σ) denote the number of consecutive part sizes (starting with 1)

in σ. For example, if σ = 12135612, then S

(σ) = 3, as the value 4 does

not occur in σ. Clearly, S

(σ) ≤ D

(σ), and using (8.20) we obtain for any

sequence {

} that

P(D

≤ 

) ≤ P(S

≤ 

) ≤ P(∃j ≤ 

, ∀i<η:Γ

= j)

≤

+ P({∃j ≤ 

, ∀i<η:Γ

= j)}∩{|η −E(η)| <t

})

≤

+2exp

−



Asymptotics for Compositions 343

where t

and n

are deﬁned in (8.21). Choosing 

=log

/ log

)gives

that P(D

)=O(1/n). We obtain an upper bound by conditioning on whether

≤ 

or D

>

and using that 0 ≤ U

≤ 1:





= E



≤

}



+ E



>

}



≤ P(D

≤ 

E(U

)



On the other hand,





≥ E



≤k

}



≥



≤k

}



≥

[E(U

) − E(U

}

)].

Choosing k

=log

(n(log

) ensures that E(U

}

) → 0 and we have

that





= E



{

≤D

≤k

}



+ E



{

≤D

≤k

}



= E



log

n ± o(log



+ E



<

}



+ E



}



≤ E



log

n ± o(log



+ P(D

<

)+P(D

Since the number of distinct parts is less than or equal to the largest part,

we can bound the last two terms as follows:

P(D

<

)+P(D

) ≤ O





+ P(max Γ

)

≤ O





+ nP(Γ

) ≤ O





≤ O



(log



and therefore,

(log n)P(E

)=E



log

e ± o(1)



+ o(1)

provided that E(U

) is bounded. The last part of the proof consists of esti-

mating the behavior of E(U

)asn →∞.Notethat

E(U

)=E

⎛

⎝



j≤n/k

{j∈U

}

⎞

⎠



j≤n/k

P(j ∈U

344 Combinatorics of Compositions and Words

With

deﬁned as in the proof of Proposition 8.44,

P(j ∈U

)=P



η−1



i=1

{Γ

=j}

= k



− P



{

= j}∩



η−1



i=1

{Γ

=j}

= k



+ P



{

= j}∩



η−1



i=1

{Γ

=j}

= k − 1



. (8.24)

Deﬁning q

=(n +1)/2 ±

2(n − 1) log n,itcanbeshownthat



−



(1 − 2

−j

)

−k

− O





≤ P(

η−1



i=1

{Γ

=j}

= k)

≤





(1 − 2

−j

)

−

−1−k

+ O





Note that for q ≈ n/2, a comparison to an appropriate integral yields that





∞



j=1

−jk

(1 − 2

−j

)

q−k

= O(1).

Using that q

and q

−

are asymptotically the same, and that



j>n

−jk

(1 − 2

−j

)

−k

≤



j>n

−j

we obtain that

E(U

) ≈





∞



j=1

−jk

(1 − 2

−j

)

q−k

as n →∞.

The remainder of the proof obtains that the right-hand side does not have a

limit, but oscillates (see [95]). 2

For further extensions of this work, see [133]. We now turn to results about

Carlitz compositions.

8.5 Asymptotics for Carlitz compositions of n

We now analyze the asymptotics for the total number of Carlitz compo-

sitions and for certain statistics on these compositions. Recall that CC (n)

(respectively CC (m; n)) denotes the number of Carlitz compositions of n with

Asymptotics for Compositions 345

parts in N (respectively with m parts in N). Theorem 3.7 gives that the

generating function CC (z,w)=



n,m≥0

CC (m; n)x

is given by

CC (z,w)=

1 −



j≥1

1+z

1 −



j≥1



i≥0

(−1)

j+ij

i+1

1 −



i≥1



j≥1

(−1)

i−1

1 −



i≥1

(−1)

i−1

1−z

1 − g(z,w)

. (8.25)

Note that CC (z)=CC (z,1) and that we will denote g(z,1) by g(z).

Again, we consider the generating function as a function of one or more

complex variables. Carlitz [38] noted that the radius of convergence of CC (z)

is at least

. Knopfmacher and Prodinger [119] found that the generating

function CC (z) has a dominant pole ρ

∗

, which is the unique real solution in

the interval [0, 1] of the equation

g(z)=



j≥1

1+z

=1.

Numerically, ρ

∗

=0.571349. The other poles are further away from the origin

which can be proved using Henrichi’s Principle of the Argument (see Theorem

8.27). Figure 8.2 shows the the curve 1 − g(z)for|z| =0.6, where 1 −g(z)is

converted into a series up to the z

term. The winding number of this curve

is one, therefore 1 − g(z) has only the root ρ

∗

inside the disc |z| < 0.6. Thus

CC (z) ≈

1 − z/ρ

∗

with

A =

∗



(ρ

∗

)

=0.456363474.

Therefore,

CC (n) ≈ A · (ρ

∗

)

−n

=0.456363474 · (1.750243)

. (8.26)

Louchard and Prodinger [134] added to the picture by giving the asymptotic

distribution of the number of parts in a random Carlitz composition, similar

to Theorem 8.35 for unrestricted compositions.

Theorem 8.48 [134, Theorem 2.1] The number M of parts in a random

Carlitz composition of large given n is asymptotically Gaussian with mean nμ

and standard deviation

√

nσ, that is,

M − nμ

√

nσ

≈N(0, 1)