ON THE DISTRIBUTION OF THE SUM OF n NON-IDENTICALLY DISTRIBUTED UNIFORM RANDOM VARIABLES

David M. Bradley and Ramesh C. Gupta Department of Mathematics and Statistics, University of Maine, Orono, ME 04469-5752, U.S.A.

         e-mail: dbradley@e-math.ams.org, rcgupta@maine.maine.edu

Key words and phrases: Uniform distribution, probability density, convolution, Fourier transform, sine integrals.

Abstract. The distribution of the sum of independent identically distributed uniform random variables is well-known. However, it is sometimes necessary to analyze data which have been drawn from different uniform distributions. By inverting the characteristic function, we derive explicit formulæ for the distribution of the sum of n non-identically distributed uniform random variables in both the continuous and the discrete case. The results, though involved, have a certain elegance. As examples, we derive from our general formulæ some special cases which have appeared in the literature.

1. Introduction

The classical uniform distribution is perhaps the most versatile statistical model: applications abound in nonparametric statistics and Bayes procedures. Chu (1957) and Leone (1961) utilized uniform distributions in connection with sample quasi-ranges. Naus (1966) applied uniform distribution in a power comparison of tests of random clustering. For additional applications and examples, see Johnson et al (1995).

Here, we are concerned with the distribution of the sum of n independent non-identically distributed uniform random variables. It is well-known that the probability density function of such a sum, in which the summands are uniformly distributed in a common interval [−a, a], can be obtained via standard convolution formulæ: see Feller (1966, p.

27) or Renyi (1970, pp. 196–197), for example. However, it is sometimes necessary to analyze data which have been drawn from non-identical uniform distributions. For example, measurements accurate to the nearest foot may be combined with measurements accurate to the nearest inch. In such cases, the distribution of the sum is more complicated. Tach (1958) gives tables to five decimal places of the cumulative distribution of the sum for n = 2, 3 and 4 for some special cases.

The first general result in this direction seems to have been made by Olds (1952), who derived the distribution of the sum ∑_{j=1}^{n} X_{j}, in which each X_{j} is uniformly distributed in an interval of the form [0, a_{j}) with a_{j} > 0. The proof is by induction, and in that respect is somewhat unsatisfactory, since in general inductive proofs require knowing beforehand the formula to be proved. Subsequently, Roach (1963) deduced what is essentially Olds’ formula using n-dimensional geometry. Later Mitra (1971), apparently unaware of these previous results, derived the distribution of the sum in which each random variable is uniformly distributed in an interval of the form [−ω_{j}, ω_{j}] using Nörlund’s (1924) difference calculus.

Here, we derive an explicit formula for the slightly more general situation of the distribution of the sum ∑_{j=1}^{n} X_{j}, in which each X_{j} is uniformly distributed in an interval of the form [c_{j} − a_{j}, c_{j} + a_{j}] with a_{j} > 0 and c_{j} an arbitrary real number. Of course, each of the aforementioned results can be obtained from ours by specializing the parameters c_{j} and a_{j} accordingly.

Our approach is via Fourier theory and is quite straightforward; specifically we invert the characteristic function. As a result, our formula differs somewhat in form from the special cases alluded to previously. However, the inversion technique is quite flexible, and readily lends itself to the study of other types of distributions, such as the discrete case, which seems not to have been discussed in the literature. Thus, in a similar fashion, we derive the distribution of the sum of n random variables with point mass at the integers in intervals of the form [−m_{j}, m_{j}], in which each m_{j} is a positive integer. The formula in the discrete case is somewhat more complicated than the corresponding formula in the continuous case; nevertheless, they are clearly closely related, and there is a certain charm and elegance to both. Of course, the same results may be obtained using the standard transformation methods.

2. The Continuous Case

Fix a positive integer n, and let a⃗ = (a_{1}, a_{2}, …, a_{n}) and c⃗ = (c_{1}, c_{2}, …, c_{n}) be vectors of real numbers with each a_{j} > 0. For each j = 1, 2, …, n, we consider a random variable X_{j} uniformly distributed on the closed interval [c_{j} −a_{j}, c_{j} +a_{j}]. The step function χ_{j} : R → R defined for real x by

