Chief Delphi - Math Quiz 9

Chief Delphi (http://www.chiefdelphi.com/forums/index.php)

- Math and Science (http://www.chiefdelphi.com/forums/forumdisplay.php?f=70)

- - Math Quiz 9 (http://www.chiefdelphi.com/forums/showthread.php?t=149436)

Quote:

Originally Posted by Ether (Post 1600321)

Using symmetry for the chords problem, you can reduce the length computation to:

Code:

sum += sin(pi*abs(random-random));

... and when the iterations are complete, multiply the sum by 2.

Because sin(x) is symmetric around pi/2, you can further optimize this to:

Code:

sum += sin(pi_2*random);

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

Quote:

Originally Posted by Ether (Post 1600321)

Using symmetry for the [full-circle] chords problem, you can reduce the length computation to:

Code:

sum += sin(pi*abs(random-random));

... and when the iterations are complete, multiply the sum by 2.

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

Code:





// naive implementation

q1 := 2*pi*random; q2 := 2*pi*random;

theta := abs(q2-q1);

len := 2*sin(theta/2.0);

sum := sum + len; 



// get rid of q1 and q2 

theta := 2*pi*abs(random-random);

len := 2*sin(theta/2.0);

sum := sum + len; 



// get rid of theta

len := 2*sin(pi*abs(random-random));

sum := sum + len; 



// get rid of len

sum := sum + 2*sin(pi*abs(random-random));



// move factor of 2 outside the loop

sum := sum + sin(pi*abs(random-random));

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).

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.

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.

Quote:

Originally Posted by Ether (Post 1596692)

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)

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:

Quote:

Originally Posted by Aren Siekmeier (Post 1597016)

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.

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.

Quote:

Originally Posted by Ether (Post 1602279)

[b]OK I'm going to drop a bombshell here.

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

...

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.

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?

Quote:

Originally Posted by Aren Siekmeier (Post 1602297)

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?

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.

Quote:

Originally Posted by Ether (Post 1602306)

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.

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

Still stuck in my old ways aren't I.

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

Code:

from random import random

from math import pi,cos,sin,sqrt

import numpy



def randseg():

        hl=random()/sqrt(2)

        th=random()*pi

        cx=random()

        cy=random()

        return [cx-hl*cos(th),cx+hl*cos(th),cy-hl*sin(th),cy+hl*sin(th)]



def inbox(seg):

        return(all([x>=0 and x<=1 for x in seg]))



def go(n):

        l=[]

        for i in range(n):

                x=randseg()

                if inbox(x):

                        l.append(x)

        return(l)



def pts(l):

        p=[]

        for x in l:

                p.append([x[0],x[2]])

                p.append([x[1],x[3]])

        return(p)



data=pts(go(1000000))



#then bin and plot 2d histrogram with plotly API

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.

Quote:

Originally Posted by Ether (Post 1602306)

I believe this is fallacious, in particular that for a given center point and two different segment lengths, there are the same number of segments. For the center point at (0.5, 0.5) and length 0.2, the candidate segments are the diameters of a circle of radius 0.1. For the center point at (0.5, 0.5) and length 1.0, the candidate segments are the diameters of a circle of radius 0.5. As there are five times as many points on the large circle to serve as either end of a diameter, it logically has five times as many diameters.

When you take this into account, the integral in the denominator becomes:

∫₀^π/4∫₀^1/cosθ (1- Lcosθ) (1- Lsinθ) L dL dθ =
∫₀^π/4∫₀^1/cosθ L - L²cosθ - L²sinθ + L³cosθsinθ dL dθ =
∫₀^π/4[ L²/2 - L³cosθ/3 - L³sinθ/3 + L⁴cosθsinθ/4 ]₀^1/cosθ dθ =
∫₀^π/4sec²θ/2 - sec²θ/3 - sec²θtanθ/3 + sec²θtanθ/4 dθ =
∫₀^π/4sec²θ/6 - sec²θtanθ/12 dθ =
[tanθ/6 - tan²θ/24 ]₀^π/4 =
[1/6 - 0 - 1/24 + 0 ] = 1/8

If you then integrate the adjusted calculation using 1/8 for the deominator, just substitute r for L and α for θ, and you will have the third equation of my most recent post in this thread.

Addition: Also, the idea of the average segment in a square of size 1 being within 1% of the average segment on any of its sides is .. counter-intuitive, to say the least.

For the center point at (0.1, 0.1) and length 0.2, the candidate segments are the diameters of a circle of radius 0.1. For the center point at (0.1, 0.1) and length 1.0, the number of candidate segments is zero.

Quote:

Originally Posted by Ether (Post 1602327)

Though it is not relevant, there are plenty of candidates, though none are selected.

Here's another case which more clearly shows the fallacy.

What is the average distance from the origin to a point in the unit square?
What is the average length of the radials from the origin to points in the first quadrant of a circle of radius √2?

Solving the first question in Cartesian coordinates, we find the answer to be (√2 + ln(1+√2))/3 = 0.765...

Solving the second question using the logic used by Ether to count radials, the answer comes out to √2/2 = 0.707..

As the quadrant of the large circle includes all the same points as the unit square plus others which area all farther away than either average, there is a fallacy here somewhere.

By weighting the density by r, the second question is properly answered 2√2//3 = .942...

Addition:
To more fully explore this point, I propose the following questions:

What is the average length of a segment in a rectangle 1 unit wide and 0.5 units high?
What is the average length of a segment in a rectangle 1 unit wide and 0.1 units high?
What is the average length of a segment in a rectangle 1 unit wide and infinitesimally high? (that is, the limit as height goes to zero from above)
How does that compare to the average length of a line segment within the line segment from 0 to 1?

Question for Gus:

What is the average length of all the vertical line segments in a unit circle?

Quote:

Originally Posted by Ether (Post 1602385)

Question for Gus:

What is the average length of all the vertical line segments in a unit circle?

If I may,

Spoiler for Thoughts:

Work attached below.

EDIT: Gosh darn I only did those with both points touching the the edges. Lemme work on that.