5.1.IntroductionThe probabilistic m

5.1.
Introduction
The probabilistic method is a technique for analyzing the properties of the elements
ofasetbyintroducingaprobabilityspaceoverthissetandthenstudyingarandomly
chosen element. The majority of its applications have been to combinatorial and
graph theory problems.
5.2.
Using Probability To Prove Existence
Suppose that we are interested in proving that there is an element of a set S that has a
certain specified characteristic. One way to accomplish this is to consider a random
element X of S, and then show that the probability that X has the characteristic is
positive. This latter step is usually accomplished by showing that the probability
of the complementary event, that X does not have the characteristic, is less than 1.
Example 5.2a
Suppose that each of the
_ _
n
2
edges in the complete graph on
n vertices is to be painted either red or blue. A question of interest is, for a fixed
integer k, to determine conditions on k and n that make it possible to color the
edges so that no set of k vertices has all of its
_ _
k
2
connecting edges the same color.
To obtain such conditions suppose that each edge is, independently, equally
likely to be colored either red or blue. Now, number the
_ _
n
k
sets of k vertices, and
let, for i
=
1
,...,
_ _
n
k
,
E be the event that all of the connecting edges of the ith
i
set of k vertices are the same color. Because each of the
_ _
k
2
connecting edges of a
set of k vertices is equally likely to be either red or blue, it follows that
P(E )
i
=
2(1
/
2)
k(k
−
1)
/
2
151



152
5
The Probabilistic Method
Therefore,
P
_
_
i
E
i
_
≤
_
i
P(E )
i
=
_ _
n
k
2(1
/
2)
k(k
−
1)
/
2
Hence, if
_ _
n
k
2(1
/
2)
k(k
−
1)
/
2
<
1
then the probability that at least one of the sets of k vertices has all of its connecting
edges the same color is less than 1. However, this implies that there is a positive
probability that no set of k vertices has all of its connecting edges the same color,
implying that there is at least one coloring that yields this result.
✷
Example 5.2b
The Result of a Round-Robin Tournament.
A
round-robin tournament of n contestants is one in which each of the
_ _
n
2
pairs
of contestants play each other exactly once, with the outcome of any play being
that one of the contestants wins and the other loses. For a fixed integer k
,
k
<
n
,
a problem of interest is to specify a sufficient condition on k and n that makes it
is possible for the tournament outcome to have the property that for every set of k
players there is a player who beats each member of this set.
To determine such a sufficient condition, suppose that the outcomes of different
games are independent and that each game is equally likely to be won by either
contestant. Now, if A is the event that for every set of k players there is a player
who beats each member of this set, then A
c
is the event that there exists a set
of k players such that no contestant beats each member of this set. Thus, if we
arbitrarily number the
_ _
n
k
sets of size k, and let B denote the event that no one
i
beats all k members of the ith set, then
P(A )
c
=
P
_
_
i
B
i
_
≤
_
i
P(B )
i
Now, the probability that any specified player not in the ith set does not beat all
members of this set is 1
−
(1
/
2)
k
.
Thus, by independence,
P(B )
i
=
[1
−
(1
/
2)
k n
]
−
k
which implies that
P(A )
c
≤
_ _
n
k
[1
−
(1
/
2)
k n
]
−
k



5.3.
Obtaining Bounds from Expectations
153
Hence, if
_ _
n
k
[1
−
(1
/
2)
k n
]
−
k
<
1
then there is a positive probability that the outcome of the tournament has the
desired property, thus showing that such an outcome is possible.
✷
5.3.
Obtaining Bounds from Expectations
Let f be a function on the elements of a finite set S, and suppose that we are
interested in
m
=
max
s
∈
S
f (s)
Useful lower bounds can often be obtained by letting X be a random element
of S for which the expected value of f (X) is computable, and then noting that
m
≥
f (X) implies that
m
≥
E[ f (X)]
with strict inequality if f (X) is not a constant random variable.
Example 5.3a
The k of r out of n circular reliability system k
≤
r
≤
n
consists of n components, each of which is either functioning or failed, that are
arranged in a circular fashion. The system itself is said to be functional if there is no
block of r consecutive components of which at least k are failed. Show that there
is no way to arrange 47 components, 8 of which are failed, to make a functional 3
of 12 out of 47 circular system.
Solution:
We must show that for any ordering of the 47 components there
is a block of 12 consecutive components that contain at least 3 failures. Thus,
consider any ordering, and randomly choose a component in such a manner
that each of the 47 components is equally likely to be chosen. Now, consider
that component along with the next 11 when moving in a clockwise manner
and let X denote the number of failures in that group of 12. To determine E[X],
arbitrarily number the eight failed components and let, for i
=
1
,...,
8
,
X
i
=
_
1
,
if failed component i is among the group of 12 components
0
,
otherwise



