Wikipedia:Reference desk/Archives/Mathematics/2009 January 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 15

Trivial questions and removal of posts

Please have a look at the talk page... PST —Preceding unsigned comment added by Point-set topologist (talk • contribs) 11:28, 15 January 2009

Forgive the trivial question, but would you put a link to the talk page, because I do not know where it is. Then, feel free to remove my post ;) --131.114.72.215 (talk) 12:36, 15 January 2009 (UTC)

After you finish reading this message hold the "alt" key and click the letter "t" on your keyboard (i.e alt-t); release these keys instantly and hit "enter". By magic, you will be directed to the discussion. PST —Preceding unsigned comment added by Point-set topologist (talk • contribs) 12:40, 15 January 2009

Hitting alt-t with Firefox on Linux I get the "Web Search" functionality, not the talk page. I have no clue what browser/platform you're running in which gets you the discussion page. For the rest of us, the talk page for any Wikipedia article can be found by scrolling to the top the page and clicking on the tab which says "discussion"- for this page, that goes to Wikipedia_talk:Reference_desk/Mathematics. PST is probably referring to the "Trivial questions and removal of posts" section (direct link to section: [1]). BTW, Wikipedia:Help_desk is the best place to ask these sort of questions. It's like the Reference desk, but about how to use Wikipedia. -- 99.154.0.155 (talk) 14:20, 15 January 2009 (UTC)

alt-shift-t on most modern browsers. See Wikipedia:Keyboard shortcuts. Algebraist 14:25, 15 January 2009 (UTC)

My keyboard doesn't have an "alt" key. --Carnildo (talk) 23:56, 15 January 2009 (UTC)

Here's that "secret" link again. hydnjo talk 02:13, 16 January 2009 (UTC)

Interesting geometric and probability question

I looked at the previous question (about chords and such) and that got me thinking about the following:

What is the probability that a quadrilateral is convex?

My approach would be to start with the first edge. Now consider the second one; this is uniformly distributed on the interval (0, 360). Now for each value in this interval, consider possible edges from there. The fourth edge is uniquely determined. I tried this tactic out and ended up with massive amounts of calculations (integrating trig. functions) which I have not yet finished. Now I don't want anyone to tell me the answer if they know it. But I just want to know whether there is a better way to solve this problem (with very few calculations). If so, an outline would be helpful (without the answer). Thanks! —Preceding unsigned comment added by 129.143.15.142 (talk) 12:33, 15 January 2009 (UTC)

The problem sounds nice, with a nice generalization to convex n-gons, but first you have to state it more completely. In fact, you have to define what is the probability distribution of the 4 vertices. Or equivalently, what is the random way you adopt to construct the quadrilateral. Notice that there is no uniform probability distribution for random points on the plane, so there is no preferred meaning to "a random quadrilateral". More choices are possible, each one giving a different answer. One possible variant is doing it on a sphere, thus choosing at random uniformly and independently 4 points on S². PMaj --131.114.72.215 (talk) 12:55, 15 January 2009 (UTC)

If I am not mistaken, this problem appeared in the Putnam competition. PST

Bertrand's paradox is relevant here: if you aren't careful to decide exactly what 'random' means, you may end up with a lot of different answers. Algebraist 13:18, 15 January 2009 (UTC)

I believe the OP means that the angles are chosen uniformly, and the the lengths of the sides does not affect the convexity (perhaps he assumes the lengths are chosen to not have self intersections). I think then no heavy calculations are needed, just the sum of the angles in a convex polygon. JackSchmidt (talk) 15:25, 15 January 2009 (UTC)

The angles are 4 positive numbers with sum $2\pi$, and can be seen as the baricentric coordinates of a point of a regular tetrahedron. Does your the angles are chosen uniformly refer to the (normalized) Lebesgue measure on the tetrahedron? If so, the probability of getting a convex quadrilateral is just the probability that all 4 coordinates are less than $\pi$ , that is, they represent a point in the inner regular octahedron: therefore it is just the ratio between the volume of the tetrahedron and the volume of the octahedron: that is 1/2, because the complement of the octahedron is made by 4 tetrahedrons of half (linear) size: 1/2=1-4(1/2)³. --PMajer (talk) 16:20, 15 January 2009 (UTC)

