BadCaseForMomentGeneratingFunctions

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Recall that the moment-generating function for a random variable X is the function E[e^αX] of α, which is equal to ∑ E[X^k]α^k/k!. Here we describe a random variable 2^X for which the moment-generating function is not defined for all α.

Suppose you start with $1. I repeatedly flip a fair coin. If it comes up heads, I double your money. If it comes up tails, I send you way with whatever you've got so far. If X is the number of times I get heads, then the money you get is 2^X = e^{X ln 2}, and your expected return is E[e^{X ln 2}]. But if we just add up all the cases, you get $1 with probability 1/2, $2 with probability 1/4, $4 with probability 1/8, etc. giving a total of 1/2+1/2+1/2+..., which diverges. So there is no expectation for 2^X and thus no value for E[e^{X ln 2}].

This doesn't mean that the distribution of X has no moment-generating function. For smaller α we can calculate E[e^αX] = $\sum_{k=0}^{\infty} e^{\alpha k} 2^{-k}$ = $\sum_{k=0}^{\infty} (e^\alpha/2)^k$ = $\frac{1}{1-e^\alpha/2}$ (provided e^α/2 < 1). So we get a moment-generating function that, like many other GeneratingFunctions, happens to have a bounded radius of convergence.

Curiously, in the original game, the likelihood that you leave with 2ⁿ or more dollars is bounded by 2⋅2^-n, which is suspiciously similar to the bound from Markov's inequality for a variable with expectation 2. This demonstrates that Markov's inequality is not reversible: knowing that Pr[X ≥ α] ≤ m/α says nothing about EX.

CategoryRandomizedAlgorithmsNotes