
Mean and Insensitive. Random Permutations. 255
as the choice of i and j is clearly insignificant.
The variables X
i,j
, or in general, variables taking values 0 and 1 depending
on the occurrence of an event, are called indicator random variables, and are
often very useful.
The following theorem is a not very subtle, but very general, tool in proving
that it is unlikely that a variable is larger than a multiple of its expectation.
(We will state the theorem in a special case that is relevant in our combina-
torial applications, but a more general treatment is possible.)
THEOREM 6.28
[Markov’s Inequality] Let X be any nonnegative random variable that has