Tricky Uniform Distribution Problem

[T50_Omaha8]

I'm trying to use game theory to evaluate the optimal number of shills for an auction house to employ.

I'm having much more trouble with a seemingly simply lemma than I thought I would:

Given n points randomly chosen along the interval [0,1] (openness or closedness irrelevant), what is the expected value of the largest point?

I can't come up with anything prettier than saying it is a sequence described by:
c(n) = a(n)/(2^((2^n)-1))
where a(n) is defined recursively by
a(1) = 1 and
a(n) = (a(n-1))^2+(2^((2^n)-2))

c(1)=1/2
c(2)=5/8
c(3)=89/128
c(4)=24305/32468
...

Beat, brag, or variance?

Or am I missing something simple?

Note that I'd prefer to keep this as a run-of-the-mill equation I can do calculations with, not a recursively defined sequence.

[southerndog]

Intuitively, I would think it would be the expected percentile of the largest order statistic.. for n=2, you would expect max = 2/3... for n=3 3/4,, looks like the formula is n/(n+1)

[T50_Omaha8]

The reason I get 5/8 for n=2 is this:

Assume the first point is p1 and is fixed, then consider a second point p2 added to the segment. With probability p1, p2 will be smaller than p1, so this portion of the expectation comes out to (p1)^2. Then, given that p2 > p1, the expectation of p2 is p1+(1-p1)/2, and this occurs with probability (1-p1). The total expectation of p2 and p1 is then
(p1)^2+(1-p1)(1+p1)/2
=(p1)^2+(1/2)(1-p1)(1+p1)
=(p1)^2+(1/2)(1-(p1)^2)
=(1+(p1)^2)/2
And E((1+(p1)^2)/2)
=(1+(E(p1))^2)/2
=(1+1/4)/2
=5/8.

[PairTheBoard]

I think we had this problem recently and someone pointed out the well known type of distribution for something like this. I forget what it is though.

I like this from-scratch technique. Let F(x) be the probabilty that the max of the numbers is less than x. Then,

F(x) = x^n

ie. the probabilty that all numbers are less than x. But F(x) also represents the Cumulative Distribution Function for the Max random variable. Therefore, its derivative, nx^(n-1), is the pdf for the Max. For the expectation, integrate xnx^(n-1) from 0 to 1 to get n/(n+1).

PairTheBoard

[pzhon]

[ QUOTE ]

And E((1+(p1)^2)/2)
=(1+(E(p1))^2)/2


[/ QUOTE ]
This step is wrong. In general, E(X)^2 is not the same as E(X^2).

The correct value is 2/3. To evaluate the expected value, you can compute the integral of 1/2 + p^2/2 dp from p=0 to p=1. There is also a symmetry argument. If you place 3 points on a circle and cut at one of the points, you get an interval containing two points, and for any other point P on the circle, 2/3 of the cuts will leave P below the higher the point.

This is a simple example of a Beta distribution. "B(i,j) with integer values of i and j is the distribution of the i-th highest of a sample of i+j-1 independent random variables uniformly distributed between 0 and 1."

[T50_Omaha8]

Thanks. The circle argument works best for me.

So the general formula is n/(n+1) then?