Page 515 - Discrete Mathematics and Its Applications

494 7 / Discrete Probability

b) Let I j,k denote the random variable that equals 1 if The covariance of two random variables X and Y on a sample
the jth smallest element and the kth smallest element space S, denoted by Cov(X, Y), is defined to be the expected
of the initial list are ever compared as the quick sort value of the random variable (X − E(X))(Y − E(Y)). That
algorithm sorts the list and equals 0 otherwise. Show is, Cov(X, Y) = E((X − E(X))(Y − E(Y))).
n k−1
I
that X = j=1 j,k .
k=2 44. Show that Cov(X, Y) = E(XY) − E(X)E(Y), and use
n k−1
c) Show that E(X) = p(the jth smallest this result to conclude that Cov(X, Y) = 0if X and Y are
k=2 j=1
element and the kth smallest element are compared). independent random variables.
d) Show that p(the jth smallest element and the kth 45. Show that V(X + Y) = V(X) + V(Y) + 2Cov(X, Y).
smallest element are compared), where k> j, equals 46. Find Cov(X, Y) if X and Y are the random variables with
2/(k − j + 1).
X((i, j)) = 2i and Y((i, j)) = i + j, where i and j are
e) Use parts (c) and (d) to show that E(X) = the numbers that appear on the first and second of two
n
2(n + 1)( 1/i) − 2(n − 1).
i=2 dice when they are rolled.
n
f) Conclude from part (e) and the fact that 1/j ≈
j=1 47. When m balls are distributed into n bins uniformly at
ln n + γ , where γ = 0.57721 ... is Euler’s constant,
random, what is the probability that the first bin remains
that the average number of comparisons used by the
empty?
quick sort algorithm is (n log n).
∗ 43. What is the variance of the number of fixed elements, 48. What is the expected number of balls that fall into the first
that is, elements left in the same position, of a randomly bin when m balls are distributed into n bins uniformly at
selected permutation of n elements? [Hint: Let X denote random?
thenumberoffixedpointsofarandompermutation.Write 49. What is the expected number of bins that remain empty
X = X 1 + X 2 + ··· + X n , where X i = 1 if the permu- when m balls are distributed into n bins uniformly at ran-
tation fixes the ith element and X i = 0 otherwise.] dom?
Key Terms and Results

TERMS distribution of a random variable X: the set of pairs
(r, p(X = r)) for r ∈ X(S)
sample space: the set of possible outcomes of an experiment
uniform distribution: the assignment of equal probabilities
event: a subset of the sample space of an experiment
to the elements of a finite set
probability of an event (Laplace’s definition): the number expected value of a random variable: the weighted av-
of successful outcomes of this event divided by the number erage of a random variable, with values of the random
of possible outcomes variable weighted by the probability of outcomes, that is,

probability distribution: a function p from the set of all out- E(X) = s∈S p(s)X(s)
comes of a sample space S for which 0 ≤ p(x i ) ≤ 1 for geometric distribution: the distribution of a random variable
n k−1
i = 1, 2,...,n and i=1 p(x i ) = 1, where x 1 ,...,x n are X such that p(X = k) = (1 − p) p for k = 1, 2,... for
the possible outcomes some real number p with 0 ≤ p ≤ 1.
probability of an event E: the sum of the probabilities of the independent random variables: random variables X and Y
outcomes in E such that p(X = r 1 and Y = r 2 ) = p(X = r 1 )p(Y = r 2 )
for all real numbers r 1 and r 2
p(E|F) (conditional probability of E given F): the ratio
variance of a random variable X: the weighted average of the
p(E ∩ F)/p(F)
square of the difference between the value of X and its ex-
independent events: events E and F such that p(E ∩ F) = pected value E(X), with weights given by the probability
p(E)p(F) 2
of outcomes, that is, V(X) = (X(s) − E(X)) p(s)
s∈S
pairwise independent events: events E 1 ,E 2 ,...,E n such standard deviation of a random variable X: the square root
√
that p(E i ∩ E j ) = p(E i )p(E j ) for all pairs of integers i of the variance of X, that is, σ(X) = V(X)
and j with 1 ≤ j< k ≤ n
Bernoulli trial: an experiment with two possible outcomes
mutually independent events: events E 1 ,E 2 ,...,E n such probabilistic (or Monte Carlo) algorithm: an algorithm in
)
that p(E i 1 ∩ E i 2 ∩ ··· ∩ E i m ) = p(E i 1 )p(E i 2 ) ··· p(E i m which random choices are made at one or more steps
whenever i j ,j = 1, 2,...,m, are integers with 1 ≤ i 1 <
probabilistic method: a technique for proving the existence
i 2 < ··· <i m ≤ n and m ≥ 2
of objects in a set with certain properties that proceeds by
random variable: a function that assigns a real number to each assigning probabilities to objects and showing that the prob-
possible outcome of an experiment ability that an object has these properties is positive