ken@ihuxq.UUCP (ken perlow) (02/23/84)
What is the expected value of the range of N random points on
a line from 0 to 1? I think that's a concise statement of the
problem. To avoid ambiguity (I'm not a mathematician), I'll
restate it as I conceived it: You have this (finite) 1-dimensional
dart board at which you throw random darts. What is the
expected dispersion of N darts if they must all hit the board,
but any point within is equally probable?
I believe this problem is related to Chris Scussel's puzzle about
cutting the correct lengths from 1 chain for N jobs about which you
have no information, but I don't know why.
--
*** ***
JE MAINTIENDRAI ***** *****
****** ****** 23 Feb 84 [4 Ventose An CXCII]
ken perlow ***** *****
(312)979-7261 ** ** ** **
..ihnp4!ihuxq!ken *** ***rao@utcsstat.UUCP (Eli Posner) (02/24/84)
What is the expected value of the range of N random points on
a line from 0 to 1?
Easy!
N - 1
_____
N + 1
--
Eli Posner
{allegra,ihnp4,linus,decvax}!utzoo!utcsstat!raoapdoo@alice.UUCP (Alan Weiss) (02/27/84)
There are at least two ways of solving this problem, which I shall now give. The problem was to find the mean range of n numbers chosen uniformly on the interval (0,1). 1. Easy solution Write u for the value of the maximum, l for the value of the minimum. Then range=u-l, and E(range)=E(u-l)=E(u)-E(l)=1-1/(n+1) -1/(n+1) = 1-2/(n+1) . 2. Harder solution, which gives more information. Suppose we ask the question "What is the DISTRIBUTION of the range?". Then we find for any number t in the range (0,1) P(range<t)=nt^(n-1) - (n-1)t^n. Now E(range)=integral(1-P(range<t))dt, which checks with the answer above, but we can also find things like the variance of the range Var=2(n-1)/((n+2)(n+1)^2) or anything else. One way to find the distribution of the range is to first show that the joint density of (l,u), the vector of (min value, max value), is n(n-1)(u-l)^(n-2) (note the difference between l and 1). Alan Weiss Bell Labs, Murray Hill, NJ
stevev@tekchips.UUCP (02/27/84)
> What is the expected value of the range of N random points on > a line from 0 to 1? I think that's a concise statement of the > problem. To avoid ambiguity (I'm not a mathematician), I'll > restate it as I conceived it: You have this (finite) 1-dimensional > dart board at which you throw random darts. What is the > expected dispersion of N darts if they must all hit the board, > but any point within is equally probable? Assuming that your definition of "range" and "dispersion" is the distance between the leftmost and rightmost points on the line, I believe that answer is (N-1)/(N+1). Here is my reasoning (this was all conjured up without any stat or caluculus) books, so--someone please post a note if I goofed up). The density function for the max of N uniformly distributed random varibles on [0,1] is N-1 f (x) = Nx N The density function for the min of N uniformly distributed random varibles on [0,z] is N N-1 g (x,z) = --- (z-x) N N z The density function h(y) for the distance between min and max computed by integrating over combinations of points whose difference is y. / 1 | h (y) = | f (x) g (x-y,x) dx N | N N-1 / y (Please excuse the "ascii" integral sign.) This integral basically sums the probablities of the max of the N points being at x, and the min of the remaining N-1 points (which are now limited to being <= x) being at x-y. This integration is easy to do because lots of terms cancel out; the result is: N-2 h(y) = N(N-1)(1-y)y The expected value of h(y) (which was the original question) is then found easily by integrating y h(y) dy over the interval [0,1], giving
stevev@tekchips.UUCP (Steve Vegdahl) (02/28/84)
> What is the expected value of the range of N random points on > a line from 0 to 1? I think that's a concise statement of the > problem. To avoid ambiguity (I'm not a mathematician), I'll > restate it as I conceived it: You have this (finite) 1-dimensional > dart board at which you throw random darts. What is the > expected dispersion of N darts if they must all hit the board, > but any point within is equally probable? Assuming that your definition of "range" and "dispersion" is the distance between the min and max points on the line, I believe that answer is (N-1)/(N+1). Here is my reasoning (this was all conjured up without any stat or caluculus books, so someone please post a note if I goofed up). The density function for the max of N uniformly distributed random varibles on [0,1] is N-1 f (x) = Nx N The density function for the min of N uniformly distributed random varibles on [0,z] is N N-1 g (x,z) = --- (z-x) N N z The density function for the distance between min and max computed by integrating over combinations of points whose difference is y. / 1 | h (y) = | f (x) g (x-y,x) dx N | N N-1 / y (Please excuse the "ascii" integral sign.) This integral basically sums the probablities of the max of the N points being at x, and the min of the remaining N-1 points (which are now limited to being <= x) being at x-y. (Note that random variables for the min and max points are not independent, so it doesn't work to compute their expectations independently and then subtract.) This integration is easy to do because lots of terms cancel out. the result is N-2 h (y) = N(N-1)(1-y)y N The expected value can then be computed by integrating y h (y) dy N over the interval [0,1], giving our result of (N-1)/(N+1). As I said before, I don't have a lot of time to verify this. A sanity check however, indicates that it works for N = 1, where the range should obviously be zero, and approaches 1 as N approaches infinity, again consistent with intuition. Finally, the density function h integrated over [0,1] is 1, and is clearly always non-negative for positive N, hence it is a feasible density function. Would someone like to corroborate or contradict? Steve Vegdahl Tektronix Inc. Beaverton, Oregon
sarwate@uicsl.UUCP (03/31/84)
#R:tekchips:-59000:uicsl:6900005:000:323 uicsl!sarwate Mar 30 10:26:00 1984 Your answer for h sub N (y) is right as is the expected value. See e.g. Michael Woodroofe "Probability with Applications", McGraw-Hill 1975. The density of the range is computed on page 190. This is a beta density with parameters alpha = N-1 and beta = 2. The expected value is given as alpha/(alpha+beta) on page 218.