#1
|
|||
|
|||
Tricky Uniform Distribution Problem
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. |
#2
|
|||
|
|||
Re: Tricky Uniform Distribution Problem
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)
|
#3
|
|||
|
|||
Re: Tricky Uniform Distribution Problem
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. |
#4
|
|||
|
|||
Re: Tricky Uniform Distribution Problem
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 |
#5
|
|||
|
|||
Re: Tricky Uniform Distribution Problem
[ 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." |
#6
|
|||
|
|||
Re: Tricky Uniform Distribution Problem
Thanks. The circle argument works best for me.
So the general formula is n/(n+1) then? |
|
|