Probabilistic Method

Aditya Ghosh
26 February, 2021
Probability
Let Ω be the set of all possible outcomes of a random experiment; we call Ω a sample
space. Here we will focus on finite sample spaces only. Any subset of Ω will be called
an event. We assign a probability to each subset of Ω. Formally, a probability P on Ω
is a function from the power set of Ω (the set of all subsets of Ω) to [0, 1] satisfying the
following rules: P(Ω) = 1 and P(A ∪ B) = P(A) + P(B) holds whenever A, B are disjoint
subsets of Ω.

Union bound
For any events A1 , A2 , . . . , An we have
n
! n
[ X
P Ak ≤ P (Ak ) .
k=1 k=1

Random variables
Suppose we have a finite sample space Ω. Then a random variable X is any function from
Ω to R. (Thus, random variable = a function of the (random) outcome.)

Expectation
Let X be a random variable taking finitely many values, say x1 , x2 , . . . , xn , each with
some probability. We define the expected value of X as
n
X
E [X] = xk P(X = xk ).
k=1

Linearity of expectation

For any two random variables X and Y (defined on same Ω) each taking finitely many
values, it holds that
E[X + Y ] = E[X] + E[Y ].
It is not hard to see that the above easily generalizes to any number of random variables:

E[X1 + · · · + Xn ] = E[X1 ] + · · · + E[Xn ].

Also note that E[aX + b] = aE[X] + b for any constants a and b.

1
 Indicator random variables
For any (random) event A we can define its indicator as
(
1 if event A occurs,
1A =
0 if event A does not occur.

Note that E[1A ] = P(A), i.e., the expected value of the indicator 1A is nothing but the
probability of the event A.

Independence

Two events are defined to be independent iff P(A ∩ B) = P(A) · P(B). If X, Y are two
random variables defined on same Ω (finite), each taking finitely many values, then X
and Y are said to be independent iff P(X = x, Y = y) = P(X = x) · P(Y = y) holds for
every x, y. For such X, Y it holds that E[XY ] = E[X] · E[Y ].

Problems
1. A university provides a list of optional courses, each of which may be offered in either of
two semesters. Suppose that each student chooses r many from that list and sends it to the
administrator as their ‘preferred courses’. If the number of students is less than 2r−1 , show
that it is always possible for the administrator to distribute the courses to the two semesters
such that each student has at least one preferred course offered in each of the two semesters.

2. At a nursery, 2006 babies sit in a circle. Suddenly, each baby randomly pokes either the
baby to its left or to its right. What is the expected value of the number of unpoked babies?

3. Suppose one is given n real numbers, not all zero, but such that their sum is zero. Prove
that one can label these numbers a1 , a2 , . . . , an in such a manner that

a1 a2 + a2 a3 + · · · + an a1 < 0.

4. Given any n red points and n blue points, suppose we connect at least n2 − n + 1 pairs of
opposite colors. Prove that we can select n segments, no two of which share an endpoint.

5. In an assembly there are 30 delegates, who have formed 300 committees of 10 persons each.
Prove that one can find two committees having at least four common members.

6. Let A be any set of n residues mod n2 . Show that there is a set B of n residues mod n2 such
that at least half of the residues mod n2 can be written as a + b with a ∈ A and b ∈ B.

7. In a class, each boy is friends with at least one girl. Show that there exists a group of at
least half of the students, such that each boy in the group is friends with an odd number of
the girls in the group.

2
 Problem 7 (Russia 1999)

In a class, each boy is friends with at least one girl. Show that there exists a group of at
least half of the students, such that each boy in the group is friends with an odd number
of the girls in the group.

Sketch of a solution. Choose girls independently with probability 1/2, and then let the set of
boys be all of those who have an odd number of friends in the girl group. Let X be the number
of boys and girls selected, and break this into the sum of indicators. For each girl, obviously
the indicator adds 1/2 to the sum. For each boy, the probability that he joins is precisely the
probability that the no. of heads in k tosses of a fair coin is odd, where k was the number of
girls in that group whom he knows. To see that this probability is 1/2, note that the final flip
independently flips or retains the parity of the number of heads in the earlier tosses, hence odd
with probability 1/2. 

15