Instructor

* 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:
- Expectation of a discrete random variable
- Expectation of a continuous random variable
- the kth moment, and kth central moment of a random variable
- Variance
- Standard Deviation
- Covariance of two rv's
- Correlation of two rv's
- Markov's Inequality
- Chebyshev's Inequality
- First-moment Method
- Second-moment Method
- 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:
- Calculate the expectation and variance of the number of fixed points in a permutation on n elements.
- Give an upper bound on the probability that fewer than n/10 elements of a permutation are fixed points, for large n
- Show that with probability > .99, a symmetric simple random walk is between -n/100 and n/100 at step n.
- In a random walk with n steps, what is the expected number of runs of 3 upsteps in a row? Variance?
- What is the expected number of times a random walk of n steps will have hit 0?
- 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?
- 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)
- Give an example of random variables with positive covariance and an example with negative covariance
- Find an upper bound on the probability that a random permutation on n elements contains a sequence of three i, i+1, i+2
- 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