Consider a sequence of n Bernoulli trials, where success occurs with probability p. Let X be the random variable denoting the total number of successes. Then for 0 ≤ k ≤ n, the probability of at least k successes is

Proof For S ⊆ {1, 2,..., n}, we let A_S denote the event that the ith trial is a success for every i ∈ S. Clearly Pr {A_S} = p^k if |S| = k. We have

where the inequality follows from Boole's inequality (C.18).

Consider a sequence of n Bernoulli trials, where success occurs with probability p. If X is the random variable denoting the total number of successes, then for

0 ≤ k ≤ n, the probability of at most k successes is

Consider a sequence of n Bernoulli trials, where success occurs with probability p and failure with probability q = 1 - p. Let X be the random variable denoting the total number of successes. Then for 0 < k < np, the probability of fewer than k successes is

Proof We bound the series by a geometric series using the technique from Section A.2, page 1064. For i = 1, 2,..., k, we have from equation (C.40),

If we let

it follows that

b(i - 1; n, p) < xb(i; n, p)

for 0 < i ≤ k. Iteratively applying this inequality k - i times, we obtain

b(i; n, p) < x_k-i b(k; n, p)

for 0 ≤ i < k, and hence

Consider a sequence of n Bernoulli trials, where success occurs with probability p and failure with probability q = 1 - p. Then for 0 < k ≤ np/2, the probability of fewer than k successes is less than one half of the probability of fewer than k + 1 successes.

Proof Because k ≤ np/2, we have

since q ≤ 1. Letting X be the random variable denoting the number of successes, Theorem C.4 implies that the probability of fewer than k successes is

Thus we have

since

Consider a sequence of n Bernoulli trials, where success occurs with probability p. Let X be the random variable denoting the total number of successes. Then for np < k < n, the probability of more than k successes is

Consider a sequence of n Bernoulli trials, where success occurs with probability p and failure with probability q = 1 - p. Then for (np + n)/2 < k < n, the probability of more than k successes is less than one half of the probability of more than k - 1 successes.

Consider a sequence of n Bernoulli trials, where in the ith trial, for i = 1, 2,...,n, success occurs with probability p_i and failure occurs with probability q_i = 1 - p_i. Let X be the random variable describing the total number of successes, and let μ = E [X]. Then for r > μ,

Proof Since for any α > 0, the function e^αx is strictly increasing in x,

where α will be determined later. Using Markov's inequality (C.29), we obtain

The bulk of the proof consists of bounding E[e^{α(X - μ)}] and substituting a suitable value for α in inequality (C.42). First, we evaluate E[e^{α(X - μ)}]. Using the notation of Section 5.2, let X_i = I {the ith Bernoulli trial is a success} for i = 1, 2,...,n; that is, X_i is the random variable that is 1 if the ith Bernoulli trial is a success and 0 if it is a failure. Thus,

and by linearity of expectation,

which implies

To evaluate E[e^{α(X - μ)}], we substitute for X - μ, obtaining

which follows from (C.23), since the mutual independence of the random variables X_i implies the mutual independence of the random variables (see Exercise C.3-5). By the definition of expectation,

where exp(x) denotes the exponential function: exp(x) = e^x. (Inequality (C.43) follows from the inequalities α > 0, q_i ≤ 1, e^αqi ≤ e^α, and e ^αpi ≤ 1, and the last line follows from inequality (3.11)). Consequently,

since . Therefore, from equation (C.41) and inequalities (C.42) and (C.44), it follows that

Choosing α = ln(r/μ) (see Exercise C.5-7), we obtain

Consider a sequence of n Bernoulli trials, where in each trial success occurs with probability p and failure occurs with probability q = 1 - p. Then for r > np,

Proof By equation (C.36), we have μ = E [X] = np.

Which is less likely: obtaining no heads when you flip a fair coin n times, or obtaining fewer than n heads when you flip the coin 4n times?

Prove Corollaries C.6 and C.7.

Show that

for all a > 0 and all k such that 0 < k < n.

Prove that if 0 < k < np, where 0 < p < 1 and q = 1 - p, then

Show that the conditions of Theorem C.8 imply that

Similarly, show that the conditions of Corollary C.9 imply that

Consider a sequence of n Bernoulli trials, where in the ith trial, for i = 1, 2,..., n, success occurs with probability p_i and failure occurs with probability q_i = 1 - p_i. Let X be the random variable describing the total number of successes, and let μ = E [X]. Show that for r ≥ 0,

(Hint: Prove that . Then follow the outline of the proof of Theorem C.8, using this inequality in place of inequality (C.43).)

Show that the right-hand side of inequality (C.45) is minimized by choosing α = ln(r/μ).

In this problem, we investigate the effect of various assumptions on the number of ways of placing n balls into b distinct bins.

1. Suppose that the n balls are distinct and that their order within a bin does not matter. Argue that the number of ways of placing the balls in the bins is bⁿ.

2. Suppose that the balls are distinct and that the balls in each bin are ordered. Prove that there are exactly (b + n - 1)!/(b - 1)! ways to place the balls in the bins. (Hint: Consider the number of ways of arranging n distinct balls and b - 1 indistinguishable sticks in a row.)

3. Suppose that the balls are identical, and hence their order within a bin does not matter. Show that the number of ways of placing the balls in the bins is . (Hint: Of the arrangements in part (b), how many are repeated if the balls are made identical?)

4. Suppose that the balls are identical and that no bin may contain more than one ball. Show that the number of ways of placing the balls is .

5. Suppose that the balls are identical and that no bin may be left empty. Show that the number of ways of placing the balls is .