Math Quiz 9

[Caleb Sykes]

Originally Posted by FiMFanatic

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.

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.

[FiMFanatic]

Originally Posted by Caleb Sykes

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.

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.

[Ether]

FWIW

[Caleb Sykes]

Originally Posted by FiMFanatic

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.

Question:

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

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.

[Aren Siekmeier]

Originally Posted by GeeTwo

... I specifically addressed your concern that the even integers and all integers are of the same cardinality.

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.

Originally Posted by GeeTwo

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.

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

Originally Posted by GeeTwo

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.

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.

[EricH]

Originally Posted by Caleb Sykes

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.

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.

[GeeTwo]

Originally Posted by Ether

FWIW

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

[Caleb Sykes]

Originally Posted by EricH

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.

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.

[Ether]

Descriptive statistics for 10 million random samples:

mean      0.52151
median    0.51212
mode*     0.48 
meansq    0.33346
IQR       0.37633
std       0.24795
var       0.06148
skewness  0.18406
kurtosis -0.66077

*based on 100 bins, max slope of smoothed percentile vs length

[GeeTwo]

Originally Posted by Ether

 mode*     0.48 
*based on 100 bins, max slope of smoothed percentile vs length

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.

[Greg Woelki]

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:

%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import time

def isInPoly(r,theta,cr,n):
    theta = theta%(2*np.pi/n) #Rotates point to first "sector" of the polygon for simplicity
    
    x = r*np.cos(theta)
    y = r*np.sin(theta)    
    
    x1 = cr #x coordinate of vertex at theta = 0
    y1 = 0.0 #y coordinate of vertex at theta = 0
    x2 = cr*np.cos(2*np.pi/n) #x coordinate of vertex at theta = 2pi/n
    y2 = cr*np.sin(2*np.pi/n) #y coordinate of vertex at theta = 2pi/n
    
    if y < ((y2 - y1)/(x2 - x1))*(x - x1) + y1: #Check using 2-point line formula
        return True
    else:
        return False


def genPolyPt(n, cr):
    '''Return tuple of random rectangular coordinate within an n-sided regular polygon centered
    at (0,0) with circumradius = cr and a vertex at (cr,0).'''

    r = cr*(np.random.random()**0.5) #Square root correction ensures even probability distribution over area
    theta = 2*np.pi*np.random.random()
    
    x = r*np.cos(theta)
    y = r*np.sin(theta)
    
    if r < cr*np.cos(np.pi/n): #If r < apothem of polygon then point is in the polygon's incircle
        return x,y
    if isInPoly(r,theta,cr,n): #Checks if point is between polygon and incircle
        return x,y
    else: #If point not in polygon
        return genPolyPt(n, cr)

t = time.time()

n = 4 #Number of sides of polygon
area = 1.0
trials = 10**7 #Number of random samples

cr = (area/(n*np.sin(2*np.pi/n)/2))**0.5 #Solves for circumradius that yields polygon with specified area

total = 0.0

#fig = plt.figure()
#ax1 = fig.gca()

#xlist = []
#ylist = []

for i in range(trials):
    x1,y1 = genPolyPt(n,cr)
    x2,y2 = genPolyPt(n,cr)

    #xlist.append(x1)
    #ylist.append(y1)
    
    total += ((x2-x1)**2 + (y2-y1)**2)**0.5

#plt.xlim(-.85, .85)
#plt.ylim(-.85, .85)
#ax1.set_aspect('equal')
#ax1.scatter(xlist,ylist,s=5)
    
print(total/trials)
print(time.time()-t)

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.

[Caleb Sykes]

Originally Posted by Greg Woelki

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.

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.

[GeeTwo]

Originally Posted by Caleb Sykes

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.

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.

[Caleb Sykes]

Originally Posted by GeeTwo

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.

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.

[Richard Wallace]

Originally Posted by Ether

FWIW

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.