154
5
The Probabilistic Method
Then,
X
=
8
_
i
=
1
X
i
and so
E[X]
=
8
_
i
=
1
E[X ]
i
Because X
i
will equal 1 if the randomly selected component is either failed
component number i or any of its 11 neighboring components in the counter-
clockwise direction, it follows that E[X ]
i
=
12
/
47
.
Hence,
E[X]
=
8(12
/
47)
=
96
/
47
Because E[X]
>
2
it follows that there is at least one possible set of 12
consecutive components that contain at least three failures.
✷
Example 5.3b
The Maximum Number of Hamiltonian Paths
in a Tournament.
Consider a round-robin tournament of n
>
2
contestants
(see Example 5
.
2b for a definition), and suppose that the players are numbered
1
,
2
,
3
,...,
n
.
The permutation i
1
,
i
2
,...,
i
n
is said to be a Hamiltonian path if
i
1
beats i
2
,
i
2
beats i
3
,...,
and i
n
−
1
beats i
n
.
A problem of some interest is to
determine the largest possible number of Hamiltonian paths.
As an illustration, suppose that there are three players. If one of them wins twice,
then there is a single Hamiltonian path (for instance, if 1 wins twice and 2 beats 3
then the only Hamiltonian path is 1
,
2
,
3);
on the other hand, if each of the players
wins once, there are three Hamiltonian paths (for instance, if 1 beats 2, 2 beats
3, and 3 beats 1, then 1
,
2
,
32
,
3
,
1
,
and 3
,
1
,
2
,
are all Hamiltonians). Hence,
when n
=
3, there is a maximum of three Hamiltonian paths.
We now show that there is an outcome of the tournament that results in more
than n!
/
2
n
−
1
Hamiltonian paths. To do so, let us suppose that the results of the
_ _
n
2
games are independent, with each contestant being equally likely to win each
encounter. Let X denote the number of Hamiltonian paths that result. To determine
E[X]
,
number the n! permutations, and for i
=
1
,...,
n! let
X
i
=
_
1
,
if permutation i is a Hamiltonian
0
,
otherwise
Because
X
=
_
i
X
i



5.3.
Obtaining Bounds from Expectations
155
it follows that
E[X]
=
_
i
E[X ]
i
However, as the probability that any specified permutation is a Hamiltonian is, by
the assumed independence of game outcomes, (1
/
2)
n
−
1
,
it follows that
E[X ]
i
=
P
{
X
1
=
1
}=
(1
/
2)
n
−
1
Therefore,
E[X]
=
n!(1
/
2)
n
−
1
which, as X is not a constant random variable, implies that there is an outcome of
the tournament having more than n!
/
2
n
−
1
Hamiltonian paths.
✷
In our previous examples the random element X of the set S was equally likely
to be any of the elements of S. However, as indicated in our next two examples,
we can sometimes obtain better results by choosing a different distribution for X.
Example 5.3c
The Maximum Cut Problem.
Consider the complete
graph on the vertices
{
1
,...,
n
}
,
where n
=
2
k is even, and suppose that for each
pair of distinct vertices i
=
j we are given a nonnegative number c(i
,
j)
=
c( j
,
i)
that we shall call the capacity of the edge (i
,
j). Any partition of the vertices into
nonempty sets X and X , is called a cut. The quantity
c
c(X
,
X )
c
=
_
i
∈
X j
_
∈
X
c
c(i
,
j)
equal to the sum of the capacities of all edges having one vertex in X and the other
in X
c
,
is called the capacity of the cut X
,
X . Let
c
m
=
max c(X
X
,
X )
c
be the maximal cut capacity, and suppose that we want to determine a lower bound
for m.
To obtain a lower bound, first consider the problem of dividing the vertices into
disjoint pairs so as to maximize the sum of the capacities of the k pairs. That is,
for a partition M of the vertices into k pairs, let
c(M)
=
_
(i
,
j)
∈
M
c(i
,
j)



156
5
The Probabilistic Method
and let M
∗
be such that
max c(M)
M
=
c(M )
∗
Also, let C
=

