chap06.htm

介绍算法的书籍

<h2>The binomial distribution</h2><P>
<a name="0751_12de"><a name="0751_12df"><a name="0751_12e0">How many successes occur during <I>n</I> Bernoulli trials, where a success occurs with probability <I>p</I> and a failure with probability <I>q</I> = 1 - <I>p</I>? Define the random variable <I>X</I> to be the number of successes in <I>n</I> trials. Then <I>X</I> has values in the range {0, 1, . . . , <I>n</I>}, and for <I>k</I> = 0, . . . , <I>n</I>,<P>
<img src="117_b.gif"><P>
<h4><a name="0751_12e3">(6.36)<a name="0751_12e3"></sub></sup></h4><P>
since there are <img src="117_c.gif"> ways to pick which <I>k</I> of the <I>n </I>trials are successes, and the probability that each occurs is <I>p<SUP>k</SUP>q<SUP>n</I></SUP>-<I><SUP>k</I>.</SUP> A probability distribution satisfying equation (6.36) is said to be a <I><B>binomial distribution</I></B>. For convenience, we define the family of binomial distributions using the notation<P>
<img src="117_d.gif"><P>
<h4><a name="0751_12e4">(6.37)<a name="0751_12e4"></sub></sup></h4><P>
Figure 6.2 illustrates a binomial distribution. The name &quot;binomial&quot; comes from the fact that (6.37) is the <I>k</I>th term of the expansion of (<I>p </I>+<I> q</I>)<I><SUP>n</I></SUP>. Consequently, since <I>p </I>+ <I>q</I> = 1,<P>
<img src="117_e.gif"><P>
<h4><a name="0751_12e5">(6.38)<a name="0751_12e5"></sub></sup></h4><P>
as is required by axiom 2 of the probability axioms.<P>
We can compute the expectation of a random variable having a binomial distribution from equations (6.14) and (6.38). Let <I>X</I> be a random variable that follows the binomial distribution <I>b</I>(<I>k; n, p</I>), and let <I>q</I> = 1 - <I>p</I>. By the definition of expectation, we have<P>
<img src="118_a.gif"><P>
<h4><a name="0751_12e6">(6.39)<a name="0751_12e6"></sub></sup></h4><P>
By using the linearity of expectation, we can obtain the same result with substantially less algebra. Let <I>X<SUB>i</I></SUB> be the random variable describing the number of successes in the <I>i</I>th trial. Then E[<I>X<SUB>i</I></SUB>] = <I>p</I> <img src="../images/dot10.gif"> 1+ <I>q</I> <img src="../images/dot10.gif"> 0 = <I>p</I>, and by linearity of expectation (6.26), the expected number of successes for <I>n</I> trials is<P>
<img src="118_b.gif"><P>
<a name="0751_12e1">The same approach can be used to calculate the variance of the distribution. Using equation (6.29), we have <img src="118_c.gif">. Since <I>X<SUB>i</SUB> </I>only takes on the values 0 and 1, we have <img src="118_d.gif">, and hence<P>
<pre>Var[<I>X<SUB>i</I></SUB>] = <I>p</I> - <I>p</I><SUP>2</SUP> = <I>pq </I>.</sub></sup></pre><P>
<h4><a name="0751_12e7">(6.40)<a name="0751_12e7"></sub></sup></h4><P>
To compute the variance of <I>X</I>, we take advantage of the independence of the <I>n</I> trials; thus, by equation (6.31),<P>
<img src="118_e.gif"><P>
<h4><a name="0751_12e8">(6.41)<a name="0751_12e8"></sub></sup></h4><P>
As can be seen from Figure 6.2, the binomial distribution <I>b(k;n,p</I>) increases as <I>k</I> runs from 0 to <I>n</I> until it reaches the mean <I>np</I>, and then it decreases. We can prove that the distribution always behaves in this manner by looking at the ratio of successive terms:<P>
<img src="119_a.gif"><P>
<h4><a name="0751_12e9">(6.42)<a name="0751_12e9"></sub></sup></h4><P>
This ratio is greater than 1 precisely when (<I>n</I> + 1)<I>p - k</I> is positive. Consequently, <I>b(k;n,p) &gt; b(k - </I>1<I>;n,p</I>) for <I>k</I> &lt; (<I>n</I> + 1)<I>p</I> (the distribution increases), and <I>b(k;n,p</I>) &lt; <I>b(k</I> - 1;<I>n</I>,<I>p</I>) for <I>k</I> &gt; (<I>n</I> + l)<I>p</I> (the distribution decreases). If <I>k</I> = (<I>n</I> + 1) <I>p </I>is an integer, then <I>b</I>(<I>k;n,p</I>)<I> </I>=<I> b(k - </I>1<I>;n,p</I>), so the distribution has two maxima: at <I>k</I> = (<I>n</I> + l) <I>p</I> and at <I>k</I> - 1 = (<I>n</I> + 1)<I>p - </I>1<I> </I>=<I> np - q</I>. Otherwise, it attains a maximum at the unique integer <I>k</I> that lies in the range <I>np - q &lt; k &lt; </I>(<I>n + </I>1)<I>p</I>.<P>
<a name="0751_12e2">The following lemma provides an upper bound on the binomial distribution.<P>
<a name="0751_12ea">Lemma 6.1<a name="0751_12ea"><P>
Let <I>n</I> <img src="../images/gteq.gif"> 0, let 0 &lt; <I>p</I> &lt; 1, let <I>q</I> = 1 - <I>p</I>, and let 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>. Then<P>
<img src="119_b.gif"><P>
<I><B>Proof</I></B>     Using equation (6.10), we have<P>
<img src="119_c.gif"><P>
<P>







