Brownian Motion and the Generalized Catalan Numbers

Joseph Abate 900 Hammond Road Ridgewood, NJ 07450-2908 USA

Ward Whitt

Department of Industrial Engineering and Operations Research Columbia University New York, NY 10027-6699 USA

                  ww2040@columbia.edu

Abstract

We show that the generating functions of the generalized Catalan numbers can be identified with the moment generating functions of probability density functions related to the Brownian motion stochastic process. Specifically, the probability density functions are exponential mixtures of inverse Gaussian (EMIG) probability density functions, which arise as the first passage time distributions to the origin of Brownian motion with a negative drift and an exponential initial distribution on the positive halfline. As a consequence of the EMIG representation, we show that the generalized Catalan numbers are the moments of generalized beta distributions. We also study associated convolution sequences arising as the coefficients of the product of two generalized Catalan generating functions.

1 Introduction

Our purpose in this paper, as in our recent [8], is to establish connections between probability theory and integer sequences. We show how established probability results can be applied to generate new integer sequences and results about integer sequences, after appropriate connections have been established. In particular, we establish a connection between the classical Brownian motion stochastic process and the generalized Catalan numbers, C_{n}(α). We show that the generalized Catalan numbers are intimately connected to certain exponential mixtures of inverse Gaussian distributions, which arise as first passage times to the origin of Brownian motion with negative drift, starting with an exponential initial distribution on the positive halfline. (See Theorems 1 and 2.) We then apply this relation to identify interesting integer sequences and relations among integer sequences.

As a consequence of our analysis, we propose the new family of integer sequences {V_{n}(α) : n ≥ 1}, where α is a positive integer and

V_{n}(α) ≡ ∑_{k=0}^{n} \binom{n + k}{k}α^{k}, n ≥ 1,  (1)

where ≡ denotes “equality by definition.” The integer sequence \{V_{n}(1)\} (\underline{A001700}) is pervasive in the OEIS [19], but we ourselves only recently contributed the integer sequence \{V_{n}(2)\} (\underline{A178792}). A primary goal is to expose the structure of the family \{V_{n}(α)\}, α ≥ 1. The general sequence {V_{n}(α)} has been studied on p. 236 of [13]; see pp. 167, 215 for more on the special case α = 1/2.

In the end, there is a fairly direct connection between the classical sequence of Catalan numbers {C_{n}}, with

C_{n} ≡ \binom{2n}{n}\frac{1}{n + 1} = \frac{(2n)!}{n!(n + 1)!}, n ≥ 1,  (2)

and the integer sequences {V_{n}(α)} via their generating functions, which we summarize now:

c(x) ≡ ∑_{n=0}^{∞} C_{n}x^{n} = \frac{2}{1 + \sqrt{1 − 4x}},  (3)

c(x; α) ≡ ∑_{n=0}^{∞} C_{n}(α)x^{n} = (1 − xc(αx))^{−1},  (4)

c(x; a, b) ≡ ∑_{n=0}^{∞} C_{n}(a, b)x^{n} ≡ c(bx; a)c(ax; b),  (5)

v(x; α) ≡ ∑_{n=0}^{∞} V_{n}(α)x^{n} ≡ c(2αx; 1/2)c(x; α); .  (6)

Supporting theory appears in Theorems 3-8. In Theorem 2 and 7 we establish integral representations, which are known to provide additional insight [16]. Many examples of integral representations appear in [19].

The relations in (4)–(6) are especially interesting to us, because they are generalizations of important relations for functions characterizing the transient behavior of reflected Brownian motion exposed in our first paper [1]. Since the transient mean is nondecreasing and bounded, it can be regarded as a probability cumulative distribution function (cdf) when we divide by the limiting value; in [1] we called it the “RBM first-moment cdf.” We discuss the connections between relations (3)-(6) and our previous papers [1, 4, 7] in §5.

2 Background

We start by giving background on the generalized Catalan numbers, Brownian motion and associated first passage time distributions.

The generalized Catalan numbers. The Catalan numbers in (2) frequently arise in combinatorics and are pervasive in the OEIS [19]; see \underline{A000108}. Following Lang (\underline{A064062}), we define the generalized Catalan numbers C_{n}(α) as the coefficients of the generating function c(x; α) defined in (4), where c(x) is the generating function of the (ordinary) Catalan numbers C_{n} in (3). Other proposed definitions for (properties of) the generalized Catalan numbers appear in \underline{A006633}, \underline{A068765}, \underline{A130564} and in [10, p. 14]. We prefer definition (3) because it builds on the basic characterization of c(x), namely,

