Expectation and Variance

MATH 4221

Fall 2013

Skiles 254

T / Th, 9:35 - 10:55 pm

Instructor

Will Perkins

wperkins3@math.gatech.edu

Office: Skiles 017

Office Hours: Thursday 11 am - 1pm, 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
  • 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