2a_{j} χ_{j}(x) = \{ \begin{matrix}1 & if |x − c_{j}| < a_{j}, \\ \frac{1}{2} & if |x − c_{j}| = a_{j}, \\ 0 & if |x − c_{j}| > a_{j} \end{matrix} (2.1)

represents the density of the random variable X_{j} for each j = 1, 2, …, n. (When employing techniques from Fourier theory, it is convenient to define the densities at jump discontinuities so that the equation χ_{j}(x+) + χ_{j}(x−) = 2χ_{j}(x) is satisfied for all real x.) The corresponding characteristic function (Fourier transform) is given by

χ̂_{j}(t) := \frac{1}{2a_{j}} ∫_{c_{j}−a_{j}}^{c_{j}+a_{j}} e^{itx} dx = e^{ic_{j}t} sinc(a_{j}t), t ∈ R,

where sinc(x) := x^{−1} sin x if x ≠ 0, and sinc(0) := 1. For real x, the density of the sum ∑_{j=1}^{n} X_{j} is given by the n-fold convolution f_{n}(x) := (χ_{1} ∗ χ_{2} ∗ ⋯ ∗ χ_{n})(x). Thus,

f_{n}(x) = ∫_{−∞}^{∞} χ_{1}(x − y_{2}) ∫_{−∞}^{∞} χ_{2}(y_{2} − y_{3}) ⋯ ∫_{−∞}^{∞} χ_{n−1}(y_{n−1} − y_{n})χ_{n}(y_{n}) dy_{2} … dy_{n}.

In particular, if each of the n intervals is centered at 0, and we write x_{1} = x − y_{2}, x_{n} = y_{n} and x_{j} = y_{j} − y_{j+1} for 1 < j < n, then the conditions on the variables x_{1}, x_{2}, …, x_{n} are that each |x_{j}| < a_{j} and ∑_{j=1}^{n} x_{j} = x. Thus, f_{n}(x) is simply the volume (in the sense of Lebesgue measure) of the (n − 1)-dimensional region

{(x_{1}, x_{2}, …, x_{n−1}) ∈ R^{n−1} : |x − ∑_{j=1}^{n−1} x_{j}| < a_{n} and |x_{j}| < a_{j} for 1 ≤ j < n}

divided by the volume ∏_{j=1}^{n} 2a_{j} of the n-dimensional hyperbox

{(x_{1}, x_{2}, …, x_{n}) ∈ R^{n} : |x_{j}| < a_{j} for j = 1, 2, …, n}. (2.2)

Despite the utility of these representations, it is desirable to have an explicit formula for f_{n}. In this vein, we have the following

Theorem 1. The density of the sum of n independent random variables, uniformly distributed in the intervals [c_{j} − a_{j}, c_{j} + a_{j}] for j = 1, 2, …, n, is given by

\begin{aligned}f_{n}(x) & = [ ∑_{ε⃗∈\{−1,1\}^{n}} (x + ∑_{j=1}^{n}(ε_{j}a_{j} − c_{j}))^{n−1} \\ & × sign(x + ∑_{j=1}^{n}(ε_{j}a_{j} − c_{j})) ∏_{j=1}^{n} ε_{j}]/[(n − 1)!2^{n+1} ∏_{j=1}^{n} a_{j}], \end{aligned} (2.3)

in which the sum is over all 2^{n} vectors of signs

ε⃗ = (ε_{1}, ε_{2}, …, ε_{n}) ∈ {−1, 1}^{n} i.e. each ε_{j} = ±1

and

sign(y) := \{ \begin{matrix}1 & if y > 0, \\ 0 & if y = 0, \\ −1 & if y < 0. \end{matrix}

Proof. Since the random variables are assumed to be independent, the characteristic function of the distribution of the sum is the product of the characteristic functions of their distributions:

f̂_{n}(t) = ∏_{j=1}^{n} χ̂_{j}(t) = ∏_{j=1}^{n} e^{itc_{j}} sinc(a_{j}t). (2.4)

Mitra (1971, p. 195) remarks that “It is difficult to obtain an inverse Fourier transform of this product in a neat form.” Indeed, his approach is to expand the product of sincs into a power series using generalized Bernoulli polynomials. However, we shall see that the inverse Fourier transform of (2.4) has an elegant representation involving a sum over the vertices of the hyperbox (2.2).

Since for all real x, f_{n}(x) = \frac{1}{2}f_{n}(x+) + \frac{1}{2}f_{n}(x−) by continuity of f_{n} for n > 1, and by definition of χ_{1} when n = 1, Fourier inversion gives

f_{n}(x) = \frac{1}{2π} ∫_{−∞}^{∞} e^{−itx}f̂_{n}(t) dt = \frac{1}{2π} ∫_{−∞}^{∞} e^{−ity} ∏_{j=1}^{n} sinc(a_{j}t) dt,

where y := x − ∑_{j=1}^{n} c_{j}. Since sinc is an even function, making the change of variable t ↦ −t yields

f_{n}(x) = \frac{1}{2π} ∫_{−∞}^{∞} e^{ity} ∏_{j=1}^{n} sinc(a_{j}t) dt. (2.5)

It remains only to evaluate the integral (2.5). Related integrals are studied in Borwein and Borwein (2001) using a version of the Parseval/Plancherel formula, and by expanding the product of sincs into a sum of cosines. Our approach is somewhat more direct. We

SUM OF NON-IDENTICAL UNIFORM RANDOM VARIABLES 7

first express the sinc functions using complex exponentials, so that

f_{n}(x) = \frac{1}{2π} (\frac{1}{2i})^{n} ( ∏_{j=1}^{n} a_{j}^{−1}) ∫_{−∞}^{∞} t^{−n}e^{ity} ∏_{j=1}^{n} (e^{ita_{j}} − e^{−ita_{j}}) dt. (2.6)

For each of the 2^{n} vectors of signs ε⃗ = (ε_{1}, ε_{2}, …, ε_{n}) ∈ {−1, 1}^{n}, let

ρ_{ε} := ∏_{j=1}^{n} ε_{j}, and ε⃗ · a⃗ = ∑_{j=1}^{n} ε_{j}a_{j}.

By carefully expanding the product of exponentials in (2.6), we find that

∏_{j=1}^{n} (e^{ita_{j}} − e^{−ita_{j}}) = ∑_{ε⃗∈{−1,1}^{n}} ρ_{ε} exp(itε⃗ · a⃗). (2.7)

It follows that

f_{n}(x) = \frac{1}{2π} (\frac{1}{2i})^{n} ( ∏_{j=1}^{n} a_{j}^{−1})^{n} ∑_{ε⃗∈\{−1,1\}^{n}} ρ_{ε} P.V. ∫_{−∞}^{∞} t^{−n} exp(it(y + ε⃗ · a⃗)) dt. (2.8)

Although each of the individual integrals in (2.8) is divergent, the singularities must cancel because (2.6) converges. Therefore, the required finite integral (2.6) is equal to its principal value, and hence by linearity is given by (2.8).

In view of the fact that (2.7) is entire with a zero of order n at t = 0, we may integrate (2.8) by parts n − 1 times and thereby obtain

\begin{aligned}f_{n}(x) & = \frac{1}{2π} (\frac{1}{2i})^{n} ( ∏_{j=1}^{n} a_{j}^{−1})\frac{i^{n−1}}{(n − 1)!} ∑_{ε⃗∈\{−1,1\}^{n}} ρ_{ε}(y + ε⃗ · a⃗)^{n−1} \\ & × P.V. ∫_{−∞}^{∞} t^{−1} exp(it(y + ε⃗ · a⃗)) dt. \end{aligned} (2.9)

But for any real number b, we have

P.V. ∫_{−∞}^{∞} t^{−1} exp(itb) dt

= lim_{ε→0+} {∫_{ε}^{∞} t^{−1} exp(itb) dt + ∫_{−∞}^{−ε} t^{−1} exp(itb) dt}

= lim_{ε→0+} {∫_{ε}^{∞} t^{−1} exp(itb) dt − ∫_{ε}^{∞} t^{−1} exp(−itb) dt}

= 2i ∫_{0}^{∞} t^{−1} sin(tb) dt

= iπ sign(b).

Applying this latter result to (2.9) yields (2.3) and completes the proof of Theorem 1.

In some applications, it may be easier to work with powers of expressions involving the maximum function y_{+} := max(y, 0) as opposed to the sign functions in (2.3). To this end, we make the following

Definition 1. Let τ : R → R be given by

τ(x) = \{ \begin{matrix}1, & if x > 0, \\ \frac{1}{2}, & if x = 0, \\ 0, & if x < 0, \end{matrix} (2.10)

and for y real and n a positive integer, let y_{+}^{n−1} := y^{n−1}τ(y). Note that y_{+}^{0} = τ(y) and y_{+}^{n} = (max(y, 0))^{n} for n > 0.

Then we have the following corollary to Theorem 1.

Corollary 1. Let f_{n} be as in Theorem 1. Then

f^{n}(x) = [ ∑_{ε⃗∈{−1,1}^{n}} (x + ∑_{j=1}^{n}(ε^{j}a^{j} − c^{j}))_{+}^{n−1} ∏_{j=1}^{n} ε^{j}]/[(n − 1)! 2^{n} ∏_{j=1}^{n} a^{j}]. (2.11)

Proof. Note that sign(x) = 2τ(x) − 1 holds for all real x. Hence, substituting the τ function for the sign function in (2.3), we see that it suffices to prove the identity

∑_{ε⃗∈{−1,1}^{n}} (x + ∑_{j=1}^{n}(ε_{j}a_{j} − c_{j}))^{n−1} ∏_{j=1}^{n} ε_{j} = 0. (2.12)

Since e^{a_{j}t} − e^{−a_{j}t} = 2a_{j}t + O(t^{2}) as t → 0, (2.12) follows easily on comparing coefficients of t^{n−1} in

∑_{ε⃗∈{−1,1}^{n}} exp {(x + ∑_{j=1}^{n} ε_{j}a_{j} − c_{j})t} ∏_{j=1}^{n} ε_{j} = e^{xt} ∏_{j=1}^{n} e^{−c_{j}t} (e^{a_{j}t} − e^{−a_{j}t}) .

Alternatively, note that if x ≥ ∑_{j=1}^{n}(c_{j}+a_{j}), then f_{n}(x) = 0 by definition: since each X_{j} is u[c_{j} −a_{j}, c_{j} +a_{j}], the sum ∑_{j=1}^{n} X_{j} must fall within the interval [∑_{j=1}^{n}(c_{j} −a_{j}), ∑_{j=1}^{n}(c_{j} + a_{j})]. But, if x ≥ ∑_{j=1}^{n}(c_{j} + a_{j}), then we can drop the subscripted “+” from (2.11) since x + ∑_{j=1}^{n}(ε_{j}a_{j} − c_{j}) ≥ 0 for each ε⃗ ∈ {−1, 1}^{n}. It follows that (2.12) holds for all x ≥ ∑_{j=1}^{n}(c_{j} + a_{j}). Since the left hand side of (2.12) is a polynomial in x which vanishes for all sufficiently large values of x, it must in fact vanish for all real x by the identity theorem.

Example 1. When n = 1, formulæ (2.3) and (2.11) give the central difference representations

χ_{1}(x) = \frac{sign(x − c_{1} + a_{1}) − sign(x − c_{1} − a_{1})}{4a_{1}} = \frac{τ(x − c_{1} + a_{1}) − τ(x − c_{1} − a_{1})}{2a_{1}}

10 SUM OF NON-IDENTICAL UNIFORM RANDOM VARIABLES

respectively. Both are equivalent to the definition (2.1) with j = 1. Example 2. When n = 2, we know that

f_{2}(x) = (χ_{1} ∗ χ_{2})(x) = ∫_{−∞}^{∞} χ_{1}(x − y)χ_{2}(y) dy.

If c_{1} = c_{2} = 0, the convolution reduces to

f_{2}(x) = \frac{1}{4a_{1}a_{2}} ∫_{max(x−a_{1}, −a_{2})}^{min(x+a_{1}, a_{2})} dy = \frac{min(x + a_{1}, a_{2}) − max(x − a_{1}, −a_{2})}{4a_{1}a_{2}},

so that, in particular,

(2.13) f_{2}(0) = \frac{1}{2π} ∫_{−∞}^{∞} \frac{sin(a_{1}t)}{a_{1}t} · \frac{sin(a_{2}t)}{a_{2}t} dt = \frac{min(a_{1}, a_{2})}{2a_{1}a_{2}}.

On the other hand, in light of the fact that y sign(y) = |y| for y real, formula (2.3) gives

f_{2}(0) = \frac{|a_{1} + a_{2}| − |a_{1} − a_{2}| − | − a_{1} + a_{2}| + | − a_{1} − a_{2}|}{8a_{1}a_{2}}

= \frac{2(a_{1} + a_{2}) − 2|a_{1} − a_{2}|}{8a_{1}a_{2}}

= \frac{min(a_{1}, a_{2})}{2a_{1}a_{2}},

in agreement with (2.13). Alternatively, since yτ(y) = y_{+} = max(y, 0), formula (2.3) gives

f_{2}(0) = \frac{max(a_{1} + a_{2}, 0) − max(a_{1} − a_{2}, 0) − max(−a_{1} + a_{2}, 0) + max(−a_{1} − a_{2}, 0)}{4a_{1}a_{2}}

= \frac{a_{1} + a_{2} − max(a_{1} − a_{2}, 0) − max(a_{2} − a_{1}, 0)}{4a_{1}a_{2}}

= \frac{min(a_{1}, a_{2})}{2a_{1}a_{2}}.

Example 3. If the random variables comprising the sum are uniformly distributed in a common interval centered at 0—say [−a, a] with a > 0—then formula (2.11) gives

f_{n}(x) = \frac{1}{(n − 1)! (2a)^{n}} ∑_{ε⃗∈\{−1,1\}^{n}} (x + a ∑_{j=1}^{n} ε_{j})_{+}^{n−1} ∏_{j=1}^{n} ε_{j}.

If k of ε_{1}, ε_{2}, …, ε_{n} are negative and the remaining n − k are positive, then summing over k yields

f_{n}(x) = \frac{1}{(n − 1)! (2a)^{n}} ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} (x + (n − 2k)a)_{+}^{n−1} ,

in agreement with Feller (1966).

Example 4. If for each j = 1, 2, …, n we set c_{j} = a_{j} and then replace a_{j} by a_{j}/2, then X_{j} will be uniformly distributed in [0, a_{j}] and will have density χ_{j} now given by

(2.14) a_{j} χ_{j}(x) := \{ \begin{matrix}1, & if 0 < x < a_{j}, \\ \frac{1}{2}, & if x = a_{j} or if x = 0, \\ 0, & if x > a_{j} or if x < 0. \end{matrix}

Formula (2.11) of Corollary 1 now gives

\begin{aligned}f_{n}(x) & = [ ∑_{ε⃗∈\{−1,1\}^{n}} (x − ∑_{j=1}^{n} (\frac{1 − ε_{j}}{2} )a_{j})_{+}^{n−1} ∏_{j=1}^{n} ε_{j}]/[(n − 1)! ∏_{j=1}^{n} a_{j}] \\ & = [ ∑_{s⃗∈\{0,1\}^{n}}(−1)^{Σs⃗} (x − s⃗ · a⃗)_{+}^{n−1} ]/[(n − 1)! ∏_{j=1}^{n} a_{j}], \end{aligned}

where the sum is now over all 2^{n} vectors s⃗ = (s_{1}, s_{2}, …, s_{n}) in which each component takes the value 0 or 1, Σs⃗ denotes the sum of the components s_{1} + s_{2} + ⋯ + s_{n} and s⃗ · a⃗ denotes the dot product s_{1}a_{1} + s_{2}a_{2} + ⋯ + s_{n}a_{n}. If we now break up the sum according to the number of non-zero components in the vector s⃗, we find that

\begin{aligned}f_{n}(x) & = [x_{+}^{n−1} − ∑_{1≤j_{1}≤n} (x − a_{j_{1}})_{+}^{n−1} + ∑_{1≤j_{1}<j_{2}≤n} (x − a_{j_{1}} − a_{j_{2}})_{+}^{n−1} − + ⋯ \\ & + (−1)^{n} ∑_{1≤j_{1}<j_{2}<···<j_{n}≤n} (x − ∑_{k=1}^{n} a_{j_{k}})_{+}^{n−1} ]/[(n − 1)! ∏_{j=1}^{n} a_{j}], \end{aligned}

which is equivalent to the formula of Olds (1952, p. 282 (1)) when n > 1. When n = 1, the two formulæ differ at x = 0 and at x = a_{1} because Olds uses the density which is 1/a_{1} for 0 ≤ x < a_{1} and 0 otherwise, in contrast to our more symmetrical density (2.14).

3. The Discrete Case

Here, we fix n positive integers m_{1}, m_{2}, …, m_{n}. For each j = 1, 2, …, n, we now consider a random variable X_{j} uniformly distributed on the set of (2m_{j} + 1) integers contained in the closed interval [−m_{j}, m_{j}], i.e. the set {−m_{j}, 1−m_{j}, …, m_{j} −1, m_{j}}. The mass function of X_{j} is the rational-valued function of an integer variable given by

(2m_{j} + 1)χ_{j}(p) := \{ \begin{matrix}1 & if |p| ≤ m_{j}, \\ 0 & if |p| > m_{j}. \end{matrix} (3.1)

We seek a formula analogous to (2.3) for the probability mass function of the sum ∑_{j=1}^{n} X_{j}, namely the n-fold convolution

g_{n}(p) := (χ_{1} ∗ χ_{2} ∗ ⋯ ∗ χ_{n})(p) = ∑_{k_{1}+k_{2}+···+k_{n}=p} ∏_{j=1}^{n} χ_{j}(k_{j}), (3.2)

where the sum is over all integers k_{1}, k_{2}, …, k_{n} such that k_{1} + k_{2} + ⋯ + k_{n} = p. Although (3.2) is a formula of sorts, the various conditions on the summation indices make it inconvenient to apply. For example, when n = 3, let u_{k} = u_{k}(p) := min(m_{2}, p − k + m_{3}) and v_{k} = v_{k}(p) := max(−m_{2}, p − k − m_{3}). Then

g_{3}(p) = ( ∏_{j=1}^{3}(2m_{j} + 1)^{−1}) ∑_{\begin{matrix}|k|≤m_{1} \\ u_{k}<v_{k} \end{matrix}}(u_{k} − v_{k} + 1),

where the sum is over all integers k for which u_{k} < v_{k} and |k| ≤ m_{1}. In general, one needs to consider cases which depend on the size of p in relation to various signed sums of subsets of the parameters m_{1}, m_{2}, …, m_{n}. The number of cases to be delineated increases exponentially with n. Thus, the situation becomes rapidly unwieldy. Fortunately, there is alternative approach provided by Fourier theory. With the convolution g_{n} : Z → Z defined as above, we have

Theorem 2. For all integers p,

\begin{aligned}g_{n}(p) & = \frac{M}{2^{n}} ∑_{ε⃗∈\{−1,1\}^{n}} sign(2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j})( ∏_{j=1}^{n} ε_{j}) \\ & × ∑_{k=0}^{(n−1)/2}(−1)^{k}b_{2k}^{(n)} \frac{(2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j})^{n−2k−1}}{(n − 2k − 1)!} , \end{aligned} (3.3)

where

M := ∏_{j=1}^{n}(2m_{j} + 1)^{−1},

14 SUM OF NON-IDENTICAL UNIFORM RANDOM VARIABLES

and the rational numbers b_{2k}^{(n)} are the coefficients in the Laurent series expansion

(\frac{1}{sin x})^{n} = ∑_{k=0}^{∞} x^{2k−n}b_{2k}^{(n)}. (3.4)

Explicitly,

(3.5) b_{2k}^{(n)} = (−1)^{k}\binom{n + 2k}{n} ∑_{m=0}^{2k} \frac{n}{n + m}\binom{2k}{m}\frac{1}{2^{m}(2k + m)!} ∑_{r=0}^{m}(−1)^{r}\binom{m}{r}(2r − m)^{2k+m}.

Proof. The corresponding characteristic functions for j = 1, 2, …, n are now given by

(2m_{j} + 1)χ̂_{j}(t) = ∑_{|k|≤m_{j}} e^{itk} = \{ \begin{matrix}\frac{sin((m_{j} + 1/2)t)}{sin(t/2)}, & if t ∉ 2πZ, \\ 2m_{j} + 1, & if t ∈ 2πZ, \end{matrix}

which we recognize as the familiar Dirichlet kernel—see eg. Korner (1988, p. 68). Since for t ∉ 2πZ, we have

(χ_{1} ∗ χ_{2} ∗ ⋯ ∗ χ_{n}) (t) = ∏_{j=1}^{n} χ̂_{j}(t) = M ∏_{j=1}^{n} \frac{sin((m_{j} + 1/2)t)}{sin(t/2)},

it follows by orthogonality of the exponential that

g_{n}(p) = \frac{M}{2π} ∫_{0}^{2π} e^{ipt} ∏_{j=1}^{n} \frac{sin((m_{j} + 1/2)t)}{sin(t/2)} dt = \frac{M}{π} ∫_{0}^{π} e^{2ipx} ∏_{j=1}^{n} \frac{sin((2m_{j} + 1)x)}{sin x} dx.

We remark in passing that the factors sin((2m_{j}+1)x)/ sin x in this latter representation are simply the Chebyshev polynomials U_{2m_{j}}(cos x) of the second kind—see eg. Abramowitz and Stegun (1972, p. 766). The partial-fraction expansion

(\frac{1}{sin x})^{n} = ∑_{k=0}^{(n−1)/2} b_{2k}^{(n)} ∑_{r=−∞}^{∞} (\frac{(−1)^{r}}{x + rπ} )^{n−2k}, (3.6)

is a modified version of the formula in Schwatt (1924, pp. 209–210), and yields

g_{n}(p) = ∑_{k=0}^{(n−1)/2} b_{2k}^{(n)} ∑_{r=−∞}^{∞} \frac{M}{π} ∫_{0}^{π} e^{2ipx}(\frac{(−1)^{r}}{x + rπ} )^{n−2k} ∏_{j=1}^{n} sin((2m_{j} + 1)x) dx. (3.7)

When n − 2k > 1, the bilateral series

∑_{r=−∞}^{∞} (\frac{(−1)^{r}}{x + rπ} )^{n−2k}

converges absolutely, and the interchange of summation and integration is easily justified using either Lebesgue’s dominated convergence theorem or Fubini’s theorem with both Lebesgue and counting measure. If n − 2k = 1, absolute convergence can be recovered by recasting the bilateral series in the form

∑_{r=−∞}^{∞} \frac{(−1)^{r}}{x + rπ} = \frac{1}{x} + ∑_{r=1}^{∞}(−1)^{r}(\frac{2x}{x^{2} − r^{2}π} ),

and the justification proceeds as in the previous case.

We shall see that the inner sum of integrals in (3.7) can be expressed as a single integral over the whole real line. To this end, we compute

∑_{r=−∞}^{∞} \frac{1}{π} ∫_{0}^{π} e^{2ipx}(\frac{(−1)^{r}}{x + rπ} )^{n−2k} ∏_{j=1}^{n} sin((2m_{j} + 1)x) dx

= ∑_{r=−∞}^{∞} \frac{(−1)^{(n−2k)r}}{π} ∫_{rπ}^{(r+1)π} t^{2k−n}e^{2ip(t−rπ)} ∏_{j=1}^{n} sin ((2m_{j} + 1)(t − rπ)) dt
= ∑_{r=−∞}^{∞} \frac{(−1)^{(n−2k)r}}{π} ∫_{rπ}^{(r+1)π} t^{2k−n}e^{2ipt} ∏_{j=1}^{n}(−1)^{(2m_{j}+1)r} sin((2m_{j} + 1)t) dt
= \frac{1}{π} ∫_{−∞}^{∞} t^{2k−n}e^{2ipt} ∏_{j=1}^{n} sin((2m_{j} + 1)t) dt.

This latter integral can be evaluated just as we evaluated the integral (2.5). After expanding the product of sines as a sum over the constituent exponentials and integrating by parts n − 2k − 1 times, one finds that

(3.8) \frac{1}{π} ∫_{−∞}^{∞} t^{2k−n}e^{2ipt} ∏_{j=1}^{n} sin((2m_{j} + 1)t) dt

= \frac{(−1)^{k}}{2^{n}(n − 2k − 1)!} ∑_{ε⃗∈\{−1,1\}^{n}} (2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j})^{n−2k−1}

× sign(2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j}) ∏_{j=1}^{n} ε_{j}.

Substituting (3.8) into (3.7) and interchanging the order of summation completes the proof of Theorem 2.

Remark. The equations (3.4), (3.5), (3.6) can also be obtained using Jordan’s (1979, §74, p. 216) general formula for the higher derivatives of a power of a reciprocal function and then applying Mittag-Leffler’s theorem.

As in the continuous case, we can replace the sign function in Theorem 2 with the τ function of Definition 1. Thus we obtain

Corollary 2. Let g_{n}, M, and b_{2k}^{(n)} be as in Theorem 2. Then, for all positive integers n and integer p,

(3.9) g_{n}(p) = \frac{M}{2^{n−1}} ∑_{k=0}^{(n−1)/2} \frac{(−1)^{k}b_{2k}^{(n)}}{(n − 2k − 1)!} ∑_{ε⃗∈\{−1,1\}^{n}} (2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j})_{+}^{n−2k−1} ∏_{j=1}^{n} ε_{j},