c(x) = \frac{1}{1 − xc(x)} or c(x)^{2} = \frac{c(x) − 1}{x}.  (7)

The first relation in (7) characterizes c(x) as the fixed point of the exponential-mixture operator; see Proposition 4 of [8]. The second relation characterizes the sequence {C_{n}} by having the two-fold convolution equal to C_{n+1}. Based on (3) and (4), we obtain

c(x; α) = \frac{2α}{2α − 1 + \sqrt{1 − 4αx}} = \frac{2α − 1 − \sqrt{1 − 4αx}}{2(α − 1 + x)}.  (8)

The generalized Catalan numbers are given explicitly by

C_{n+1}(α) = ∑_{k=0}^{n} a(n, k)α^{k},  (9)

where the triangle numbers a(n, k) given in \underline{A009766} are the famous ballot numbers

a(n, k) ≡ (1 − \frac{k}{n + 1}) \binom{n + k}{k};  (10)

see pp. 130, 152 of [17].

Brownian motion and EMIG distributions. Brownian motion is one of the most extensively studied stochastic processes; e.g., see Chapter 1 of [14] or [12]. It has two parameters: the drift parameter μ and the diffusion or variance parameter σ^{2}. If X ≡ {X(t) : t ≥ 0} is a (μ, σ^{2})-Brownian motion, then X(t) has a normal or Gaussian distribution with mean μt and variance σ^{2}t for each t. We will be interested in the first passage time from one state to another for Brownian motion with drift, which is well understood. The standard way to study such first passage time problems is to apply martingales. For the problem at hand with drift, it is standard to apply exponential martingales, in particular, the Wald martingale

W (t) ≡ exp {cX(t) − q(c)t}, t ≥ 0,  (11)

where q(c) ≡ μc + σ^{2}c^{2}/2; see §§1.5 and 3.2 of [14]. We can calculate the Laplace transform of the first passage time distribution by using the optional stopping theorem with the first passage time serving as the stopping time.

Here we consider Brownian motion (BM) with constant drift μ = −1/(2α) and constant diffusion coefficient σ^{2} = 1/(2α), depending on the positive real parameter α. By the reasoning above, or in other ways, we determine the Laplace transform of the probability density function (pdf) f(t, y; α) of the first passage time from initial state y > 0 at time 0 to final state 0,

f̂(s, y; α) ≡ ∫_{0}^{∞} e^{−st}f(t, y; α) dt = exp \{−y(\sqrt{1 + 4αs} − 1)\},  (12)

which is defined for complex s with positive real part, and then the pdf itself,

f(t, y; α) = ((αy^{2})/(πt^{3}))^{1/2} exp {−(t − 2αy)^{2}/(4αt)}, t ≥ 0,  (13)

which is the pdf of an inverse Gaussian (IG) distribution. For the classical approach before martingales, see (73) on p. 221 of [12]. The seminal work was done independently by Schroedinger and Smoluchowski in 1915; see p. 1 of [18].

A closely related stochastic process is reflected Brownian motion (RBM), which is the BM above, with the same parameters, and a reflecting barrier at 0; see §1.9 and Chapter 5 of [14], where it is called regulated Brownian motion (a name which has not caught on). Clearly, the first-passage-time from y > 0 to 0 for RBM has the same pdf f(t, y; α) in (13). Unlike the BM, the RBM has a proper limiting distribution as t → ∞, which is also a stationary distribution for the RBM. That stationary distribution has an exponential pdf p with mean 1/2, i.e.,

p(y; η) = ηe^{−ηy}, y ≥ 0, for η = 2;  (14)

see §5.6 of [14].

An important quantity associated with RBM is the first passage time to 0 starting from the stationary distribution p, which we have called the equilibrium time to emptiness; see Theorem 1.3 and Corollary 1.3.1 of [1]. Since the equilibrium time to emptiness is a mixture of the distribution of the first-passage time to 0 with respect to the initial stationary distribution, where the first-passage-time distribution is inverse Gaussian and the stationary distribution is exponential, the equilibrium time to emptiness has a distribution that is an exponential mixture of inverse Gaussian (EMIG) distributions.

EMIG distributions and the generalized Catalan numbers. We will show that a particular family of EMIG pdf’s are intimately connected to the generalized Catalan numbers. We define the family of EMIG pdf’s indexed by α as

g(t; α) ≡ ∫_{0}^{∞} p(y; α)f(t, y; α) dy, t ≥ 0.  (15)

For each α > 0, g(t; α) is a bona fide pdf, but it only corresponds to the equilibrium time to emptiness for RBM in the special case α = 1. However, the EMIG distribution is the first passage time to the origin for both BM and RBM, when they have negative drift, with respect to a particular exponential initial distribution on the positive halfline. We studied EMIG probability distributions in [1, 3, 4, 5, 6]; see §2 of [3], §8 of [4], Example 8.3 in [5] and §3 of [6].

