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 Random Variables Warm-Up
Let X and Y be random variables, each taking values in the set {0,1,2}, with joint distribution
P[X = 0,Y = 0] = 1/3 P[X = 0,Y = 1] = 0 P[X = 0,Y = 2] = 1/3
P[X = 1,Y = 0] = 0 P[X = 1,Y = 1] = 1/9 P[X = 1,Y = 2] = 0 P[X = 2,Y = 0] = 1/9 P[X = 2,Y = 1] = 1/9 P[X = 2,Y = 2] = 0.
(a) What are the marginal distributions of X and Y?
(b) What are E[X] and E[Y]?
(c) (optional) What are Var(X) and Var(Y)?
(d) Let I be the indicator that X = 1, and J be the indicator that Y = 1. What are E[I], E[J] and
E[IJ]?
(e) In general, let IA and IB be the indicators for events A and B in a probability space (Ω,P). What is E[IAIB], in terms of the probability of some event?
2 Marginals
(a) Can there exist three random variables X1,X2,X3, each taking values in the set {+1,−1}, with the property that for every i 6= j, the joint distribution of Xi and Xj is given by
P[Xi = Xj] = 0? (1)
If so, specify the joint distribution of X1,X2,X3; if not, prove it.
(b) For which natural numbers n ≥ 3 can there exist random variables X1,X2,…,Xn, each taking values in the set {+1,−1}, with the property that for every i and j satisfying i− j =1 (mod n), the joint distribution of Xi and Xj is given by (1)? For any n that work, specify the joint distribution; for those that do not, prove it.
3 Testing Model Planes
Amin is testing model airplanes. He starts with n model planes which each independently have probability p of flying successfully each time they are flown, where 0 < p < 1. Each day, he flies every single plane and keeps the ones that fly successfully (i.e. don’t crash), throwing away all other models. He repeats this process for many days, where each “day” consists of Amin flying any remaining model planes and throwing away any that crash. Let Xi be the random variable representing how many model planes remain after i days. Note that X0 = n. Justify your answers for each part.
(a) What is the distribution of X1? That is, what is P[X1 = k]?
(b) What is the distribution of X2? That is, what is P[X2 = k]? Name the distribution of X2 and what its parameters are.
(c) Repeat the previous part for Xt for arbitrary t ≥ 1.
(d) What is the probability that at least one model plane still remains (has not crashed yet) after t days? Do not have any summations in your answer.
(e) Considering only the first day of flights, is the event A1 that the first and second model planes crash independent from the event B1 that the second and third model planes crash? Recall that two events A and B are independent if P[A∩B] = P[A]P[B]. Prove your answer using this definition.
(f) Considering only the first day of flights, let A2 be the event that the first model plane crashes and exactly two model planes crash in total. Let B2 be the event that the second plane crashes on the first day. What must n be equal to in terms of p such that A2 is independent from B2? Prove your answer using the definition of independence stated in the previous part.
(g) Are the random variables Xi and Xj, where i < j, independent? Recall that two random variables X and Y are independent if P[X = k1 ∩Y = k2] = P[X = k1]P[Y = k2] for all k1 and k2. Prove your answer using this definition.
4 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 E(X)? Consider X to be the sum of the indicators Xi that vertex i is isolated. Why isn’t X a binomial random variable?
(b) (optional) What is Var(X)?
5 Triangles in Random Graphs
Let’s say we make a simple and undirected graph G on n vertices by randomly adding m edges, without replacement. In other words, we choose the first edge uniformly from all n2 possible edges, then the second one uniformly from among the remaining n2 1 edges, etc. What is the expected number of triangles in G? (A triangle is a triplet of distinct vertices with all three edges present between them.)