f is a continuous real-valued function on the closed interval [0, 1] such that f(1) = 0. A point (a1, a2, ... , an) is chosen at random from the n-dimensional region 0 < x1 < x2 < ... < xn < 1. Define a0 = 0, an+1 = 1. Show that the expected value of ∑0n (ai+1 - ai) f(ai+1) is ∫01 f(x) p(x) dx, where p(x) is a polynomial of degree n which maps the interval [0, 1] into itself (and is independent of f).
The expected value is simply ∫ S dv / ∫ dv, where the integral is taken over the allowed region and S is the sum given.
∫ dv = 1/n! [First integrate 1 from x1 = 0 to x2, giving x2/1!. Then integrate that from x2 = 0 to x3, giving x32/2! and so on.]
We now have to attack the main integral. We can take the sum outside the integral, giving a sum of n integrals. Now there at most two variables in each integral. The trick is to use a different order of integration for each integral, so that one integrates last over the variables in the integrand. Starting at the x1 end gives us a factor xi/i! and starting at the xn end gives us a factor (1 - x)j/j!. We are then left with the a single final integration from 0 to 1 of a term like f(x) xn-i(1 - x)i/( (n - i)! i! ).
At this point we switch the order of summation and integration again to get:
∫01 xn/n! + xn-1(1 - x)/( n - 1! 1! ) + xn-2(1 - x)2/( n - 2! 2! ) + ... + x (1 - x)n-1/( 1! n - 1! ) dx.
After dividing by the other integral (equivalent to multiplying by n!) we get an integrand which is simply (x + 1 - x)n - (1 - x)n = 1 - (1 - x)n. So we have the required result with p(x) = 1 - (1 - x)n.
50th Putnam 1989
© John Scholes
1 Jan 2001