chap06.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h4><a name="0742_12b7">(6.13)<a name="0742_12b7"></sub></sup></h4><P>
<a name="0742_12af"><a name="0742_12b0">is the <B>(</B><I><B>binary) entropy function</I></B> and where, for convenience, we assume that 0 lg 0 = 0, so that <I>H </I>(0) = <I>H </I>(1) = 0.<P>
<P>







<h2><a name="0743_12b4">Exercises<a name="0743_12b4"></h2><P>
<a name="0743_12b5">6.1-1<a name="0743_12b5"><P>
How many <I>k</I>-substrings does an <I>n</I>-string have? (Consider identical <I>k</I>-substrings at different positions as different.) How many substrings does an <I>n</I>-string have in total?<P>
<a name="0743_12b6">6.1-2<a name="0743_12b6"><P>
<a name="0743_12b1">An <I>n</I>-input, <I>m</I>-output <I><B>boolean</I> </B><I><B>function</I> </B>is a function from {<FONT FACE="Courier New" SIZE=2>TRUE, FALSE</FONT>}<I><SUP>n</I> </SUP>to {<FONT FACE="Courier New" SIZE=2>TRUE, FALSE</FONT>}<I><SUP>m</I></SUP>. How many <I>n</I>-input, 1-output boolean functions are there? How many <I>n</I>-input, <I>m</I>-output boolean functions are there?<P>
<a name="0743_12b7">6.1-3<a name="0743_12b7"><P>
In how many ways can <I>n</I> professors sit around a circular conference table? Consider two seatings to be the same if one can be rotated to form the other.<P>
<a name="0743_12b8">6.1-4<a name="0743_12b8"><P>
In how many ways can three distinct numbers be chosen from the set {1, 2, . . . , 100} so that their sum is even?<P>
<a name="0743_12b9">6.1-5<a name="0743_12b9"><P>
Prove the identity<P>
<img src="103_a.gif"><P>
<h4><a name="0743_12ba">(6.14)<a name="0743_12ba"></sub></sup></h4><P>
for 0 &lt; <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>.<P>
<a name="0743_12bb">6.1-6<a name="0743_12bb"><P>
Prove the identity<P>
<img src="103_b.gif"><P>
for 0 <img src="../images/lteq12.gif"> <I>k</I> &lt; <I>n</I>.<P>
<a name="0743_12bc">6.1-7<a name="0743_12bc"><P>
To choose <I>k</I> objects from <I>n</I>, you can make one of the objects distinguished and consider whether the distinguished object is chosen. Use this approach to prove that<P>
<img src="103_c.gif"><P>
<a name="0743_12bd">6.1-8<a name="0743_12bd"><P>
<a name="0743_12b2"><a name="0743_12b3">Using the result of Exercise 6.1-7, make a table for <I>n</I> = 0, 1, . . . , 6 and 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I> of the binomial coefficients <img src="104_a.gif"> with <img src="104_b.gif"> at the top, <img src="104_c.gif"> and <img src="104_d.gif"> on the next line, and so forth. Such a table of binomial coefficients is called <I><B>Pascal's triangle.</I></B><P>
<a name="0743_12be">6.1-9<a name="0743_12be"><P>
Prove that<P>
<img src="104_e.gif"><P>
<a name="0743_12bf">6.1-10<a name="0743_12bf"><P>
Show that for any <I>n</I> <img src="../images/gteq.gif"> 0 and 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>, the maximum value of <img src="104_f.gif"> is achieved when <I>k</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> or <I>k</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT>.<P>
<a name="0743_12c0">6.1-11<a name="0743_12c0"><P>
Argue that for any <I>n</I> <img src="../images/gteq.gif"> 0, <I>j</I> <img src="../images/gteq.gif"> 0, <I>k</I> <img src="../images/gteq.gif"> 0, and <I>j</I> + <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>,<P>
**image 104_g.gif not available**<P>
<h4><a name="0743_12c1">(6.15)<a name="0743_12c1"></sub></sup></h4><P>
Provide both an algebraic proof and an argument based on a method for choosing <I>j</I> + <I>k</I> items out of <I>n</I>. Give an example in which equality does not hold.<P>
<a name="0743_12c2">6.1-12<a name="0743_12c2"><P>
Use induction on <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>/2 to prove inequality (6.10), and use equation (6.4) to extend it to all <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>.<P>
<a name="0743_12c3">6.1-13<a name="0743_12c3"><P>
Use Stirling's approximation to prove that<P>
**image 104_h.gif not available**<P>
<h4><a name="0743_12c4">(6.16)<a name="0743_12c4"></sub></sup></h4><P>
<a name="0743_12c5">6.1-14<a name="0743_12c5"><P>
By differentiating the entropy function <I>H </I>(<img src="../images/lambdauc.gif">), show that it achieves its maximum value at <img src="../images/lambdauc.gif">= 1/2. What is <I>H </I>(1/2)?<P>
<P>


