The Largest Missing Value in a Composition of an Integer and Some Allouche-Shallit-Type

Identities

Guy Louchard Université Libre de Bruxelles Département d’Informatique, CP 212 Boulevard du Triomphe B-1050 Bruxelles Belgium

                  louchard@ulb.ac.be

Helmut Prodinger University of Stellenbosch Mathematics Department 7602 Stellenbosch South Africa

                  hproding@sun.ac.za

Dedicated to Jean-Paul Allouche on the occasion of his 60th birthday.

Abstract

Archibald and Knopfmacher recently considered the largest missing value in a composition of an integer and established the mean and variance. Our alternative, probabilistic approach produces (in principle) all moments in an almost automatic way. In order to show that our forms match the ones given by Archibald and Knopfmacher, we have to derive some identities which are interesting on their own. We construct a one-parameter family of identities, and the first one is (equivalent to) the celebrated identity due to Allouche and Shallit. We finally provide a simple direct analysis of the LMV(−1) case: if the largest missing value is exactly one smaller than the largest value, we say that the sequence has the LMV(−1) property.

1 Introduction

Our attention was recently attracted by a paper by M. Archibald and A. Knopfmacher [1] about some asymptotic properties of a sequence of n geometric independent identically distributed random variables, with distribution pq^{j−1}, q := 1−p. In the particular case p = 1/2, (which is related to compositions of integers, see below), and using generating functions techniques, the authors study the asymptotic mean and variance of largest missing value (if it exists). If the largest missing value is exactly one smaller than the largest value, they say that the sequence has the LMV(−1) property. They compute the LMV(−1) probability, and the corresponding mean value.

Here, within our alternative and more powerful approach, we think about an urn model, with urns labelled 1, 2, …, the probability of each ball falling into urn j being given by pq^{j−1}. In this probabilistic urn model, we throw n balls, and have the following properties, which we collect below although the full relevance of them will only appear later in the text.

• We have asymptotic independence of urns, for all events related to urn j, j = O(log n). This is proved, by Poissonization-DePoissonization, in [11], [3] and [8] (in this paper for p = 1/2, but the proof is easily adapted). The error term is O(n^{−C}) where C is a positive constant.

• We obtain asymptotic distributions of the random variables (RV) of interest. The number of balls in urn j, j = O(log n) is now Poisson-distributed with parameter (np/q)q^{j}. The asymptotic distributions are related to Gumbel distribution functions or convergent series of such. The error term is O(n^{−1}).

• We have uniform integrability for the moments of our RV. To show that the limiting moments are equivalent to the moments of the limiting distributions, we need a suitable rate of convergence. This is related to a uniform integrability condition (see Loève [9, Section 11.4]). For the kind of limiting distributions we consider here, the rate of convergence is analyzed in detail in [10, 3]. The error term is O(n^{−C}).

• Asymptotic expressions for the moments are obtained by Mellin transforms. The error term is O(n^{−C}).

• Γ(s) decreases exponentially in the direction i∞ ([5]):

|Γ(σ + it)| ∼ \sqrt{2π}|t|^{σ−1/2}e^{−π|t|/2}.

Also, we have a “slow increase property” for all other functions we encounter. So inverting the Mellin transforms is easily justified.

We proceed as follows: from the asymptotic properties of the urns, we obtain the asymptotic distributions of our RV of interest. Next we compute the Laplace transform ϕ(α) from which we can derive the dominant part of probabilities and moments as well as the (tiny) periodic part in the form of a Fourier series.

If we compare the approach in this paper with other ones that appeared previously (related to similar problems), then we notice the following. Traditionally, one would stay with exact enumerations as long as possible, and only at a late stage move to asymptotics. Doing this, one would, in terms of asymptotics, carry many unimportant contributions around, which makes the computations quite heavy, especially when it comes to higher moments. Here, however, approximations are carried out as early as possible, and this allows for streamlined (and often automatic) computations of the higher moments.

