[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 is a random variable that can take on values 0, 1, 2, 3, and etc. We know that the expected value of is 1, the expected value of is 2, and the expected value of is 5. What is the smallest possible probability that the variable 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 taking on the non-negative integer value is , then the conditions of the problem imply that:
(1) (the sum of the probabilities must be 1)
(2) (the expected value of is 1)
(3) (the expected value of is 2), and
(4) (the expected value of is 5).
So let’s make a function . Note first that since all of the ‘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) and , and
We’d like to use equation (3) above to find and to do that we need a little trick. If we take the second derivative of we’ll end up with a bunch of terms like rather than a bunch of terms with multiplied by as we have in equation (3). The trick is to take the derivative of rather than alone. That’s a simple application of the product rule for derivatives and we find equation (3) tells us that:
which tells us that
Going through a similar exercise for we find that we need to take the derivative of to use equation(4). So:
which tells us that
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 ‘s being positive and the series (1), (2), (3), and (4) converging are enough to tell you that the function 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 from and some of the derivatives of evaluated at In particular it says that:
for some in [0,1]. Simplifying a little:
Since is increasing on [0,1], the largest value of on that interval is 1, which occurs at . Combining that information with the fact that we can see that must be greater than or equal to 1/3.
To see if we can have the situation in which equals 1/3, we can set all of the ‘s with equal to zero. We know that for to equal 1, has to be 1/6. Setting = 1/2 (and thus ) 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, 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) , and
Note that evaluated at is exactly twice the series in Mr. Honner’s proof. Since we have an explicit formula for , we can see that just use the quotient rule to differentiate and see that:
Since 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?