December 9, 2014 – Mike's Math Page

[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:

As usual, some great problems on the Putnam exam. https://t.co/hBqICfImII Love the expected value question! #math #mathchat

— Patrick Honner (@MrHonner) December 8, 2014

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:

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?

Day: December 9, 2014

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