The paper is organized as follows: in Section 2, we consider compositions of an integer. Section 3 is devoted to a first computation of the dominant part of the moments. In Section 4, we analyze the periodicities and we briefly consider the conditioning on the event that there exists a largest missing value. Section 5 contains the main result of this paper: we present some general Allouche-Shallit-type formulas^{1} and the direct moments computations. Section 6 is devoted to the LMV(−1) case and Section 7 concludes the paper.

2 Compositions of an integer

Let us consider the composition of an integer υ with n parts, i.e., υ = ∑_{i=1}^{n} x_{i}, where x_{i} are natural numbers. Considering all compositions as equiprobable, we know ([8]) that the number of parts n is asymptotically Gaussian, υ → ∞:

n ∼ N (\frac{υ}{2} , \frac{υ}{4} ) ,  (1)

and that the part sizes are asymptotically identically distributed as GEOM(1/2) and independent. All distributions we analyze in this paper depend on log_{2} n. Hence, with (1), the same random variables related to υ are asymptotically equivalent by replacing log_{2} n by log_{2} υ − 1 ([8]).

We will consider the case p = 1/2 and use the following notations:

n := number of balls, n large,
P(λ, u) := e^{−λ}λ^{u}/u!, (Poisson distribution),
log := log_{2},
η := j − log n,
L := ln 2,
α̃ := α/L,
χ_{l} := \frac{2lπi}{L}.

Let B be the event that there exists a largest missing value, i.e., a maximal empty urn before the last non-empty urn. Following previous results of the authors [10], let J be the position of this maximal empty urn before the last non-empty urn. We have (here and in the sequel ∼ always denotes ∼_{n→∞})

1We were kindly informed by Allouche that the first forms of the identities in question are due to Woods and Robbins [13, 12]. However, Allouche and Shallit greatly extended them and made them into what they are today, thanks to the great book [4]. Thus, also, since this is the birthday volume for Jean-Paul Allouche, we took the liberty to use the term Allouche-Shallit-type identities.

ℙ[J = j; B] ∼ φ(η),
φ(η) := exp(−e^{−Lη}) ∑_{r≥1} ∏_{i=1}^{r} [1 − exp(−e^{−L(η+i)})] exp(−e^{−L(η+r)}).

Here is the explanation: we recall that we have i.i.d. geometrically distributed RVs, and that the urns are asymptotically independent, for all events related to urn j containing O(1) balls. Also the number of balls in each such urn is now asymptotically Poisson-distributed with parameter npq^{j−1} in urn j. So the asymptotic number ℓ of balls in urn j is given by

exp (−npq^{j−1}) \frac{(npq^{j−1})^{ℓ}}{ℓ!} ,

and with p = 1/2, η = j − log n, this is equivalent to P (e^{−Lη}, ℓ). Here, urn j is empty, we have r ≥ 1 non-empty urns after urn j, and all urns after urn j + r are empty. This leads to

ℙ[J = j; B] ∼ P(e^{−Lη}, 0) ∑_{r≥1} ∏_{i=1}^{r} [1 − P(e^{−L(η+i)}, 0)] P(e^{−L(η+r)}, 0).

Following [10] again, we now compute the Laplace transform (with the change of variables y = e^{−Lη}):

ϕ(α) = ∫_{−∞}^{∞} e^{−αη}φ(η)dη
= ∫_{0}^{∞} y^{−α̃}e^{−y} ∑_{r≥1} ∏_{i=1}^{r} [1 − e^{−ye^{−Li}}] e^{−ye^{−Lr}} \frac{dy}{Ly}  (2)

= ∫_{0}^{∞} y^{−α̃}e^{−y} ∑_{r≥1} ∏_{i=1}^{r} [1 − e^{−y2^{−i}}] e^{−y2^{−r}} \frac{dy}{Ly} .

Again by [10], we have, with

F_{0}(s) := ϕ(α)|_{α=−Ls} ,  (3)
ℙ(B) ∼ ϕ(0) + ∑_{l≠0} F_{0}(χ_{l})e^{−2lπi log n}.  (4)

But, from [11] and [7], we know that ℙ(B) = 1/2. So we should first independently confirm that