Now let ĝ(s; α) be the Laplace transform of the pdf g(t; α) in (15), i.e.,

ĝ(s; α) ≡ ∫_{0}^{∞} e^{−st}g(t; α) dt.  (16)

Let ĝ(−x; α) for positive real x be the associated moment generating function of g(t; α). Our main observation is

Theorem 1. The EMIG moment generating function ĝ(−x; α) coincides with the generating function c(x; α) in (8). Equivalently, the Laplace transform in (16) can be represented as

ĝ(s; α) = c(−s; α) = \frac{2α}{2α − 1 + \sqrt{1 + 4αs}}.  (17)

Proof. By direct integration, we can verify that ĝ(s; α) in (17) has the integral representation

ĝ(s; α) = ∫_{0}^{∞} 2αe^{−2αy}f̂(s, y; α) dy,  (18)

where f̂(s, y; α) is the Laplace transform in (12); see (29.3.82) on p. 1026 of [9] and (8.4) on p. 95 of [4].

3 Further Connections

The explicit representation. We now apply Theorem 1 to make connections. We first apply Theorem 1 to give an alternative derivation of the explicit expression for the generalized Catalan numbers in (9). From (18), we directly obtain

C_{n+1}(α) = ∫_{0}^{∞} 2αe^{−2αy} \frac{m_{n+1}(f)}{(n + 1)!} dy,  (19)

where

m_{n}(f) ≡ ∫_{0}^{∞} x^{n}f(x) dx,  (20)

so that m_{n+1}(f) is the (n + 1)^{st} moment of the pdf f ≡ f(t, y; α) in (13), with

\frac{m_{n+1}(f)}{(n + 1)!} = ∑_{k=0}^{n} a(n, k)α^{k} \frac{(2αy)^{n+1−k}}{(n + 1 − k)!};  (21)

see Proposition 2.14 on p. 46 of [18]. After the final expression for C_{n+1}(α) in (9) is factored out of (19), the remaining integral reduces to 1, because it can be identified as the integral of a gamma pdf over its entire domain.

Examples are

\{2^{n}C_{n}(1/2)\} = 1, 2, 6, 20, 70, 252 (\underline{A000984})
\{C_{n}(2)\} = 1, 1, 3, 13, 67, 381 (\underline{A064062})
\{2^{n}C_{n}(3/2)\} = 1, 2, 10, 68, 538, 4652 (\underline{A110520})
\{C_{n}(3)\} = 1, 1, 4, 25, 190, 1606 (\underline{A064063})

In addition, the OEIS includes C_{n}(4) − C_{n}(10) as sequences \underline{A064087}–\underline{A064093}. Note that {2^{n}C_{n}(1/2)} is the sequence of central binomial numbers (see (28) below) and that c(x; α) = 1/\sqrt{1 − 2x}.

It is immediate from (3) and the well known continued fraction representation for c(x) that c(x; α) has the continued fraction representation

c(x; α) = \frac{1}{1−} \frac{x}{1−} \frac{αx}{1−} \frac{αx}{1−} \frac{αx}{1−}. · · ·  (22)

As a consequence, we see that c(x; 0) = (1 − x)^{−1}.

The generalized Catalan numbers as moments. Next we give the mixing-density representation for the EMIG. We say that a pdf h(y) has a mixing density w(x) if h has the integral representation

h(t) = ∫_{τ_{1}}^{τ_{2}} y^{−1}e^{−t/y}w(y) dy, y ≥ 0,

for some fixed τ_{1} and τ_{2} with τ_{1} < τ_{2}. The associated Laplace transforms are related by

ĥ(s) = ∫_{τ_{1}}^{τ_{2}} w(y) \frac{dy}{1 + sy};

see (3.2) and (3.4) in [5].

For our EMIG pdf’s, we have the mixing-density representation

ĝ(s; α) = ∫_{0}^{4α} β(y; α)\frac{dy}{1 + ys},  (23)

where

β(y; α) ≡ \frac{\sqrt{4α − y}}{2π\sqrt{y}(1 + (α − 1)y)};  (24)

i.e., β(y; α) is the pdf of a generalized beta distribution; see (94.22) on p. 375 of [20] and Theorem 4.1 on p. 29 of [6]. For the two cases α = 1/2 and α = 1, β(y; α) is an ordinary beta pdf.

As an immediate consequence, we obtain the following characterization of the generalized Catalan numbers.

