1
$\begingroup$

Let $a,b,c,d,e$ be drawn independently and uniformly at random from $[0,1]$. What is the probability that $a+b+c>d+e$?

Considering a unit hypercube, we want the volume "below" the plane $a+b+c-d-e=0$. The corners that are "above" the plane are $$(0,0,0,1,0),(0,0,0,0,1),(0,0,0,1,1),(1,0,0,1,1),(0,1,0,1,1),(0,0,1,1,1).$$ How can we compute the volume of this part of the hypercube?

$\endgroup$
  • $\begingroup$ The $4-\operatorname{volume}$? $\endgroup$ – user142198 Feb 27 '15 at 3:00
4
$\begingroup$

Notice if $d, e$ are random variables uniform over $[0,1]$, so do $\tilde{d} \stackrel{def}{=} 1 - d\;$ and $\;\tilde{e}\stackrel{def}{=} 1 - e$.
We have $$a + b + c > d + e \quad\iff\quad a + b + c + \tilde{d} + \tilde{e} > 2$$ For any $p = (x_1,x_2,x_3,x_4,x_5) \in \mathbb{R}^5$, let $\;\ell(p) = x_1 + x_2 + x_3 + x_4 + x_5$.
The probability $\mathcal{P}$ we seek is equal to:

$$\mathcal{P} = \verb/Volume/\big\{\; p \in [0,1]^5 : \ell(p) > 2 \;\big\} = 1 - \verb/Volume/\big\{\; p \in [0,1]^5 : \ell(p) \le 2 \;\big\}\tag{*1}$$

Let $e_1, e_2, \ldots, e_5$ be the standard bases of $\mathbb{R}^5$ and $\Delta_p(\lambda)$ be the simplex $$\big\{\; q \in \mathbb{R}^5 : q_i \ge p_i, i = 1\ldots5\;\text{ and }\; \ell(q-p) \le \lambda \;\big\}$$

The polytope on the right of $(*1)$ can be constructed by cutting 5 small simplices based at $e_i$ from the simplex $\Delta_0(2)$. More precisely, up to a set of measure zero, we have: $$\big\{\; p \in [0,1]^5 : \ell(p) \le 2 \;\big\} = [0,1]^5 \cap \Delta_0(2) \approx \Delta_0(2) \setminus \left( \bigcup_{i=1}^5 \Delta_{e_i}(1) \right)$$ This leads to$\color{blue}{^{[1]}}$

$$\mathcal{P} = 1 - \frac{2^5}{5!} + 5 \left(\frac{1^5}{5!}\right) = 1 - \frac{32 - 5}{120} = \frac{31}{40}$$

Notes

  • $\color{blue}{[1]}$ In general, in any dimension, the volume of the simplex $\Delta_0(\lambda)$ inside the unit hyper-cube is given by following formula: $$\verb/Volume/\big( [0,1]^n \cap \Delta_0(\lambda) \big) = \sum_{k=0}^{\lfloor\lambda\rfloor} (-1)^k \binom{n}{k} \frac{(\lambda-k)^n}{n!}$$ One can prove this formula using inclusion exclusion principle. Look at my answer for a similar question in $\mathbb{R}^3$, it has more explanation of the underlying ideas.
$\endgroup$
3
$\begingroup$

$$\int_0^1 da \int_0^1 db \int_0^1 dc \int_0^{{\rm min}(1,a+b+c)} dd \int_0^{{\rm min}(1,a+b+c-d)} de = \frac{31}{40}=0.775$$

$\endgroup$
  • $\begingroup$ Could you please show how to do this integral? The $\min$ part makes it complicated. $\endgroup$ – python55 Feb 27 '15 at 3:27
  • $\begingroup$ As a warmup, consider the simpler problem $a+b>c$. The integral is $\int_0^1 da \int_0^1 db \int_0^{{\rm min}(1,a+b)} dc$. For the last integral you consider two cases: $a+b<1$ and $a+b\ge1$, each of which affects the limits for the $db$ integral (in the first case, $b$ runs from $0$ to $1-a$; in the second case, $b$ runs from $1-a$ to $1$.) You end up with two triple integrals and no "min"s in sight. (The answer here is 5/6, as a check.) $\endgroup$ – Tad Feb 27 '15 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.