ϕ(0) = ∫_{0}^{∞} e^{−y} ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}} \frac{dy}{Ly} = \frac{1}{2}.  (5)

To do that, set

f_{0}(y) := ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}.

Then

f_{0}(2y) = ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i−1}})e^{−y/2^{r−1}}

= ∑_{r≥0} ∏_{i=0}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}

= (1 − e^{−y})e^{−y} + ∑_{r≥1} ∏_{i=0}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}

= (1 − e^{−y})e^{−y} + (1 − e^{−y}) ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}

= (1 − e^{−y})e^{−y} + (1 − e^{−y})f_{0}(y).

Now

G_{0}(t) := ∫_{0}^{∞} e^{−ty}f_{0}(y)\frac{dy}{y} = ∫_{0}^{∞} e^{−2ty}f_{0}(2y)\frac{dy}{y}

= ∫_{0}^{∞} e^{−2ty}[(1 − e^{−y})e^{−y} + (1 − e^{−y})f_{0}(y)]\frac{dy}{y}

= ln(2t + 2) − ln(2t + 1) + ∫_{0}^{∞} e^{−2ty}(1 − e^{−y})f_{0}(y)\frac{dy}{y} .

So

G_{0}(t) = ln(2t + 2) − ln(2t + 1) + G_{0}(2t) − G_{0}(2t + 1).

If one iterates this formally, one gets

G_{0}(1) = ∑_{n≥3}(−1)^{ν(n−1)} ln n.

Here ν(k) is the number of ones in the binary expansion of the integer k. We will only need the properties ν(2k) = ν(k) and ν(2k + 1) = 1 + ν(k).

This is not a convergent series, but it makes good sense as follows. We have

G_{0}(1) = ∑_{n≥2}(−1)^{ν(n)} ln(n + 1)

= ∑_{j≥1}(−1)^{ν(j)}[ln(2j + 1) − ln(2j + 2)]

= ∑_{j≥0}(−1)^{ν(j)} ln [\frac{2j + 1}{2j + 2}] + ln 2

= −\frac{1}{2} ln 2 + ln 2 = \frac{ln 2}{2} = \frac{L}{2}  (6)

by the Allouche-Shallit (or Woods-Robbins) identity ([4, 2, 11]). This proves (5).

Now we must confirm that F_{0}(χ_{l}) = 0 in order to prove that the second part of (4) is null. Set

f_{α}(y) = ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}y^{−α}.

Then

f_{α}(2y) = ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i−1}})e^{−y/2^{r−1}}(2y)^{−α}

= ∑_{r≥0} ∏_{i=0}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}(2y)^{−α}

= (1 − e^{−y})e^{−y}(2y)^{−α} + ∑_{r≥1} ∏_{i=0}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}(2y)^{−α}

= (1 − e^{−y})e^{−y}(2y)^{−α} + (1 − e^{−y}) ∑_{r≥1} ∏_{i=1}^{r} (1 − e^{−y/2^{i}})e^{−y/2^{r}}(2y)^{−α}

= (1 − e^{−y})e^{−y}(2y)^{−α} + (1 − e^{−y})2^{−α}f_{α}(y).

Now

G_{α}(t) := ∫_{0}^{∞} e^{−ty}f_{α}(y)\frac{dy}{y} = ∫_{0}^{∞} e^{−2ty}f_{α}(2y)\frac{dy}{y}

= ∫_{0}^{∞} e^{−2ty}[(1 − e^{−y})e^{−y}(2y)^{−α} + (1 − e^{−y})f_{α}(y)2^{−α}]\frac{dy}{y}

= 2^{−α}Γ(−α)[(2t + 1)^{α} − (2t + 2)^{α}] + ∫_{0}^{∞} e^{−2ty}(1 − e^{−y})f_{α}(y)2^{−α} \frac{dy}{y} .

So

G_{α}(t) = Γ(−α)2^{−α}[(2t + 1)^{α} − (2t + 2)^{α}] + 2^{−α}G_{α}(2t) − 2^{−α}G_{α}(2t + 1).

