For today though, I am simply going to post the solution to the problem as Matt and I initially solved it. First, I must solve a very simple problem that gives us a technique that will be needed later. Consider the following problem:
N numbers between 0 and 1 are selected uniformly at random. On average what is the value of the smallest one?
First, let us try to solve this for N=2. We can see that we simply must solve the integral
∫ min(x,y) dxdy
integrated over [0,1]x[0,1], and min(,) is the minimum function. Clearly min(x,y)=min(y,x) so we can instead integrate over the "lower half triangle" and double our answer. So, instead integrate x in [0,1] and y in [0,x] in
2∫ y dxdy
the 2 is because we are only covering half the area we should be covering, and min(x,y) has been replaced by y, because x>y now. The integral is pretty simple to do, and gives the answer 1/3.
Now in the general N case we must consider we have a collection of N points {x[1],x[2],x[3]...,x[N]}, and integrate
∫ min(x[1],x[2],x[3]...,x[N]) dx[1]dx[2]dx[3]...dx[N]
As before, we order them x[1]>x[2]>x[3]...>x[N], so the min function always returns x[N], and we must integrate x[1] in [0,1], x[2] in [0,x[1]], x[3] in [0,x[2]] and so on. We must also find the prefactor, which is one over the area of the triangle we are integrating. Integrating the function 1 over the region of integration, we find the prefactor must be N!. So we must integrate
N!∫ x[N]dx[1]dx[2]dx[3]...dx[N]
over our triangular region. The final answer comes out to be 1/(N+1), sort of neat, but anyway I just wanted to demonstrate the technique so it is less confusing later.
Back to the problem at hand. We have N points {x[1],x[2],x[3]...,x[N]}, and we will order them as x[1]>x[2]>x[3]...>x[N]. Let us define
d[i]=x[i]-x[i+1]
so d[i] is the size of the ith region, and this i runs from 1 to N-1.
Next, we will define S[i] to be equal to d[i] if the ith region is shaded, and S[i] will be zero if it is not. The answer we seek is
S=N!∫ Σ S[j] dx[i]
Integrated over all the x[i] positions, and j summed from 1 to N-1 to add up all the shaded regions.
S[i] will be nonzero (and equal to d[i]) in one of two conditions:
1) x[i+1]-x[i+2] > x[i]-x[i+1]
2) x[i-1]-x[i] > x[i]-x[i+1]
That is, if d[i+1] is greater than d[i] or if d[i-1] is greater than d[i], d[i] will get shaded in.
With calculating probabilities, whenever you have to find the chance that A or B happens, it is often easier to find the chance that neither happened and take one minus that. Similarly here, rather than integrate whenever 1) or 2) happens, it is easier to find the situation of neither of them happening. Let is define q[i] as d[i]-S[i], so q[i] represents the unshaded regions, it is equal to d[i] when S[i]=0 and it is zero when S[i]=d[i]. Clearly then
S=N!∫ Σ S[j] dx[i]
=1 - N!∫ Σ q[j] dx[i]
We can of course move the sum outside of the integral, so we simply must calculate
∫ q[j] dx[i]
for an arbitrary j and then we can sum it up and multiply by N!.
The integration has x[1] running from 0 to 1 and x[i] running from 0 to x[i-1]. q[j] is zero in some of this region and nonzero is other parts, let us identify exactly where q[j] is nonzero. It is exactly the negation of conditions 1) and 2) earlier, that is
1) x[j+2] > 2x[j+1]-x[j]
2) x[j+1] < x[j-1]-2x[j]
This actually needs to break into a few cases, the first inequality is trivial if 2x[j+1] < x[j], since x[j+2] is always positive. The second case depends on whether x[j-1] is greater than or less than 3x[j] (because if x[j-1] is more than 3 times x[j] then the second inequality is made trivial by the fact that x[j+1] < x[j]).
So the integration region over dx[j-1] until dx[j+2] breaks up into many smaller pieces that one can cleanly write out with this information, but its fairly lengthy, so I'm not going to bother here. In this region, q[j]=d[j] so you simply integrate x[j]-x[j+1] in this region. This integral is most easily done in Maple (or whatever other math program you like) by first doing the integrals from dx[N] to dx[j+3] (the function is constant there and the integration region is simple) then doing the next four integrals carefully, then finishing it off integrating to x[1].
In the end, you get a somewhat awful function of N and j. You then sum j going from 1 to N-1 and multiply by N!. You will get something somewhat less awful, but a still terrible function of N. Finally, you must take the limit of N going to infinity (this step will be easy enough to do by hand, but by this point you already have Maple open anyway, and your spirit will have been far too crushed to do such a limit) and in then end you get 11/18. This was the unshaded region (the shaded region was 1-(the integral of q[j])) so the shaded region is given by 7/18.
Next time I'll go into a bit of the analysis by the other solutions found at the cut the knot page. One of them I found to be particularly interesting so I wanted to show it in detail, but I wanted to demonstrate my own horrible method first.
Also, I expect the date on this post will be confusing, I started writing it some time ago, but it took me more than a month to get around to finishing it.