Theorem 2. The generalized Catalan numbers arise as the moments of the generalized beta pdf β(y; α) in (24); i.e.,

C_{n}(α) = ∫_{0}^{4α} y^{n}β(y; α) dy.  (25)

The moments in (25) can also be expressed in terms of the Gauss series, because C_{n}(α) = F (1 − n, n; −n, a); see (15.4.2) on p. 561 of [9].

4 Implications for Other Integer Sequences

A product of EMIG generating functions. We now study the (two-fold) convolution of the sequence {a^{n}C_{n}(b)} with the sequence {b^{n}C_{n}(a)}, i.e., the sequence {C_{n}(a, b)} defined in (5), using (3). An interesting property of EMIG distributions is that the convolution represented by (5) can be represented as a linear combination of EMIG’s; see (8.13) on p. 97 of [4]. As a consequence, we obtain

Theorem 3. For a ≠ b,

c(bx; a)c(ax; b) = \frac{1}{b − a} (bc(bx; a) − ac(ax; b))  (26)

and

C_{n}(a, b) = \frac{1}{b − a} (b^{n+1}C_{n}(a) − a^{n+1}C_{n}(b)) .  (27)

The case a = b is covered by Corollary 6 below. As an aside, we point out that for a = b = 1, the multiple convolutions of \{C_{n}\} with itself are represented by the triangle \underline{A033184}, which has some very interesting properties; see [15]. From a probabilistic perspective, see p. 568 of [1].

Two examples are

\{C_{n}(2, 3)\} = 1, 5, 49, 653, 10201, ⋯ (\underline{A116873})
\{C_{n}(2, 4)\} = 1, 6, 76, 1336, 27696, ⋯ (\underline{A116874})

The OEIS includes \{C_{n}(2, 5)\} through \{C_{n}(2, 8)\} as \underline{A116875}(n+1) through \underline{A116878}(n+1). To illustrate how Theorem 3 can be applied, from (27) we obtain

C_{4}(2, 3) = 3^{5}C_{4}(2) − 2^{5}C_{4}(3)
= 3^{5}\underline{A064062}(4) − 2^{5}C_{4}(3)\underline{A064063}(4)
= 3^{5}(67) − 2^{5}(190) = 10201.

The sequence {V_{n}(α)}. We now come to the sequence {V_{n}(α)} in (1) and (6). In §3 we mentioned that the sequence {2^{n}C_{n}(1/2)} is the sequence of central binomial numbers; i.e.,

c(2x; 1/2) = \frac{1}{\sqrt{1 − 4x}} = ∑_{n=0}^{∞} \binom{2n}{n}x^{n}.  (28)

Define the sequence {V_{n}(α)} and its generating function v(x; α) via (6). We obtain the following result; we give proofs of this theorem and following ones in §6 below.

Theorem 4. The numbers V_{n}(α) have the explicit representation

V_{n}(α) = \frac{1}{2α − 1} ((2α)^{n+1}C_{n}(1/2) − C_{n}(α)) = ∑_{k=0}^{n} \binom{n + k}{k}α^{k}.  (29)

It seems that the representation in Theorem 4 is new. The only two cases of {V_{n}(α)} in the OEIS we are aware of are

\{V_{n}(1)\} = 1, 3, 10, 35, 126, 1716 ⋯ (\underline{A001700})
\{V_{n}(2)\} = 1, 5, 31, 209, 1471, 10625 ⋯ (\underline{A178792})

Indeed, we ourselves recently contributed the case α = 2.

For the relatively simple case of α = 1/2, by (6) the generating function is given by 1/(1 − 2x), so that V_{n}(1/2) = 2^{n}. Therefore, from Theorem 4, we deduce that

2^{n} = ∑_{k=0}^{n} \binom{n + k}{k} (\frac{1}{2})^{k} .  (30)

Formula (30) is given on p. 167 of [13].Also (5.137) on p. 236 of [13] gives the following recurrence relation

V_{n}(α) + (α − 1)V_{n+1}(α) = (2α − 1)α^{n+1}V_{n}(1).  (31)