By iteration we find

M(α) := G_{α}(1) = −Γ(−α) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(2^{k}+j)}2^{−αk}(2^{k} + j + 1)^{α}

= Γ(−α) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}2^{−αk}(2^{k} + j + 1)^{α},  (7)

and

ϕ(α) = M(α̃)/L.  (8)

Now, by (3) and setting s = χ_{l},

F_{0}(χ_{l}) = \frac{1}{L}Γ(χ_{l}) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + 1)^{−χ_{l}}.

It is already proved in [11] that this is zero. (But it follows readily from the computations that appear in this paper.)

3 The moments

The purpose of this section is to obtain the dominant terms of the moments of J, the first two of which have been computed already in [1].

The paper [10] contains the following theorem, which we express in our notation

F_{k}(s) := ϕ^{(k)}(α)|_{α=−Ls} .

Theorem 1. Let J be the position of the maximal empty urn before the last non-empty urn. The first two moments of the parameter J are asymptotically given by

𝔼(J − log n; B) ∼ ϕ′(0) + ∑_{l≠0} F_{1}(χ_{l})e^{−2lπi log n},
𝔼((J − log n)^{2}; B) ∼ ϕ′′(0) + ∑_{l≠0} F_{2}(χ_{l})e^{−2lπi log n}.

□

Now, by (7) and (8),

ϕ(α) = M(α̃)/L,
M(α) = Γ(−α)H(α), with  (9)
H(α) := ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}2^{−αk}(2^{k} + j + 1)^{α}.

The following expansion is well known, where γ is the Euler’s constant ([5]):

Γ(−α) = −\frac{1}{α} − γ − (\frac{π^{2}}{12} + \frac{γ^{2}}{2} ) α + · · · .

Now we expand H(α):

H(α) = 0 + H′(0)α + H′′(0)\frac{α^{2}}{2} + H′′′(0)\frac{α^{3}}{6} + ⋯,
H′(0) = ∑_{k≥1}[−Lk ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} + L ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + 1)],

H′′(0) = ∑_{k≥1}[L^{2}k^{2} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} − 2L^{2}k ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + 1)  (10)

+ L^{2} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{2}(2^{k} + j + 1)],

H′′′(0) = ∑_{k≥1}[−L^{3}k^{3} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} + 3L^{3}k^{2} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + 1)

− 3L^{3}k ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{2}(2^{k} + j + 1) + ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{3}(2^{k} + j + 1)].

Note that, as ϕ(0) = 1/2, the first term in these equations is identically 0 and H′(0) = −\frac{L}{2}. Set

f(x) = ∑_{k≥0} k ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + x),

g(x) = ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + x).

A similar computation as before shows that

f(x) = f(\frac{x}{2}) − f(\frac{x + 1}{2}) + g(x) − log(1 + x)

and

g(x) = log(1 + x) + g(\frac{x}{2}) − g(\frac{x + 1}{2}).

(Later we will make one general observation that produces all the necessary identities at once.) Therefore

g(0) = g(0) − g(\frac{1}{2}) ⇒ g(\frac{1}{2}) = 0 ⇒ g(1) = 1 + g(\frac{1}{2}) − g(1) ⇒ g(1) = \frac{1}{2}.

Likewise

f(0) = f(0) − f(\frac{1}{2}) + g(0) ⇒ f(\frac{1}{2}) = g(0) ⇒
f(1) = f(\frac{1}{2}) − f(1) + g(1) − 1 ⇒ f(1) = \frac{1}{2}g(0) + \frac{1}{4} − \frac{1}{2} = \frac{1}{2}g(0) − \frac{1}{4}.

We don’t know what g(0) is, but it will cancel out later on. Furthermore, we note that the constant g(0) is related to N′(0) from a paper by Flajolet and Martin [6]; this observation is, however, irrelevant here. The notation refers to N(s) which is the analytic continuation of

∑_{j≥1}(−1)^{ν(j)}/j^{s}.

Set

h(x) = ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{2}(2^{k} + j + x).

Then we derive in a similar fashion that

