N people agree to meet between 2:00 and 3:00 P.M.

probability/no.two.meet New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

N people agree to meet between 2:00 and 3:00 P.M.  Each arrives at a
random time and waits no more than 15 minutes.  What is the probability
that NONE of them meet?

> A computer is to generate n random variables, x1, x2, ..., xn.  They
> are i.i.d. (identical and independently distributed).  Each variable
> can take on a value between 0 and 1 inclusively.  That is to say,
> they can have any REAL value between 0 and 1.  What is the
> probability that the absolute value of the difference between ANY TWO
> of them is GREATER than 0.25?
>
> Here is a real world example of this problem.  N people agree to meet
> between 2:00 P.M. and 3:00 P.M..  Each can wait no more than 15
> minutes.  What is the probability that NONE of them will meet.  I
> know that if we were asking for the probability that ALL of them
> would meet, the probability would be
>
> (1+((1/d)-1)*n)*d^n = n*d^(n-1)-(n-1)*d^n
>
> for n people, each of whom can wait no more than d hours, or n
> variables, any two of which must be no more than d.  But, the problem
> that I'm posing here is the probability that NONE of the people will
> meet, or the probability that any two of the variables will have an
> absolute difference greater than 0.25.  I'd like a general formula
> for any value of n, and any value of d.  I suppose that if n>(1/d)
> then the answer is 0.  For example, if d=0.25, and if four or more
> people agree to meet each other between the two agreed upon times,
> then at least two of them must meet.

-- Patrick <prockwel@trumpet.aix.calpoly.edu>, to the puzzle oracle,
   November 1994

Show solution

> I suppose that if n>(1/d) then the answer is 0.  For example, if
> d=0.25, and if four or more people agree to meet each other between
> the two agreed upon times, then at least two of them must meet.

This is not correct for n=4; they can come in the intervals 0-.05,
.30-.35, .60-.65, .90-1, for example.

An easier way to look at the problem is to measure the probability that
the n variables will be in ascending order, and will differ by at least
d.  The probability of this is clearly 1/n! times the probability you
want.

First, we must exclude the trivial case in which the probability is 0;
if (n-1)d>1, there is not enough room for all n variables to be
separated by d, because the smallest is at least 0, each one must be at
least d more than the next smaller one, and the largest must thus be
more than 1.

Let x_i be the ith variable, and let y_i=x_i-(i-1)d.  Then
x_{i+1}-x_i>d is equivalent to y_{i+1}>y_i.  Thus the x_i have the
proper separation if and only if the y_i are in order.

Let q be the maximum value for y_n, which is 1-(n-1)d.  Since each of
the y_i has probability q of being in the interval (0,q), and they must
all be in that interval to be in ascending order, the probability that
they will be in ascending order is (q^n)/n!.

Thus this is the probability that the x_i are in ascending order and
separated by at least d.  The probability that you want is n! times
this number, which is

q^n = [1-(n-1)d]^n

For your example, with d=0.25:

n     q     q^n
1     1     1
2     3/4   9/16  = .5625
3     1/2   1/8   = .125
4     1/4   1/256 = .00390625
5     0     0

-- David Grabiner <grabiner@math.harvard.edu>