Rigorous Random

[Erik1089]

I was posed a math problem in which 3 points are randomly chosen in the plane (every real number is equally probable for the coordinates), and I have to find the probability that the triangle formed by them is acute-angled. So I figured it would be good to have the answer beforehand: I created a simple C++ program that, in a loop that repeats 300,000 times, generates 3 random points (their coordinates are chosen with a simple rand() call) and checks if the triangle is acute. Of course, I seeded the random with

srand((unsigned)time(0));

before the loop. After that, the program tells how many of them were acute-angled (I found the value of 27.49%, give or take 0.005). But I've always learned that this rand() function, even when seeded, is not a rigorously random process. And I don't know what "rigorous" means in the case of this problem...

So, can I trust that value I found? If not, how can I get... well, a more random type of randomness? =]

Thanks!

[potatoCode]

maybe this link will provide some help
Using rand()

[hoxsiew]

VC++ has rand_s which is supposed to produce cryptographically secure random numbers using an API call which gets its entropy from keyboard and mouse (and other) events.

http://msdn.microsoft.com/en-us/libr...8VS.80%29.aspx

[D_Drmmr]

I was posed a math problem in which 3 points are randomly chosen in the plane (every real number is equally probable for the coordinates)

How did you do this using rand()? It only gives integer numbers, so you'll have to do something to generate pseudo-random real numbers.

So, can I trust that value I found? If not, how can I get... well, a more random type of randomness? =]

Have a look at the random number generators in boost. http://www.boost.org/doc/libs/1_41_0...enerators.html

[nuzzle]

So, can I trust that value I found? If not, how can I get... well, a more random type of randomness? =]

There's nothing wrong with rand(). You get a sequence of sufficiently random numbers between 0 and RAND_MAX.

I've verified your result using Java. Instead of random ints I used random doubles and I got 27.5% which is almost identical with your result.

Note that your simulation doesn't quite correspond to the problem formulation. The plane is infinite and your approach is to generate the points within a square. I tried different square sizes in my simulation but the result was the same so the size doesn't seem to matter but still, a square is not the plane.

I tried to find an alternate formulation of the problem. A triangle is uniquely described by its 3 internal angles - alfa, beta and gamma. So instead of generating the triangles from random points in a square, I generated them from their internal angles. These angles are dependent because alfa+beta+gamma=180 degrees. I generated alfa as a random angle between 0 and 180. The beta angle is limited by alfa so I generated it as a random angle between 0 and 180-alfa. Then the gamma angle is fully determined as 180-alfa-beta.

The result of the alternate simulation is 19.3%

The first formulation cannot be fully correct because generating triangles in the infinite plane definately isn't the same as limiting them to within a finite square. But the square size doesn't seem to matter so maybe it's approximately correct? The alternate formulation doesn't use points in the plane at all. Instead it generates the triangles from the internal angles. But it gives a different result so it seems it's not equivalent to the original formulation.

So maybe the formulations are equivalent indeed and the different results are caused by the fact that the first simulation generates triangles in a square rather than the whole plane, something the second simulation avoids?

[Philip Nicoletti]

I am not sure that the answer is known ...

http://mathworld.wolfram.com/ObtuseTriangle.html

[nuzzle]

I am not sure that the answer is known ...

http://mathworld.wolfram.com/ObtuseTriangle.html

Well, the OP's problem is for an acute triangle but I suppose its the same solution strategy if it were obtuse.

Anyway your link states it's impossible to generate random points in the infinite plane. I don't think this matters really because a triangle is invariant under scaling and translation. Take any triangle in the plane. You can scale it and move it to fit any square in the plane without changing its inner angles. No amount of scaling or moving will change whether a triangle is acute or not. This means that you can as well generate the triangle in a square of your choise in the first place. This is consistent with my simulation result which are the same regardless of the size of the square. I wouldn't be surprised if the problem turns out to have some "fractal" aspect, that it's the same regardless of scale.

If someone wants to try this simulation an acute triangle is one where all three inner angles are less than 90 degrees. It's simple to test this if you have the lengths of the triangle sides. A triangle is acute if this relation is true,

c*c < a*a + b*b

where a, b and c are the lengths of the sides of the triangle and c is the longest.

[superbonzo]

I am not sure that the answer is known ...

http://mathworld.wolfram.com/ObtuseTriangle.html

I would'nt say that the answer is unknown... and I'm quite surprised that teachers give such bad-posed problems .