h(x) = log^{2}(1 + x) + 2g(\frac{x}{2}) + h(\frac{x}{2}) − 2g(\frac{x + 1}{2}) − h(\frac{x + 1}{2}).

Hence

h(0) = 2g(0) + h(0) − 2g(\frac{1}{2}) − h(\frac{1}{2}) ⇒ 0 = 2g(0) − h(\frac{1}{2}) ⇒ h(\frac{1}{2}) = 2g(0),

and

h(1) = 1 + 2g(\frac{1}{2}) + h(\frac{1}{2}) − 2g(1) − h(1) ⇒ 2h(1) = 1 + 2g(0) − 1 ⇒ h(1) = g(0).

Note that

f(1) − \frac{1}{2}h(1) = \frac{1}{2}g(0) − \frac{1}{4} − \frac{1}{2}g(0) = −\frac{1}{4},

and the quantity g(0) cancels out. Writing it in extended form,

∑_{k≥1} k ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log(2^{k} + j + 1) − \frac{1}{2} ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{2}(2^{k} + j + 1) = −\frac{1}{4}.

Hence H′′(0) = −L^{2}/2.

Let us turn to the third derivative. Omitting the details (introducing various auxiliary functions), we can prove that H′′′(0) = −L^{3}/2. But we will soon show (in Section 5) how one can streamline these computations to get all moments in a mechanical way.

Now we substitute α = α̃ in M(α)/L and expand w.r.t. α. By (8) and (9), this immediately gives

ϕ(0) = \frac{1}{2},
ϕ′(0) = \frac{1}{2} (\frac{γ}{L} + \frac{1}{2}) ,
ϕ′′(0) = \frac{1}{2} (\frac{1}{3} + \frac{γ}{L} + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} ) .

Note that this conforms to [1], as it should.

4 The periodicities

Let us analyze F_{1}(χ_{l}). To simplify the notation, we will simply write χ. We have

ϕ(α) = \frac{1}{L}Γ(−α/L) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}e^{−αk}(2^{k} + j + 1)^{α/L},
ϕ′(α) = \frac{1}{L}[−\frac{1}{L}Γ(−α/L)ψ(−α/L) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}e^{−αk}(2^{k} + j + 1)^{α/L}

+ Γ(−α/L)[− ∑_{k≥1} ∑_{j=0}^{2^{k}−1} k(−1)^{ν(j)}e^{−αk}(2^{k} + j + 1)^{α/L}

+ ∑_{k≥1} ∑_{j=0}^{2^{k}−1} log(2^{k} + j + 1)(−1)^{ν(j)}e^{−αk}(2^{k} + j + 1)^{α/L}]],

F_{1}(χ) = −\frac{1}{L^{2}} Γ(χ) ∑_{k≥1} ∑_{j=0}^{2^{k}−1}(2^{k} + j + 1)^{−χ}(ψ(χ) + kL − L log(2^{k} + j + 1)).

We need an auxiliary function

g(x) := ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + x)^{−χ}.

As usual,

g(x) = (1 + x)^{−χ} + ∑_{k≥0} ∑_{j=0}^{2^{k+1}−1}(−1)^{ν(j)}(2^{k+1} + j + x)^{−χ}

= (1 + x)^{−χ} + ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + \frac{x}{2})^{−χ} − ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + \frac{x + 1}{2})^{−χ},

and so

g(x) = (1 + x)^{−χ} + g(\frac{x}{2}) − g(\frac{x + 1}{2}).

Therefore

g(0) = 1 + g(0) − g(\frac{1}{2}) ⇒ g(\frac{1}{2}) = 1 ⇒ g(1) = 1 + g(\frac{1}{2}) − g(1)
⇒ 2g(1) = 2 ⇒ g(1) = 1.

We need a further auxiliary function

f(x) := ∑_{k≥0} k ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + x)^{−χ}

and derive

f(x) = ∑_{k≥1}(k − 1) ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + x)^{−χ} − (1 + x)^{−χ} + g(x)

