Page 486 - Discrete Mathematics and Its Applications

7.2 Probability Theory 465

can use it as one of the two primes used in an encryption key for the RSA cryptosystem. If n is
actually composite and is used as part of the key, the procedures used to decrypt messages will
not produce the original encrypted message. The key is then discarded and two new possible
primes are used. ▲

The Probabilistic Method

We discussed existence proofs in Chapter 1 and illustrated the difference between constructive
existence proofs and nonconstructive existence proofs. The probabilistic method, introduced by
Paul Erd˝os and Alfréd Rényi, is a powerful technique that can be used to create nonconstructive
existence proofs. To use the probabilistic method to prove results about a set S, such as the
existence of an element in S with a specified property, we assign probabilities to the elements
of S. We then use methods from probability theory to prove results about the elements of S.
In particular, we can show that an element with a specified property exists by showing that the
probability an element x ∈ S has this property is positive. The probabilistic method is based on
the equivalent statement in Theorem 3.

THEOREM 3 THE PROBABILISTIC METHOD If the probability that an element chosen at random
from a S does not have a particular property is less than 1, there exists an element in S with
this property.

An existence proof based on the probabilistic method is nonconstructive because it does not find
a particular element with the desired property.
We illustrate the power of the probabilistic method by finding a lower bound for the Ramsey
number R(k, k). Recall from Section 6.2 that R(k, k) equals the minimum number of people at
a party needed to ensure that there are at least k mutual friends or k mutual enemies (assuming
that any two people are friends or enemies).

THEOREM 4 If k is an integer with k ≥ 2, then R(k, k) ≥ 2 k/2 .

Proof:Wenotethatthetheoremholdsfork = 2andk = 3becauseR(2, 2) = 2andR(3, 3) = 6,
as was shown in Section 6.2. Now suppose that k ≥ 4. We will use the probabilistic method to
show that if there are fewer than 2 k/2 people at a party, it is possible that no k of them are mutual
friends or mutual enemies. This will show that R(k, k) is at least 2 k/2 .
To use the probabilistic method, we assume that it is equally likely for two people to be
friends or enemies. (Note that this assumption does not have to be realistic.) Suppose there
n

are n people at the party. It follows that there are k different sets of k people at this
party, which we list as S 1 ,S 2 ,...,S n . Let E i be the event that all k people in S i are ei-
( )
k
ther mutual friends or mutual enemies. The probability that there are either k mutual friends
n
( )
k
or k mutual enemies among the n people equals p( i=1 E i ).
According to our assumption it is equally likely for two people to be friends or enemies.
The probability that two people are friends equals the probability that they are enemies; both
k

probabilities equal 1/2. Furthermore, there are 2 = k(k−1)/2 pairs of people in S i because
there are k people in S i . Hence, the probability that all k people in S i are mutual friends and the
probability that all k people in S i are mutual enemies both equal (1/2) k(k−1)/2 . It follows that
p(E i ) = 2(1/2) k(k−1)/2 .