i
<
j
c(i
,
j) denote the sum of all the edge capacities.
✷
Proposition 5.3.1
m
≥
C
/
2
+
c(M )
∗
/
2
Proof
Let (i
r
,
j )
r
,
r
=
1
,...,
k
,
be the pairs of M , and suppose that one
∗
member from each pair is independently and randomly chosen. Let X consist of
the k randomly chosen vertices, and X
c
consist of the others. Then, let
I(i
,
j)
=
_
0
,
if i
∈
X
,
j
∈
X
or
i
∈
X
c
,
j
∈
X
c
1
,
otherwise
That is, I(i
,
j) is equal to 1 if i and j are not both in X or in X . Consequently,
c
we have
c(X
,
X )
c
=
_ _
j
i
<
j
c(i
,
j)I(i
,
j)
implying that
E[c(X
,
X )]
c
=
_ _
j
i
<
j
c(i
,
j)E[I(i
,
j)]
=
_ _
j
i
<
j
c(i
,
j)P
{
I(i
,
j)
=
1
}
However,
P
{
I(i
,
j)
=
1
}=
_
1
,
if (i
,
j)
∈
M
∗
1
/
2
,
if (i
,
j)
/
∈
M
∗
and the result follows as m
≥
E[C(X
,
X )].
c
✷
5.4.
The Maximum Weighted Independent Set Problem:
A Bound and a Random Algorithm
Consider a graph with vertex set
{
1
,...,
n
}
,
and call a set of vertices independent
if no pair of vertices in this set are adjacent, where we say that two edges i and j are
adjacent if (i
,
j) is an edge ofthe graph. For instance, for the graph of Figure 5.1, the



