The 2014 Putnam Problem A4 and Mr. Honner’s Square

[this could use a little editing / clarifying, and I might return to that later today if I have time]

Saw this tweet about last weekend’s Putnam Exam from Patrick Honner:

I love checking out the Putnam problems, so before heading into work yesterday I looked at the expected value problem he recommended. It is Problem A4 here:

The 2014 Putnam exam at the Art of Problem Solving site

The problem asks the following question:

Assume that X is a random variable that can take on values 0, 1, 2, 3, and etc. We know that the expected value of X is 1, the expected value of X^2 is 2, and the expected value of X^3 is 5. What is the smallest possible probability that the variable X will take on the value 0?

At the risk of possibly embarrassing myself by printing an incorrect solution, here’s how I thought about this problem on my bike ride into work yesterday. I wanted to write it up because of a fun little connection to an old blog post of . . . . surprise: Patrick Honner:

Proof Without Words: Two Dimensional Geometric Series

In particular, the connection is to this “proof without words” showing that 1/4 + 2/8 + 3/16 + . . . = 1:

Mr Honner Square

Back to the Putnam problem. I’ll say at the start that this solution isn’t meant to be rigorous, it was just my thoughts on how to solve the problem.

If we assume that the probability of X taking on the non-negative integer value k is p_k, then the conditions of the problem imply that:

(1) \sum_{k = 0}^{\infty} p_k = 1 (the sum of the probabilities must be 1)

(2) \sum_{k = 0}^{\infty} k * p_k = 1 (the expected value of X is 1)

(3) \sum_{k = 0}^{\infty} k^2 * p_k = 2 (the expected value of X^2 is 2), and

(4) \sum_{k = 0}^{\infty} k^3 * p_k = 5 (the expected value of X^3 is 5).

So let’s make a function f(x) = \sum_{k = 0}^{\infty} p_k * x^k. Note first that since all of the p_k‘s are non-negative, the function and all of its derivatives are increasing (or at least not decreasing, I suppose) on the interval (0,1). Note also that the four equations above imply that:

(5) f(1) = 1 and f(0) = p_0, and

(6) f^{'}(1) = 1 and f^{'}(0) = p_1

We’d like to use equation (3) above to find f^{''}(1) and to do that we need a little trick. If we take the second derivative of f(x) we’ll end up with a bunch of terms like (n)(n-1)p_n*x^{n-2} rather than a bunch of terms with p_n multiplied by n^2 as we have in equation (3). The trick is to take the derivative of x f^{'}(x) rather than f^{'}(x) alone. That’s a simple application of the product rule for derivatives and we find equation (3) tells us that:

(7) 2 = f^{'}(1) + (1) f^{''}(1)

which tells us that f^{''}(1) = 1.

Going through a similar exercise for f^{'''}(x) we find that we need to take the derivative of x*( f^{'}(x) + xf^{''}(x) ) to use equation(4). So:

(8) 5 = (f^{'}(1) + (1)f^{''}(1)) + (1)( f^{''}(1) + f^{''}(1) + (1)*f^{'''}(1))

which tells us that f^{'''}(1) = 1.

There’s probably a little bit of technical work you need to do to be sure that you can apply Taylor’s theorem now, but I didn’t think that part through on my bike. Or even now! My guess is that the p_k‘s being positive and the series (1), (2), (3), and (4) converging are enough to tell you that the function f(x) is well defined and three times differentiable on the interval [0,1]. I could be wrong about that though.

Taylor’s theorem tells you that you can estimate f(0) from f(1) and some of the derivatives of f(x) evaluated at x = 1. In particular it says that:

(9) f(0) = f(1) + (-1)f^{'}(1) + \frac{(-1)^2}{2} f^{''}(1) + \frac{(-1)^3}{6} f^{'''}(z)

for some z in [0,1]. Simplifying a little:

(10) f(0) = 1 - 1 + \frac{1}{2} - \frac{1}{6} f^{'''}(z)

Since f^{'''}(x) is increasing on [0,1], the largest value of f^{'''}(z) on that interval is 1, which occurs at x = 1. Combining that information with the fact that f(0) = p_0 we can see that p_0 must be greater than or equal to 1/3.

To see if we can have the situation in which p_0 equals 1/3, we can set all of the p_i‘s with i > 3 equal to zero. We know that for f^{'''}(1) to equal 1, p_3 has to be 1/6. Setting p_1 = 1/2 (and thus p_2 = 0) gives us these sums from (1) through (4) above:

(11) 1/3 + 1/2 + 1/6 = 1

(12) 1/2 + 3*(1/6) = 1

(13) 1/2 + 9*(1/6) = 2, and

(14) 1/2 + 27/6 = 5.

So, p_0 = 1/3 is achievable!

The connection to Mr. Honner’s proof without words is also pretty neat. His picture above shows the neat equality:

(15) 1/4 + 2/8 + 3/16 + 4/32 + . . . = 1.

By analogy with our solution to the Putnam problem above, consider the infinite series:

(16) g(x) = 1 + \frac{x}{2} + \frac{x^2}{4} + \frac{x^3}{8} + \ldots = \frac{1}{1 - x/2}, and

(17) g^{'}(x) = \frac{1}{2} + \frac{2x}{4} + \frac{3x^2}{8} + \ldots

Note that g^{'}(x) evaluated at x = 1 is exactly twice the series in Mr. Honner’s proof. Since we have an explicit formula for g(x), we can see that just use the quotient rule to differentiate and see that:

(18) g^{'}(x) = \frac{1}{2} \frac{1}{(1 - x/2)^2}

Since g^{'}(1) = 2 we see analytically that Mr. Honner’s series sums to 1.

Which makes me wonder – is there a clever geometric solution to the Putnam problem, too?