There should be infinitely many "solutions" to this if you are allowed to define the sampling method arbitrarily.
Intuitively, one would think that random points are uniformly distributed, but that is not maintained in two of these solutions. If you randomly generate two points in [0,2pi) with a uniform distribution then you will quickly get the 1/3 probability empirically or provably by the limit.
However, if you are allowed to derive the second point from the first (such as the cross section example) or create some other dependency, then you are given great liberty as to what the resulting "probability" will be. Sure you can even guarantee that every two points on the circle will be present "eventually" but infinity is very large and how you approach it will determine your eventual outcome. Here we could subsample preferred points first and actually derive any specific probability (0,1) and maybe even make it sound reasonable. This behaviour will even be maintained into the limit, but it is certainly not intuitive, at least to me.
The other two solutions are also results of generating points from uniform distribution: radius and point on radius result from uniformly drawing pair from [0, 2pi) x [0, 1) (radius, distance from center), while "random midpoint" draws from the uniform distribution on the open unit disc. There's no "dependency" at the drawing time.
However, if one remembers the substitution formula for multiple variable integrals, this hints why the Jacobian multiplier is necessary in it: all three underlying spaces mentioned ([0,2pi)^2, [0,2pi)x[0,1], B^2\boundary) are diffeomorphic. They clearly don't have the same measure though -- the first one measures 4pi^2, second 2pi, and third pi. However, one can obtain one value from another by integrating Jacobian of appropriate diffeomorphism.
On most discrete samples for the 1/4 or 1/2 case, the probability of choosing any two points in the subset may be uniform, but the location of the permitted points is definitely not. If you add the requirement that all discrete point samples should be equidistant, then you fix yourself on 1/3 and there is really no way to break that conclusion.
Sorry, in this case "uniform" is ambiguous and I didn't mean the usual definition related to probability, but rather to point spacing.
> infinity is very large and how you approach it will determine your eventual outcome. Here we could subsample preferred points first and actually derive any specific probability (0,1) and maybe even make it sound reasonable
Your reasoning seems right to me, but can you come up with an example way of sampling that gives a probability very close to 0? What about very close to 1?
I'm curious, but having a hard time coming up with a reasonable way of sampling that makes for "obviously you're almost never/always getting a chord longer than sqrt3 if you do it like this".
Accepted! Now let's derive almost any "probability" from almost any deterministic variable through arbitrarily bad sampling methods...
Choose a goal probability B in the range (0,1). It can't be at 0 or 1, but can be arbitrarily close.
Now let's start sampling, and we'll take this all the way to the limit. For any discrete sample size as sample size goes to infinity, let's choose some positive/negative outcomes such that our probability approaches B. Remember that because our goal probability is greater than 0 and less than 1, there are infinite positive/negative outcomes to choose from.
This distribution has some interesting properties. The derived probability is B. The sample will grow to include all points. There are infinitely many functions to generate this outcome.
Right! That does half answer my request :) Those crazy infinities,right? :)
The other half is where I said "reasonable", like the three approaches from the article are--in my subjective opinion--quite reasonable. Picking samples from an uncountable (right?) infinity of options explicitly to satisfy the desired probability, somewhat less subjectively, is not :)
So yes, your method allows for B arbitrarily close to 0 or 1 (or anywhere in between), and it's clever.
But let's not go for "arbitrarily close", but just "very close", or "closer". I wonder if there's (subjectively) reasonable ways of sampling chords from a circle, like you could explain with a realistic(ish) scenario for a ninja pizza slicerator or an erratic mermaid, that give a probability even less than 1/4th or more than a half?
So if we want to get pedantic, "random chord" is undefined here, which means that all the methods presented in the article as well as my sampling methods, and even the 0 and 1 case are all technically correct probabilities.
For example one of the most relatable alternative probabilities for me are, now thinking about it, actually the 0 or 1 cases: spinning a compass will generate a randomly oriented chord inside the face. What is the probability that the chord is of length > sqrt3? 1. Is this result informative or useful? no.
The result is that there are different generating functions with different biases which may or may not be useful. The three sources of randomness in the article correspond to physical stories that are possibly useful, and as such relatable. Otherwise they are no more legitimate than my absurdist examples.
I got 1/3, but with a "different" distribution. (I took symmetrized pairs rather than pairs. But I realized after I wrote this comment that folding a square in half preserves relative area so symmetrizing makes no difference.)
I started off with a flat torus (two ordered points on the circle) and then quotiented out by (x, y) ~ (y, x) (since the chord corresponding to both is the same) to get a triangle as in the diagram [0].
By geometric intuition/trigonometry/etc it's clear that a chord has length < sqrt(3) iff the difference between the angles x and y is less than 2pi/3. The region corresponding to pairs with distance distance less than 2pi/3 is shaded in [0]. One adds it up and sees that the unshaded region is 1/3 of the whole.
I think that the most important part of the article is the following quote in the introduction:
> probabilities may not be well defined if the mechanism or method that produces the random variable is not clearly defined.
So comparing the answer of 1/2, where the chords are generated by moving along the radius in increments of dr, with the answer of 1/3, where the chords are generated based on the angle from the starting point.
The problem doesn't specify how to pick random points, though I suspect that if you were to choose two random points on the radius of a circle by picking a reference "going around the edge" of the circle clockwise by some amount in [0, 2pi), we get the angular situation that produces the 1/3 answer.
>> probabilities may not be well defined if the mechanism or method that produces the random variable is not clearly defined.
i don't agree. Because it is too vague and contradictory. If you defined probabilities it strongly implies that you defined Borel algebra of sets in the space. This is what meant by the "mechanism or method that produces the random variable". Without well defined Borel set (implicitly or explicitly) there is no probability at all, not just "well defined".
To illustrate - lets take our example of random chord. One would think - take the set of all possible chords and assign equal probability to each. As the number of chords uncountable, one can't really do such assignment and still obtain an additive measure (one of the condition of something to be a probability). We're forced to go more coarse grained. Find or choose a set of subsets such that we can assign numbers to them such that there would be additivity when the subsets are combined and other properties making that assignment of numbers a "probability", ie. we need to define a Borel algebra. The way one builds such set of subsets, an algebra, is the actual definition of the probability and it is "the mechanism or method that produces the random variable".
So, in the Wikipedia article, for example, taking random endpoints means that we're using, as the basis for the algebra, the open sets in the space x S1, while taking random midpoints means that we're building the algebra on the basis of the open sets in the space of the 2 dimensional sphere. It is pretty obvious that these 2 algebras are completely different and thus the probabilities they define are completely different, and one can't talk about probabilities without specifying the Borel algebra defining it.
It appears each approach depends on the way random chords are selected. Each approach yields different probabilities of selecting a chord with a certain property.
But my intuition suggests that constructing a proof for all chords should be relatively simple, and indeed 1/3 of them hold the property that they are longer than √3.
I would put it in this way: Merely saying "random" is insufficient information.
To solve the problem, you have to know from what distribution chords are drawn. It could be equal probability per unit angle, per unit distance along the circle, or something else altogether.
Similar difficulties emerge when someone gives you a problem that starts with a "random real number."
All real numbers have an infinite number of digits. For the numbers that you probably meant to exclude, all but finitely many of those infinitely many digits are 0.
(This is almost just nitpicking, but in another sense it's important: viewing an apparently terminating decimal expansion as actually 0-padded lets one say correctly that "a real number is rational if and only if its decimal expansion eventually repeats", full stop, rather than having to add the qualification "… or is eventually 0.")
Well, to be sure, one can say that it does count or that it doesn't—the axioms of mathematics are only as humans make them. I was arguing why it might make sense to have it count.
Another reason that it might be a good reason to have it count: by my definition, I can say "the decimal expansion of a number eventually repeats if and only if the binary expansion of that number eventually repeats." This becomes considerably more awkward if you don't consider a terminating expansion as consisting of eventually repeating 0's; for example, 1/5 has a terminating decimal expansion 0.2 but an immediately-repeating binary expansion 0.repeat(0011).
A point can by described by two numbers (the coordinates). If we are selecting a "random point in a square", everybody's intuition agrees that this means selecting the x coordinate and the y coordinate from a flat distribution.
In a similar manner, a chord can by described by a point and a direction.
– The first (1/2) method selects a point from a flat distribution along x-axis, and defines that the direction is always vertical. (Edit: this is how I interpreted the animated gif, but Wikipedia says that actually from a flat distribution along a random radius, and then the direction is perpendicular to the radius.)
– The second (1/3) method selects a point from a flat distribution on the perimeter, and then actually selects another point also from the same distribution, to define the direction by connecting these points.
– The third (1/4) method selects a point from a flat distribution on the circle area, and the defines that the direction is always perpendicular to the radius.
The whole point of the paradox is to demonstrate that there is no single universally agreed upon way to define a flat distribution for the set of all chords. And when we start to try to define one, by breaking the definition of a cord into components, and sampling these components from a flat distribution (or just selecting one direction, because symmetry says they are all equal), we get different results depending on how we broke the concept of cord into components.
Interestingly, if you use the second method and chose a point somewhere on the circle, and then select a random direction (instead of another point on the circle) you'll get the same 1/3 answer.
When you say that 1/3 of them have a certain property, how are you counting that? Are you enumerating all chords with and without the property, then dividing? :-)
This is exactly the issue: when dealing with infinities and probabilities, you need to choose a measure. Depending on how that measure is chosen, you might get different answers.
Maybe I'm missing something, but this doesn't seem so hard. Every cord must start at some point on the circle and end at some point on the circle. If P is the set of all points on the circle, then the set of all cords is the set of all possibilities of (p1, p2), where p1 and p2 are in P.
The ninja story doesn't work here, since for any p1 I think there's exactly one p2 possible. The photographer story DOES work, since he can start at any point, and the mermaid can then be at any second point. I'm not sure about the dragon story, but I'm guessing it doesn't work either.
What about lines across a square? They must also all hit two points on its perimeter, but randomly choosing p1, p2 in that case will show a clear bias towards the diagonals.
Of course a circle has no corners to complicate things like that, but it can still have biases. Just because we have found a way to uniquely identify cords does not mean it will lead to a uniform distribution.
> Just because we have found a way to uniquely identify cords does not mean it will lead to a uniform distribution.
This is the sentence that helped me understand the paradox.
Perhaps this analogy will help. Think about how technically picking a value at random from a normal distribution can result in any value at all, extending to infinity in both directions, but that doesn't mean all values are equally likely. Every real number can be uniquely expressed as a number of standard deviations from mean in a normal distribution, but that still has a bias.
All you need to add to make the ninja story work is to randomly rotate the pizza after it is cut (which clearly has no effect on the size of the resulting piece). It is then possible to select any chord of the circle -- though the probability density would be different than in the other two methods.
Rotating doesn't alter the probability density of the length function, and I suppose that's one reading of what I wrote, but it's not what I meant.
This method has different probability density from the random-center and random-endpoints methods. That's the whole point of the exercise: you get different probability density across the chord space depending on how you select from it.
One could just as easily make an argument for a ratio of sqrt(3)/2. The chord is selected by randomly picking a length out of the range [0, 2], placing it arbitrarily on the circle, and then rotating it randomly between zero and one revolution[1].
Before we can select a random chord, we must first map the set of chords onto the set of real numbers (or, equivalently, tuples of real numbers). This is required in order to meaningfully apply a distribution to them. The problem is that there are multiple ways to do this. Which mapping we select has as much effect on the outcome as the probability distribution.
Likewise, if we want to "count" all random chords, we need to do the same thing (map them onto the set of real numbers). We will get different "counts" depending on which mapping we select.
[1]- Edit: This is not a very satisfying approach, but it does demonstrate the problem well. Being satisfying isn't a requirement for a mathematical construct.
Years ago I posted a question on CraigsList (https://forums.craigslist.org/?ID=20211237) Science and Math discussion board, that I think may be nearly equivalent, and equivalently ambiguous in it's notion of random, to this post. It went on for quite some time, and was even reprised later (https://forums.craigslist.org/?areaID=4&ID=20432604) by someone else. Helpful people went back and forth with beautiful 3d renders to illustrate their solutions, though those links are sadly broken now.
It is very gratifying to read this post, as I think it explains why we were never able to come to a satisfying answer.
I don't agree with any of these solutions. In my opinion the circle should be positioned in an infinite plane, then random vectors should be drawn on the plane and ignored unless they intersect the circle. Then after making some large amount of intersecting vectors you calculate. I'm guessing that this essentially reduces to the random endpoints method.
The other two methods don't make sense at all to me. Random chords is just obviously not a random sampling of possible vectors-- it's essentially the same as sampling a gaussian(x) distribution using an equal sampling in x and ignoring the fact that a gaussian is a PDF and you can't sample that way, you need to invert it into a CDF and take an equal sampling in _y_. Very basic I think...
And random midpoint doesn't strike me as random either as it forces the orientations of the vectors to be non-random and systematically smaller than random because of the pi*r^2 area-dependence of concentric circles...
> In my opinion the circle should be positioned in an infinite plane, then random vectors should be drawn on the plane and ignored unless they intersect the circle.
After looking at the Wikipedia page, it seems that your method would be equivalent to the "random radius" aka "1/2" aka "ninja" method.
This is a good demonstration of the paradox here. You phrase your method as "random vectors in an infinite plane", but even when it is equivalent to the "ninja" method, the ninja method doesn't seem right to you.
I don't think so, like say you had a point outside the circle, and from that point you equally selected angles to slice the space in. You would get systematically longer slices than if all your slices are cut parallel to each other (and you ended up with the same number slicing the pizza).
edit: I worked it out and you're right, I get the same answer as the ninja one.
>You would get systematically longer slices than if all your slices are cut parallel to each other (and you ended up with the same number slicing the pizza).
You're only cutting once per pizza, so there's no parallel slices, so no such effect.
And allowing a dense set of possible parallel vectors from every angle is equivalent to rotating the pizza. Which obviously doesn't affect the sizes.
I tried to script that together after the same idea occurred to me. What's interesting is the selection plane affects the outcome quite heavily. As the plane of random line selection increases in size, the probability of a random chord having length>sqrt3 seems to approach about 0.13
My math might be wrong; doesn't seem to be a floating point precision issue.
from math import sqrt
from random import random
def randomPoints(width):
return [
[random()*width-width/2, random()*width-width/2],
[random()*width-width/2, random()*width-width/2]
]
def chordCalc(points):
def quadraticEquation(a,b,c):
descriminant=(b**2 - 4*a*c)
if descriminant <= 0:
return None
x1 = (-b+sqrt(descriminant))/(2*a)
x2 = (-b-sqrt(descriminant))/(2*a)
y1 = sqrt(1-x1**2)
y2 = sqrt(1-x2**2)
return [[x1, y1],[x2,y2]]
m = (points[0][1] - points[1][1]) / (points[0][0] - points[1][0])
b = points[0][1] - m*points[0][0]
qa = 1+m**2
qb = 2*b*m
qc = b**2-1
return quadraticEquation(qa, qb, qc)
def distance(points):
return sqrt((points[0][1] - points[1][1])**2
+ (points[0][0] - points[1][0])**2)
chords=0
largeChords=0
sqrt3=sqrt(3)
while True:
if random() > 0.9999:
print float(largeChords)/chords
points = randomPoints(500) #adjust me down to 0.5 and see probability go to ~0.33
intersections=chordCalc(points)
if intersections is None:
continue
chords += 1
if distance(intersections) > sqrt3:
largeChords += 1
I was wrong. My initial approach appears to be the ninja approach like sampo said above. I got 50% -_-
import numpy as np
import random as rnd
import math as m
chords = []
samp = 10000
for c in range(samp):
#random point on infinite plane is described by a single coordinate
dist = rnd.uniform(1., 1000.)
#DO NOT KNOW HOW TO DO INTERNAL SLICES
#ignore all possible lines that do not intesect circle
xsec_half = m.atan(1./dist)
angle = rnd.uniform(-xsec_half, xsec_half)
#make 2 points on the randomly chosen line
x1, y1 = -dist, 0
x2, y2 = dist, 2*dist*m.tan(angle)
#copy and paste some shit from wolfram alpha
dx = x2-x1
dy = y2-y1
dr = (dx**2 + dy**2)**0.5
D = x1*y2 - x2*y1
sqr = (dr**2 - D**2)**0.5
xa = (D*dy + np.sign(dy)*dx*sqr) / (dr**2)
xb = (D*dy - np.sign(dy)*dx*sqr) / (dr**2)
ya = (-D*dx + np.abs(dy)*sqr) / (dr**2)
yb = (-D*dx - np.abs(dy)*sqr) / (dr**2)
chords.append(((xa-xb)**2 + (ya-yb)**2)**0.5)
print len([a for a in chords if a > 3**0.5])/float(samp)
Basically make the unit circle at 0,0. Pick any radius up to infinity (infinite plane). By symmetry, we don't need 2 coordinates, just a distance from the circle.
Choose any angle from that point which will draw a vector that intersects the circle (to not waste CPU). Calculate the length of the intersecting chord.
I was really surprised by the distribution of chord lengths, it peaks at chord lengths of 2.0, which is the maximum chord length, and falls exponentially with smaller chord lengths. I don't know what I expected, but not that.
i think that any probability measure you can define on your proposed solution assigns a probability of zero to actually hitting the circle, which might complicate things somewhat :)
I came up with a third -- it seemed fairly obvious after some thought. I do not quite get the 1/2 and 1/4 explanations. (Unfortunately these gif analogies do not do such a great job of clarifying.) So I decided to ask good old "Reality".
N = 1000
SQRT3 = Math.sqrt(3).to_r
def point_on_circle
x = (rand().to_r * 2) - 1
y = Math.sqrt(1 - x**2)
y = -y if rand(2) == 0
return [x,y]
end
tally = 0
N.times do
x1, y1 = point_on_circle
x2, y2 = point_on_circle
d = Math.sqrt( (x2 - x1)**2 + (y2 - y1)**2 )
tally += 1 if d > SQRT3
end
puts "#{tally}/#{N}"
Oddly, it gives an answer close to a third (yeah me!). But... it is always a bit high at approx 36%.
I'm thinking though that if you talk a fairly large area surrounding a circle, and then randomly selected two points within it. Draw a line between the two points. If the line intersects the circle, calculate the length the length of it's chord. Bigger then sqrt(3) or less get put into bins, and the probability is calculated from there. Obviously this would work better if the area was an infinite plane, but I would expect to see the answer tending to a value as the size of the area increased.
I don't believe that this approach makes any assumptions about the chords that it generates. Here's a ruby snippet that does just that (err, I think!)
plane_size = 10000.0
chords = []
while chords.size < 100
p1 = {}
p2 = {}
p1[:x] = Random.rand(plane_size) - plane_size / 2
p1[:y] = Random.rand(plane_size) - plane_size / 2
p2[:x] = Random.rand(plane_size) - plane_size / 2
p2[:y] = Random.rand(plane_size) - plane_size / 2
puts p1
puts p2
#gradient 'm'
m = (p2[:y] - p1[:y]) / (p2[:x] - p1[:x])
#y = mx + b
# => b = y - mx
b = p2[:y] - m * p2[:x]
#x^2 + y^2 = 1
#sub in y from the line equation
#x^2 + (mx + b) * (mx + b) = 1
#x^2 + m^2x^2 + 2bmx + b^2 = 1
#x^2(1 + m^2) + 2bmx + b^2 - 1 = 0
#apply the quadratic equation to find the roots
#Ax^2 + Bx + C = 0
#=>x = (-B +- sqrt(b^2 - 4AC)) / 2A
#in our case, A = (1 + m^2), B = 2bm, C = b^2 -1
#the line intersects if B^2 -4AC > 0
discriminator = (2 * b * m) * (2 * b * m) - 4 * (1 + m * m) * (b * b - 1)
if discriminator > 0 then
chord1 = {}
chord2 = {}
chord1[:x] = (-2 * b * m + Math.sqrt(discriminator) ) / (2 * (1 + m * m))
chord1[:y] = m * chord1[:x] + b
chord2[:x] = (-2 * b * m - Math.sqrt(discriminator) ) / (2 * (1 + m * m))
chord2[:y] = m * chord2[:x] + b
length = Math.sqrt((chord2[:x] - chord1[:x]) * (chord2[:x] - chord1[:x]) +
(chord2[:y] - chord1[:y]) * (chord2[:y] - chord1[:y]))
chords << length
end
end
smaller = 0
chords.each {|c| smaller += 1 if c < Math.sqrt(3) }
puts "The number of chords smaller than sqrt(3) = #{smaller/100.0}%"
If I believe the result, the real world seems to feel that the answer is 0.5
Edit: Hah! Should have read just a few comments further, and I would have seen some other posts doing exactly the same thing. Good to see we ended up with the same answer :D
Your answer will follow from the chosen "random" sampling method. Since the sampling method is not stated as part of the problem, there is ambiguity.
For this Ruby snippet, you chose random (x,y) coordinate pairs on a plane. This corresponds to selection method #2 as outlined on the Wikipedia article [0]. Scroll down a bit to see different selection methods visualized!
IMO the most natural interpretation of "random" with no qualifiers is the one that gives you 1/3. Pick a point, pick another point, a third of the time the second point in within the far arc of the triangle.
I'm not sure the ninja method gives you what I'd call a representative sample of possible chords. Looks like he only cuts vertically, so he can never give you a skew-slice.
It doesn't matter if he only cuts vertically in the animation. The pizza could be on a spinning wheel, and as long as it's a perfect circle, that wouldn't matter to the ninja's cuts.
User antimagic thought it was most natural to draw lines by picking random (x,y) coordinates on a plane, then overlaying a circle. This "natural" choice corresponds to selection method #2, so they ended up getting the 1/2 answer.
Intuitively, one would think that random points are uniformly distributed, but that is not maintained in two of these solutions. If you randomly generate two points in [0,2pi) with a uniform distribution then you will quickly get the 1/3 probability empirically or provably by the limit.
However, if you are allowed to derive the second point from the first (such as the cross section example) or create some other dependency, then you are given great liberty as to what the resulting "probability" will be. Sure you can even guarantee that every two points on the circle will be present "eventually" but infinity is very large and how you approach it will determine your eventual outcome. Here we could subsample preferred points first and actually derive any specific probability (0,1) and maybe even make it sound reasonable. This behaviour will even be maintained into the limit, but it is certainly not intuitive, at least to me.