I take him to mean: The first angle A is chosen uniformly in the open interval (0°,360°). The second angle B is chosen uniformly in the open interval (0°,360°-A), and then the convexity is now determined by A+B: if it is 180° or more, then the quadrilateral must be convex, if it is less than 180° then the quadrilateral cannot be convex. This gives a larger probability than 1/2 (but again a nice fraction, now counting sub-triangles instead of sub-tetrahedra), so the OP might be able to decide which he meant based on the "50-50" or "better than 50-50" chance. He did specifically ask not to post the answer. I think both distributions are reasonable, so without reading minds it is hard to tell which he meant. JackSchmidt (talk) 17:13, 15 January 2009 (UTC)

You say 'the convexity is now determined by A+B: if it is 180° or more, then the quadrilateral must be convex, if it is less than 180° then the quadrilateral cannot be convex'. This doesn't seem to be true at all. Whatever do you mean? Algebraist 17:19, 15 January 2009 (UTC)

Oh that is too bad. I think this follows the OP word for word, except that the third edge is not specified, and I guess it matters, more or less wrecking my model. If A+B ≥ 180°, then C+D ≤ 180°, so C,D ≤ 180° so it is convex assuming A,B are ok. If A+B < 180°, then it is possibly convex, possibly not. Less of a problem: I guess one needs to subtract out the probability that A or B itself is bigger than 180°. This now leaves 1/4 where the quadrilateral must be convex, 1/2 where it cannot be, and 1/4 where it depends on the third side. Since one does need to specify the third side, I think it no longer makes sense to model it as a two dimensional choice. PMajer's model may be the most reasonable way, though I am not sure this is how the OP wanted the third side chosen. JackSchmidt (talk) 17:52, 15 January 2009 (UTC)

It may be easier to consider the first angle being chosen to be between 0 and 180, since the orientation of the polygon doesn't affect its convexity. --Tango (talk) 17:49, 15 January 2009 (UTC)

Thanks for you help everyone! I actually did not want the answer (although I am not sure it is correct: no offense intended). Maybe I should have written: "Consider the collection of all four-point subsets of the plane that determine a quadrilateral, uniformly distributed". What is the probability that the quadrilateral determined is convex. Let me explain my method.

Method:

I first consider an arbitrary line segment (of length s). Now my second line segment can be subtended at an angle between 0 and 360; without loss of generality, we may assume that the angle is distributed uniformly between 0 and 180 (by symmetry). Suppose, the line segment is subtended at an angle θ and has length l. Consider the extension of the line infinitely. If the third side of the quadrilateral originates from the start of this extension and has angle greater than θ (with respect to the first line segment), the quadrilateral will certainly not be convex. It turns out that the third side must subtend an angle (with respect to the second side) between 0 and α/2 where α equals the sum of θ and the cosine inverse of (s^2 + x^2 - l^2)/2xs. But the angle can also be between α/2 and α: however, in this case, the length matters. It turns out that the length (where the third side subtends an angle of β with the second side extended) must be:

k = (z+s)^2 + l^2 - 2*(z+s)*l*cos(θ)

where z equals the ( (sine of α - β) into (l^2 + s^2 - 2*l*s*cos(θ)) ) divided by (the sine of ( ( the cosine inverse of (s^2 + x^2 - l^2)/2xs ) - α + β ) ). Induce a measure on [0, 1] using the bijection:

(2/π) * arctan (x) : [0, posinf] -> [0, 1]

When the third side subtends an angle between 0 and α/2 with the second side, it can have any length so the probability is 1 for each such angle. For angles between α/2 and α, the max side length is k (as above) which when transformed to [0, 1] gives (2/π) * arctan (k). Putting this together, the net "mass of favorable region" is (probability = mass of favorable region/total mass):

f = (α/2) + [(integral (β=α/2 to β=α)) ((2/π)*arctan (k)) dβ]

The total mass is π + f + q where again we define a similar integral as above for q (q represents the probability that the third side subtends an angle greater than α with respect to the second side). Now this expression, (f)/(π + f + q) represents the probability that the quadrilateral is convex for particular l and θ. We now integrate this expression for θ between 0 and π and l between 0 and 1 (note that this is a double integral). We have then got the probability that the quadrilateral is convex

Q.E.D

This method seems overly long but I am pretty sure it works. Any comments would be greatly appreciated. Thankyou so much!

But as they were saying "the collection of all four-point subsets of the plane that determine a quadrilateral, uniformly distributed" has not a big meaning, for the same reason that, for instance, there is not a uniform probability on the natural numbers (what should be the probability of {1}, if it has to be equal to the probability of {2}, of {3} etc?). What you could do is : compute the probability P_R for 4 points independently and uniformly choosen in the disk of radius R (given that they make a quadrilateral); then compute the limit of P_R as R goes to infinity (no risk that somebody here steals your pleasure of doing the computation). This is maybe close to what you are thinking, and should be a limit probability in some sense. --84.221.209.239 (talk) 20:46, 15 January 2009 (UTC)

