[SOLVED] Probability & statistics for eecs homework 01

1. Define
� n
k
�
as the number of ways to partition {1, 2, . . . , n} into k non-empty subsets,
or the number of ways to have n students split up into k groups such that each group
has at least one student. For example,
� 4
2
�
= 7 because:
•{1}, {2, 3, 4}, • {1, 2}, {3, 4},
•{2}, {1, 3, 4}, • {1, 3}, {2, 4},
•{3}, {1, 2, 4}, • {1, 4}, {2, 3},
•{4}, {1, 2, 3}. Prove the following identities:
(a)
� n + 1
k
�
=
� n
k − 1
�
+ k
� n
k
�
.
(b)
�n
j=k
� n
j
� � j
k
�
=
� n + 1
k + 1
�
.2. A norepeatword is a sequence of at least one (and possibly all) of the usual 26 letters
a, b, c, . . . , z, with repetitions not allowed. For example, “course” is a norepeatword,
but “statistics” is not. Order matters, e.g., “course” is not the same as “source”. A
norepeatword is chosen randomly, with all norepeatwords equally likely. Show that the
probability that it uses all 26 letters is very close to 1/e.3. An academic department offers 8 lower level courses: {L1, L2, . . . , L8} and 10 higher
level courses: {H1, H2, . . . , H10}. A valid curriculum consists of 4 lower level courses
and 3 higher level courses.
(a) How many different curricula are possible?
(b) Suppose that {H1, . . . , H5} have L1 as a prerequisite, and {H6, . . . , H10} have L2
and L3 as prerequisites, i.e., any curricula which involve, say, one of {H1, . . . , H5}
must also include L1. How many different curricula are there?4. In the birthday problem, we assumed that all 365 days of the year are equally likely
(and excluded February 29). In reality, some days are slightly more likely as birthdays
than others.For example, scientists have long struggled to understand why more
babies are born 9 months after a holiday. Let p = (p1, p2, . . . , p365) be the vector of
birthday probabilities, with pj the probability of being born on the jth day of the
year (February 29 is still excluded, with no offense intended to Leap Dayers). The kth
elementary symmetric polynomial in the variables x1, . . . , xn is defined by
ek(x1, . . . , xn) = �
1≤j1<j2<···<jk≤n
xj1 . . . xjk .This just says to add up all of the
�n
k
�
terms we can get by choosing and multiplying
k of the variables. For example, e1(x1, x2, x3) = x1 + x2 + x3, e2(x1, x2, x3) = x1x2 +
x1x3 + x2x3, and e3(x1, x2, x3) = x1x2x3. Now let k ≥ 2 be the number of people.(a) Find a simple expression for the probability that there is at least one birthday
match, in terms of p and an elementary symmetric polynomial.
(b) Explain intuitively why it makes sense that P(at least one birthday match) is
minimized when pj = 1
365 for all j, by considering simple and extreme cases.(c) The famous arithmetic mean-geometric mean inequality says that for x, y ≥ 0
x + y
2 ≥ √xy.This follows from adding 4xy to both sides of x2 −2xy + y2 = (x−y)2 ≥ 0. Define
r = (r1, . . . , r365) by r1 = r2 = (p1 + p2)/2, rj = pj for 3 ≤ j ≤ 365. Using the
arithmetic mean-geometric mean bound and the fact, which you should verify,
that
ek(x1, . . . , xn) = x1x2ek−2(x3, . . . , xn)
+ (x1 + x2)ek−1(x3, . . . , xn) + ek(x3, . . . , xn),
show that
P(at least one birthday match | p) ≥ P(at least one birthday match | r)
with strict inequality if p ∕= r, where the given r notation means that the birthday
probabilities are given by r. Using this, show that the value of p that minimizes
the probability of at least one birthday match is given by pj = 1
365 for all j.5. Note that for each natural number n, we have the following equation:
13 + 23 + · · · + n3 = (1 + 2 + · · · + n)
2
.
In this problem, we will try to prove this identity with the technique of story proof.
(a) Give a story proof of the identity
1 + 2 + · · · + n =
�n + 1
2
�
.
(b) Give a story proof of the identity
13 + 23 + · · · + n3 = 6
�n + 1
4
�
+ 6
�n + 1
3
�
+
�n + 1
2
�
.
It is then just basic algebra (not required for this problem) to check that the square of
the right-hand side in (a) is the right-hand side in (b).