The Irwin-Hall Distribution

A while ago I came across this problem from Stanford’s Putnam seminar:

Two points are independently selected uniformly at random from a line of length {b}. What is the probability that they are at least a distance {a} apart, where {b > a}? (Putnam 1961 B2)

This problem has a very neat solution which exploits what I find to be a rather clever technique. We put the line on a coordinate system and say it runs from {0} to {b}. Let {X_1} be the coordinate of the first point and {X_2} be the coordinate of the second, where {X_1} and {X_2} are random variables which are clearly uniformly distributed. Now draw the unit square, as in the following diagram [1]:

IH_pic1

The shaded region represents the area in which the points are at least {a} apart. It has area {2(\tfrac{1}{2}(b-a)^2) = (b-a)^2}, so the probability the two points are at least {a} apart is simply {\tfrac{(b-a)^2}{b^2}}.

This trick can be applied to a whole host of problems. As far as I can tell the only requirement is that we are sampling from uniform distributions. One somewhat classic problem is to find the probability density function of a random variable {Y = X_1 + X_2} where {X_1, X_2 \sim U(0,1)}. By the same trick we can compute the CDF of {Y}, we just need to split it into cases:

IH_pic2IH_pic3

The CDF is therefore {F_Y(s) = \tfrac{s^2}{2}} when {0 < s < 1} and {F_Y(s) = 1 - \tfrac{s^2}{2}} when {1 < s < 2}. Differentiating gives us the triangular distribution {f_Y(s) = s} when {0 < s < 1} and {f_Y(s) = -s} when {1 < s < 2}.

Looking at the last post I thought an interesting idea would be to generalize this to {n} uniform random variables. This is of course a solved problem: the density function is known as the Irwin-Hall distribution. I wanted to take a run at it from our high-dimensional geometry perspective, since we can apply the same idea as above to the unit cube in {n} dimensions to compute the CDF of Irwin-Hall.

Before we attack this we need to know how to compute the volume of the standard {n}-simplex, or the volume of the set {\{\vec{x} | \sum{x_i} < 1\}} where the {x_i}s are nonnegative. We’ll follow the explanation given in [2]. First let’s consider the simplex in {\mathbb{R}^n} defined by {(1,0,\cdots,0), (1,1,0,\cdots,0), \cdots, (1,1,\cdots,1)} and the origin. This is just the set {\{\vec{x} | 1 \geq x_1 \geq x_2 \cdots \geq x_n \geq 0\}}. We can fit exactly {n!} of these in the unit cube since there are {n!} such orderings and each point in the unit cube is in one of these simplices (I’m fudging some issues with the boundaries but it should be fine I think). Thus the original simplex has volume {\tfrac{1}{n!}}. We can map this simplex to the standard simplex by the transformation {y_n = x_n; y_{n-1} = x_n + x_{n-1}; \cdots; y_1 = y_n + y_{n-1} + \cdots + y_1}. This is a transformation with determinant one so the volume remains unchanged, so the volume of the standard simplex is {\tfrac{1}{n!}}.

I drew some pictures of the three dimensional case since some interesting things happen there. We’re keeping track of the volume underneath the plane {x_1 + x_2 + x_3 = s} that’s contained within the unit cube. Similar to the two-dimensional case, our function will be piecewise since it changes when it hits vertices of the cube. First our simplex increases at an obvious rate, maintaining a volume of {\tfrac{s^3}{3!}}. It looks kind of like this:

IH_pic4

Then the function changes when {s} passes {1}. The way we compute the new volume is by taking the volume of the red simplex and subtracting out the volume of the blue simplices (outlined in the following figure), which gives us {\tfrac{s^3}{n!} - \binom{3}{1}\tfrac{(s-1)^3}{n!}}.

IH_pic5

Finally the function changes for a last time when {s} passes {2}. We could just compute the volume of the missing simplex and subtract that from one, but we’ll try a method that works a little more generally. Note that the blue simplices have overlapped to form new simplices which are outlined in green below. Our method of computation is to take the red simplex, subtract out the blue simplices, and then add back in the green simplices. It’s basically inclusion-exclusion. This gives us {\tfrac{s^3}{n!} - \binom{3}{1}\tfrac{(s-1)^3}{n!} + \binom{3}{2}\tfrac{(s-2)^3}{3!}}.

IH_pic6

This appears to generalize in a fairly simple manner. Note that our function changes based on the integer part of {s}. The first piece of our function is naturally just {\tfrac{s^n}{n!}}. When {s} hits {1}, the plane hits exactly {\binom{n}{1}} vertices (more precisely it hits {(1,0,\cdots,0) \cdots (0,\cdots,1)}). Our volume computation then requires that we subtract out the newly formed simplices. These have side length {s-1} and there are exactly {\binom{n}{1}} of them, since one forms at each vertex.

If {\lfloor s \rfloor = i} then we see that we will be computing {\tfrac{1}{n!}\sum_{k=0}^{i}{(-1)^k \binom{n}{k} (s-k)^n}}. Each time {s} crosses an integer {i} the plane hits {\binom{n}{i}} vertices (choose which {i} of the coordinates are {1}) and exactly that many new simplices are formed to be added or subtracted out, depending on parity. Thus our CDF is exactly

{P(X < s) = \tfrac{1}{n!} \displaystyle\sum_{k=0}^{\lfloor s \rfloor}{(-1)^k \binom{n}{k} (s-k)^n}}

And differentiating with respect to {s} gives us our PDF

{f_X(s) = \tfrac{1}{(n-1)!} \displaystyle\sum_{k=0}^{\lfloor s \rfloor}{(-1)^k \binom{n}{k} (s-k)^{n-1}}}

Admittedly there are easier ways to go about proving the expressions for the PDF or CDF are valid, but I like this one since it minimizes the amount of “clairvoyance” involved. As a whole I find this trick with the unit cube to be fairly useful whenever solving problems with uniform distributions. I’m not sure of legitimate practical applications but it seems to come up in contest math from time to time. Hopefully someday I will spot an opportunity to use it in a real-world setting.

Sources:
[1] I drew the figures but I basically stole and modified the code found here: http://tex.stackexchange.com/a/75974
[2] Foundations of Data Science by Hopcroft and Kannan.
A draft can be found here: http://www.cs.cornell.edu/jeh/book112013.pdf
Used for the computation of volume of a standard simplex

Advertisements