You have attempted to conquer the problem that the edges may have indefinite length by definining a transformation to the unit interval. Life becomes much simpler if you assume that the quadrilateral is bounded.

PST —Preceding unsigned comment added by Point-set topologist (talk • contribs) 20:16, 15 January 2009

The question doesn't make sense in that form, there is no uniform distribution for 4 points on the plane. (Basically, the probability of any of the points being in any given bounded region would have to be 0 in order for the total for the whole plane no to be more than 1, but obviously that doesn't work.) --Tango (talk) 20:27, 15 January 2009 (UTC)

The OP's solution works assuming there is a uniform distribution for four points in the interior of a ball. So that is certainly not a flaw with his/her method. PST —Preceding unsigned comment added by Point-set topologist (talk • contribs) 20:36, 15 January 2009

Another possible model is to transport the uniform measure of the Riemann sphere via the stereographic projection onto the plane and choosing independently the 4 points. You get this way the same situation of 131's variant. Note that, thanks to the conformality, the angles are preserved. On the sphere variant it seems to me that, choosing the fourth point X, the quadrilateral is (geodesically) convex if and only if switching X with -X it is not. So this choice also gives 1/2 (maybe it's the same?) --PMajer (talk) 21:03, 15 January 2009 (UTC)

That just gives you one of many non-uniform distributions on the plane, no-one said they didn't exist. --Tango (talk) 22:26, 15 January 2009 (UTC)

are you talking to me? In this case, yes, but I didn't say no-one said they didn't exist ;) Here we are just suggesting some possible natural distributions, just to speak. --PMajer (talk) 22:32, 15 January 2009 (UTC)

"What is the probability that a quadrilateral is convex"? The obvious and stupid answer is that it depends on which quadrilateral you are talking about: if it is a convex quadrilateral, then the probability is one, otherwise it is zero. Want to ask another question such as "What is the probability that a random quadrilateral is convex"? Well, there is no such thing as a random quadrilateral. Every quadrilateral is unique. "What is the probability that a randomly chosen quadrilateral is convex"? That depends on from where it is chosen. You may have a box of quadrilaterals and choose one randomly. The probability depends on the contents of the box. If all the quadrilaterals in the box are squares, then the probability that a randomly chosen quadrilateral is convex is one. The OP's question does not make sense, and so the answer is perfectly undefined. Bo Jacoby (talk) 12:04, 16 January 2009 (UTC).

Well I just don't agree that one cannot speak of a "random quadrilateral", why? According to the customary use, the meaning is: a random variable with codomain in the set of all quadrilaterals (which is a space with its natural topology). But as everybody was saying, the base probability space (the domain) has to be given too, to make the question meaningful. --131.114.72.215 (talk) 15:53, 16 January 2009 (UTC)

Sure, you can have a random quadrilateral, you just need to specify the probability distribution. The OP tried to specify a uniform distribution, which doesn't exist, but plenty of other distributions do. --Tango (talk) 17:09, 16 January 2009 (UTC)

Ok, even if I do not completely understand why you feel that it has to be repeated again something remarked so many times starting from the first answer... --PMajer (talk) 22:42, 16 January 2009 (UTC)

The "customary use" of the word random is sloppy mathematical shorthand. There is no such thing as a random number. What is ment by a random number is a randomly chosen number. The number 6 is not random even when it is the result of throwing dice. Bo Jacoby (talk) 18:00, 16 January 2009 (UTC).

