Probability of forming an n-gon

Question

We have more than 3 lengths. Each length is exponentially distributed with parameter $\lambda$ and each is independent and identically distributed. I want to calculate the probability of constructing a n-gon using these lengths?

I am beginning with the hint that an n-gon can be constructed iff. the longest length is shorter than the sum of the rest. But I am unable to get an intuition on how to proceed. Thanks for the help.

Answer 1

Just to flesh out @HagenvonEitzen's sketch, because I always find fleshed-out solutions helpful.

To state it explicitly, geometrically, the relevant fact is that a set of lengths will be able to form a polygon as long as none of the lengths are bigger than the sum of all the others.

Taking, as Hagen says, for all $k \leq n$, $Y_k$ to be $Y_k:=X_1+\cdots+X_{k-1}+X_{k+1}+\cdots +X_n$, as you've noted, $Y_k$ is Erlang distributed. Explictly, $$ Y_k \sim \operatorname{Erlang}(n-1, \lambda) $$ Now, we know that $X_k \sim \operatorname{Exp}(\lambda)$.

Our general approach is to compute the probability that $Y_k < X_k$, let's call that event $E_k$. The key observation here is that these events are disjoint. Because, if one $X_k$ is bigger than the sum of all the others, then there's no way any of the other $X_k$ can be bigger than a sum that includes the biggest one, which we know is at least bigger than it.

Let's compute the complement of the event we're interested in. In particular, the probability the lengths don't form a polygon is the probability that at least one of the events $E_k$ occurs. This is the probability of the union of these events, and they are disjoint. So, the probability that any of them occur is just the sum of their individual probabilities. And by symmetry, that's just $n$ times the probability of each particular $E_k$, $E_1$, say.

So, we still have the brass tax question of computing the probability of $E_k$. We know that $Y_k$ and $X_k$ are independent, so we know their joint pdf by multiplying their individual pdfs. So we compute the probability $X_k > Y_k$ by just integrating over the region $x > y$ in the first quadrant. In particular $$ \mathbb{P}(E_k) = \int_0^\infty \int_0^x \left(\lambda e^{-\lambda x}\right) \left(\frac{\displaystyle \lambda^{n-1} y^{n-2}e^{-\lambda y}}{\displaystyle (n-2)!}\right) \ \text{d}y \ \text{d}x$$

The inner integral we recognize as an incomplete gamma function, which you might guess is hopeless, so your best bet is to switch the order of integration to get \begin{align} \mathbb{P}(E_k) &= \int_0^\infty \int_y^\infty \left(\lambda e^{-\lambda x}\right)\left(\frac{\displaystyle \lambda^{n-1} y^{n-2}e^{-\lambda y}}{\displaystyle (n-2)!}\right) \ \text{d}x \ \text{d}y \\ &= \int_0^\infty \left(\frac{\displaystyle \lambda^{n-1} y^{n-2}e^{-\lambda y}}{\displaystyle (n-2)!}\right) \int_y^\infty \left(\lambda e^{-\lambda x}\right) \ \text{d}x \ \text{d}y \\ &= \int_0^\infty \left(\frac{\displaystyle \lambda^{n-1} y^{n-2}e^{-\lambda y}}{\displaystyle (n-2)!}\right) e^{-\lambda y} \ \text{d}y \\ &= \frac{\lambda^{n-1}}{(n-2)!} \int_0^\infty y^{n-2} e^{-2\lambda y} \ \text{d}y \end{align}

We notice that this looks a lot like a gamma function, and so we substitute to make that more direct. We sub $u = 2\lambda y$. In that case $\text{d}y = \frac{1}{2\lambda} \ \text{d}u$. In total, this gives.

\begin{align} \mathbb{P}(E_k) &= \frac{\lambda^{n-1}}{(n-2)!} \int_0^\infty \left(\frac{u}{2\lambda}\right)^{n-2} e^{-u} \ \frac{1}{2\lambda} \text{d}u \\ &= \frac{\lambda^{n-1}}{(n-2)!} \left(\frac{1}{2\lambda}\right)^{n-1} \int_0^\infty u^{n-2} e^{-u} \ \text{d}u \\ &= \frac{\lambda^{n-1}}{(n-2)!} \left(\frac{1}{2\lambda}\right)^{n-1} \Gamma(n-1) \\ &= \frac{\lambda^{n-1}}{(n-2)!} \left(\frac{1}{2\lambda}\right)^{n-1} (n-2)! = \frac{1}{2^{n-1}}\end{align}

Which is very pretty. (It's so nice, though, there's almost surely an easier derivation).

And from the logic we had before about out macroscopic approach, we have $$\mathbb{P}\left(\bigcup_{k=1}^n E_k\right) =\sum_{k=1}^n\mathbb{P}(E_k) = n \mathbb{P}(E_1) = \frac{n}{2^{n-1}} $$

This is the probability that we can't form a polygon, since it's the probability one of the $E_k$ happen, so the probability we can form a polygon is $$ \boxed{1 - \frac{n}{2^{n-1}}} $$ Notice, in particular, it is independent of the rate parameter $\lambda$, which makes sense since geometrically we can adjust our length scales so that $\lambda$ can be set to some standard value.

As a note, it's always useful to check a result like this. Here's a couple of lines of Python I used to verify this answer.

import numpy as np

rate = 1
n = 3
trials = 10000

def simulate():
    vals = sorted(np.random.exponential(scale=1/rate, size=n), reverse=True)
    return 1 if vals[0] <= sum(vals[1:]) else 0

res = sum(simulate() for _ in range(trials))/trials
guess = 1 - n/(2**(n-1))

print('Result: ' + str(round(res, 6)))
print('Guess:  ' + str(round(guess, 6)))