uniform mess

[radosr]

Let U_1, U_2, ..., U_n be i.i.d. uniform random variables on (0,1).
Let U_(1), U_(2), ..., U_(n) be the order statistics. Also, let U_(0) = 0, and U_(n+1) = 1.
Let R_i = U_(i+1) - U(i), for i = 0, 1, ..., n.
Let M = maximum of all R_i's.
The problem of calculating E[M] has been asked in job interview setting for n = 2 and/or n = 3.
Can you do it?
Can anybody do it for general n?

 

[ThisGuy]

It seems like I'm not the only one who is finding this difficult. The vector \((R_0,\ldots,R_n)\) is uniformly distributed on the standard n-simplex. I don't see any magic way to calculate E[M] so I'm left trying to calculate P(M <= m) which is given by the volume of the intersection of the standard simplex and the half-spaces \(R_i \leq m\). For small enough m, that's just going to be a simplex so that's easy enough but as m gets bigger, things get more complicated. For n = 2, it's not so bad to work out but even for n = 3, it seems like it gets a bit messy...

 

[pruse]

Note that given \(R_0+R_1+\cdots + R_n =1\), we need to find the probability \(P(\min(R_0,...,R_n)\leq m)=1-P(\min(R_0,...,R_n)\geq m)=1-P(R_0\geq m,...,R_n\geq m)=1-P(R_0-m\geq 0, ..., R_n-m\geq 0)\), where \(t_0=R_0-m,...,t_n=R_n-m\) satisfy \(t_0+\cdots +t_n=1-(n+1)m\)

In general, the region in \(R^{n+1}\) represented by \(\{(x_0,...,x_n): x_0+\cdots+x_n=S, x_0,...,x_n\geq 0\}\) is an \(n\)-dimensional simplex with volume \(\frac{S^n\sqrt{n+1}}{n!}\), so the probability above evaluates to \(1-(1-(n+1)m)^n\). The PDF of the minimum is then \(n(n+1)(1-(n+1)m)^{n-1}\), and the expectation of the minimum is

\(n(n+1)\int_0^{\frac{1}{n+1}}x(1-(n+1)x)^{n-1}dx=n(n+1)\cdot \frac{1}{n(n+1)^3}=\frac{1}{(n+1)^2}\)

 

[ThisGuy]

Actually, the case for n=3 isn't that bad (though the arithmetic gets ugly). I'm getting 11/18 for n = 2 and 25/48 for n = 3, both of which agree with my one-line simulation in R.

 

[ThisGuy]

Note that given \(R_0+R_1+\cdots + R_n =1\), we need to find the probability \(P(\min(R_0,...,R_n)\leq m)=...\)

Rados actually asked about the maximum of the R_i rather than the minimum. I hadn't thought about the minimum but it works out so nicely that I have to wonder if that's what Rados actually meant to ask. I don't think the maximum problem has such a nice solution since (as you point out) in the minimum case you always get a simplex while in the maximum case you get more complicated objects.

 

[pruse]

Oops, yeah, I misread it.

 

[pruse]

This problem is definitely more difficult than the one concerning the minimum. But for \(n=3\) it's not bad. For \(\frac{1}{3}\leq m\leq \frac{1}{2}\), the probability \(P(\max(R_i)\leq m)\) is \((3m-1)^2\) (the region in question is a triangle) and for \(\frac{1}{2}\leq m\leq 1\), the probability is \(6m-3m^2-2\) (the region here is a hexagon). The PDF of the max is then

\(f(x)=\begin{cases}18x-6 &\text{ if } \frac{1}{3}\leq x\leq \frac{1}{2}\\6-6x &\text{ if } \frac{1}{2}\leq x\leq 1\end{cases}\)

so the expected value of the max is \(\int_\frac{1}{3}^1 xf(x)dx=\frac{11}{18}\)

Rados, what is the solution to the general case?

 

[ThisGuy]

I actually finally worked out the solution to the general case. It wasn't nearly as hard as I had thought; my main mistake was looking at what was left (a complicated object) rather than what was taken away (just a bunch of simplices!). Using inclusion-exclusion, I arrived at:
\[\frac{1}{n + 1} + \sum_{k = 1}^n (-1)^{k + 1} {n + 1 \choose k} \frac{1}{k(n + 1)} \large(1 - \frac{k}{n + 1}\right)^{n + 1}\]
I haven't managed to simplify that yet but it looks like it's correct.

 

[ThisGuy]

This problem is definitely more difficult than the one concerning the minimum. But for \(n=3\) it's not bad. For \(\frac{1}{3}\leq m\leq \frac{1}{2}\), ... (the region in question is a triangle) and for \(\frac{1}{2}\leq m\leq 1\), ... (the region here is a hexagon).

I think that's n = 2, no? For n = 3, the region is a simplex when m is between 1/4 and 1/3, then a simplex with its corners cut off (so minus four smaller simplices) between 1/3 and 1/2 and then the entire standard simplex with its corners cut off between 1/2 and 1. I was trying to figure out how this would work for n = 4 when I realized there was an easier way than intersecting four-dimensional simplices.

 

[ThisGuy]

Well, with the assistance of Wolfram Alpha, I managed to simplify that and the answer is so simple and unexpected that I think it was worth the effort. Here it is:
\[\frac{H_{n + 1}}{n + 1}\]

Yes, that's the (n + 1)th harmonic number in there.

 

[pruse]

Nice!

Yes, I meant \(n=2\). Our results do match for n=1 and n=2, so I'm convinced you're right. Can you explain how you got that expression?

 

[pruse]

Well, with the assistance of Wolfram Alpha, I managed to simplify that and the answer is so simple and unexpected that I think it was worth the effort. Here it is:
\[\frac{H_{n + 1}}{n + 1}\]
Yes, that's the (n + 1)th harmonic number in there.

Explanation?

 

[radosr]

Honestly, it took me awhile to work this one out for general n. This guy's answer is correct. I will scan my proof tomorrow and post it in the pdf format here.