Math Quiz 9
 

What's the average length of all the line segments which can be drawn inside a 1 inch square?

(accurate to 5 decimal digits)

(show your work)

Re: Math Quiz 9
 

point of clarification: I assume you mean the average of all possible line segments, which allows for intersecting and overlapping lines, if drawn within a single square. For example, you could have an X formed by two lines stretching from opposite corners, or you could have two lines that lay on top of each other, one going from corner to opposite corner and the other from the center to the same corner.

Re: Math Quiz 9
 

by "inside" are they allowed to touch the edge of the square?

Re: Math Quiz 9
 

Does it matter?

Re: Math Quiz 9
 

.42833
I I'll post my work tonight

What assumed was that when you do this, every line length possible creates a square with rounded edges with radius from 0 to 1/2. So I integrated all those together and divided by 1/2 to get my answer

Re: Math Quiz 9
 

My second attempt over lunch came up with 0.55272, but I'm pretty sure that's not right (It's too high). I know what i'm missing from my equations (logically, even if i haven't figured out how to express it mathematically just yet) though.

I just wish I remembered more of my calculus than I do!

Re: Math Quiz 9
 

I finally came up with 0.28967 as my final answer. Work below, colored white so people can ignore it until they've done their own work on the problem :) Note: I don't remember my calculus very well anymore, so I had to use wolfram alpha to get me (hopefully) close enough!

To solve this (assuming it's correct), I needed a couple of components and assumptions/assertions.

Lets start with a simple case - the average length of line segments contained within a N length line. A good description of this can be found here: http://math.stackexchange.com/questi...ints-on-a-line

What that boils down to, is that if I draw a line such that it intersects two edges of the square, taking the length of that line divided by 3 gives me the average length of every line segment that sits on that line. This little trick lets us GREATLY simplify the calculations, as we can use it to assume we're only looking at lines that intersect two walls of the square, and effectively ignore snort lines that don't intersect the lines of the square.

So, with that in hand, we can now figure out the length of every possible line that intersects two lines of the square. This can be broken down into two categories: lines that intersect adjacent edges of the square, and lines that intersect non-adjacent edges. Due to the symmetry of a square, we know that the first group can be simplified into 4 repetitions (top/right, right/bottom, bottom/left, left/top) and the second into 2 repetitions (top/bottom, left/right). This will come in handy later.

So, lets look at the case where you have adjacent sides. You really have two variables here, X and Y, each being an independent number between 0 and 1 representing their location on one of the sides, and the line that stretches between them. The length of that line, as defined by the Pythagorean Theorem is sqrt(x^2+y^2)... but remember we want that length/3 to get the average length of line segments along it. And remember that we have an infinite number of points between 0 and 1 for both x and y... calculus! So, written in a form wolfram alpha will recognize, integrating over x and y gives us:

integrate integrate (sqrt(x^2+y^2)/3) dx dy from 0 to 1 from 0 to 1

or 0.255065.

We can do the same for the case of non adjacent sides. Here the equation is a little trickier, but ultimately the line length is sqrt((x-y)^2+1). Dividing by 3 and integrating gives us:

integrate integrate (sqrt((x-y)^2+1)/3) dx dy from 0 to 1 from 0 to 1

or 0.358879.

Keep in mind that the average of an integral is that integral times 1/(b-a) - in this case, b-a is 1, so we don't need to do anything else.

So, lets get these two numbers together. Remember, we have 4 sets of the adjacent sides, and 2 sets of the non-adjacent sides. And since those sides all integrated over the same values, we should just be able to average the sets, right? So, averaging those in proportion gives us:

(4*0.255065 + 2*0.358879)/6

or 0.28967.

Re: Math Quiz 9
 

Do a sanity check with a simple Monte Carlo simulation.

Re: Math Quiz 9
 

:confused:

:confused:

Re: Math Quiz 9
 

Here's my wild guess: 0.52026

In other words, sqrt(2)/e

Why?

I ran a simulation with 100M iterations and got 0.521388
The value seemed to be decreasing with greater numbers of iterations. Then I plugged the value into this handy tool and took the first result :rolleyes:

Re: Math Quiz 9
 

After seeing the original post earlier today, I did not check back until I had this. It does not seem that anyone got as far as I did:

Initial thoughts and reasoning:
After looking at the problem for about a minute, my "eyeball integrator" came up with "a bit ovor 0.5". While I did not go through all these steps conciously, this is roughly what I think happened:

Consider a circles of radius 1/2 unit and 1 unit. Considering 25 points in a 5x5 grid, including the corners of the square and the center of the square.
When the circles are co-centered with the square, about 79% of the square is inside the small circle, all within the large circle. There is one such point.
When the circles are located halfway between the center and an edge, the small circle covers 66% of the square, the large circle all of the square. There are four such points.
When the circles are located halfway between the center and a corner, the small circle covers 55% of the circle. The large circle covers 99+% of the square (ignore). There are four such points.
When the circles are located at the center of an edge, the small circle covers 37% of the large square. About 4% of the square is outside of the large circle. There are four such points, but only half of a square centered here is inside the square. Weight=2.
When the circles are located halfway between the previous point and a corner, the small circle covers 33% of the square. About 8% of the square is outside the large circle. There are 8 such points, only half of the square centered here is inside the big square. Weight = 4.
When the circles are located at the corner, only 18% of the square is inside the small circle, and 21% of the square is outside the large circle. There are four points, onle a quarter of a square centered here is inside the big square. Weight=1.
Therefore, for an arbitrary point, .79 + .18 + 2 * .37 + 4 * (.66 + .55 + .33) / 16 = 49% of segments are shorter than 1/2 a unit. Likewise, (.04*2 + .08 * 4 + .21 * 1)/16 = 4% of the segments are longer than a full unit. I expect the answer to be close to a half unit, perhaps a bit larger.

Next, a numerical solution:Output: [code]
10 0.518687
20 0.520757
30 0.521121
40 0.521247
50 0.521304
60 0.521336
70 0.521354
80 0.521366
90 0.521375
100 0.52138
110 0.521385
120 0.521388
130 0.521391
140 0.521393
150 0.521394
160 0.521396
170 0.521397
180 0.521398
190 0.521399

This appears to meet Ether's criterion of 5 significant digits at ".52140".

Nonetheless, let's try to find a closed-form solution. As indicated in my numerical solution, the problem is at its most basic the ratio of two quadruple integrals over the interval of [0,1], the content of the numerator integral being the hypotenuse formula and the denominator being unity. As integrating 1 over the range 0 to 1 yields 1, doing this four times still yields one, so we can skip the denominator. I recognize that this solution counts all of the non-zero-length segments twice,and the zero-length segments only once. As there are infinitely fewer zero-length segments than non-zero-length segments, and I am calculating an average, this is a problem that I can safely ignore.
I had originally envisioned (i,j) as one point, and (k,l) as the other point, and did not see how to approach the problem. Fortunately, I used the form above for the numerical solution, which seems to indicate a simpler integral.
Let us address the simpler problem of "What is the average length of a segment within the unit line segment?" and keep track of the statistics. This problem is more easily understood by considering individual points for the "outer integral" and what the lengths are for the "inner integral".
When the outer integral as near the center, the inner integral yield lengths equally likely between 0 and 0.5 (one each way). When the outer integral variable is at an end, the inner integral value yields lengths equally likely between 0 and 1.
When the outer integral variable has a value x<0.5, the inner integral yeilds 2 solutions for numbers less than x, and one for answers between x and 1-x.
These indicate a linear ramp of "x-lengths" from a maximum likelihood of 1.0 at lenth zero, to a likelihood of 0.0 at length one. Multiplying this by the line length yields the integral of 2(1-x)(x), or 2(x-x²). The integral of 2x over 0..1 is one. The integral of 2x² over 0..1 is 2/3. The average length of a segment on a unit segment is 1/3.

The simple linear ramp found in the integral above implies a fairly simple two-variable integral for the average length of a segment in a square:
4ʃʃ(1-x)(1-y)√(x²+y²)dxdy, both integrals being over 0..1.
After looking for a couple of hours, I’ll admit that I do not see an obvious closed-form solution. Unless I find one in the thread, I’ll probably search for one on and off for the next two or three months.

Re: Math Quiz 9
 

No one has yet come up with an answer correct to 5 decimal places.

OK to use whatever computational tools you like.

Re: Math Quiz 9
 

Here's a script I wrote in order to try to solve this problem. My second attempt was to, for each line length find the area where the center of the line could be. This resulted, for line length 0 --> 1 in a box with quarter circles cut out. For 1 --> sqrt(2), it was a little more complicated. Overall, it gives the answer of 0.77019523

Re: Math Quiz 9
 

Sanity-check your answer with a simple Monte Carlo simulation.



*this can be done with a one-line AWK script

Re: Math Quiz 9
 

What is a Monte Carlo simulation?

Re: Math Quiz 9
 

https://en.wikipedia.org/wiki/Monte_Carlo_method

Randomly sample the set of all line segments, and find the mean length of only the segments in the sample (a finite number chosen to suit your computational resources, rather than the uncountably infinite number in the entire set). If the sampling matches the probability distribution/weighting of the set, then the law of large numbers says your mean will approach the true mean as sample size increases.

Re: Math Quiz 9
 

Aren beat me to it.

One-line AWK script:

BEGIN{for(i=1;i<100000;i++){sum+=sqrt((rand()-rand())^2+(rand()-rand())^2);}print sum/i;}

Re: Math Quiz 9
 

I ran the Monte Carlo thing in a python script and the answers, each run with 1,000,000 trials, were all around 0.333. I'm gonna keep thinking, though, how to get an exact answer.


EDIT: I found the error - the value comes out to 0.521

Re: Math Quiz 9
 

I am thinking the answer is a number that is very small (close to 0), as you can draw a ton more 0.000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 01 lines than you can 1 inch (or larger on a diagonal) lines.

Re: Math Quiz 9
 

Yet if you look at the Monte Carlo simulation, it looks closer to 0.521"

Re: Math Quiz 9
 

Your script has an error.

Compare it to the one-line AWK script I posted.

Re: Math Quiz 9
 

My simple Python Monte Carlo script gave me an average of 0.521408 (or 0.52141 rounded to 5 digits) in ~5e9 iterations (10 miles of hiking worth).

Code is below:

I split it into two scripts just so I could stop the computation whenever without altering the result.

Edit: Reps to whoever finds the bug in my code and explains what it does.

Re: Math Quiz 9
 

That is the correct answer. Reps to you :)

Re: Math Quiz 9
 

Now, how would you get the correct answer accurate to, let's say, 8 decimal places?

Re: Math Quiz 9
 

Makes no logical sense unless the question is improperly worded or bounded. You can fit an infinite number of lines in the box, and fact is, more lines closer to 0 in length fit in the box than lines averaging 0.52xxxx

Re: Math Quiz 9
 

I think the problem is more "Choose two random points inside by a 1" square and measure the distance between them. Repeat infinitely. What's the average of those measurements?"

Re: Math Quiz 9
 

I agree then - your answer would make sense if that were the question. However, it was:

What's the average length of all the line segments which can be drawn inside a 1 inch square?

Re: Math Quiz 9
 

If the problem is interpreted as you describe (What is the average length of all the line segments that could be packed into a 1" square at once without overlapping?), there would be no meaningful answer, since infinite line segments of any length l < sqrt(2)" could be fit within the square, as line segments have no thickness thus can be packed infinitely densely.

Re: Math Quiz 9
 

Exactly - hence why people struggled to answer I think......

Re: Math Quiz 9
 

Precisely ln(1+sqrt(2))/3 + sqrt(2)/15 + 2/15

Or approximately 0.52140543316
Rounded to 8 digits: 0.52140543
Rounded to 5 digits: 0.52141

A fun exercise in every integration tool I've ever learned, plus a cool rationalization trick I wasn't familiar with.

The computation took a bit to hash through some arithmetic errors and one silly differential error (chain rule!). In practice you probably wouldn't bother to do this (or use a symbolic manipulation tool like Mathematica - this is how I checked my work), and sometimes there is no closed form for the integral. To get 8 digits simply run a larger Monte Carlo simulation (a couple lines of code instead of several pages of derivation). In the end we are always limited to some finite number of digits, so numerical methods win out.

Re: Math Quiz 9
 

Wonderful! I've been stuck on the ln(1+√(1+y2)) terms. Didn't think to keep the ln(y) terms with them. (I did the x integrals first, so was using y where you have x-bar).

Edit - Now that I've had a chance to spend more than a few minutes on it, I see that wasn't the trick at all. I just need to go back and re-learn integration by parts.

Edit2: Gathering up my paper notes, this is what I had so far (haven't double-checked everything yet):

Checking the CRC Handbook integrals table (2000 edition):
Where the | is an implied evaluation over 0..1.

• ʃ(1-y)( (√(1+y²)/2+y²ln(1+√(1+y²))/2-y²lny/2+(1+y²)3/2/3-y3/3)dy

evaluated over y=0..1. This expands to ten terms:

1. ʃ√(1+y²)dy/2
2. -ʃy√(1+y²)dy/2
3. +ʃy²ln(1+√(1+y²))dy/2
4. -ʃy³ln(1+√(1+y²))dy/2
5. -ʃy²lnydy/2
6. +ʃy³lnydy/2
7. +ʃ(1+y²)^3/2dy/3
8. -ʃy(1+y²)^3/2dy/3
9. -ʃy³dy/3
10. +ʃy⁴dy/3

I know or quickly found all but the forms with ln(1+√(1+y²)) in an online table of integrals or the CRC table: http://2000clicks.com/mathhelp/Calcu...rals.aspx#CatL
I have also worked through term 3, using your same u for integration by parts, and term 4 looks trivially different. Now I'm going to look for a solution that exploits the symmetry between x and y.

Re: Math Quiz 9
 

Really nice work Aren and Gus.

Here's how I did it.

Re: Math Quiz 9
 

Now that this has been satisfactorily solved, I'll post a youtube video of this problem that I literally saw the week before Ether posted. I didn't feel right in just posting it, or claiming it as my own solution.

The problem gets to the 4ʃʃ(1-x)(1-y)√(x^2+y^2)dxdy GeeTwo derived, but then it does a polar coordinate substitution to make the integration "easier"
It's another approach which gives a closed form solution, demonstrating that there can be multiple ways to validly solve a problem.

Re: Math Quiz 9
 

There are uncountably infinite lines of length 0.01, just as there are an uncountably infinite number of lines of length 0.52.

It makes no logical sense to say that there are "more" or "less" of one uncountably infinite thing than another uncountably infinite thing.

Re: Math Quiz 9
 

Excellent point. Hence the question was not worded well enough to allow for a proper solution. :D

Re: Math Quiz 9
 

The question is worded just fine. It asks for an average length of all lines, not the length of the line of most frequent length.

Re: Math Quiz 9
 

For example, would you be able to answer the question: "What is the average of all numbers between 0 and 1?"

Re: Math Quiz 9
 

Also, we got several proper solutions...

Re: Math Quiz 9
 

Cool, I much prefer how you dropped to the double integral, I don't think about stats enough when doing these things.

While you can certainly say that there are multiple ways to solve a problem, I'll venture that the one presented in the video is considerably more elegant than mine :p The immediate trig sub works wonders on the rest of it.

Thanks for the link!

Re: Math Quiz 9
 

This is the route I was following. (I have not looked at the video, so perhaps this is exactly what is there.) My original thought was to substitute r for √(x²+y²), rcosθ for x, and rsinθ for y. dxdy then becomes rdrdθ. While driving to mom's house for Sunday dinner, I realized that I could take advantage of the symmetry of x and y by rotating θ by π/4, so that y is √2(cosθ + sinθ)r/2 and x is √2(cosθ - sinθ)r/2. Then the integration is over an interval symmetric over θ=0, and any odd terms in θ can be tossed (I already figured out while driving that there aren't any, however), and then the integration can be done from 0 to π/4. The fun part is the limit of integration - for r<=1, there's no issue. For 1<r<√2, the limits of one integration need to be set so that the maximum of r is √2/(cosθ + sinθ) (ignoring the required absolute values because I've limited θ to the first quadrant). Alternately, the limits of θ can be set based on r.

It makes just as much sense as to ask "What fraction of integers are even?" There are uncountably many even integers and uncountably many integers, and it is possible to identify a different even integer for every integer (e=2i), so that the sets have the same number of elements. This does not change the equally meaningful statement that exactly half of the integers are even.

Re: Math Quiz 9
 

You are using the word "uncountably" incorrectly here.

The integers are countably infinite.

The reals are uncountably infinite.


It's meaningful only if you define what you mean :)

If you mean "the set of all even integers has an asymptotic density of ½", then yes, it's meaningful. Otherwise, not.

Re: Math Quiz 9
 

These solutions are quite above my mathematics level, but nonetheless I can somewhat follow along, thanks for the cool thread.

Re: Math Quiz 9
 

That has a clear answer, despite the infinite number of numbers between 0 and 1, as each number only occurs once.

The original question has no proper solution as worded.

However, I do applaud the high level of solutions that were provided - well done.

Re: Math Quiz 9
 

:confused:

I'm not sure what's missing... What extra information is being used in solving this problem?

Re: Math Quiz 9
 

"Countably infinite" is still uncountable for us mortals. When you finish, please get back to me.



I fully admit to having (yes, consciously and deliberately) blown through the difference between aleph null and aleph one in my earlier reply, to make a statement that might make sense to shose who found the original problem "meaningless". (That is, I was more worried about enlightenment than mathematical rigor.) I specifically addressed your concern that the even integers and all integers are of the same cardinality.

A far as I am aware, any argument that decides the statement "Half of the integers are even." as meaningless can also be used to decide the concept of "average length of a line segment located within the unit square" as meaningless -- or worse.

Edit:
OK, I'll go with that -- and it's a remarkably fast asymptotic function, as of every pair of consecutive integers, exactly one is even.

Here's a bit more precise statement: For every set of consecutive integers with a non-zero, even number of members, exactly half are even.

Re: Math Quiz 9
 

Each line segment in the problem statement also appears only once. So the two questions are directly comparable.

If you can answer my first question (with calculus if you know any), try this one (again with calculus if you know any):
What is the average x coordinate of all ordered pairs (x,y) within the range 0<x<1 and 0<y<1?

In this scenario, multiple (in fact, uncountably infinite) ordered pairs can contain the same x coordinate, but the statement of the problem is sound.

Re: Math Quiz 9
 

Where in the question does it state that each line segment may only appear once? If that is true, then I 100% agree with you.

Re: Math Quiz 9
 

FWIW

Re: Math Quiz 9
 

Question:

The average of all segments is the sum of the length of each segment within the set divided by the number of segments in the set. There is no reasonable interpretation of average which counts the same element of the sample set more than once.


Consider the following question:
What is the average number of autonomous boulders scored per match by robots in Michigan?

To solve this problem, you would first identify all of the robots in Michigan, then determine their autonomous boulders scored per match, then sum each of those scores together, then divide by the number of robots in Michigan.

What you cannot do though, is double count 33, quadruple count 67, and triple count 469, while counting all of the other teams once. If you do this, you are not determining a quantity which can be accurately described as "the average number of autonomous boulders scored per match by robots in Michigan." Also, just because two teams score the same number of autonomous boulders does not necessarily make the two teams identical. Likewise, two line segments which have the same length are not necessarily identical.


For the OP's question, we could theoretically follow the same procedure:
Identify all of the line segments in the set
Determine their lengths
Sum the lengths together
Divide by the number of segments

The processes are identical because the definition of average does not change when dealing with infinite sets. The tools of calculus can then be used to arrive at an answer that would otherwise take an infinite amount of time to solve if you were to try to enumerate every line segment. It is a bit unfortunate that our fancy math notation hides the fact that we essentially do the above to arrive at our answer, but that is a small price to pay to be able to determine properties (like average) of infinite sets.


I hope that makes things a little clearer. Essentially, it makes no more sense to double count line segments than it does to double count 33's auto boulder scoring ability. The fact that we are dealing with an infinite set does not change anything in that regard.

Re: Math Quiz 9
 

FTFY. When discussing cardinality, distinction between aleph-0 and aleph-1 is key. The integers (aleph-0) have measure 0 in the real line (aleph-1), so any "proportion" there would be 0.

Rather, what composes half of an infinite set is not well-defined at all, since there is no well-defined limit of half of a finite set. The average of an infinite set, on the other hand, is well understood as the limit of the average of a finite set (an infinite series or an integral).

The error bounding condition is still error <= 1/2n, so not quite that fast. You just happen to hit the limit exactly on every other term.

Re: Math Quiz 9
 

Doesn't work. Robots who can play in Michigan also play--and have scored auto boulders--outside of MI. So unless you mean "robots from Michigan", it's a much easier solution.

Count the matches played in MI, count the auto boulders scored in those matches, note that humans can't score boulders, and divide the auto boulders scored by the number of matches. Unless you really mean the median or the mode.

Re: Math Quiz 9
 

It's worth enough to make me reconsider doing theta integration first so I can generate a closed form for this distribution. :)

Re: Math Quiz 9
 

I did mean "all robots from Michigan." Your interpretation is not something I had considered. Yours seems a bit pedantic to me, but I understand how one could reasonably arrive at that interpretation.

Re: Math Quiz 9
 

Descriptive statistics for 10 million random samples:

Re: Math Quiz 9
 

I finished the polar integral up to r=1, found the mode to be (4+√(16-3π))/3 = .47859...

So thanks for the sanity check!

Other stats so far:

• The first part of the histogram curve (0..1) is 2πr - 8r² + 2r³.
• I have covered π/4 of the square (78.54%) by area
• I have integrated over π - 13/6 of the segments (97.49%).
• The numerator of the integral is up to 2π/3 - 8/5 = .494395..
• There were only three terms in the integral over Θ, the most complicated one being cos2Θ.
• I have only have four terms to integrate over r=[1..√2]. Two are powers of r, one looks familiar from the rectangular integration, and the last one looks strange, but probably no worse than anything in the rectangular problem.

Definitely an easier way to go unless that last one proves nastier than it looks.

Also, doing the integral this way explains the sudden change in behavior of the histogram at length=1.

Re: Math Quiz 9
 

Here is a generalized Monte Carlo simulation in python for the average line segment length in any regular polygon with one square unit of area:

The following are average lengths based on ten million samples:

Triangle: 0.554367342879
Square: 0.521395852676
Pentagon: 0.514797872593
Hexagon: 0.512588030594
Heptagon: 0.51176618103
Octagon: 0.511213933924
Nonagon: 0.511120940654
Decagon: 0.511039068646
25-gon: 0.510860752385
100-gon: 0.510794294963
1000-gon: 0.510750983962
1000000-gon: 0.510902061585

Can anyone think of another general way of generating a random point in an n-gon that is more efficient than mine for small values of n (without sacrificing significantly for larger values of n, of course)? When n=3, my program is discarding almost 60% of the points it generates.

Re: Math Quiz 9
 

1. Generate a random point (xrand,yrand) within a unit square.
2. If xrand+yrand is greater than 1, use the point (1-xrand, 1-yrand) instead. You will now have a point within a right triangle of unit width and height that I will call (x, y).
3. Determine the apothem a and the perimeter p of your regular n-gon.
4. Regular n-gons are made up of n isosceles triangles which have a base width of p/n and a height of a. Each of these isosceles triangles is made up of 2 right triangles of width p/(2n) and height a. Take your point (x, y) and scale it accordingly to a right triangle described above, to get a point (x*p/(2n),y*a).
5. Randomly decide if this point will be on the left or the right half of an isosceles triangle (you could even use the leftover data from part 2 if you don't want to generate another random number).
6. Randomly decide in which of the n isosceles triangles your point should go.

100% of these points will be within your regular n-gon, and the distribution will be uniform.

Given, you do need to generate at least 3 random numbers for this process, so if generating random numbers is resource intensive you may want to look for other methods.

Re: Math Quiz 9
 

You can do this with two random numbers by noticing that those right triangles get pretty skinny. Essentially, take the regular N-gon apart into those right isosceles triangles, and re-arrange them into a rectangle. In the large N limit, this rectangle will only be pi times as wide as it is tall.

Procedurally, calculate W = floor(r1/N); this tells you which wedge you are in (0 to N-1), then use r1 - W/N and r2 to determine where in that wedge as suggested above.

To do this (or Caleb's original suggestion) efficiently, you may want to pre-calculate a trig table of appropriate size.

Edit - and thanks, Caleb! I was thinking about attacking the same problem with the unit circle next, and I just realized I can adapt this technique to randomly pick r and theta with a uniform spatial distribution.

Re: Math Quiz 9
 

Slick, I like that. I was pretty confident that there existed a way to do get there with just two random numbers, considering that we were in a relatively nice-behaving 2D space, but I didn't realize how close I was.

Re: Math Quiz 9
 

So the distribution of lengths is Rayleigh. Neat example.

What would the distribution look like if the line segments were contained in a cube (3D) boundary? That one may be easier to visualize using a Monte Carlo simulation.

Re: Math Quiz 9
 

Rayleigh distributions can't have upper bounds though, right? This distribution will clearly have an upper bound at sqrt(2).

Re: Math Quiz 9
 

Similar, but not quite a Rayleigh Distribution.

After going to signed x ̅ = x₁-x₂ and y ̅ = y₁-y₂ components, but before collapsing the four quadrants, this problem is to evaluate the mean of the magnitude of a two-dimensional random vector whose coordinates are independent, identcially distributed, mean 0 triangular variables. That is, x ̅ and y ̅ are defined by the triangle function, max(0,1-abs(x)), rather than the normal distribution which would mean one proportional to e^-ax2 (aka the Gaussian "bell curve"). As Caleb notes, this distribution, like the normal distribution, has no upper bound (an infinitely long tail).

If the working space were a cube, the small end of the distribution would start out with zero slope and a parabolic ramp of 4πr². It would peak at a somewhat higher length (WAG of 0.6), have a similar change of curvature at length 1, and have an upper bound at √3.

Re: Math Quiz 9
 

Re: Math Quiz 9
 

Wrapping up some loose ends...

Why or why not? Explain.

Re: Math Quiz 9
 

If I could,

The reason I don't think it matters is that let's say you were to take one end point of any line very very very close to the edge. If you keep pushing it infinetly closer, it's essentially on the edge already (limits woo), so it doesn't matter.

Re: Math Quiz 9
 

Enough hours have passed:

Allowing the borders of the square does NOT matter. The likelihood of one of the endpoints falling in any given area within the permissible bounds is proportional to the area. The lines at the edge of the square have length but zero area, so even if they're allowed, the selected point will "never" be on the edge. A bit more formally, the chances of a point on an edge being chosen is infinitesimally small and (excepting something massively discontinuous like a delta function) does not affect the integration over the area.

Re: Math Quiz 9
 

You can generate uniformly distributed coordinates in a unit circle much more easily, actually (if you look at genPolyPt() in my code, I do exactly that). Just setting r to the square root of a random number will correct the unevenness of the distribution.

Re: Math Quiz 9
 

What's the average length of all the line segments whose endpoints both lie on the unit square's perimeter?

Re: Math Quiz 9
 

Modified above Monte Carlo code to solve this:

2.1e7 iterations yields 0.73511, standard deviation 0.00095 (between blocks averaging 1e6 iterations). More iterations will give a more accurate answer.

Re: Math Quiz 9
 

Ah okay that makes sense. Thanks!

Re: Math Quiz 9
 

Thank you!

Re: Math Quiz 9
 

Close enough :)

Two billion samples yields a value about 0.003% less than that. Plotting the average vs the number of samples gives a rough view of when you've reached the point of diminishing returns.

Note that this problem can be easily solved using all three methods discussed in this thread:

Monte Carlo simulation

Numerical Integration

Symbolic Integration


Standard deviation is not so meaningful when the distribution looks this this.

Re: Math Quiz 9
 

Yes, apart from the different piecing together the different lengths, every term in the integrals for this problem appeared in Aren's solution.

This is a non-sequitur. Z.B. was referring to the standard deviation across groups of samples, not standard deviation across line lengths. However, the graph of the population also suggests that a nominal MonteCarlo solution might do well to treat these as three separate populations, as Ether has done with the integration cases.

• The "same side" population ramps up from zero, follows a third order polynomial, and goes back to zero at 1.0.
• The "adjacent side" population ramps up linearly from zero to one, has a kink (continuous value, discontinuous slope), and decays back to zero at the square root of two. As Ether has indicated implicitly, note that this side has to be weighted double the other two, because given the first point, the second point can be on only one "same" side, one "opposite" side, or two "adjacent" sides.
• The "opposite side" set has no population with length less than unity, 13+% of its values between 1.00 and 1.01, and 39+% of its lengths between 1.0 and 1.1, and the population continues to decay down to the square root of two.

Edit: By decay, I mean that the population curve is concave up as it approaches zero, not necessarily an exponential decay.

Re: Math Quiz 9
 

5000 samples of sample size 1,000,000.

Mean of the sample means = 0.735089
Standard Error of the Mean = 0.000361

Re: Math Quiz 9
 

OK, another follow-on challenge (cleared with Ether):

What is the average length of all the line segments which can be drawn within the unit circle (1 unit in radius, 2 units in diameter)?

Reps for both the first numeric (good to 1 part per million) and first closed form solution.

Edit: Of course, you must show your work in either case!

Re: Math Quiz 9
 

This can actually be solved in closed form with much less intricate calculus than the case of the square, with proper selection of coordinate system.

Some warmup questions to this if you can't figure out where to start:

• What is the average of the squares of the lengths of all the line segments which can be drawn within the unit circle? [taking out the square root simplifies the problem greatly, and helps provide an upper bound to the original question]
• What is the average of the lengths of all the chords of the unit circle? (That is, line segments with both endpoints on the border of the circle)
• What is the average of the lengths of all the line segments between a point on the [border of] a circle of radius R, and a point within the same circle?

OBTW, with proper scaling, Greg's answer for the 100000-gon of area 1 provides an answer to the original problem good to within 1 part per 10,000:

And, OBTW2: if you can find the closed form, each of the four questions can be calculated in fewer than 10 keystrokes on a calculator with the following buttons:

Re: Math Quiz 9
 

I have posted this figure which I created to describe variables in my calculation of the length of the average line segment from a point on the edge of a circle to a point on the interior. I used this, or a very similar coordinate system, to solve all the "circle questions" except for the one about the mean square of the segments. I am also confident that the same questions can be answered for the sphere using a similar point of view.

Re: Math Quiz 9
 

I did the integral for the average length of a line segment within a sphere, and found that the answer is rational! This problem was actually simpler to integrate (though just a bit trickier to set up) than any of the two-dimensional problems. If no one posts anything (yes, even a "hold on, I'm working it!") on the circle or sphere questions by Wednesday at 1800 US-CDT, I'll post my solutions so we can close out these quiz questions.

Re: Math Quiz 9
 

0.9525383819936485
Sample size: 60 million

Re: Math Quiz 9
 

Post your code and we'll show you where you went wrong.

Re: Math Quiz 9
 

The average length of sphere chords (line segments with both endpoints on sphere surface) is also rational.

Re: Math Quiz 9
 

Yes, as well as the intermediate case where one endpoint is on the sphere and the other is internal. I don't recall whether the mean square length was rational or not; I'll check this evening.

Re: Math Quiz 9
 

It is. (mean square length with one endpoint on surface).

Re: Math Quiz 9
 

I was referring to both endpoints in the volume, but I see that for all three cases (both exterior, one exterior, both interior), the mean length as well as the mean square length are all rational.

Given AM's interest, I will hold off until at least Friday at 6pm to post solutions.

When posting a candidate solution, please show your work, and specify whether you are solving for:

• Circle or sphere?
• Mean length or mean square length?
• Both, one, or none of the endpoints constrained to the boundary?

Re: Math Quiz 9
 

A Monte Carlo simulation written in python and running on my laptop isn't a great solution if 1 part in a million accuracy is required, but since I had essentially already written the program, I figured that I might as well give it a shot. For the average length of line segments in the interior of an r=1 circle, I got 0.9054124568 after 4e10 trials. I'm not certain whether or not this meets the accuracy requirement. I also made minor modifications so that I could simulate the chord problem, and I got 1.2732310914 after 7e09 trials. This problem requires far fewer trials to get an accurate result and I believe this solution meets the accuracy spec. I can post my code if anyone is interested.

Re: Math Quiz 9
 

Wrong by ~3 ppm.

Wrong by ~7 ppm.

Re: Math Quiz 9
 

1) How long did 4e10 trials take to run?

2) Yes, please post your code.

edit:

3) What's the period of the PRNG you used?

Re: Math Quiz 9
 

About 16 hours. My laptop has an Intel Core i7-6700HQ Quad Core and I ran 4 copies of my program at once instead of implementing multithreading. This seemed to work as desired based on the cpu usage and left me with enough overhead to not impact my normal computer use.

Internal points code:

Chord problem code:

I have since made both programs about 2.5x faster by using the polar distance formula to cut down on trig functions (really add up after a few billion trials), by cutting the number of angles generated from 2 to 1 in each trial of the line segment problem, and by switching to using the math module trig functions instead of the NumPy ones. I was somewhat surprised to find that the math module ones are about twice as fast as NumPy's. I've often been impressed by the speed of doing things in NumPy, but it turns out that the Python developers also have some idea what they're doing :p .

I used numpy.random.random(), which uses the Mersenne Twister sequence and has a period of 2^19937 − 1. Unfortunately I wasn't able to run quite that many trials.

Re: Math Quiz 9
 

You can shave a few more CPU cycles by storing the squares of the radii rather than the radii, so you only need two square roots per segment, rather than three. I am not familiar with this detail in python, but in most languages, the dedicated sqrt(x) function is faster than x ** 0.5.

Re: Math Quiz 9
 

Greg, try this for the internal points problem: taking advantage of symmetry, generate 2 random points in Quadrant1, then reflect one of the points into Quadrants 2 thru 4 so you get 4 lengths per iteration. Then you can use 4 times fewer iterations. Also, doing this allows you to significantly optimize the code to eliminate a lot of repetitious floating point operations. I think you'll find that approach to be much faster. I was able to get 1 ppm accuracy in 7 minutes of runtime on a 10-year-old Pentium D desktop machine (using 32 bit compiled code). Here's the pseudocode for it:


Using symmetry for the chords problem, you can reduce the length computation to:
... and when the iterations are complete, multiply the sum by 2.

Re: Math Quiz 9
 

Because sin(x) is symmetric around pi/2, you can further optimize this to:
where pi_2 is pi/2. As before, when the iterations are complete, multiply the sum by 2.

Also, as no one has attempted a closed form solution for these averages, I'm attaching the solutions. I have solved all of the circle and sphere problems for both the mean length and the mean square length. As such, these results can be used to solve for the variance or standard deviation of the population, by calling that:

• variance of the population is the mean of the squares minus the square of the mean
• standard deviation of the population is the square root of the variance of the population

Re: Math Quiz 9
 

In case there are any readers wondering where the above code came from, here's a brief explanation:

Gus pointed out that sin(pi*abs(random-random)) could then be optimized to sin(pi*random).

Some readers may be wondering why. It is due to the interaction between the symmetry of sin(x) around x=pi/2 and the shape of the pi*abs(random-random) distribution.

The distribution of pi*abs(random-random) has the shape f(x):=1-x/pi. That function is symmetric about the point [pi/2,0.5] and has the property that, for any value "a" between -pi/2 and pi/2, f(pi/2-a)+f(pi/2+a) is always equal to 1. This interacts with the symmetry of sin(pi/2±a) to make the distribution sin(pi*abs(random-random)) be the same as sin(pi*random).

Re: Math Quiz 9
 

Hey Math Quiz 9 thread readers,

I'm a bit disappointed to see Gus' paper has only 4 downloads. He put a lot of work into it, and there's some very interesting stuff in there. If you're a math-gifted high school or college student, do yourself a favor and take a look at it.

Re: Math Quiz 9
 

Thanks, Ether! I really did put more work into making it readable than doing the math (though not nearly as much work as for a textbook, which I can vouch is a truly painstaking task if you've never done it). I don't think there's anything in there beyond second semester calculus; I know I was routinely doing more complex multidimensional integrals in second semester college physics.

Anyway, as I promised a while back, I came back to solving the square problem in radial coordinates. Once I didn't try too hard for symmetry and integrated over r first, it was pretty straightforward:

As already established, the mean segment length in Cartesian coordinates is:

Ḹ = 4∫₀¹∫₀¹ (1-x)(1-y)√(x²+y²) dx dy

Converting to polar coordinates, placing the lower left corner of the square at the origin and aligning so that the x axis is along θ=0, the y axis along θ=π/2, we replace √(x²+y²) = r, x=rcosθ, y=rsinθ, and dxdy = rdrdθ. For bounds of integration, note that the lower and left sides of the square are θ=0 and θ=π/2 for 0<=r<=1. The right side is defined by rcosθ=1, or r=secθ for 1<=r <= √2. Similarly the top side is r=cscθ for 1<=r <= √2. This yields:

Ḹ = 4∫₀^π/4∫₀^secθ(1- rcosθ)(1- rsinθ)r rdrdθ + 4∫_π/4^π/2∫₀^cscθ(1- rcosθ)(1- rsinθ)r rdrdθ

In the first integral, we substitute α=θ, and in the second we substitute α=π/2-θ, which means cscθ = secα, cosθ = sinα, and sinθ = cosα. After these substitutions and a reversal of the limits of integration on the second term, the first and second term are identical, so combine them:

Ḹ = 8∫₀^π/4∫₀^secα(1- rcosα)(1- rsinα)r rdrdα
Ḹ = 8∫₀^π/4∫₀^secα r² – (cosα+sinα)r³ + cosαsinαr⁴ drdα

The integrals over r are polynomials:

Ḹ = 8∫₀^π/4[⅓r³ – ¼(cosα+sinα)r⁴ + ⅕cosαsinαr⁵ ]₀^secα dα
Ḹ = 8∫₀^π/4[⅓sec³α – ¼(cosα+sinα)sec⁴α + ⅕cosαsinαsec⁵α]dα
Ḹ = 2/15∫₀^π/420sec³α – 15 sec³α -15tanαsec³α + 12tanαsec³α dα
Ḹ = 2/15∫₀^π/45sec³α -3tanαsec³α dα

To solve the integral of sec³α, try tanαsecα. By the product rule,

dtanαsecα/dα = sec³α + tan²αsecα = sec³α + (sec²α-1)secα = 2sec³α - secα

We can fill in with the well-known integral of secα to offset. The integral of 3tanαsec³α is seen to be sec³α:

Ḹ = 2/15[5(secαtanα + ln|secα+tanα|)/2 – sec³α]₀^π/4
Ḹ = 2/15[5(√2-0 + ln(√2+1)-ln(1))/2 - 2√2 + 1]
Ḹ = 2/15[5ln(√2+1)/2 + 5/2√2 - 2√2 + 1]
Ḹ = 2/15[5ln(√2+1)/2 + √2/2 + 1]
Ḹ = ln(√2+1)/3 + √2/15 + 2/15

Which is the same result achieved by Aren Siekmeier through a much longer process.
The above process did not result in a population density of segment lengths (many of Ether's histograms), which was my primary motivation to do the polar integral. To get this population, leave out the "r" factor representing segment length and integrate over angle only:

Ƥ(r) = 4∫^□(1- rcosθ)(1- rsinθ)rdθ
Ƥ(r) = 4∫^□r - r²(cosθ+sinθ)+ r³cosθsinθ dθ
Ƥ(r) = 4[rθ - r²(sinθ-cosθ)+ r³sin²θ/2 ]^□

For 0<=r <=1, the limits of integration are 0 to π/2. This is the integral over the intersection of the unit circle and this unit square:

Ƥ(r)|_r<=1 = 4[rθ - r²(sinθ-cosθ) + r³sin²θ/2]₀^π/2
Ƥ(r)|_r<=1 = 4[πr/2 - 0 - r²(1 - 0 - 0 + 1)+ r³(1-0)/2]
Ƥ(r) = 2πr - 8r + 2r³

For 1<=r <= √2, the limits are cos^-1(1/r) and sin^-1(1/r) (or equivalently sec^-1r and csc^-1r); this is the integral over the part of the unit square which is outside of the unit circle. To evaluate sin(cos^-1(1/r)) and cos(sin^-1(1/r)), recall that sin²x = 1-cos²x:

Ƥ(r)|_r>=1 = 4[rθ - r²(sinθ-cosθ)+ r³sin²θ/2]_cos^-1(1/r)^sin-1(1/r)
Ƥ(r)|_r>=1 = 4[r(sin^-1(1/r)-cos^-1(1/r)) - r²(1/r-√(1-1/r²)-√(1-1/r²)+1/r)+ r³(1/r²-(1-1/r²))/2]

Ƥ(r)|_r>=1 = 4r(sin^-1(1/r)-cos^-1(1/r)) - 8r + 8r√(r²-1) + 4r - 2r³

Ƥ(r)|_r>=1 = 4r(csc^-1r - sec^-1r) - 4r + 8r√(r²-1) - 2r³

As a sanity check, I calculated the population, population * length, and the integrals of each using excel with a step size of 0.001, and plotted all four (image and excel file attached). The sum of the population was 0.99999947, good to six decimal places, and the average length came out to 0.521405427, which is good to eight decimal places.

Re: Math Quiz 9
 

OK I'm going to drop a bombshell here.

The correct answer to the OP, as worded, is 0.33634

Aren was the first to articulate the key principle when he wrote:
Sampling segments by choosing the segment endpoint coordinates from a random uniform distribution does not match the probability density of the segment lengths in the infinite set.

Re: Math Quiz 9
 

It's hard to disagree with your first figure.

If you can switch the order of integration and then integrate the pdf over theta, then you should have a pdf for L only. I'm trying to wrap my head around why that pdf for L should be different than the one effected by a uniform weighting of dx1dx2dy1dy2 differential elements. The concept in my head is that there's no invertible change of variables with which to set up that translation. The transformation from coordinates to length is not injective, so the Jacobian in the change of variables is zero: hard to divide by, conceivably giving the ratio between our answers in some sort of limit. Or from another view the four-dimensional differential element is of measure zero within the one-dimensional one, reflected by a pdf for the coordinates that is somehow undefined or not finite??

I'm very curious if there is an appropriate pdf for the coordinate approach that would give this result. Or is it just the wrong way to look at the problem?

This seems to boil down to the difference between:
[1] Average distance between all unordered pairs of points
[2] Average length of all line segments
But what's the difference?

Re: Math Quiz 9
 

The difference is in how you choose samples.

If you want the average distance between all unordered pairs of points, then you choose coordinates of pairs of points from a uniform random distribution, and compute the corresponding distance.

If you want the average length of all segments, you randomly choose a segment length, a segment orientation, and the coordinates of the center of the segment. Then you discard any chosen segments which are not inside the square. If you run a Monte Carlo sim of that, you'll get 0.3363

...and you'll get a pdf of L only, if you make a histogram of the data and adjust it to have an area of 1.

Re: Math Quiz 9
 

How practical of you ;)

I'd like to think it's possible to parametrize the choice of line segment by end points. Curious about the difference between that and the problem (simply choosing uniformly distributed end points) that we wrote 94 posts about. Obviously the end points of all line segments are not uniformly distributed in the square.

I've got an idea for finding just what their distribution is that I might get to if ever get unswamped this week.

Re: Math Quiz 9
 

FWIW: seglen pdf for L theta x y versus x1 y1 x2 y2 sampling

Re: Math Quiz 9
 

Still stuck in my old ways aren't I.

Here's the distribution of endpoints using your sampling procedure.
https://plot.ly/~compwiztobe/9/

Curious about an analytical form, but this at least shows the idea. The way we solved the problem before assumed this plot was all one color.