SUM OF NON-IDENTICAL UNIFORM RANDOM VARIABLES 17

where y_{+}^{n−2k−1} = y^{n−2k−1}τ(y) as in Definition 1. Proof. Making the substitution sign(y) = 2τ(y) − 1 in Theorem 2 and noting that the coefficient of t^{n−2k−1} in

∑_{ε⃗∈{−1,1}^{n}} exp {(2p + ∑_{j=1}^{n}(2m_{j} + 1)ε_{j})t} = e^{2pt} ∏_{j=1}^{n} (e^{(2m_{j}+1)t} − e^{−(2m_{j}+1)t})

vanishes for 0 ≤ k ≤ (n − 1)/2, we obtain the desired result. Example 5. When n = 1, formulæ (3.3) and (3.9) give the representations

(2m_{1} + 1)χ_{1}(p) = \frac{1}{2}sign(p + m_{1} + \frac{1}{2}) − \frac{1}{2}sign(p − m_{1} − \frac{1}{2})
= τ(p + m_{1} + \frac{1}{2}) − τ(p − m_{1} − \frac{1}{2}),

respectively. Both are equivalent to the definition (3.1) with j = 1. Example 6. When n = 2, we have M := (2m_{1} + 1)^{−1}(2m_{2} + 1)^{−1}, and