= f(\frac{x}{2}) − f(\frac{x + 1}{2}) − (1 + x)^{−χ} + g(x).

Therefore

f(0) = f(0) − f(\frac{1}{2}) − 1 + g(0) ⇒ f(\frac{1}{2}) = −1 + g(0) ⇒ f(1) = f(\frac{1}{2}) − f(1)
⇒ f(1) = −\frac{1}{2} + \frac{1}{2}g(0).

We need a third function

h(x) := ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(2^{k} + j + x)^{−χ} log(2^{k} + j + x).

The usual procedure (that we suppress) leads to

h(x) = h(\frac{x}{2}) − h(\frac{x + 1}{2}) + g(\frac{x}{2}) − g(\frac{x + 1}{2}) + (1 + x)^{−χ} log(1 + x).

Therefore

h(0) = h(0) − h(\frac{1}{2}) + g(0) − g(\frac{1}{2}) ⇒ h(\frac{1}{2}) = g(0) − 1 ⇒
h(1) = h(\frac{1}{2}) − h(1) + g(\frac{1}{2}) − g(1) + 1 ⇒ h(1) = \frac{1}{2}g(0).

Now

F_{1}(χ) = −\frac{1}{L^{2}} Γ(χ)[ψ(χ)(g(1) − 1) + Lf(1) − L(h(1) − 1)]

= −\frac{1}{L}Γ(χ)[ − \frac{1}{2} + \frac{1}{2}g(0) − \frac{1}{2}g(0) + 1] = −\frac{1}{2L}Γ(χ).

Finally, we turn to F_{2}(χ). Omitting the details, we can prove that

F_{2}(χ) = −\frac{Γ(χ)}{2L} + \frac{Γ(χ)ψ(χ)}{L^{2}}.

Note that the periodicities conform to [1]. We will not pursue these computations as we will soon give a simple, direct way of getting all the expressions we need.

To obtain the conditioned moments, we divide by ℙ(B) = 1/2. So

𝔼(J − log n|B) ∼ 2[ϕ′(0) + ∑_{l≠0} F_{1}(χ_{l})e^{−2lπi log n}],

𝔼((J − log n)^{2}|B) ∼ 2[ϕ′′(0) + ∑_{l≠0} F_{2}(χ_{l})e^{−2lπi log n}]

and we have the conditioned variance

𝕍(J|B) ∼ 2ϕ′′(0) − 4(ϕ′(0))^{2} + 2 ∑_{l≠0} F_{2}(χ_{l})e^{−2lπi log n}

− 8ϕ′(0)[∑_{l≠0} F_{1}(χ_{l})e^{−2lπi log n}] − 4[ ∑_{l≠0} F_{1}(χ_{l})e^{−2lπi log n}]^{2}.

This has been computed in [1] already.

5 General Allouche-Shallit-type formulas and direct moments computations

In this section, we first prove a very simple expression for H^{(m)}(0) which translates to ϕ(α). As a byproduct, we have a direct form for all moments and also a family of new interesting identities.

Set

A(a, b) := ∑_{k≥0} k^{a} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)} log^{b}(2^{k} + j + 1).

We have seen already, by (6), that

A(0, 1) = \frac{1}{2},

which is the Allouche-Shallit identity, and

A(0, 2) − 2A(1, 2) = \frac{1}{2}.

Introducing more and more auxiliary functions, one is led to

A(0, 3) − 3A(1, 2) + 3A(2, 2) = \frac{1}{2},

A(0, 4) − 4A(1, 3) + 6A(2, 2) − 4A(3, 1) = \frac{1}{2}.

An obvious pattern appears:

∑_{l=0}^{m} \binom{m}{l}(−1)^{m−l}A(l, m − l) = \frac{1}{2}.

All these formulas follow from the master formula for m ≥ 0:

Theorem 2.

∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(log(2^{k} + j + 1) − k)^{m} = \frac{1}{2}.

Proof. Here is the simple proof. Set

f(x) := ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(log(2^{k} + j + x) − k)^{m}.

Then

