Mathematics for Computer Science

17.3. Distribution Functions 583

f 20 .k/

0:18

0:16

0:14

0:12

0:10

0:08

0:06

0:04

0:02

0

k

0 5 10 15 20

Figure 17.4 The pdf for the unbiased binomial distribution fornD 20 ,f 20 .k/.

This is because there are

n

k

sequences ofncoin tosses with exactlykheads, and
each such sequence has probability 2 n.
A plot off 20 .k/is shown in Figure 17.4. The most likely outcome iskD 10
heads, and the probability falls off rapidly for larger and smaller values ofk. The
falloff regions to the left and right of the main hump are called thetails of the
distribution.
In many fields, including Computer Science, probability analyses come down to
getting small bounds on the tails of the binomial distribution. In the context of a
problem, this typically means that there is very small probability that something
badhappens, which could be a server or communication link overloading or a ran-
domized algorithm running for an exceptionally long time or producing the wrong
result.
As an example, we can calculate the probability of flipping at most 25 heads
in 100 tosses of a fair coin and see that it is very small, namely, less than 1 in
3,000,000.
In fact, the tail of the distribution falls off so rapidly that the probability of flip-
ping exactly 25 heads is nearly twice the probability of flipping fewer than 25
heads! That is, the probability of flipping exactly 25 heads —small as it is —
is still nearly twice as large as the probability of flipping exactly 24 headsplusthe
probability of flipping exactly 23 headsplus... the probability of flipping no heads.