<P>







<h1><a name="0744_12b9">6.2 Probability<a name="0744_12b9"></h1><P>
<a name="0744_12b4">Probability is an essential tool for the design and analysis of probabilistic and randomized algorithms. This section reviews basic probability theory.<P>
<a name="0744_12b5"><a name="0744_12b6">We define probability in terms of a <I><B>sample space</I></B> <I><B>S,</I></B> which is a set whose elements are called <I><B>elementary events</I>.</B> Each elementary event can be viewed as a possible outcome of an experiment. For the experiment of flipping two distinguishable coins, we can view the sample space as consisting of the set of all possible 2-strings over {<FONT FACE="Courier New" SIZE=2>H, T</FONT>}:<P>
<pre><I>S</I> = {HH, HT, TH, TT} .</sub></sup></pre><P>
<a name="0744_12b7"><a name="0744_12b8">An<I> <B>event</I></B> is a subset<SUP>1</SUP> of the sample space <I>S</I>. For example, in the experiment of flipping two coins, the event of obtaining one head and one tail is {<FONT FACE="Courier New" SIZE=2>HT, TH</FONT>}. The event <I>S</I> is called the <I><B>certain event</I></B><I>, </I>and the event <img src="105_a.gif"> is called the <I><B>null event</I></B><I>.</I> We say that two events <I>A</I> and <I>B</I> are <I><B>mutually exclusive</I></B><I> </I>if <img src="105_b.gif">. We sometimes treat an elementary event <I>s</I> <img src="../images/memof12.gif"> <I>S</I> as the event {<I>s</I>}. By definition, all elementary events are mutually exclusive.<P>
<SUP>1</SUP> For a general probability distribution, there may be some subsets of the sample space <I>S</I> that are not considered to be events. This situation usually arises when the sample space is uncountably infinite. The main requirement is that the set of events of a sample space be closed under the operations of taking the complement of an event, forming the union of a finite or countable number of events, and taking the intersection of a finite or countable number of events. Most of the probability distributions we shall see are over finite or countable sample spaces, and we shall generally consider all subsets of a sample space to be events. A notable exception is the continuous uniform probability distribution, which will be presented shortly.<P>





<h2>Axioms of probability</h2><P>
<a name="0745_12b9"><a name="0745_12ba"><a name="0745_12bb">A <I><B>probability distribution</I></B> Pr{} on a sample space <I>S</I> is a mapping from events of <I>S</I> to real numbers such that the following <I><B>probability axioms </I></B>are satisfied:<P>
1.     Pr {<I>A</I>} <img src="../images/gteq.gif"> 0 for any event <I>A</I>.<P>
2.     Pr {<I>S</I>} = 1.<P>
3.     Pr {<I>A</I> <img src="../images/wideu.gif"> <I>B</I>} = Pr {<I>A</I>} + Pr {<I>B</I>} for any two mutually exclusive events <I>A</I> and <I>B</I>. More generally, for any (finite or countably infinite) sequence of events <I>A</I><SUB>1</SUB>, <I>A</I><SUB>2</SUB>, . . . that are pairwise mutually exclusive,<P>
<img src="105_c.gif"><P>
We call Pr {<I>A</I>} the <I><B>probability</I></B> of the event <I>A</I>. We note here that axiom 2 is a normalization requirement: there is really nothing fundamental about choosing 1 as the probability of the certain event, except that it is natural and convenient.<P>
<a name="0745_12bc">Several results follow immediately from these axioms and basic set theory (see Section 5.1). The null event <img src="105_d.gif"> has probability <img src="105_e.gif">. If <I>A</I> <img src="../images/rgtubar.gif"> <I>B</I>, then Pr{<I>A</I>} <img src="../images/lteq12.gif"> Pr{<I>B</I>}. Using <img src="105_f.gif"> to denote the event <I>S</I> - <I>A</I> (the<I> <B>complement</I></B> of <I>A</I>), we have <img src="105_g.gif">. For any two events <I>A</I> and <I>B</I>,<P>
<pre>PR{<I>A</I> <img src="../images/wideu.gif"><I>B</I>} = Pr{<I>A</I>} + Pr{<I>B</I>} - Pr{<I>A</I> <img src="../images/dome.gif"> <I>B</I>}</sub></sup></pre><P>
<h4><a name="0745_12bd">(6.17)<a name="0745_12bd"></sub></sup></h4><P>
<pre><img src="../images/lteq12.gif"> Pr{<I>A</I>} + Pr{<I>B</I>} .</sub></sup></pre><P>
<h4><a name="0745_12be">(6.18)<a name="0745_12be"></sub></sup></h4><P>
In our coin-flipping example, suppose that each of the four elementary events has probability 1/4. Then the probability of getting at least one head is<P>
<pre>Pr{HH, HT, TH} = Pr{HH} + Pr{HT} + Pr{TH}</sub></sup></pre><P>
<pre>= 3/4.</sub></sup></pre><P>
Alternatively, since the probability of getting strictly less than one head is Pr{<FONT FACE="Courier New" SIZE=2>TT</FONT>} = 1/4, the probability of getting at least one head is 1 - 1/4 = 3/4.<P>
<P>