f(x) = log^{m}(1 + x) + ∑_{k≥0} ∑_{j=0}^{2^{k+1}−1}(−1)^{ν(j)}(log(2^{k+1} + j + x) − k − 1)^{m}

= log^{m}(1 + x) + ∑_{k≥0} ∑_{j=0}^{2^{k+1}−1}(−1)^{ν(j)}(log(2^{k} + \frac{j + x}{2}) − k)^{m}

= log^{m}(1 + x) + ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(log(2^{k} + \frac{2j + x}{2}) − k)^{m}

− ∑_{k≥0} ∑_{j=0}^{2^{k}−1}(−1)^{ν(j)}(log(2^{k} + \frac{2j + 1 + x}{2}) − k)^{m}

= log^{m}(1 + x) + f(\frac{x}{2}) − f(\frac{x + 1}{2}).

Therefore, by setting x = 0,

f(\frac{1}{2}) = 0,

and by setting x = 1,

f(1) = \frac{1}{2}.

The master theorem leads to (note that the summation on k is from k = 0, but the summation in H^{(m)} starts from k = 1)

H^{(m)}(0) = −\frac{1}{2}L^{m},  m ≥ 1.

This gives the following Laplace transforms:

Theorem 3.

M(α) = Γ(−α)H(α) = −\frac{1}{2}Γ(−α)(e^{Lα} − 1),
ϕ(α) = M(α̃)/L = −\frac{1}{2L}Γ(−α̃)(e^{Lα̃} − 1).

Now that we found that ϕ(α) has such a simple explicit form, we recover immediately ϕ(0), ϕ′(0), ϕ′′(0), and a new expression ϕ′′′(0) related to the third moment:

ϕ′′′(0) = \frac{ζ(3)}{L^{3}} + \frac{π^{2}γ}{4L^{3}} + \frac{π^{2}}{8L^{2}} + \frac{γ}{2L} + \frac{γ^{3}}{2L^{3}} + \frac{1}{8} + \frac{3γ^{2}}{4L^{2}} .  (11)

Similarly, we recover F_{1}(χ), F_{2}(χ), and a new expression

F_{3}(χ) = Γ(χ) [−\frac{3ψ(1, χ)}{2L^{3}} − \frac{3ψ^{2}(χ)}{2L^{3}} + \frac{3ψ(χ)}{L^{2}} − \frac{1}{2L}] .  (12)

For instance, we can state the third moment:

Theorem 4.

𝔼((J − log n)^{3}; B) ∼ ϕ′′′(0) + ∑_{l≠0} F_{3}(χ_{l})e^{−2lπi log n}

with (11) and (12).

All moments can in principle be computed automatically.

6 The LMV(−1) case

If the largest missing value is exactly one smaller than the largest value, we say, following Archibald and Knopfmacher [1], that the sequence has the LMV(−1) property. In this case, contrarily to the previous sections, our urn model leads almost immediately to all probabilistic properties: we have here a very simple form for ϕ(α). Let B be now the event that the LMV(−1) property is satisfied, and J be the largest missing value exactly one smaller than the largest value. We easily derive (we just plug r = 1 into (2))

ϕ(α) = ∫_{0}^{∞} y^{−α̃}e^{−y} [1 − e^{−ye^{−L}}] e^{−ye^{−L}} \frac{dy}{Ly}

= \frac{1}{L} (2^{−α̃}3α̃ − 2α̃) Γ(−α̃).

Hence, automatically,

ϕ(0) = 2 − log 3,
ϕ′(0) = \frac{2γ}{L} + log 3 − \frac{γ log 3}{L} − \frac{log^{2} 3}{2},
ϕ′′(0) = −\frac{log^{3} 3}{3} + \frac{2}{3} + log^{2} 3 − \frac{log 3γ^{2}}{L^{2}} + 2\frac{γ log 3}{L} − \frac{π^{2} log 3}{6L^{2}} − log 3 + \frac{π^{2}}{3L^{2}} + 2\frac{γ^{2}}{L^{2}} − \frac{γ log^{2} 3}{L}.

The first two expressions are already given in [1]. The third one is new. All moments are obtained in the same way.

