## Sum less than N

What is the probability that N real numbers randomly picked in the range (0,N) add up to less than N?

Source: Ravi Subramanian

Solutions were received from several people. The probability is 1/N!. Two representative solutions are shown here:
Philippe Fondanaiche sent:
```Step by step, for N=2,3,4,5....the corresponding probabilities
p(2),p(3),p(4)...can be determined thanks to geometrical representations or
by the integral calculus.They are respectively 1/2, 1/6, 1/24, 1/120...and
the general term is 1/N!.

For N=2,the two real numbers define the coordinates of a point M randomly
located within a square of side 2. The points M such as the sum of the
coordinates are lower than 2 are within a right isosceles triangle whose the
hypotenuse is the diagonal of the square.So the required probability p(2) is
defined by the ratio of the area of this right isosceles triangle to the area
of the square,that is to say p(2)=1/2. The integral calculus leads to the
same result, p(2) being defined by the integral 1/4*sum[x*dx] for x=0 to 2
For N=3,the three real numbers define a point M within a cube of side 3.The
points M such as the sum of the coordinates are lower than 3 are within a
pyramid whose 3 edges perpendicular to each other are 3 long.The required
probability p(3) is defined by the ratio of the volume of this pyramid to the
volume of the cube,that is to say p(3) = 1/6.Moreover,p(3) can be calculated
by the integral 1/27*sum[x^2/2 * dx] for x=0 to 3

In order to calculate p(N) which corresponds to the general case,the integral
calculus is the most adequate and it is easy to demonstrate that each of the
coefficients of dx: x, x^2/2,x^3/6,x^4/24...for the different values of
N=1,2,3,4...is the integral of the previous one.So p(N) = 1/N^N
*sum[x^(N-1)/(N-1)! * dx] for x=0 to N.Therefore p(N) = 1/N!
```

Joseph DeVincentis sent:
```Picking N real numbers at random in (0,N) is equivalent to picking a
point at random in an N-dimensional hypercube of side N.  The probability
that their sum is less than N is the probability that the point also
lies in the N-dimensional right hyperpyramid within that cube that lies
between a given vertex and N-1 dimensional hyperplane which intersects
each of the vertices that share an edge with the given vertex.  This
pyramid has 1/(N!) the volume of the cube, so the probability is 1/(N!).

Since not everybody can visualize such things, and some might not take the
formula for a the volume of a hyperpyramid for granted...

Let p(A,B,C) be the probability that the sum of a set of A numbers in the
range (0,B) is less than C.

Now, the Ath number varies from 0 to B, and for each value, we can compute
the probability that the remaining numbers sum to less than C minus that
number.  So, p(A,B,C) is the integral over x=0..B of p(A-1,B,C-x)/B.  Note,
though, that p(A,B,C) is zero if C<0, so we can reduce the integral to
that over x=0..C if C<=B.

Now, p(1,B,C) is the probability that a single number in (0,B) is less
than C; for 0<=C<=B, this is C/B.

What I want to show by induction is that p(A,B,C) for 0<=C<=B is
[(C/B)^A]/(A!), given p(A-1,B,C)=[(C/B)^(A-1)]/[(A-1)!] for 0<=C<=B.

We know p(A,B,C) = Integral[p(A-1,B,C-x)/B,x=0..C] for 0<=C<=B.
Substiting our given formula,
p(A,B,C) = Integral[([(C-x)/B]^[A-1])/(B*[(A-1)!]),x=0..C].
= 1/(B*[B^(A-1)]*[A-1]!) * Integral[(C-x)^(A-1),x=0..C]

Now, I can use the same symmetry/change of variables trick I used in
the last POTW problem to replace C-x in the integral with x, since
the integral is from 0 to C.

The Integral[x^(A-1),x=0..C] = (C^A)/A, so:

p(A,B,C) = [(C^A)/(B^A)]/([A-1]!*A) = [(C/B)^A]/(A!).

For our problem, A=B=C=N, and this reduces to 1/(N!).
```

Mail to Ken