Well, no. "Randomly chosen" is not better than "random", and is pointlessly longer ( and, what is less relevant, personally I do not like so much this pictoresque use of the verb "to choose": who choses the number, and where, from what box?). But the choice is mainly a matter of personal taste and has nothing to do with sloppy use. You certainly agree that what makes the language sloppy is: lack of definitions, non-uniform terminology, use of undefined terms, not to speak of bad notation, in the case of written maths. In the current language of a large group of probabilists "random integer number" is perfectly clear and just means: a random integer-valued variable, that is, a measurable map $\scriptstyle X:\Omega \to \mathbb {Z}$, $\Omega$ being a probability space, $\scriptstyle \mathbb {Z}$ equipped with the discrete topology. In fact, these differences in the mathematical language are not only a matter of personal taste: there is more, the anthropological phenomenon for which a group of people (from a specific discipline or school or country) have their own jargon, by which they identify (smell) themselves from the others (enemies). By the way, I noticed that each time here people speak about probability everybody becomes immediately more rigid... why? (Discaimer: I'm not a probabilist). --PMajer (talk) 21:36, 16 January 2009 (UTC)

When talking about a random number it is not the number, but rather the process of selecting the number, that is random. I agree that the word choose might not be the best choice. What makes the language sloppy is, apart from the points you make, that words are redefined from an original meaning. A random variable is a well defined mathematical concept, but it is neither random nor variable! The words were carelessly chosen, and that is sloppy language. Similarily the concept of probability was once called degree of probability, which is easier to understand outside the ivory tower. Generally I think that statisticians are doing a bad job in clarifying their language and popularizing their science. Bo Jacoby (talk) 09:40, 17 January 2009 (UTC).

Hi guys, Assume that the quadrilaterals are bounded within the unit circle so the uniform distribution works. Then my method (have a look please) would work: wouldn't it? Thanks! —Preceding unsigned comment added by 129.143.15.142 (talk) 17:32, 16 January 2009 (UTC)

Well I didn't check your method in detail (sorry) but the answer will clearly come as the value of a big multiple integral, and the problem will be evaluate it. I do not see any simmetry argument that could reduce the complexity of the computation. A more tractable, still puzzling question is already, whether the probability is more or less that 50%! --PMajer (talk) 21:26, 17 January 2009 (UTC)

I would imagine that it is quite easy to see that the probability is greater than 1/2. Maybe I am thinking incorrectly but given four points in the interior of the unit disk, assume without loss of generality that no three are collinear. Take a set of three points and consider the triangle formed by these three points. If the fourth point lies within this triangle, the resulting quadrilateral is easily seen to not be convex. Otheriwise it is. So we may solve this problem by just computing the area of the complement. Of course it is not as easy as that: we must note that there is a factor of four involved (it depends on which point, out of the four, we choose to be the fourth one) and we are obviously integrating over all sets of such three points (note that we can use symmetry). In general, given three non-collinear points, the area of the complement of the triangular disk formed will in general be greater than the area of the triangular disk. This necessarily implies that the probability is greater than 1/2. But I think that from now on the problem is fairly trivial; you just have to calculate a rather messy (but computable) double integral. I would imagine that you will end up doing a polar integral (definitely some trig. functions involved here). Anyway, I think this is the easier method you are looking for: hope this helps. --PST 23:31, 17 January 2009 (UTC)

What are the two things you're integrating over? I see 6 variables. --Tango (talk) 23:43, 17 January 2009 (UTC)

Also, what is meant by "otherwise it is"? If the triangle has its vertices at (0, 0), (½, 0) and (0, ½), and we add the point (−½, −½), how do you make a convex quadrilateral from that? -- Jao (talk) 23:58, 17 January 2009 (UTC)

The probability is exactly 1/2. Proof: Let the four corners of the quadrilateral be (x₁, y₁), (x₂, y₂), (x₃, y₃), and (x₄, y₄). Compute a nontrivial solution A₁, A₂, A₃, A₄, to the homogeneous system of linear equations A₁·x₁ + A₂·x₂ + A₃·x₃ + A₄·x₄ = A₁·y₁ + A₂·y₂ + A₃·y₃ + A₄·y₄ = A₁ + A₂ + A₃ + A₄ = 0. Consider the product P = A₁·A₂·A₃·A₄. Note that the sign of P does not depend on the choice of the A _i. If P < 0 the quadrilateral is concave, because then one of the corners can be written as a convex combination of the others. By symmetry, the probability that P < 0 equals the probability that P > 0. The probability that P = 0 is zero. Bo Jacoby (talk) 12:37, 18 January 2009 (UTC).

Sorry, I can't follow the symmetry argument... Do you mean that you see a simple measure-preserving transformation on the set of quadrilaterals in the disk, D⁴, that exchanges the sign of P? (thus the transformation brings convex quadrilaterals into non-convex and conversely) --PMajer (talk) 14:46, 18 January 2009 (UTC)

Hi, it seems that we have met the Sylvester's four points problem. For the disk the probability is around 70%. Have a look here... [2]--PMajer (talk) 16:35, 18 January 2009 (UTC)

Furthermore, this was a Putnam competition problem. Exercise for OP: can you see where Bo Jacoby's proof fails? --PST 17:48, 18 January 2009 (UTC)