Abstract
Abstract. Under the assumption that the distribution of a nonnegative random variable X admits a bounded coupling with its size biased version, we prove simple and strong concentration bounds.
Introduction
For any random variable X, we write F (x) := P(X ≤ x), G(x) := P(X ≥ x).
Introduction
When X has finite mean a, concentration inequalities refer to estimates on the upper tail probability G(x) = P(X ≥ x) for x ≥ a and on the lower tail probability F (x) = P(X ≤ x) for x ≤ a. The remarkably effective idea of using bounded size bias couplings to prove concentration inequalities comes from Ghosh and Goldstein [8] ; their proof is inspired by the x → e x is convex argument used to prove the Azuma-Hoeffding concentration bounds. Here we prove stronger bounds, under weaker hypotheses, and with a simpler proof, inspired by the easy proof, from [12] , that Dickman's function ρ satisfies ρ(u) ≤ 1/Γ(u + 1), for u ≥ 0. See [7, 8, 1, 4] for many examples of the application of concentration bounds derived from size bias couplings, for situations involving dependence.
Introduction
We recall the notation, definition, and most basic fact about size bias: given a nonnegative random variable X with 0 < E X < ∞, we say that the distribution of Y is the size biased distribution of X, written Y = d X * , if the Radon-Nikodym derivative of the distribution of Y , with respect to the distribution of X, is given by P(Y ∈ dx)/P(X ∈ dx) = x/E X. If Y = d X * , then for all bounded measurable g, E g(Y ) = E (Xg(X))/E X. This last fact will be applied in the proof of Lemma 2.1 with g(z) = 1(z ≥ x) and with g(z) = 1(z ≤ x). See [2] , or [3, pp 78-80] . The main hypothesis of Lemma 2.1 below can be said as "The distribution of X admits a c-bounded coupling with its size biased version," or less formally, "X admits a c-bounded size bias coupling."
Product bounds
Lemma 2.1. Suppose that a nonnegative random variable X has E X = a ∈ (0, ∞), that c < ∞, and that for Y = d X * , there exists a coupling in which Y ≤ X + c.
Product bounds
Then
Product bounds
and ∀x, F (x) ≤ x + c a F (x + c).
Product bounds
Proof. To prove the upper bound on G(x), note that (1) implies that the event Y ≥ x is a subset of the event X ≥ x − c. Hence for x > 0, xG(x) = x E 1(X ≥ x) ≤ E (X1(X ≥ x)) = a P(Y ≥ x) ≤ a G(x − c).
Product bounds
When x > 0 we can divide by x to get (2) .
Product bounds
To prove the upper bound on F (x), note that (1) implies that the event Y ≤ x is a superset of the event X ≤ x − c. Hence
Product bounds
This does not require that x be positive; for x < 0 it is the trivial inequality, that 0 ≥ 0. Replacing x by x + c and dividing by a > 0 yields (3) .
Product bounds
Given x > 0, the obvious strategy for obtaining good bounds is to iterate (2) or (3) for as long as the new value of x, say x ′ = x ± ic, still gives a favorable ratio, a/x ′ in (2), or (x ′ + c)/a in (3), and using G(t) ≤ 1 or F (t) ≤ 1 as needed, to finish off.
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
so that k is a nonnegative integer, possibly zero. Then
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
and
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
Proof. Simply apply the strategy described in the paragraph preceding the statement of this theorem. 
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
Proof. Since X ≥ 0, trivially M(β) ≤ 1 if β ≤ 0, so assume β > 0. For motivation: as x increases by c, e βx increases by a factor of e βc , while the upper bound u(x, a, c) on G(x) decreases by a factor of a/x; hence for x > x 0 := 2ae βc , the product e βx u(x, a, c) decreases by a factor of at least 2.
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
Writing
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
the series on the right side is bounded by a geometric series with ratio 1/2, and the net result will be M(β) ≤ exp(βx 0 ) + 2 exp(β(x 0 + c)).
Theorem 2.2. Under the hypotheses of Lemma 2.1, given x let
Remark 2.4. Note the difference between the indexing in the products (5, 6): u(x, a, c) includes the factor indexed by i = 0, while ℓ(x, a, c) excludes the factor indexed by i = 0. In case x ∈ (a, a + c), which is equivalent to a < x and k = 0, the bound in (5) has one factor, and simplifies to G(x) ≤ u(x, a, c) = a/x < 1. In case x ∈ (a − c, a), which is equivalent to x < a and k = 0, the bound in (6) has no factors, and simplifies to the trivial observation F (x) ≤ ℓ(x, a, c) = 1.
2.1.
Product bound combined with one-sided Chebyshev. The recursive nature of Lemma 2.1 allows the possibility of combining it with other information about F (x) or G(x). Here we pursue one possibility. For a random variable X with mean a and variance σ 2 , the one-sided Chebybshev inequality states that, for all x ≤ a,
2.1.
Thus, under the hypotheses of Lemma 2.1, for all x ≤ a,
2.1.
We want to improve on (6) by using one-sided Chebyshev in combination with iteration of (3). More precisely, given x < a and any non-negative integer j such that x + jc ≤ a we can iterate (3) from x to x + jc and then use the one-sided Chebyshev inequality at x + jc to obtain 
2.1.
In particular the upper bounds in (5) and (6), for all a, c > 0 and x ≥ 0, satisfy
2.1.
Opportunities to use (10) are presented by (14) and (15).
Gamma bounds
In this section we restrict to the case c = 1. Results for general c > 0 can be recovered using equation (10) , see Remark 2.5. For c = 1, making use of zΓ(z) = Γ(z +1), the conclusions (5) and (6) in Theorem 2.2 can be rewritten as: for x ≥ a and k = ⌊x − a⌋,
Gamma bounds
and for 0 ≤ x ≤ a and k = ⌊a − x⌋,
Gamma bounds
These upper and lower tail bounds might be viewed as too complicated; as x varies they are not closed-form expressions, and are not analytic function. Here we replace them by simpler (but weaker) expressions which are analytic in a and x.
Gamma bounds
Lemma 3.1. For a > 0 and 0 ≤ f ≤ 1
Gamma bounds
with equality for f = 0, 1 and strict inequality for f ∈ (0, 1).
Gamma bounds
Proof. The result is true (with equality) when f = 0 or 1, so we can assume 0 < f < 1. We use the integral formula Γ(x) =
Gamma bounds
f and using Hölder's inequality (with p = 1/(1 − f )) gives
Gamma bounds
Since aΓ(a) = Γ(a + 1) we get
Gamma bounds
and we are done.
Gamma bounds
with equality if and only if x − a is an integer.
Gamma bounds
(ii) For 0 ≤ x ≤ a with a > 0, the lower tail bound defined by (6) satisfies
Gamma bounds
with equality if and only if a − x is an integer.
Gamma bounds
. Since c = 1 and x ≥ a, this is consistent with the notation in (4). Note that x − k = a − f , and combine (11) with (13).
Gamma bounds
(ii) Let k = ⌊a − x⌋ and f = a − x − k ∈ [0, 1). Since c = 1 and a ≥ x, this is consistent with the notation in (4). Replacing f by 1 − f in (13) gives a f Γ(a − f + 1) ≤ Γ(a + 1). Combining this with (12) and noting that x + k = a − f gives the result.
Moment generating function
We recall our notation, M(β) := E e βX for the moment generating function of X. Recall that every random variable has M(0) = 1 We observe that if X is Poisson with parameter a, then log M (β) = a(e β − 1), and X admits a c-bounded size bias coupling with c = 1, so that in this case, the inequality (16) holds as an equality for all β.
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
for all β ∈ R.
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
Proof. We know from Corollary 2.3 that the moment generating function M(β) is finite for all β ∈ R. It follows that M is continuously differentiable and M ′ (β) = E (Xe βX ). Moreover, since Y is the size biased version of X, we have E (Xe βX ) = aE (e βY ). Together we have
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
For β ≥ 0 we have e βY ≤ e β(X+c) = e βc e βX so that
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
for all β ≥ 0. For β ≤ 0 we have e βY ≥ e β(X+c) = e βc e βX so that
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
and the proof is complete.
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
We can now obtain some different upper tail and lower tail bounds, using the standard "large deviation upper bound" method together with the information about M(β) in Proposition 4.1.
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
With the convention that (1/0)
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
x/c as being well-defined and taking the value 1 when x = 0. This is the interpretation to use for the right side of (18) when x = 0, as well as elsewhere in the paper. 
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
and
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
Proof. Suppose first x ≥ a. For any β ≥ 0 we have
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
Choosing β = (1/c) log(x/a) ≥ 0 we get
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
. Now suppose 0 ≤ x ≤ a. For any β ≤ 0 we have
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
If 0 < x ≤ a take β = (1/c) log(x/a) ≤ 0 to get
Proposition 4.1. Under the hypotheses of Lemma 2.1 the moment generating function
See Sections 8 and 9 for results relating (17, 18) to our earlier bounds.
Examples admitting a 1-bounded size bias coupling
Here we give some examples of random variables X which satisfy the hypotheses of Lemma 2.1 with c = 1. Examples with general c > 0 can be obtained by scaling, see Remark 2.5.
Examples admitting a 1-bounded size bias coupling
Remark 5.2 (Sharpness of the bounds). Suppose X is Poisson distributed with mean a ∈ (0, ∞). Taking x = 0 in the lower tail bound (18) from Theorem 4.2 we get F (0) ≤ e −a whereas the exact value is F (0) = e −a . Therefore in this setting the lower tail bound (18) from Theorem 4.2 is sharp.
Examples admitting a 1-bounded size bias coupling
Now suppose further that a ∈ (0, 1]. When x = n, the upper tail bound (5) in Theorem 2.2 simplifies, with k = n − 1, to G(x) ≤ u(n, a, 1) = a n /n!, while for large n, G(n) ∼ P(X = n) = e −a a n /n!. Hence, for large x with x an integer, the upper bound (5) is sharp up to a factor of approximately e a . Letting a → 0 so that e a → 1, one sees that the upper bound (5), for large x, is sharp up to a factor arbitrarily close to 1. Proof. Suppose that X is uniformly distributed on [0, 1], and that Y is the size biased version of X. On [0, 1], the density of X is f X (x) = 1, the density of Y is f Y (x) = 2x, the cumulative distribution functions are F X (t) = t and F Y (t) = t 2 , and the inverse cumulative distribution functions are
Examples admitting a 1-bounded size bias coupling
, achieved at u = Proposition 5.6. Suppose X = i X i is the sum of finitely or countably many independent non-negative random variables X i with 0 < E X = i E X i < ∞. If each X i admits a 1-bounded size bias coupling, then so does X.
Proof.
the sum of (possibly infinitely many) independent Bernoulli random variables (with possibly different parameters) with 0 < E X < ∞ then X has a 1-bounded size bias coupling. 
Proof.
where a ∈ (0, ∞) and α is the probability distribution of a nonnegative nonzero random variable D, with P(D ∈ [0, c]) = 1. Given this characteristic function, the random variable X has a = E X, and, with X, D independent,
Proof.
See [2] . Special cases include:
Proof.
(1) c = 1, P(D = 1) = 1; X is Poisson with mean a.
Proof.
(2) c = 1, a = 1, D is uniformly distributed on (0, 1); X has density f (x) = e −γ ρ(x) where ρ is Dickman's function and γ is Euler's constant.
Universal Dickman function like behavior.
Theorem 6.1. Suppose X has distribution given by (19) for c > 0, and that for every ε > 0, the probability measure α is not supported on [0, c − ε]. Then G(x) := P(X ≥ x) satisfies, as x → ∞,
Universal Dickman function like behavior.
Proof. The upper bound on G(x) follows directly and easily from (5) in Theorem 2.2; see also Theorem 3.2 or the first inequality in Proposition 8.2. For the lower bound, let ε > 0 be given, with ε < c. The characteristic function in (19) can also be expressed as
Universal Dickman function like behavior.
Here γ is a nonnegative measure on (0, ∞), with γ(dy)/α(dy) = a/y, and may be called the Lévy measure of the infinitely divisible random variable X; see Sato [15, Section 51], Bertoin [5] , or [2] . The random variable X can be realized as the constant aα 0 plus the sum of the arrivals in the Poisson process X on (0, c] with intensity measure γ. Let Z be the number of arrivals of X in [c − ε, c]. We have X ≥ (c − ε)Z. This yields
Finally, Z is a Poisson random variable with mean
We recall an elementary calculation: for integers k → ∞, the Poisson (λ) distribution for Z has P(Z ≥ k) ≥ P(Z = k) with
Finally, Z is a Poisson random variable with mean
We use this with k = ⌈x/(c − ε)⌉ ∼ x/(c − ε) and log k ∼ log x.
Finally, Z is a Poisson random variable with mean
Remark 6.2. Most probabilists are familiar with the ≈ notation of (20), with a n ≈ b n defined to mean log a n ∼ log b n , for use in the context where a n grows or decays exponentially. The standard example is the large deviation statement that for i.i.d. sums, P(S n ≥ an) ≈ exp(−nI(a)), and the ≈ relation hides factors with a slower than exponential order of growth or decay, in this case 1/ √ n. When both a n and b n grow or decay even faster, for example with a n ∼ n ±n/c , an unfamiliar phenomenon arises, with ≈ hiding factors which grow or decay exponentially fast. One example appears in the conclusion (20) of Theorem 6.1, where x −x/c ≈ (x/c) −x/c ≈ 1/Γ(x/c) as x → ∞ -with the last expression being relevant because it corresponds to the Gamma function upper bound in Theorem 3.2. A second example occurs in (22), where at first it appears strange that the parameter λ does not appear on the right hand side -this reflects the fact that for any fixed λ, λ ′ > 0, when Z and Z ′ are Poisson with parameters λ, λ ′ respectively, P(Z = k) ≈ P(Z ′ = k) as k → ∞. The first example hides the exponentially growing factor c x/c , and the second hides the factor (λ ′ /λ) k .
Bounded coupling, monotone coupling, and a sandwich principle
Suppose that the distributions of random variables X, Y have been specified, with cumulative distribution functions F X , F Y respectively. We will clarify the relations between hypotheses of the form
Bounded coupling, monotone coupling, and a sandwich principle
It is well-known that if Y = d X * , then (26) holds. We observe that (23) is the hypothesis for our Lemma 2.1 and Theorem 2.2, while (24) and (25) are used as hypotheses for the first results on concentration via size bias couplings, in [8] .
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
The proof of Proposition 7.1 will be given later in this section. 
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
and it is well known that (27) is equivalent to (26). See for example Lemma 7.2. Stochastic domination is often considered in the more general context where X, Y are random elements in a partially ordered set, see for example [14] . 
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
iii) There exists a coupling such that
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
Proof. To prove that i) implies ii) we use the coupling in which P(X ≤ Y + b) = 1 and calculate
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
and similarly for
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
To show ii) implies iv) we may use the quantile transform to couple X and Y to a single random variable U, uniformly distributed in (0,1). This transform is written informally as
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
and more formally as X(ω) := inf{t :
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
Finally, iv) implies iii) trivially, and iii) implies i) a fortiori. 
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
If there is a c-bounded coupling of X and Z, as defined via (24), then there exists a c-bounded monotone coupling of X and Y , as defined by (25).
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
Proof. Using Lemma 7.2 with Z in place of Y , the c-bounded coupling of X and Z implies
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
for all t, and Lemma 7.2 gives the existence of the c-bounded monotone coupling of X and Y .
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
Application. As an illustration of the sandwich principle, we prove the following corollary. The special case where X is Binomial(m, p) for p ∈ (0, 1) and m ≥ 1 was proved in [9, Lemmas 3.2, 3.3] by an explicit calculation. The sandwich principle enables a short proof for the general case, with no calculation. Proof. Trivially, Y stochastically dominates X. Take the distribution of Z to be the size biased distribution of X. By assumption, there is a coupling in which P(Z − X ∈ [0, 1]) = 1. Trivially, the distribution of Z, initially defined as the size-biased distribution of X, is also the size-biased distribution of Y . Hence Z dominates Y , and the sandwich principle applies with c = 1.
Proposition 7.1. Given that (26) holds, all of (23) -(25) are equivalent.
This result may be applied to any of the random variables X discussed in Section 5, and in particular to those obtained using Proposition 5.6. If X is (non-negative) integer valued, for example, a Binomial random variable or a sum of independent Bernoulli random variables, then Y is also integer valued and the conclusion of Corollary 7.4 is easily strengthened to Y − X ∈ {0, 1} for all ω.
Analysis of the upper tail and lower tail bounds
In this section we obtain results enabling us to compare the upper and lower tail bounds in Theorem 3.2 with those in Theorem 4.2.
Analysis of the upper tail and lower tail bounds
Proof. For x > 0, using Gauss' formula, see [17, Sect 12.3] , (log Γ) ′ (x + 1/2) = 1 − e −t dt
Analysis of the upper tail and lower tail bounds
Therefore for 0 < u ≤ v,
Analysis of the upper tail and lower tail bounds
a+1/2 (ae)
Analysis of the upper tail and lower tail bounds
(32)
Analysis of the upper tail and lower tail bounds
Proof. Taking u = a + 1/2 and v = x + 1/2 in (31), we get
Analysis of the upper tail and lower tail bounds
giving (32). A simple calculus argument shows that t → (a+t) a /(x+t)
Analysis of the upper tail and lower tail bounds
x is decreasing for t ∈ [0, ∞). In particular a + 1 2
Analysis of the upper tail and lower tail bounds
x ≤ a a /x x , and this gives (33).
Analysis of the upper tail and lower tail bounds
(34)
Analysis of the upper tail and lower tail bounds
Proof. Essentially the same as for Proposition 8.2, but with the roles of x and a switched. (10) ) that the product bounds (5, 6) are at least as strong (i.e. small) as the corresponding Gamma bounds (14, 15) . However the relationship between the Gamma bounds and the bounds (17, 18) (14) is sharper than the bound (17) from Theorem 4.2 by a factor (a + c/2)/(x + c/2). However, the situation is reversed for the lower tail, with 0 ≤ x ≤ a, where now the bound (18) from Theorem 4.2 is sharper than the Gamma bound (15) by a factor (x + c/2)/(a + c/2). Since the Gamma bound (15) and the product bound (6) agree whenever a − x is an integer, this suggests (but does not prove) that the bound (18) is the best of the three for the lower tail.
Analysis of the upper tail and lower tail bounds
Numerical investigations suggest that (18) is in fact the best estimate to use for the lower tail, and beats the simple product rule ℓ(x, a, c) of (6). Recall however, from Section 2.1, the lower tail bounds derived from (3) in combination with the one-sided Chebyshev inequality (7), in particular the functions ℓ j (x, a, c) defined in (8) . Numerical investigations suggest that for all a, c > 0 with sufficiently large a/c there exists x ∈ (0, a) such that the bound given in (18) is less than the product bound (6) and is less than the one-sided Chebyshev estimate (7), but is greater than ℓ j (x, a, c) for some nonnegative integer j ≤ (a − x)/c.
9.2.
Results of Ghosh and Goldstein. The paper [8] proved the inequalities
9.2.
for x ≤ a for a random variable which admits a c-bounded size bias coupling. The following lemmas show that our bounds given in Theorem 4.2 outperform those given by [8] . Dividing by c and applying the exponential function to both sides gives (37).
9.2.
9.3. Hoeffding bounds. Suppose X = X 1 + · · · + X n where the X i are independent and take values in [0, 1], and let a = E X. Clearly a < ∞ and to avoid trivialities we assume a > 0. Hoeffding [13, Thm 1] proved that for a ≤ x < n P(X ≥ x) ≤ a x x n − a n − x n−x .
9.2.
The inequality n − a n − x n−x ≤ e x−a for 0 < x < n, (see for example [11] ), and the fact that P(X ≥ x) = 0 for x > n, together give the upper tail bound
9.2.
for all x ≥ a.
9.2.
A similar argument with X i replaced by 1 − X i and X replaced by n − X gives the lower tail bound P(X ≤ x) ≤ a x
9.2.
x e x−a whenever 0 ≤ x ≤ a.
9.2.
Notice that the right sides of (38) and (39) do not depend on the number n of summands in X. Other related inequalities, also referred to as Hoeffding or Chernoff-Hoeffding bounds, involve the parameter n.
9.2.
From Proposition 5.6 we know that any random variable X of the form above admits a 1-bounded size bias coupling. Therefore the Hoeffding bounds (38, 39) are a special case of the bounds (17, 18) in our Theorem 4.2. Our best upper tail bound, given by (5) 

{'paper_id': '119709432', 'title': 'Bounded size bias coupling: a Gamma function bound, and universal Dickman-function behavior', 's2_url': 'https://api.semanticscholar.org/CorpusID:119709432', 'source': 'S2ORC'}