The problem here stems from the common confusion on what the terms probability and randomness mean. Indeed, there are different conceptual definitions of them that agree on the practical results (in the sense that given two probability theories T and V a calculation in T can be cast in a valid calculation in V) but are very different from a foundational point of view which is the key aspect when well-posedness is the issue.

For example, the most common form of a probability theory consists in the specification of a probability measure over a set, that is a triple (X,O,p) where X is the "configuration" set, O is the sigma algebra of "events" (="measurable" sets of configurations) and p is a function from O to the real interval [0,1] satisfying certain axioms (total additivity,...).

Here the specification of the configuration space and events is part of the definition of the problem. Thus, expression like "randomly pick X from Y" have no sense until you have properly defined Y, a sigma algebra of Y's subsets and a probability measure over them. If you have demonstrated that they satisfy the axioms of a probability space then you can start answering questions about it (eg. what's the probability of a specific event E, ...).

You cannot liberally say "randomly pick X from Y" becouse there's (in general) an infinite number of possibile inequivalent probability structure on the same set. It's like asking how much does something cost without specifying any currency.

In the OP example, you must define what a triangle is, then you introduce a probability measure over the sets of triangles. Each different choice will give in general different results. For example, if your triangles are triples of points on the euclidean space of dimension 2 R2 then given any bounded measurable set A in R2 you can define a uniform prob.measure over A as p(E):=l(E)/l(A) where l(-) is the Lebesgue measure (eg. the "standard" measure over R2 ). Then you can ask the question: what's the p.measure of the set of acute triangles ( in A^3 ) ? whenever you change A (a square, a circle interior, ...) you'll get a different result (of course, in general).

BTW, note that R2 does not admit a translation invariant (eg.uniform) probability measure, for this reason Philip's link says that there's no way of randomly picking a triangle from the whole plane. But again this is by definition. In fact, nothing stops you from taking the same set (R2) and introducing another geometrical structure admitting a uniform prob.measure.

In conclusion, you first need to define what's the more natural definition which best fit your foundational assumptions on the problem.

[nuzzle]

I would'nt say that the answer is unknown... and I'm quite surprised that teachers give such bad-posed problems .

Well, open and under-specified problems are fun and hopefully the results are discussed in class.

At least to be able to perform a computer simulation the infinite plane must be limited to a region. Two natural choises are a square and a circle. Is there a difference between these two shapes? Yes there is. The diagonal of a square is longer than the side. This means the orientation of a triangle may determine whether it's going to fit or not. The square induces a directional bias which the circle is free from.