Also we easily derive

F_{0}(χ_{l}) = \frac{1}{L}(3^{−χ_{l}} − 1)Γ(χ_{l}),
F_{1}(χ_{l}) = −\frac{Γ(χ_{l})3^{−χ_{l}}}{L^{2}} [L − L log 3 + L3^{χ_{l}} + ψ(χ_{l}) − ψ(χ_{l})3^{χ_{l}}] ,
F_{2}(χ_{l}) = −\frac{Γ(χ_{l})3^{−χ_{l}}}{L^{3}} [−L^{2} + L^{2}3^{χ_{l}} + 2 log 3L^{2} − 2ψ(χ_{l})L − 2ψ(χ_{l})L3^{χ_{l}}
− log^{2} 3L^{2} + 2ψ(χ_{l}) log 3L − ψ(1, χ_{l}) + ψ(1, χ_{l})3^{χ_{l}} − ψ^{2}(χ_{l}) + ψ^{2}(χ_{l})3^{χ_{l}}].

Again the first two expressions are already given in [1]. The third one is new. That described the moments, but we can also get the (asymptotic) probability that B holds:

ℙ(B) ∼ ϕ(0) + ∑_{l≠0} F_{0}(χ_{l})e^{−2lπi log n}.

7 Conclusion

We succeeded in analyzing the instance p = 1/2, related to random compositions. The (semi)automatic computations of all moments led us to a one parameter extension of the celebrated identity due to Allouche and Shallit. Unfortunately, this analysis cannot be extended to the case p ≠ 1/2, as no expansions that involve ν(k) are available. Of course we could use a general integral form similar to (2) and use the theorems we developed in [10], but it would not be really explicit. One could also use some recursion on the number of gaps and some inclusion-exclusion expressions, but it would not be simpler.

The instance p = 1/2 is privileged inasmuch as it leads to very beautiful mathematics, and this is just appropriate for the present birthday issue.

References

[1] M. Archibald and A. Knopfmacher. The largest missing value in a composition of an integer. Discrete Math. 311 (2011), 723–731.

[2] J.-P. Allouche, H. Cohen, M. Mendès France, and J. O. Shallit. De nouveaux curieux produits infinis. Acta Arith. 49 (1987), 141–153.

[3] G. Louchard, H. Prodinger, and M. D. Ward. The number of distinct values of some multiplicity in sequences of geometrically distributed random variables. Discr. Math. and Theoret. Comp. Sci. (2005), 231–256. 2005 International Conference on Analysis of Algorithms.

[4] J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.

[5] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1965.

[6] P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31 (1985), 182–209.

[7] P. Hitczenko and A. Knopfmacher. Gap-free samples of geometric random variables. Discrete Math. 294 (2005), 225–239.

[8] P. Hitczenko and G. Louchard. Distinctness of compositions of an integer: a probabilistic analysis. Random Structures & Algorithms 19 (2001), 407–437.

[9] M. Loève. Probability Theory, 3rd edition. D. Van Nostrand, 1963.

[10] G. Louchard and H. Prodinger. Asymptotics of the moments of extreme-value related distribution functions. Algorithmica 46 (2006), 431–467. Long version:

    http://www.ulb.ac.be/di/mcs/louchard/moml.ps.

[11] G. Louchard and H. Prodinger. On gaps and unoccupied urns in sequences of geometrically distributed random variables. Discrete Math. 308-309 (2008), 1538–1562. Long

    version: http://www.ulb.ac.be/di/mcs/louchard/gaps18.ps.

[12] D. Robbins. Solution to Elementary problem E2692. Amer. Math. Monthly 86 (1979), 395–395.

[13] D. R. Woods. Elementary problem E2692. Amer. Math. Monthly 85 (1978), 48.

2010 Mathematics Subject Classification: Primary 05A16; Secondary 60C05. Keywords: composition, largest missing value, asymptotic expansion, identity, sum-of-digits function.

(Concerned with sequence \underline{A000120}.)

Received April 18 2012; revised version received October 25 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.