Math Quiz 9

[GeeTwo]

Originally Posted by Ether

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

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

Originally Posted by Ether

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

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.

[Ether]

5000 samples of sample size 1,000,000.

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

[Hitchhiker 42]

Originally Posted by Ether

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)

.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

[Ether]

Originally Posted by Hitchhiker 42

every line length possible creates a square with rounded edges

So I integrated all those together and divided by 1/2

[euhlmann]

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

[GeeTwo]

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:

#!/bin/gawk -f
BEGIN {
  for (steps=10; steps<200; steps+=10){
    numer=denom=0;
    for (i=0; i< steps; i++)
      for (j=0; j< steps; j++)
        for (k=0; k< steps; k++)
          for (l=0; l< steps; l++) {
            numer += sqrt((i-j)*(i-j)+(k-l)*(k-l));
            denom+=steps;
    }
    print steps, numer/denom
  }
}

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.

[Ether]

Originally Posted by Ether

(accurate to 5 decimal digits)

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

OK to use whatever computational tools you like.

[Hitchhiker 42]

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

[Ether]

Originally Posted by Hitchhiker 42

0.77019523

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



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

[Hitchhiker 42]

Originally Posted by Ether

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



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

What is a Monte Carlo simulation?

[Aren Siekmeier]

Originally Posted by Hitchhiker 42

What is a Monte Carlo simulation?

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.

[Ether]

Originally Posted by Hitchhiker 42

What is a Monte Carlo simulation?

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;}

[Hitchhiker 42]

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.

Originally Posted by Ether

Your script has an error.

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

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

[FiMFanatic]

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.

[Hitchhiker 42]

Originally Posted by FiMFanatic

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.

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