<h2>Discrete probability distributions</h2><P>
<a name="0746_12bd">A probability distribution is <I><B>discrete</I></B> if it is defined over a finite or  countably infinite sample space. Let <I>S</I> be the sample space. Then for any event <I>A</I>,<P>
<img src="106_a.gif"><P>
since elementary events, specifically those in <I>A</I>, are mutually exclusive. If <I>S</I> is finite and every elementary event <I>s</I> <img src="../images/memof12.gif"> <I>S</I> has probability<P>
<pre>Pr{<I>s</I>} = 1/<img src="../images/sglvrt.gif"><I>S</I><img src="../images/sglvrt.gif"> ,</sub></sup></pre><P>
<a name="0746_12be">then we have the <I><B>uniform probability distribution</I> </B>on <I>S</I>. In such a case the experiment is often described as &quot;picking an element of <I>S</I> at random.&quot;<P>
<a name="0746_12bf">As an example, consider the process of flipping a<B> </B><I><B>fair coin</I>, </B>one for which the probability of obtaining a head is the same as the probability of  obtaining a tail, that is, 1/2. If we flip the coin n times,we have the uniform probability distribution defined on the sample space <I>S</I> = {<FONT FACE="Courier New" SIZE=2>H, T</FONT>}<I><SUP>n</I></SUP>, a set of size 2<I><SUP>n</I></SUP>. Each elementary event in <I>S</I> can be represented as a string of length <I>n</I> over {<FONT FACE="Courier New" SIZE=2>H, T</FONT>}, and each occurs with probability 1/2<I><SUP>n</I></SUP>. The event<P>
<pre><I>A</I> = {exactly <I>k</I> heads and exactly <I>n</I> - <I>k</I> tails occur}</sub></sup></pre><P>
is a subset of <I>S</I> of size <img src="106_b.gif">, since there are <img src="106_c.gif"> strings of length <I>n</I> over {<FONT FACE="Courier New" SIZE=2>H, T</FONT>} that contain exactly <I>k</I> <FONT FACE="Courier New" SIZE=2>H'S</FONT>. The probability of event <I>A</I> is thus <img src="106_d.gif">.<P>
<P>







<h2>Continuous uniform probability distribution</h2><P>
The continuous uniform probability distribution is an example of a probability distribution in which all subsets of the sample space are not considered to be events. The continuous uniform probability distribution is defined over a closed interval [<I>a, b</I>] of the reals, where <I>a</I> &lt; <I>b</I>. Intuitively, we want each point in the interval [<I>a, b</I>] to be &quot;equally likely.&quot; There is an uncountable number of points, however, so if we give all points the same finite, positive probability, we cannot simultaneously satisfy axioms 2 and 3. For this reason, we would like to associate a probability only with <I>some</I> of the subsets of <I>S</I> in such a way that the axioms are satisfied for these events.<P>
<a name="0747_12c0">For any closed interval [<I>c,d</I>], where <I>a </I><img src="../images/lteq12.gif"> c <I><img src="../images/lteq12.gif"> d </I><img src="../images/lteq12.gif"> b<I>, the</I> <B>continuous uniform probability distribution<I></B> defines the probability of the event [</I>c, d<I>] to be</I><P>
<img src="107_a.gif"><P>
Note that for any point <I>x</I> = [<I>x, x</I>], the probability of <I>x</I> is 0. If we remove the endpoints of an interval [<I>c, d</I>], we obtain the open interval (<I>c, d</I>). Since [<I>c, d</I>] = [<I>c, c</I>] <img src="../images/wideu.gif"> (<I>c, d</I>) <img src="../images/wideu.gif"> [<I>d, d</I>], axiom 3 gives us Pr{[<I>c, d</I>]} = Pr{(<I>c, d</I>)}. Generally, the set of events for the continuous uniform probability distribution is any subset of [<I>a, b</I>] that can be obtained by a finite or countable union of open and closed intervals.<P>
<P>