<h2><a name="0752_12e5">Exercises<a name="0752_12e5"></h2><P>
<a name="0752_12e6">6.4-1<a name="0752_12e6"><P>
Verify axiom 2 of the probability axioms for the geometric distribution.<P>
<a name="0752_12e7">6.4-2<a name="0752_12e7"><P>
How many times on average must we flip 6 fair coins before we obtain 3 heads and 3 tails?<P>
<a name="0752_12e8">6.4-3<a name="0752_12e8"><P>
Show that <I>b</I>(<I>k</I>; <I>n</I>, <I>p</I>) = <I>b</I>(<I>n</I> - <I>k</I>; <I>n</I>, <I>q</I>), where <I>q</I> = 1 - <I>p</I>.<P>
<a name="0752_12e9">6.4-4<a name="0752_12e9"><P>
<a name="0752_12e3"><a name="0752_12e4">Show that value of the maximum of the binomial distribution <I>b(k; n, p</I>) is approximately <img src="120_a.gif"> where <I>q </I>=<I> 1 </I>-<I> p</I>.<P>
<a name="0752_12ea">6.4-5<a name="0752_12ea"><P>
Show that the probability of no successes in <I>n</I> Bernoulli trials, each with probability <I>p</I> = 1/<I>n</I>, is approximately 1/<I>e</I>. Show that the probability of exactly one success is also approximately 1/<I>e</I>.<P>
<a name="0752_12eb">6.4-6<a name="0752_12eb"><P>
Professor Rosencrantz flips a fair coin <I>n</I> times, and so does Professor Guildenstern. Show that the probability that they get the same number of heads is <img src="120_b.gif">. (<I>Hint</I>: For Professor Rosencrantz, call a head a success; for Professor Guildenstern, call a tail a success.) Use your argument to verify the identity<P>
<img src="120_c.gif"><P>
<a name="0752_12ec">6.4-7<a name="0752_12ec"><P>
Show that for 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>,<P>
<pre><I>b(k;n</I>, 1/2) <img src="../images/lteq12.gif"> 2<I><SUP>nH(k/n)-n</I></SUP>,</sub></sup></pre><P>
where <I>H</I>(<I>x</I>) is the entropy function (6.13).<P>
<a name="0752_12ed">6.4-8<a name="0752_12ed"><P>
Consider <I>n</I> Bernoulli trials, where for <I>i</I> = 1,2, . . . ,<I>n</I>, the <I>i</I>th trial has probability <I>p<SUB>i</I></SUB> of success, and let <I>X</I> be the random variable denoting the total number of successes. Let <I>p </I><img src="../images/gteq.gif"><I> p<SUB>i</I></SUB> for all <I>i</I> = 1, 2, . . . , <I>n</I>. Prove that for 1 <img src="../images/lteq12.gif"> <I>k </I><img src="../images/lteq12.gif"> n<I>,</I><P>
<img src="120_d.gif"><P>
<a name="0752_12ee">6.4-9<a name="0752_12ee"><P>
Let <I>X</I> be the random variable for the total number of successes in a set <I>A</I> of <I>n</I> Bernoulli trials, where the <I>i</I>th trial has a probability <I>p<SUB>i</I></SUB> of success, and let <I>X</I>'<I><FONT FACE="Times New Roman" SIZE=5> </I></FONT>be the random variable for the total number of successes in a second set <I>A</I><I>'</I> of <I>n</I> Bernoulli trials, where the <I>i</I>th trial has a probability p'<I><SUB>i </I></SUB><img src="../images/gteq.gif"> <I>p<SUB>i</I></SUB> of success. Prove that for 0 <img src="../images/lteq12.gif"> <I>k </I><img src="../images/lteq12.gif"><I> n</I>,<P>
<pre>Pr{<I>X</I>' <img src="../images/gteq.gif"> k} <img src="../images/gteq.gif"> Pr{<I>X</I> <img src="../images/gteq.gif"> k} .</sub></sup></pre><P>
(<I>Hint</I>: Show how to obtain the Bernoulli trials in <I>A</I>' by an experiment involving the trials of <I>A</I>, and use the result of Exercise 6.3-6.)<P>
<P>


<P>







<h1><a name="0753_12e8">* 6.5 The tails of the binomial distribution<a name="0753_12e8"></h1><P>
<a name="0753_12e5"><a name="0753_12e6"><a name="0753_12e7">The probability of having at least, or at most, <I>k</I> successes in <I>n</I> Bernoulli trials, each with probability <I>p</I> of success, is often of more interest than the probability of having exactly <I>k</I> successes. In this section, we investigate the <I><B>tails</I></B> of the binomial distribution: the two regions of the distribution <I>b(k; n, p</I>) that are far from the mean <I>np</I>. We shall prove several important bounds on (the sum of all terms in) a tail.<P>
We first provide a bound on the right tail of the distribution <I>b(k; n, p</I>). Bounds on the left tail can be determined by inverting the roles of successes and failures.<P>
<a name="0753_12e9">Theorem 6.2<a name="0753_12e9"><P>
Consider a sequence of <I>n</I> Bernoulli trials, where success occurs with probability <I>p</I>. Let <I>X</I> be the random variable denoting the total number of successes. Then for 0 <img src="../images/lteq12.gif"> <I>k </I><img src="../images/lteq12.gif"><I> n</I>, the probability of at least <I>k</I> successes is<P>
<img src="121_a.gif"><P>
<I><B>Proof     </I></B>We make use of the inequality (6.15)<P>
<img src="121_b.gif"><P>
We have<P>
<img src="121_c.gif"><P>
since <img src="122_a.gif"> by equation (6.38).      <P>
The following corollary restates the theorem for the left tail of the binomial distribution. In general, we shall leave it to the reader to adapt the bounds from one tail to the other.<P>
<a name="0753_12ea">Corollary 6.3<a name="0753_12ea"><P>
Consider a sequence of <I>n</I> Bernoulli trials, where success occurs with probability <I>p</I>. If <I>X</I> is the random variable denoting the total number of successes, then for 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>, the probability of at most <I>k</I> successes is<P>
<img src="122_b.gif"><P>
Our next bound focuses on the left tail of the binomial distribution. Far from the mean, the number of successes in the left tail diminishes exponentially, as the following theorem shows.<P>
<a name="0753_12eb">Theorem 6.4<a name="0753_12eb"><P>
Consider a sequence of <I>n</I> Bernoulli trials, where success occurs with probability <I>p</I> and failure with probability <I>q</I> = 1 - <I>p</I>. Let <I>X</I> be the random variable denoting the total number of successes. Then for 0 <I>&lt;</I> <I>k</I> &lt; <I>np</I>, the probability of fewer than <I>k</I> successes is<P>
<img src="122_c.gif"><P>
<I><B>Proof     </I></B>We bound the series <img src="122_d.gif"> by a geometric series using the technique from Section 3.2, page 47. For <I>i</I> = 1, 2, . . . , <I>k</I>, we have from equation (6.42),<P>
<img src="122_e.gif"><P>
If we let<P>
<img src="123_a.gif"><P>
it follows that<P>
<pre><I>b</I>(<I>i</I> - 1;<I>n</I>,<I>p</I>) &lt; <I>x</I> <I>b</I>(<I>i</I>;<I>n</I>,<I>p</I>)</sub></sup></pre><P>
for 0 &lt; <I>i </I><img src="../images/lteq12.gif"><I> k</I>. Iterating, we obtain<P>
<pre><I>b</I>(<I>i</I>;<I>n</I>,<I>p</I>) &lt; x<I><SUP>k</I>-<I>i</I> </SUP><I>b</I>(<I>k</I>;<I>n</I>,<I>p</I>)</sub></sup></pre><P>
for 0 <img src="../images/lteq12.gif"> i &lt; k, and hence<P>
<img src="123_b.gif"><P>
When <I>k</I> <img src="../images/lteq12.gif"> <I>np</I>/2, we have <I>kq</I>/(<I>np - k</I>) <img src="../images/lteq12.gif"> 1, which means that <I>b(k; n, p</I>) bounds the sum of all terms smaller than <I>k</I>. As an example, suppose we flip <I>n</I> fair coins. Using <I>p</I> = 1/2 and <I>k</I> = <I>n</I>/4, Theorem 6.4 tells us that the probability of obtaining fewer than <I>n</I>/4 heads is less than the probability of obtaining exactly <I>n</I>/4 heads. Furthermore, for any <I>r</I> <img src="../images/gteq.gif"> 4, the probability of obtaining fewer than <I>n/r</I> heads is less than that of obtaining exactly <I>n/r </I>heads. Theorem 6.4 can also be quite useful in conjunction with upper bounds on the binomial distribution, such as Lemma 6.1.<P>
A bound on the right tail can be determined similarly.<P>
<a name="0753_12ec">Corollary 6.5<a name="0753_12ec"><P>
Consider a sequence of <I>n</I> Bernoulli trials, where success occurs with probability <I>p</I>. Let <I>X</I> be the random variable denoting the total number of successes. Then for <I>np &lt; k &lt; n</I>, the probability of more than <I>k</I> successes is<P>
<img src="123_c.gif"><P>
The next theorem considers <I>n</I> Bernoulli trials, each with a probability <I>p<SUB>i</I></SUB> of success, for <I>i</I> = 1, 2, . . . , <I>n</I>. As the subsequent corollary shows, we can use the theorem to provide a bound on the right tail of the binomial distribution by setting <I>p<SUB>i</I></SUB> = <I>p</I> for each trial.<P>
<a name="0753_12ed">Theorem 6.6<a name="0753_12ed"><P>
Consider a sequence of <I>n</I> Bernoulli trials, where in the <I>i</I>th trial, for <I>i</I> = 1, 2 , . . . , <I>n</I>, success occurs with probability <I>p<SUB>i</I></SUB> and failure occurs with probability <I>q<SUB>i</SUB> </I>=<I> </I>1<I> - p<SUB>i</I></SUB>. Let <I>X</I> be the random variable describing the total number of successes, and let <img src="../images/mu12.gif"> = E[<I>X</I>]. Then for <I>r </I>&gt; <img src="../images/mu12.gif">,<P>
<img src="124_a.