21
$\begingroup$

If the probability that $5$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$ occur to be the vertices of a convex pentagon is $\frac{49}{144}$, what is the probability that a subset of $6$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$ occurs to be the vertices of a convex pentagon? Thanks a lot.

$\endgroup$
  • $\begingroup$ By the way, I mean the exact value of the probability in the question. Thanks. $\endgroup$ – kejma Jan 18 '13 at 5:27
  • 3
    $\begingroup$ Where does the $49/144$ come from? Maybe the place where that's proved would be a good place to start on the 6-point problem. $\endgroup$ – Gerry Myerson Jan 18 '13 at 6:21
  • 1
    $\begingroup$ It would have made sense to provide a link to this related question of yours, both initially and in particular in response to @Gerry's question. $\endgroup$ – joriki Jan 18 '13 at 7:26
  • 2
    $\begingroup$ I think this is considerably harder than the corresponding question with $5$ and $4$ points that you posed in the comments under my answer to the other question, because if the convex hull is a quadrilateral the remaining two points may or may not be part of a convex pentagon, and if the convex hull is a pentagon, the remaining point may be part of $0$, $1$ or $2$ convex pentagons; I think these cases will be hard to deal with. In case someone does come up with an answer, you can check it against the value $0.7565$ estimated by this code. $\endgroup$ – joriki Jan 18 '13 at 8:11
  • 1
    $\begingroup$ Also posted to MO, mathoverflow.net/questions/119300/… $\endgroup$ – Gerry Myerson Jan 19 '13 at 3:49
2
$\begingroup$

This is the same as the probability that no two of the six points lie within the convex hull of the other four.

The number of cases for this complementary event to happen is $${6\choose2}=15$$ and all these cases are (with 100% probability) mutually exclusive and equiprobable, except that we have triple-counted the cases when three of the points actually lie within the convex hull of the other three, of which there are $${6\choose3}=20.$$ These cases are also all equiprobable, they are mutually exclusive except on a set of null measure, and they have to be re-included twice. This completes the inclusion-exclusion.

Given this, it is easy to solve the original problem if we can calculate the probability distribution of the area of the convex hull of the first four randomly chosen points and the marginal probability q that the last two uniformly and independently chosen points both lie within this area, and likewise the marginal probability r that the last three points all lie within the convex hull of the first three.

Then the probability that any five of the six points chosen uniformly and independently on $(0,1)\times(0,1)$ form a convex pentagon is $$p=1-15q+40r$$

So let $H_3(x)$ be the marginal cumulative distribution function of the area of the convex hull of the first three points, and $H_4(x)$ be the marginal cdf of the area of the convex hull of the first four points. Then $$q=\int_0^1 x^2dH_4(x);$$ and $$r=\int_0^1 x^3dH_3(x).$$ Computing $H_3(x)$ and $H_4(x)$ is tedious but straightforward calculus. Otherwise the problem is solved.

(Small hint: it may be easier to compute $H_4(x)$ after computing $H_3(x)$. The integrals are actually the second and third moments about the origin for these distributions, respectively. They are taken over the Kolmogorov space $[0,1]$ as the cdf ranges from 0 to 1.)

For $H_3(x)$ see The PDF of the area of a random triangle in a square. For $H_4(x)$ see PDF of area of convex hull of four random points in square.

$\endgroup$
-2
$\begingroup$

Your original set has cardinality 6, your target set has cardinality 5, set member order does not matter, so you have $C^6_5=6$ possible subsets. Each of these has a $\frac{49}{144}$ probability of forming a convex pentagon. What is the probability that at least one of these forms a convex pentagon? It is 1 minus the probability that none of them form a convex pentagon:

$1-(1-\frac{49}{144})^6\approx1-65.97\%^6=1-8.2445\%=91.76\% $

$\endgroup$
  • 4
    $\begingroup$ You seem to be under the impression that the six events (of five given points forming a pentagon) are independent. Why would that be the case ? Also what if the six points form a convex hexagon ? We don't want them to form a hexagon but you're still counting this case. $\endgroup$ – mercio Feb 1 '13 at 15:44
  • $\begingroup$ Independence: Occam's razor. In the absence of information about event dependency, I did assume the simplest formulation of the question. Anyhow, if the events are dependent, then the question has insufficient information to be answerable. $\endgroup$ – Sérgio Carvalho Feb 2 '13 at 1:21
  • 3
    $\begingroup$ I think it's safe to assume that the six random points are independent among themselves (as in the linked question) so that it is a well-posed problem. But then the six random variables "do these 5 points form a convex pentagon ?" are not independent from each other. If they are, it is really really not obvious and needs justification. $\endgroup$ – mercio Feb 2 '13 at 2:47
  • 2
    $\begingroup$ To see that this argument does not work, consider the same situation when we ask what is the probability that out of $5$ random points we can pick $4$ which are in convex position. Your argument would give $1-(1-p_4)^5<1$, where $p_4$ is the probability that $4$ random points are in convex position (it is strictly smaller then $1$). But this is false: Every set of five points in general position contains the vertices of a convex quadrilateral. (see en.wikipedia.org/wiki/Happy_ending_problem) $\endgroup$ – Gilles Bonnet May 9 '14 at 19:58
  • 1
    $\begingroup$ Even if we where talking about whether the $6$ random points are independent among themselves, I don't think assuming that has anything to do with Occam's razor. $\endgroup$ – user133281 Jun 21 '14 at 12:55

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.