So the introduction of a limiting region definately influences the problem, but of all possible shapes it seems the circle has the least impact. Does the size of the limiting reqion matter? Not according to the results of my simulations. The probability of getting an acute triangle is the same regardless of the size of the limiting region. This is quite interesting I think (if it's true). It suggests the problem has a fractal nature. The proportion of acute triangles is the same regardless of scale.

The formula I've used to identify acute triangles is defined here,

http://mathworld.wolfram.com/AcuteTriangle.html

I've been able to locate the analytical result of the problem for a circular limiting region,

http://www.math.sdu.edu.cn/mathency/math/o/o012.htm

That reference treats obtuse triangles but they're just the complement of acute triangles so from (1) in the above reference I conclude that the solution is,

4/(pi*pi) - 1/8 = 0.2802847

This is very close to the result I got from my simulation.

The remaining question of course is how the analytical solution is accomplished. And also if it's valid regardless of circle size. I suspect that. Finally the introduction of a limiting region definately influences the solution. It rules out certain triangles which must skew the probablities (just as a square region skews it compared with a circular one). Whether a solution exists without a limiting region is an open question I think. Could someone please call William P. Thurston and ask.

double rnd() { // random double between 0.0 and 1.0
	return double(rand()) / double(RAND_MAX);
}

void test() {
	srand(unsigned(time(0)));

	int N=1000000; // number of tries
	double L = 1.0; // size of square side and circle diameter
	int n = 0; // hit counter
	   // square region
	for (int i=0; i<N; i++) {
		double ax = (rnd()-0.5)*L; // 3 random points within square
		double ay = (rnd()-0.5)*L;
		double bx = (rnd()-0.5)*L;
		double by = (rnd()-0.5)*L;
		double cx = (rnd()-0.5)*L;
		double cy = (rnd()-0.5)*L;
		
		double a2 = (ax-bx)*(ax-bx) + (ay-by)*(ay-by); // side lengths squared
		double b2 = (bx-cx)*(bx-cx) + (by-cy)*(by-cy);
		double c2 = (cx-ax)*(cx-ax) + (cy-ay)*(cy-ay);
		
		if (a2+b2>c2 && b2+c2>a2 && c2+a2>b2) n++; // count acute triangles
	}	
	std::cout << double(n) / double(N) << "\n"; // print frequency (probability)
	
       // circular region
	n = 0;
	for (int i=0; i<N; i++) {
		double ax,ay;
		do {
			ax = (rnd()-0.5)*L; // random point
			ay = (rnd()-0.5)*L;
		} while (ax*ax + ay*ay > L*L/4.0); // reject until point is within circle
		double bx,by;
		do {
			bx = (rnd()-0.5)*L;
			by = (rnd()-0.5)*L;
		} while (bx*bx + by*by > L*L/4.0);
		double cx,cy;
		do {
			cx = (rnd()-0.5)*L;
			cy = (rnd()-0.5)*L;
		} while (cx*cx + cy*cy > L*L/4.0);
		
		double a2 = (ax-bx)*(ax-bx) + (ay-by)*(ay-by); 
		double b2 = (bx-cx)*(bx-cx) + (by-cy)*(by-cy);
		double c2 = (cx-ax)*(cx-ax) + (cy-ay)*(cy-ay);

		if (a2+b2>c2 && b2+c2>a2 && c2+a2>b2) n++;
	}	
	std::cout << double(n) / double(N) << "\n";
}

[superbonzo]

Well, open and under-specified problems are fun and hopefully the results are discussed in class.

maybe they are fun but they are also dangerous. It's a matter of bad-posedness and not of "under" specification. In science, bad posed problems should be absolutely avoided because they are difficult to diagnose and treat being of essentially physcological nature.

Of course, this case is trivial and has an easy in some sense acceptable solution but liberally thinking about probability (and geometry and mathematics and phsyics in general ... ) can give disastrous results in less trivial ( and more interesting and useful ) situations.

but of all possible shapes it seems the circle has the least impact. Does the size of the limiting reqion matter? Not according to the results of my simulations. The probability of getting an acute triangle is the same regardless of the size of the limiting region. This is quite interesting I think (if it's true).

again, this easily follows from the very definition of the problem; as I mentioned in my pervious post what you call "randomly picking points in a finite region" is a probability measure P(E):=L(E)/L(A) where E is any measurable subset of a bounded measurable subset A of the euclidean space R2 and L(-) is the Lebesgue measure. Now, L satisifies the property L(k*X)=|k|L(X) where X is any measurable set, k any real number and k*X is the set of "scaled points" {k*x, x in X}. Thus the probability of an event is scale invariant whenever the event is scale invariant (in the sense that sending A into k*A sends E into k*E ). Of course angle properties are scale invariant (and this has little to do with fractals...).

The remaining question of course is how the analytical solution is accomplished.

it's a simple integral, in the circle case easily solvable in polar coordinates. If you try that you'll directly see that the event is indeed invariant of scale ( eg. vector multiplication by a real number ).

Whether a solution exists without a limiting region is an open question I think.

There's no absolute/universal/natural solution to the problem. There's an infinite number of (often easily) solvable specific problems. For example, you could take the limit of the probability with respect to a monotonic sequence of measurable sets (like a growing sequence of circles, squares, circles and squares and so on...) and each time you'll obtain a different limiting result ( which includes non convergence ), in general.

Of course, you could "feel" that a growing sequence of circles is the "right" sequence; in this case ( as with any sequence {X_i}_i>0 where X_i+1 = k*o*X_i , k real, o an orthogonal transformation ) the probabilities P(E_i) are constant thus the limit trivially converges to P(E)=P(E_i) for any i.

But again "picking randomly" from any unbounded set of an euclidean space in a translation invariant way is pure-non-sense.

[nuzzle]

There's no absolute/universal/natural solution to the problem.
.....
But again "picking randomly" from any unbounded set of an euclidean space in a translation invariant way is pure-non-sense.

Have you discussed this with Thurston?

Mathematics has a long history of seemingly impossible problems. Then someone looks at it from a fresh angle and suddenly there's an unexpected solution. And especially probability is problematic. The jury is still out on what it really means. There are deep issues waiting to be resolved. Math is nothing but a tool you know. Maybe you're applying the wrong yardstick. A problem doesn't become nonsensical just because your favorite yardstick cannot measure it. I wouldn't be too categorical I were you.

If you feel the analytical solution on a limiting cicle is simple, why don't you post it? It's been two weeks now since the OP started this thread so it should be appropriate.

[nuzzle]

I'm posting a new solution here,

http://www.codeguru.com/forum/showth...33#post1924433