Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Graph
Consider a random graph (undirected, no multi-edges, no self-loops) on n nodes, where each possible edge exists independently with probability p. Let X be the number of isolated nodes (nodes with degree 0).
(a) What is Var(X)?
2 Whitening
Let X and Y be two random variables, with Var(X) > 0,Var(Y) > 0. Show that it is possible to construct X˜ = aX +bY and Y˜ = cX +dY, where a,b,c,d are scalars to be chosen subject to the constraint ad −bc 6= 0, such that cov(X˜,Y˜) = 0.
0.
3 Probabilistic Bounds
A random variable X has variance Var(X) = 9 and expectation E[X] = 2. Furthermore, the value of X is never greater than 10. Given this information, provide either a proof or a counterexample for the following statements.

(b) P[X = 2] > 0.
(c) P[X ≥ 2] = P[X ≤ 2].
(d) P[X ≤ 1] ≤ 8/9.
(e) P[X ≥ 6] ≤ 9/16.
4 Subset Card Game
Jonathan and Yiming are playing a card game. Jonathan has k > 2 cards, and each card has a real number written on it. Jonathan tells Yiming (truthfully), that the sum of the card values is 0, and that the sum of squares of the values on the cards is 1. Specifically, if the card values are c1,c2,…,ck, then we have 0 and 1. Jonathan and Yiming also agree on a positive target value of α.
The cards are then going to be dealt randomly in the following fashion: for each card in the deck, a fair coin is flipped. If the coin lands heads, then the card goes to Yiming, and if the coin lands tails, the card goes to Jonathan. Note that it is possible for either player to end up with no cards/all the cards.
A player wins the game if the sum of the card values in their hand is at least α, otherwise it is a tie.
(a) Prove that the probability that Yiming wins is at most .
(b) Find a deck of k cards and target value α where the probability that Yiming wins is exactly
.
5 Just One Tail, Please
Let X be some random variable with finite mean and variance which is not necessarily nonnegative. The extended version of Markov’s Inequality states that for a non-negative function φ(x) which is monotonically increasing for x > 0 and some constant α > 0,

Suppose E[X] = 0, Var(X) = σ2 < ∞, and α > 0.
(a) Use the extended version of Markov’s Inequality stated above with φ(x) = (x+c)2, where c is some positive constant, to show that:

.
(c) Recall that Chebyshev’s inequality provides a two-sided bound. That is, it provides a bound on P(|X −E[X]| ≥ α) = P(X ≥ E[X]+α)+P(X ≤ E[X]−α). If we only wanted to bound the probability of one of the tails, e.g. if we wanted to bound P(X ≥ E[X]+α), it is tempting to just divide the bound we get from Chebyshev’s by two. Why is this not always correct in general? Provide an example of a random variable X (does not have to be zero-mean) and a constant α such that using this method (dividing by two to bound one tail) is not correct, that is, .
Now we see the use of the bound proven in part (b) – it allows us to bound just one tail while still taking variance into account, and does not require us to assume any property of the random variable. Note that the bound is also always guaranteed to be less than 1 (and therefore at least somewhat useful), unlike Markov’s and Chebyshev’s inequality!
(d) Let’s try out our new bound on a simple example. Suppose X is a positively-valued random variable with E[X] = 3 and Var(X) = 2. What bound would Markov’s inequality give for P[X ≥ 5]? What bound would Chebyshev’s inequality give for P[X ≥ 5]? What about for the bound we proved in part (b)? (Note: Recall that the bound from part (b) only applies for zero-mean random variables.)
6 Sum of Poisson Variables
Assume that you were given two independent Poisson random variables X1,X2. Assume that the first has mean λ1 and the second has mean λ2. Prove that X1 +X2 is a Poisson random variable with mean λ1 +λ2.
Hint: Recall the binomial theorem.
(x+y)n = xkyn−k