# Expectation and Variance

### Fall 2012

#### M / W / F, 12:05 - 12:55 pm

Instructor

Will Perkins

wperkins3@math.gatech.edu

Office: Skiles 017

Office Hours: Wednesday 10 am - 12pm, or by appointment

Topics
• Sections: 3.3, 3.4, 4.3, 4.7, 5.6
• Definitions:
1. Expectation of a discrete random variable
2. Expectation of a continuous random variable
3. the kth moment, and kth central moment of a random variable
4. Variance
5. Standard Deviation
6. Covariance of two rv's
7. Correlation of two rv's
8. Markov's Inequality
9. Chebyshev's Inequality
10. First-moment Method
11. Second-moment Method
12. Formula for variance of a sum in terms of sums of variances and covariances
• Theorems: 3.3.3, 3.3.8, 3.3.9, 3.3.11, 7.3.1, 7.3.2, 7.3.3
• Examples from the book
• Problems from the book
• Sample Questions:
1. Calculate the expectation and variance of the number of fixed points in a permutation on n elements.
2. Give an upper bound on the probability that fewer than n/10 elements of a permutation are fixed points, for large n
3. Show that with probability > .99, a symmetric simple random walk is between -n/100 and n/100 at step n.
4. In a random walk with n steps, what is the expected number of runs of 3 upsteps in a row? Variance?
5. What is the expected number of times a random walk of n steps will have hit 0?
6. What is the expected number of runs of upsteps of lenth sqrt n in a simple random walk? What can you say about the probability that a SRW of n steps has at leat one such run?
7. Choose a sbuset of {1, ... n} by picking each integer independently with probability p. What is the expected number of 3-term arithmetic progressions in the subset (i.e. x,y, z s.t. y-x = z-y)
8. Give an example of random variables with positive covariance and an example with negative covariance
9. Find an upper bound on the probability that a random permutation on n elements contains a sequence of three i, i+1, i+2
10. Prove that whp (prob. -> 1 as n -> infty), the maximum of n Poisson, mean 1, random variables is at most 2 log n, regardless of the dependence between them