5.4.
The Maximum Weighted Independent Set Problem
157
6
5
3
4
2
1
Figure 5.1.
1
2
3
4
5
6
Figure 5.2.
set of vertices
{
2

Kết quả (Việt) 1:

5.1.Giới thiệuCác phương pháp xác suất là một kỹ thuật cho việc phân tích các thuộc tính của các yếu tốofasetbyintroducingaprobabilityspaceoverthissetandthenstudyingarandomlyphần tử được lựa chọn. Phần lớn các ứng dụng của nó đã đến tổ hợp vàvấn đề lý thuyết đồ thị.5.2.Sử dụng xác suất để chứng minh sự tồn tạiGiả sử rằng chúng tôi đang quan tâm trong chứng minh là có một phần tử của một tập hợp S có mộtmột số đặc tính specified. Một cách để thực hiện việc này là để xem xét một ngẫu nhiênphần tử X của S, và sau đó cho thấy xác suất rằng X có đặc tính làtích cực. Bước thứ hai này thường được thực hiện bằng cách hiển thị mà xác suấtcủa sự kiện bổ sung, X rằng không có các đặc tính, là ít hơn 1.Ví dụ 5.2aGiả sử rằng mỗi của các_ _n2cạnh trong đồ thị đầy đủ ngàyn đỉnh là phải được sơn màu đỏ hoặc màu xanh. Một câu hỏi quan tâm là, đối với một fixedsố nguyên k, để xác định điều kiện về k và n mà làm cho nó có thể để màu sắc cácđa cung để không có tập các k đỉnh có tất cả của nó_ _k2kết nối đa cung cùng một màu sắc.Để có được điều kiện như vậy giả sử rằng mỗi cạnh là, độc lập, như nhaukhả năng là màu đỏ hoặc màu xanh. Bây giờ, số các_ _nkbộ k đỉnh, vàcho phép, cho tôi=1,...,_ _nk,E là sự kiện rằng tất cả các cạnh kết nối của ithtôitập hợp các k đỉnh có cùng màu. Bởi vì mỗi người trong số các_ _k2kết nối các cạnh của mộttập hợp các đỉnh k là như nhau có khả năng là một trong hai màu đỏ hoặc màu xanh, nó sau đóP (E)tôi=2 (1./2)k (k−1)/2151 1525Các phương pháp xác suấtDo đó,P__tôiEtôi_≤_tôiP (E)tôi=_ _nk2 (1./2)k (k−1)/2Do đó, nếu_ _nk2 (1./2)k (k−1)/2<1sau đó xác suất đó ít nhất một bộ đỉnh k có tất cả các kết nốicạnh cùng màu là ít hơn 1. Tuy nhiên, điều này có nghĩa là có một tích cựcxác suất rằng không có bộ k đỉnh có tất cả các kết nối đa cung cùng màu,ngụ ý là có ít nhất một màu mang lại kết quả này.✷Ví dụ 5.2bKết quả của một giải đấu vòng tròn.Agiải đấu vòng tròn n thí sinh là một trong đó mỗi của các_ _n2Cặpthí sinh chơi nhau đúng một lần, với kết quả của bất kỳ người chơilà một trong những thí sinh thắng và khác mất. Cho một fixed số nguyên k,k<n,một vấn đề quan tâm là để chỉ định một điều kiện sufficient trên k và n mà làm cho nócó thể cho kết quả giải đấu có tài sản mà cho mọi tập kngười chơi có là một cầu thủ người nhịp đập mỗi thành viên của nhóm này.Để xác định một điều kiện sufficient, giả sử rằng các kết quả khác nhautrò chơi là độc lập và rằng mỗi trò chơi là như nhau có khả năng để được chiến thắng bởi một trong haithí sinh. Bây giờ, nếu A là sự kiện cho mỗi bộ k người chơi có là một cầu thủngười nhịp đập mỗi thành viên trong tập này, sau đó Aclà sự kiện rằng có tồn tại một tập hợpcủa người chơi k như vậy mà không có thí sinh nhịp đập mỗi thành viên của điều này thiết lập. Vì vậy, nếu chúng tôitự ý số các_ _nksets of size k, and let B denote the event that no oneibeats all k members of the ith set, thenP(A )c=P__iBi_≤_iP(B )iNow, the probability that any specified player not in the ith set does not beat allmembers of this set is 1−(1/2)k.Thus, by independence,P(B )i=[1−(1/2)k n]−kwhich implies thatP(A )c≤_ _nk[1−(1/2)k n]−k 5.3.Obtaining Bounds from Expectations153Hence, if_ _nk[1−(1/2)k n]−k<1then there is a positive probability that the outcome of the tournament has thedesired property, thus showing that such an outcome is possible.✷5.3.Obtaining Bounds from ExpectationsLet f be a function on the elements of a finite set S, and suppose that we areinterested inm=maxs∈Sf (s)Useful lower bounds can often be obtained by letting X be a random elementof S for which the expected value of f (X) is computable, and then noting thatm≥f (X) implies thatm≥E[ f (X)]with strict inequality if f (X) is not a constant random variable.Example 5.3aThe k of r out of n circular reliability system k≤r≤nconsists of n components, each of which is either functioning or failed, that arearranged in a circular fashion. The system itself is said to be functional if there is noblock of r consecutive components of which at least k are failed. Show that thereis no way to arrange 47 components, 8 of which are failed, to make a functional 3of 12 out of 47 circular system.Solution:We must show that for any ordering of the 47 components thereis a block of 12 consecutive components that contain at least 3 failures. Thus,consider any ordering, and randomly choose a component in such a mannerthat each of the 47 components is equally likely to be chosen. Now, considerthat component along with the next 11 when moving in a clockwise mannerand let X denote the number of failures in that group of 12. To determine E[X],arbitrarily number the eight failed components and let, for i=1,...,8,Xi=_1,if failed component i is among the group of 12 components0,otherwise 1545The Probabilistic MethodThen,X=8_i=1Xiand soE[X]=8_i=1E[X ]iBecause Xiwill equal 1 if the randomly selected component is either failedcomponent number i or any of its 11 neighboring components in the counter-clockwise direction, it follows that E[X ]i=12/47.Hence,E[X]=8(12/47)=96/47Because E[X]>2it follows that there is at least one possible set of 12consecutive components that contain at least three failures.✷Example 5.3bThe Maximum Number of Hamiltonian Pathsin a Tournament.Consider a round-robin tournament of n>2contestants(see Example 5.2b for a definition), and suppose that the players are numbered1,2,3,...,n.The permutation i1,i2,...,inis said to be a Hamiltonian path ifi1beats i2,i2beats i3,...,and in−1beats in.A problem of some interest is todetermine the largest possible number of Hamiltonian paths.As an illustration, suppose that there are three players. If one of them wins twice,
then there is a single Hamiltonian path (for instance, if 1 wins twice and 2 beats 3
then the only Hamiltonian path is 1
,
2
,
3);
on the other hand, if each of the players
wins once, there are three Hamiltonian paths (for instance, if 1 beats 2, 2 beats
3, and 3 beats 1, then 1
,
2
,
32
,
3
,
1
,
and 3
,
1
,
2
,
are all Hamiltonians). Hence,
when n
=
3, there is a maximum of three Hamiltonian paths.
We now show that there is an outcome of the tournament that results in more
than n!
/
2
n
−
1
Hamiltonian paths. To do so, let us suppose that the results of the
_ _
n
2
games are independent, with each contestant being equally likely to win each
encounter. Let X denote the number of Hamiltonian paths that result. To determine
E[X]
,
number the n! permutations, and for i
=
1
,...,
n! let
X
i
=
_
1
,
if permutation i is a Hamiltonian
0
,
otherwise
Because
X
=
_
i
X
i



5.3.
Obtaining Bounds from Expectations
155
it follows that
E[X]
=
_
i
E[X ]
i
However, as the probability that any specified permutation is a Hamiltonian is, by
the assumed independence of game outcomes, (1
/
2)
n
−
1
,
it follows that
E[X ]
i
=
P
{
X
1
=
1
}=
(1
/
2)
n
−
1
Therefore,
E[X]
=
n!(1
/
2)
n
−
1
which, as X is not a constant random variable, implies that there is an outcome of
the tournament having more than n!
/
2
n
−
1
Hamiltonian paths.
✷
In our previous examples the random element X of the set S was equally likely
to be any of the elements of S. However, as indicated in our next two examples,
we can sometimes obtain better results by choosing a different distribution for X.
Example 5.3c
The Maximum Cut Problem.
Consider the complete
graph on the vertices
{
1
,...,
n
}
,
where n
=
2
k is even, and suppose that for each
pair of distinct vertices i
=
j we are given a nonnegative number c(i
,
j)
=
c( j
,
i)
that we shall call the capacity of the edge (i
,
j). Any partition of the vertices into
nonempty sets X and X , is called a cut. The quantity
c
c(X
,
X )
c
=
_
i
∈
X j
_
∈
X
c
c(i
,
j)
equal to the sum of the capacities of all edges having one vertex in X and the other
in X
c
,
is called the capacity of the cut X
,
X . Let
c
m
=
max c(X
X
,
X )
c
be the maximal cut capacity, and suppose that we want to determine a lower bound
for m.
To obtain a lower bound, first consider the problem of dividing the vertices into
disjoint pairs so as to maximize the sum of the capacities of the k pairs. That is,
for a partition M of the vertices into k pairs, let
c(M)
=
_
(i
,
j)
∈
M
c(i
,
j)



156
5
The Probabilistic Method
and let M
∗
be such that
max c(M)
M
=
c(M )
∗
Also, let C
=

i
<
j
c(i
,
j) denote the sum of all the edge capacities.
✷
Proposition 5.3.1
m
≥
C
/
2
+
c(M )
∗
/
2
Proof
Let (i
r
,
j )
r
,
r
=
1
,...,
k
,
be the pairs of M , and suppose that one
∗
member from each pair is independently and randomly chosen. Let X consist of
the k randomly chosen vertices, and X
c
consist of the others. Then, let
I(i
,
j)
=
_
0
,
if i
∈
X
,
j
∈
X
or
i
∈
X
c
,
j
∈
X
c
1
,
otherwise
That is, I(i
,
j) is equal to 1 if i and j are not both in X or in X . Consequently,
c
we have
c(X
,
X )
c
=
_ _
j
i
<
j
c(i
,
j)I(i
,
j)
implying that
E[c(X
,
X )]
c
=
_ _
j
i
<
j
c(i
,
j)E[I(i
,
j)]
=
_ _
j
i
<
j
c(i
,
j)P
{
I(i
,
j)
=
1
}
However,
P
{
I(i
,
j)
=
1
}=
_
1
,
if (i
,
j)
∈
M
∗
1
/
2
,
if (i
,
j)
/
∈
M
∗
and the result follows as m
≥
E[C(X
,
X )].
c
✷
5.4.
The Maximum Weighted Independent Set Problem:
A Bound and a Random Algorithm
Consider a graph with vertex set
{
1
,...,
n
}
,
and call a set of vertices independent
if no pair of vertices in this set are adjacent, where we say that two edges i and j are
adjacent if (i
,
j) is an edge ofthe graph. For instance, for the graph of Figure 5.1, the



5.4.
The Maximum Weighted Independent Set Problem
157
6
5
3
4
2
1
Figure 5.1.
1
2
3
4
5
6
Figure 5.2.
set of vertices
{
2