Now consider the convolution of the sequence {C_{n}(α} with itself, denoting its terms by C_{n}^{(2)}(α); i.e., let

c^{(2)}(x; α) ≡ ∑_{n=0}^{∞} C_{n}^{(2)}x^{n} ≡ c(x; α)^{2}.  (32)

Then we find the following result.

Theorem 5. We can represent the numbers C_{n}^{(2)}(α) via

c^{(2)}(x; α) ≡ c(x; α)^{2} = 2αv(x; α) − (2α − 1)\frac{d}{dx}c(x; α)  (33)

and

C_{n}^{(2)}(α) = 2αV_{n}(α) − (2α − 1)(n + 1)C_{n+1}(α).  (34)

Two examples are

\{C_{n}^{(2)}(2)\} = 1, 2, 7, 32, 169, ⋯ (\underline{A115197})
\{C_{n}^{(2)}(3)\} = 1, 2, 9, 58, 446, ⋯ (\underline{A116867})

We can apply Theorem 5 to treat the missing case in Theorem 3; i.e., we can determine the numbers C_{n}(a, a).

Corollary 6. We can represent the numbers C_{n}(a, a) via

C_{n}(a, a) = a^{n}C_{n}^{(2)}(a).  (35)

By combining (34) and (35), we can obtain explicit representations for the sequence \{C_{n}(a, a)\}. The OEIS includes \{C_{n}(2, 2)\} through \{C_{n}(9, 9)\} as \underline{A064340} (n+1) through \underline{A064347} (n+1).

The following integral representation for V_{n}(α) is obtained from Theorem 4 using (23)- (25)

Theorem 7. We have the following integral representation for the numbers V_{n}(α)

V_{n}(α) = ∫_{0}^{4α} y^{n}w(y; α)dy,  (36)

where the mixing density is given by

w(y; α) = \frac{1}{2α − 1} (\frac{2α}{π\sqrt{y(4α − y)}} − β(y; α))

= \frac{1}{2π} \sqrt{y/(4α − y)} (\frac{2α − 1}{1 + (α − 1)y} ) .  (37)

Paralleling the observation after Theorem 2, we note that the numbers V_{n}(α) also have a Gauss series representation, namely, V_{n}(α) = F (−n, n + 1; −n; α). We discuss it further below.

Next we give a continued fraction representation for v(x; α).

Theorem 8. The generating function v(x; α) has the continued fraction representation

v(x; α) = \frac{1}{1 − (2α + 1)x−} \frac{α(2α − 1)x^{2}}{1 − 2αx−} \frac{(αx)^{2}}{1 − 2αx−} \frac{(αx)^{2}}{1 − 2αx−} ⋯  (38)

Note that v(x, 0) = 1/(1 − x). From Theorem 8, we can “pick off” the Hankel transform of the integer sequence {V_{n}(α)}. As in [8, 11], the Hankel transform of an integer sequence provides a useful partial characterization; it is a many-to-one function mapping an integer sequence into another integer sequence. Starting from a sequence {ω_{n} : n ≥ 0} ≡ ω_{0}, ω_{1}, ω_{2}, ω_{2}, … with ω_{0} ≡ 1, let the Hankel matrix M^{(n)} be the (n + 1) × (n + 1) symmetric matrix with elements M_{i,j}^{(n)} ≡ ω_{i+j−2}, 0 ≤ i ≤ n, 0 ≤ j ≤ n. (The first row contains the first n + 1 elements and M_{n+1,n+1} ≡ ω_{2n}. Let H_{2n} ≡ det(M^{(n)}), the even Hankel determinant. Let the Hankel transform of the sequence {ω_{n} : n ≥ 0} above be the sequence {H_{2n} : n ≥ 0}; it starts with H_{0} = 1. With (38), we can apply (12.2) and (12.3) of [11] to obtain

HT ({V_{n}(α}) = (2α − 1)^{n}α^{n^{2}}.  (39)

The Gauss Contiguous Relation. After Theorems 2 and 7, we observed that both C_{n}(α) and V_{n}(α) have Gauss series representations, namely,

C_{n}(α) = F (1 − n, n; −n; α) and V_{n}(α) = F (−n, n + 1; −n; α).  (40)

These are nicely linked via the Gauss contiguous relation (15.2.14) on p. 558 of [9], yielding

\frac{C_{n}(α)}{2} + \frac{V_{n}(α)}{2} = F (−n, n; −n; α) ≡ ∑_{k=0}^{∞} R(n, k)α^{k},  (41)

where

R(n, k) ≡ \binom{n + k − 1}{k} = \binom{−n}{k}(−1)^{k},  (42)

as in \underline{A158498}. The case α = 2 is \underline{A119259}.

5 Connections with Our Previous Papers

Our interest was drawn to the generating functions in (3)-(6) largely because they are natural generalizations of probabilistic quantities that we studied previously via Laplace transforms. These generating functions in (3)-(6) are directly moment generating functions (mgf’s) of probability density functions on the nonnegative halfline. If we replace x by −s, where s is a complex number with positive real part, then we obtain the corresponding Laplace transform. The relations we have established are simultaneously relations among integer sequences and relations among probability distributions. We think that we have uncovered relations of interest in both domains. We are also intrigued by the possibility of establishing more connections between the two domains.

First, as noted before Theorem 9 of [8], c(−s) = ĥ_{1}(s), where ĥ_{1}(s) is the Laplace transform of the pdf h_{1}(t) of the first moment cdf of RBM, H_{1}(t) ≡ E[R(t)|R(0) = 0]/E[R(∞)], t ≥ 0, which we first studied in [1]. In [1] we consider RBM with drift coefficient −1 and diffusion coefficient 1, whereas here we consider RBM with drift coefficient −1/(2α) and diffusion coefficient 1/(2α), so that there is a scale difference, even when α = 1; e.g., in [1], ĥ_{1}(s) = c(−s/2) for c(x) in (3).

We can expand upon the second relation in (7). Corollaries 1.3.2 and 1..5.1 in [1] show that the Laplace transform of the pdf h_{2} of the RBM second moment cdf H_{2}(t) ≡ E[R(t)^{2}|R(0) = 0]/E[R(∞)^{2}] can be represented as

ĥ_{2}(s) ≡ ∫_{0}^{∞} e^{−ys}h_{2}(y) dy = ĥ_{1,e}(s) ≡ \frac{1 − ĥ_{1}(s)}{s} = ĥ_{1}(s)^{2},  (43)

where, for any cdf H(t) ≡ P (X ≤ t), the associated stationary-excess (or equilibrium residual lifetime) cdf and pdf are defined by

H_{e}(t) ≡ \frac{1}{E[X]} ∫_{0}^{t} P (X > y) dy and h_{e}(t) ≡ \frac{1 − H(t)}{E[X]}, t ≥ 0,  (44)

having associated Laplace transform

ĥ_{e}(s) ≡ ∫_{0}^{∞} e^{−sy}h_{e}(y) dy = \frac{1 − ĥ(s)}{E[X]s}.  (45)

Thus, equation (43) states that the RBM second moment pdf h_{2} is simultaneously the stationary excess of the RBM first-moment pdf h_{1} and the two-fold convolution of the cdf h_{1} with itself. The pdf h_{1} is the only pdf on the nonnegative real line for which the associated stationary-excess pdf coincides with the two-fold convolution.. As discussed in Theorem 9 of [8], the pdf h_{1} is intimately connected to the Catalan numbers in (3).

Next, the definition we use for the generalized Catalan numbers in (4) is tantamount to applying the exponential mixture operator to construct a new probability distribution via its Laplace transform. As discussed in §7 of [4], given a Laplace transform f̂ of a pdf f, the exponential-mixture operator yields EM(f̂)(s) ≡ (1 + sf̂(s))^{−1}. We get the two scale parameters by first replacing f̂(s) by f̂(as) for some a > 0 and then replacing EM(f̂)(s) by EM(f̂)(bs) for some b > 0. With the introduction of these two scale parameters, we see that c(−s; α) can be viewed as an application of the exponential-mixture operator, so that it too is the Laplace transform of a bona fide pdf. Next, the product operation in (5) and (6) is known to correspond to convolution, so that all generating functions correspond directly to mgf’s of probability density functions.

Finally, the new relations in (5) and (6) generalize previous ones in our earlier papers. First, when a = b = 1, equation (5) is equivalent to the equivalence of the two representations for the RBM second moment pdf h_{2} in (43) above. When α = 1, the relation in (6), appropriately adjusted for scale, reduces to a special relation among distributions that are Beta mixtures of exponential distributions, as defined in [7]. In the language of [7],

v̂_{e}(1/2, 1/2; s) = v̂(3/2, 1/2; s) = v̂(1/2, 1/2; s) · v̂(1/2, 3/2; s)  (46)

where

v(p, q; t) ≡ ∫_{0}^{1} y^{−1}e^{−ty}b(p, q; y) dy and b(p, q; y) ≡ \frac{Γ(p + q)}{Γ(p)Γ(q)}y^{p−1}(1 − y)^{q−1}  (47)

and the subscript e again corresponds to the stationary-excess operator in (44) above. The first equality in (46) follows from (1.14) in Theorem 1.3 in [7]. By Table 3 on p. 536 of [7], the second relation in (46) then reduces to

γ̂_{e}(s) = γ̂(s) · ĥ_{1}(s),  (48)

where

γ(t) ≡ γ(1/2; t) ≡ \frac{e^{−t}}{\sqrt{πt}} and γ̂(s) ≡ γ̂(1/2; s) = \frac{1}{\sqrt{1 + s}}.  (49)

The second relation in (46) and the equivalent representation in (48) can be verified by direct calculation from the explicit expressions above and in Table 3 of [7].

And all of this has a corresponding story in the world of integer sequences. In particular, the associated integer sequences are: for γ(1/2; t) in (48) and (49): C(2n, n) ≡ (1, 2, 6, 20, 70, … (\underline{A000984}), for h_{1}: C_{n} ≡ (1, 1, 2, 5, 14, …) in (2) (\underline{A000108}); and for γ_{e} in (48): C(2n + 1, n) ≡ (1, 3, 10, 35, 126, …) (\underline{A001700}). Our equations (6) and (29) generalize

\underline{A001700} = convolution(\underline{A000984}, \underline{A000108})
\underline{A001700} = 2 · \underline{A000984} − \underline{A000108},

occurring when α = 1. The second formula above is not yet in the formula section for \underline{A001700}.

In summary, our goal here, as in our previous papers [2, 4, 7, 8] is to generalize the relations originally observed in [1] and, at the same time, make connections to integer sequences. We view this paper as uncovering a little bit more about a much bigger story, rather than just generating a few sequences not yet in the OEIS [19].. A major part of that larger story is the development of an operational calculus for probability distributions, which may be implemented via their transforms and moment sequences as well as via the pdf’s and cdf’s.. This short paper is neither the end of that story nor the beginning.

6 Proofs

Proof of Theorem 4. Multiply the recurrence (31) by x^{n} and sum, producing

∑_{n=0}^{∞} V_{n}(α)x^{n} + (α − 1) ∑_{n=0}^{∞} V_{n+1}(α)x^{n} = (2α − 1)α ∑_{n=0}^{∞} V_{n}(1)(αx)^{n}.

Apply that to get a relation for the generating functions, namely,

v(x; α) + \frac{(α − 1)(v(x; α) − 1)}{x} = \frac{(2α − 1)(1 − \sqrt{1 − 4αx})}{2x\sqrt{1 − 4αx}},

which yields

v(x; α) = \frac{2α − 1 − \sqrt{1 − 4αx}}{2(x + α − 1)\sqrt{1 − 4αx}},

which is equivalent to (29).

Proof of Theorem 5. Observe that

2αv(x; α) − (2α − 1)\frac{d}{dx}c(x; α) = \frac{(2α)^{2}}{\sqrt{1 − 4αx}(2α − 1 + \sqrt{1 − 4αx})}

−\frac{(2α − 1)(2α)^{2}}{\sqrt{1 − 4αx}(2α − 1 + \sqrt{1 − 4αx})^{2}}

= c(x; α)^{2} (\frac{2α − 1 + \sqrt{1 − 4αx}}{\sqrt{1 − 4αx}} − \frac{2α − 1}{\sqrt{1 − 4αx}})
= c(x; α)^{2}.

Proof of Theorem 7. As a consequence of Theorem 4,

w(y; α) = \frac{2αϕ(y; α) − β(y; α)}{2α − 1},

where ϕ(y; α) is the mixing density of c(2αx; 1/2) and β(y; α) is the mixing density of c(x; α) given in (24). From (28), c(2αx; 1/2) = 1/\sqrt{1 − 4αx}. Therefore, ϕ(y; α) = 1/π\sqrt{y(4α − y)}. Hence, we have

w(y; α) = \frac{1}{2α − 1} (\frac{2α}{π\sqrt{y(4α − y)}} − \frac{\sqrt{4α − y}}{2π\sqrt{y}(1 + (α − 1)y)})

= (\frac{1}{2π(2α − 1)}) (\begin{matrix}√ & \overline{y} \\ √ & \overline{4α − y} \end{matrix} ) (\frac{4α}{y} − \frac{4α − y}{y(1 + (α − 1)y)}) ,

which gives the desired result (37).

Proof of Theorem 8. Let Q be the continued fraction

Q ≡ \frac{(αx)^{2}}{1 − 2αx−} \frac{(αx)^{2}}{1 − 2αx−} \frac{(αx)^{2}}{1 − 2αx−} ⋯

Then Theorem 8 is equivalent to

v(x; α) = \frac{1}{1 − (2α + 1)x − (2α − 1)Q/α}.  (50)

Formula (50) is proved by showing that

(i) Q = αx(c(αx) − 1) and (ii) v(x; α) = \frac{1}{(1 − 2x − (2α − 1)xc(αx))}.  (51)

Proof of (i) in (51): From

c(αx) = \frac{1}{1−} \frac{αx}{1−} \frac{αx}{1−} ⋯

we have the even part as

c(αx) = \frac{1}{1 − αx−} \frac{(αx)^{2}}{1 − 2αx−} \frac{(αx)^{2}}{1 − 2αx−} ⋯
= \frac{1}{1 − αx − Q}.

Hence, using (7) via 1/c(x) = 1 − xc(x), we obtain

Q = 1 − αx − \frac{1}{c(αx)} = αx(c(αx) − 1).

Proof of (ii) in (51): From (6), v(x; α) = c(2x; 1/2)c(x; α) and from (3), (4) and (8), we find that

v(x; α) = (\frac{1}{1 − 2αxc(αx)}) (\frac{1}{1 − xc(αx)}) .

Then after some algebra, exploiting (7) via xc(x)^{2} = c(x) − 1, we get the desired result.

7 Acknowledgment

The second author was supported by NSF Grant CMMI 0948190.

References

[1] J. Abate and W. Whitt, Transient behavior of regulated Brownian motion, Adv. Appl. Prob. 19 (1987), 560–598.

[2] J. Abate and W. Whitt, Transient behavior of the M/G/1 workload process. Operations Research 42 (1994) 750–764.

[3] J. Abate and W. Whitt, Limits and approximations for the busy-period distribution in single-server queues, Prob. Engr. Inform. Sci. 9 (1995), 581–602.

[4] J. Abate and W. Whitt, An operational calculus for probability distributions via Laplace transforms, Adv. Appl. Prob. 28 (1996), 75–113.

[5] J. Abate and W. Whitt, Computing Laplace transforms for numerical inversion via continued fractions, INFORMS J. Computing 11 (1999), 394–405.

[6] J. Abate and W. Whitt, Explicit M/G/1 waiting-time distributions for a class of longtail service-time distributions, Oper. Res. Letters 25 (1999), 25–31.

[7] J. Abate and W. Whitt, Modeling service-time distributions with non-exponential tails: Beta mixtures of exponentials. Stochastic Models 15 (1999), 517–546.

[8] J. Abate and W. Whitt, Integer sequences from queueing theory, J. Integer Sequences 13 (2010), Article 10.5.5.

[9] M. Abramowitz and I. Stegun, Handbook of Mathematical Functions, Dover, New York.

[10] P. Barry, On integer-sequence-based constructions of generalized Pascal triangles. J. Integer Sequences 9 (2006), Article 06.2.4.

[11] P. Barry, A Study of Integer Sequences, Riordan Arrays, Pascal-like Arrays and Hankel Transforms, Ph. D. dissertation, Department of Mathematics, University College Cork, Ireland, 2009.

[12] D. R. Cox and H. D. Miller, The Theory of Stochastic Processes, Methuen, London, 1965.

[13] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1994.

[14] J. M. Harrison, Brownian Motion and Stochastic Flow Systems, Wiley, New York, 1985.

[15] W. Lang, Solution to Problem 10850. Amer. Math. Monthly 109 (2002), 82–83.

[16] K. A. Penson and J. M. Sixdeniers, Integral representations of Catalan and related numbers. J. Integer Sequences 4 (2001), Article 01.2.5.

[17] J. Riordan, Combinatorial Identities, Wiley, New York, 1968.

[18] V. Seshadri, The Inverse Gaussian Distribution, Oxford, New York, 1993.

[19] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2010.

[20] H. S. Wall, Analytic Theory of Continued Fractions, Van Nostrand, New York, 1948.

2000 Mathematics Subject Classification: Primary 11B25; Secondary 60J65, 60E05. Keywords: Catalan numbers, generalized Catalan numbers, inverse Gaussian probability distributions, exponential mixtures, exponential mixtures of inverse Gaussian distributions, Brownian motion, generalized beta distribution, equilibrium time to emptiness, moments.

(Concerned with sequences \underline{A000108}, \underline{A000984}, \underline{A001700}, \underline{A006633}, \underline{A009766}, \underline{A033184}, \underline{A064062}, \underline{A064063}, \underline{A064087}, \underline{A064088}, \underline{A064089}, \underline{A064090}, \underline{A064091}, \underline{A064092}, \underline{A064093}, \underline{A064340}, \underline{A064341}, \underline{A064342}, \underline{A064343}, \underline{A064344}, \underline{A064345}, \underline{A064346}, \underline{A064347}, \underline{A068765}, \underline{A110520}, \underline{A115197}, \underline{A116867}, \underline{A116873}, \underline{A116874}, \underline{A116875}, \underline{A116876}, \underline{A116877}, \underline{A116878}, \underline{A119259}, \underline{A130564}, \underline{A158498}, and \underline{A178792}.)

Received August 6 2010; revised version received December 5 2010; February 8 2011. Published in Journal of Integer Sequences, February 20 2011.

Return to Journal of Integer Sequences home page.