5
$\begingroup$

What is the probability that a particular set of integer edge lengths selected from an interval $[1, N]$, can form a triangle? How might this extend to the case where one selects real number edge lengths from the unit interval?

I'd also be very interested in any comments on what the probability distribution would look like for the distances between the triangles vertices.

$\endgroup$
5
  • $\begingroup$ I don't understand what permutations have to do with it? $\endgroup$ Commented Dec 29, 2011 at 16:57
  • 1
    $\begingroup$ @Raskolnikov They have to do with a mental lapse on my part, since the problem I was originally thinking about involved assemblies with more than three edges. My apologies. $\endgroup$ Commented Dec 29, 2011 at 17:03
  • $\begingroup$ @Raskolnikov Looking about the site, I was unable to find an equivalent version of this question, though there was a somewhat related and interesting question on the probability that a stick broken in two places will form a triangle (math.stackexchange.com/questions/676/…). $\endgroup$ Commented Dec 29, 2011 at 17:10
  • $\begingroup$ You're right, I had that question in mind. But it's definitely different. $\endgroup$ Commented Dec 29, 2011 at 17:37
  • $\begingroup$ great question I must say! $\endgroup$ Commented Dec 29, 2011 at 17:53

2 Answers 2

Reset to default
6
$\begingroup$

To form a triangle you need each of the three sides to be less than the sum of the other two.

So for the unit interval case you might consider a unit cube and exclude three corner pyramids each with volume $1/6$ making the probability $1/2$.

For the discrete case you have $N^3$ points and again have to exclude three pyramids, each with $(N^3-N)/6$ points, which will give a probability of $\frac{1}{2}+\frac{1}{2N^2}$.

$\endgroup$
7
  • $\begingroup$ But it is easy to see that the probability for $n=2$ equals 1. Please see my post. $\endgroup$ Commented Dec 29, 2011 at 18:26
  • $\begingroup$ @Sasha: For $N=2$, I think $(2,1,1)$, $(1,2,1)$ and $(1,1,2)$ are not triangles so the probability is $5/8$. $\endgroup$ Commented Dec 29, 2011 at 18:42
  • $\begingroup$ Yes, as seen in my post, I was using $\geqslant$ instead of $>$ in the triangular inequalities. I have deleted my post. +1 $\endgroup$ Commented Dec 29, 2011 at 20:37
  • $\begingroup$ @Sasha In other words, you solved for the probability that a set of rigid edges, with lengths chosen in the described manner, can be cyclized in R^3, which I think is interesting. $\endgroup$ Commented Dec 29, 2011 at 21:35
  • $\begingroup$ @Sasha, it seems like the probability using $>=$ instead of $>$ is: (2 + 5*(n - 1) + (n - 1)^2)/(2*n^2), which holds up to {n, 1, 200}. Is there an obvious reason why this should be true? $\endgroup$ Commented Dec 29, 2011 at 21:40
1
$\begingroup$

This answers a slightly different question. The original question seeks, instead, to determine $$ \mathbb{P}\left( \left[ \begin{array}{c} X_1+X_2 > X_3 \\ X_1+X_3 > X_2 \\ X_2+X_3 > X_1 \end{array}\right] \right). $$

Let $X_1$, $X_2$, $X_3$ be uniform discrete random variables over interval $[1,n]$. We are seeking to determine: $$ \begin{eqnarray} p = \mathbb{P}\left( \left[ \begin{array}{c} X_1+X_2 \geqslant X_3 \\ X_1+X_3 \geqslant X_2 \\ X_2+X_3 \geqslant X_1 \end{array}\right] \right) &=& \sum_{k_3=1}^n \sum_{k_2=1}^{n} \sum_{k_1=1}^{n} \frac{1}{n^3} \left[ \begin{array}{c} k_1+k_2 \geqslant k_3 \\ k_1+k_3 \geqslant k_2 \\ k_2+k_3 \geqslant k_1 \end{array}\right] \\ &=& \sum_{k_3=1}^n \sum_{k_2=1}^{n} \sum_{k_1=\max(1,|k_3-k_2|)}^{\min(n, k_2+k_3)} \frac{1}{n^3} \\ &=& \sum_{k_3=1}^n \sum_{k_2=1}^{n} \frac{ \min(n,k_2+k_3) - \max(1,|k_3-k_2|) + 1}{n^3} \\ \end{eqnarray} $$ Evaluating the above sum requires careful consideration of three cases, $k_2=k_3$, $k_2< k_3$ and $k_2 > k_3$, each of which needs to be further split to resolve $\min(n,k_2+k_3)$. The end result is bound to be rational function of $n$, so can as well "guess" it: $$ p = \frac{1}{2} + \frac{3n-2}{2 n^2} $$

In[33]:= Table[ Sum[1/n^3, {k3, 1, n}, {k2, 1, n}, {k1, Max[1, Abs[k3 - k2]], Min[n, k2 + k3]}], {n, 1, 12}] // FindSequenceFunction[#, n] & Out[33]= (-2 + 3 n + n^2)/(2 n^2)
$\endgroup$
6
  • $\begingroup$ Running your Mathematica script for {n, 1, 100} yields: (2 + 5*(n-1)+(n-1)^2)/(2*n^2) $\endgroup$ Commented Dec 29, 2011 at 19:47
  • $\begingroup$ The scaling behavior seems right, but I'm hoping for an exact result! $\endgroup$ Commented Dec 29, 2011 at 19:55
  • $\begingroup$ @Steve But $2+5(n-1)+(n-1)^2$ is identically $n^2 + 3 n -2$, which coincides with the result I stated. $\endgroup$ Commented Dec 29, 2011 at 20:31
  • $\begingroup$ @Steve By the exact result, do you mean step-by-step evaluation of the sum ? If so, I can add one to the post. $\endgroup$ Commented Dec 29, 2011 at 20:33
  • $\begingroup$ Are we sure that the FindSequenceFunction result is correct for all values of N? $\endgroup$ Commented Dec 29, 2011 at 22:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.