g_{2}(p) = χ_{1} ∗ χ_{2}(p) = ∑_{k+j=p} χ_{1}(k)χ_{2}(j).

Since this is simply the coefficient of t^{p} in the product

M ∑_{|k|≤m_{1}} t^{k} ∑_{|j|≤m_{2}} t^{j},

letting u(p) := min(m_{1}, p + m_{2}) and v(p) := max(−m_{1}, p − m_{2}), we have

g_{2}(p) = M × \{ \begin{matrix}u(p) − v(p) + 1 & if u(p) ≥ v(p), \\ 0 & if u(p) < v(p). \end{matrix}

On the other hand formula (3.3) gives the elegant representation

g_{2}(p) = \frac{1}{2}M (|p + m_{1} + m_{2} + 1| − |p + m_{1} − m_{2}| − |p − m_{1} + m_{2}|
+|p − m_{1} − m_{2} − 1|) ,

in which we have used the relation y sign(y) = |y| for y real.

References

Abramowitz, M. and Stegun, I. A. (1972). Handbook of Mathematical Functions, Dover Publications, New York.

Borwein, D. and Borwein, J. M. (2001). Some remarkable properties of sinc and related integrals. The Ramanujan Journal, 5, (1), 73–89.

Chu, J. T. (1957). Some uses of quasi-ranges, Annals of Mathematical Statistics, 28, 173–180.

Feller, W. (1966). An Introduction to Probability Theory and its Applications, Vol. II, John Wiley & Sons, New York.

Johnson, N. L., Kotz, S. and Balakrishnan, N. (1995). Continuous univariate distributions, (2nd ed.) John Wiley, New York.

Jordan, C. (1979). Calculus of Finite Differences, Chelsea Publishing, (3rd ed. reprinted).

SUM OF NON-IDENTICAL UNIFORM RANDOM VARIABLES 19

Körner, T. W. (1988). Fourier Analysis, Cambridge University Press. Leon, F. C. (1961). The use of sample quasi-ranges in setting confidence intervals for the population standard deviation, Journal of the American Statistical Association, 56, 260–272. Mitra, S. K. (1971). On the probability distribution of the sum of uniformly distributed random variables, SIAM J. Appl. Math., 20, (2), 195–198. Naus, I. (1966). A power comparison of two tests of non-random clustering, Technometrics, 8, 493–517. Nörlund, N. E. (1924). Vorlesungen über Differenzenrechnung, Springer, Berlin. Olds, E. G. (1952). A note on the convolution of uniform distributions, Annals of Mathematical Statistics, 23, 282–285. Rényi, A. (1970). Probability Theory, North-Holland Publishing, Amsterdam. Roach, S. A. (1963). The frequency distribution of the sample mean where each member of the sample is drawn from a different rectangular distribution, Biometrika, 50, 508–513.

Schwatt, I. J. (1924). An Introduction to the Operations with Series, University of Pennsylvania Press, Philadelphia.

Tach, L. T. (1958). Tables for cumulative distribution function of a sum of independent random variables, Convair Aeronautics Report M, ZU-7-119-TN, San Diego.