Conference rusure::math

    
    
    
            First thought:
    
            For a given hemisphere, the probability of finding all n points
            in it is 2**(-n).
    
            For point 1, take any hemisphere that contains it.
            The probability that all the other n-1 points are in
            this hemisphere is 2**(1-n).
            Do the same for all the points and add the probabilities,
            giving n*2**(1-n).
    
    /�ke

    Re .1:
    
    Any three points are in some hemisphere (probability 1), but n*2^(1-n)
    is 3/4 when n is 3.
    
    Here's another approach:  Draw a hemisphere around the each point.  If
    there is a hemisphere that contains all the points, then there is some
    area in which all the drawn hemispheres intersect.  As long as the
    hemisphere around any new point intersects that area, there is still a
    hemisphere containing all the points.
    
    But I don't have a handle on figuring the probability that a new
    point's hemisphere intersects that area of complete intersection.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    Hey, come on somebody and solve this one: there's some neat algebra
    that I want to explore with the n-dimensional solution to this problem,
    but I don't want to spoil the puzzle.
    
    edp is *definitely* on the right track by looking at areas where all the
    hemispheres intersect.,,
    
    Cheers,
    Andrew.

    I don't see how to determine, from the characteristics of the region
    where the hemispheres intersect, what the probability is that a new
    point's hemisphere will intersect that region.  You can't go by area; a
    very thin wedge from pole to pole will have a 100% chance of
    intersection.
    
    The region is going to be a spherical analog of a convex polygon, with
    boundaries formed by arcs of great circles.  A new hemisphere might
    cover the region entirely, cut across the middle, miss it entirely, or
    just clip a corner.
    
    From each angle that a great circle might approach the region, the
    region will have a certain width that is proportional to its
    probability of being hit.  But I do not see a neat relationship from an
    arbitrary region to this width.
    
    I don't think we want to consider arbitrary regions; there must be some
    neater solution.  But I don't have any ideas at the moment.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

        The hint in usenet was that all points lie within the same
        hemisphere if and only if their convex hull does not include
        the center.
        
        Dan

How about warming up to this problem with a training problem ?

How about

	What is the probability that n points on a line segment are on the
	same semi-segment ?  (In other words, the distance between the two
	most distant points does not exceed half the length of the segment)

Then we might try

	What is the probability that n points on a circular region are also
	contained in the same semi-circular region (In other words, we can
	draw a diameter of the circular region such that all the points
	are on the same side of that diameter)

/Eric

p.s.	I won't talk about the nit about points being ON the boundary vs
	a smidgeon off it

    Re: -.1.
    
    	Eric's second training problem is very relevant.
    
    	And as he says, we can ignore sets of measure 0 (= infinitely unlikely
    coincidences), as we work our way to the solution.
    
    	However no measure theoretic thinking is needed. The reasoning is
    just needs common-sense.
    
    Cheers,
    Andrew.

   If n uniformly chosen k dimensional unit vectors lie on one side
   of a hyperlane, then they'll lie in a polyhedral cone issuing from
   the origin.

   Form n choose k-1 sets of n-k+1 k by k matrices as follows.
   Set the first k-1 columns to one of the n choose k-1 subsets
   of vectors, and add one by one the remaining vectors in the
   last column.  Some of these sets of matrices will all have the
   same sign if our condition holds.

   I don't see an obvious way to use this to get a closed form
   answer, though it is easy to write a monte carlo simulation.
   It looks like in 2 and 3 dimensions, the numbers are rational.
   It suffices to take vectors whose components are independant
   identically distributed gaussian variates for this.

   I'd also thought of the "hint" mentioned by Dan, but don't see
   how that helps either.

   I don't have access to newsgroups at the moment (probably just
   as well, I don't have time to spend on this kind of stuff... :-)

   - Jim

To attack Eric's second training problem...

Consider a circle with circumference 1, and n points contained in a segment
of length s <= 1/2.  If we add an additional point P, three things can
happen:
  (1) P is contained within the segment, with probability s.
  (2) The point diametrically opposite P is contained within the segment,
      with probability s.  In this case, there is no semicircle that
      contains the n+1 points.
  (3) Otherwise, we can extend the segment to include p.  The length of the
      new segment is uniformly distributed within (s,1/2) -- ie, its expected
      length is (s + 1/2) / 2.  Probability is 1 - 2*s.

One point is contained in a segment of length 0.
Two points are contained in a segment whose length is uniformly distributed
within (0,1/2) -- expected length 1/4.

I'm going to take a leap here that I suspect is not justified, and start
working with expected lengths instead of distributions.  It seems not justified
because the various events aren't independent.  But anyway...

Assuming the expected length of a segment containing 2 points is 1/4,
adding a third point will:
  (1) probability 1/4: fall in the segment: new expected length = 1/4
  (2) probability 1/4: make a semicircle impossible
  (3) probability 1/2: extend the segment: new expected length = 3/8.

So, if there are three points that fit, the segment's expected length is
(1/4*1/4 + 1/2*3/8) / (3/4) = 1/3.

In general, if n points fit in a segment of expected length s, and the new
point we add actually fits, then the expected length of the new segment is:
[  s*s			! case (1), new point fits in segment
 + (1-2*s) (s+1/2)/2 ]	! case (3), new point extends segment
/ (1 - s)		! probability of case (1) or (3)

Simplifying:

  [ s*s + (1 - 2*s) (s+1/2)/2 ] / (1-s)
= [ s*s + s/2 + 1/4 - s*s - s/2 ] / (1-s)
= (1/4) / (1-s)

s1 = 0				0.00
s2 = 1/4			0.25
s3 = (1/4) / (3/4) = 1/3	0.33
s4 = (1/4) / (2/3) = 3/8	0.38
s5 = (1/4) / (5/8) = 2/5	0.40
s6 = (1/4) / (3/5) = 5/12	0.42

Now, to answer the original question: what is the probability that n points
fit in a semicircle?  They fit if (n-1) of them fit, and the n'th doesn't
fall into case (2).  f(n) = (1-s(n-1))*f(n-1)
f1 = 1
f2 = 1
f3 = 3/4
f4 = (2/3)*(3/4) = 1/2
f5 = (5/8)*(1/2) = 5/16
f6 = (3/5)*(5/16) = 3/16

Perhaps someone who's handy with recurrences can put these into closed form...

To extend this to the surface of the sphere, you need to change the length of
the segment into the area of a polygon (on the surface of the sphere), and
figure out the distribution for the new area in case (3).
	-- Bill

    I'm on vacation for 424 hours.  Don't go solving this problem without
    me.  The center of the sphere is outside the convex hull of the points
    if the center cannot be expressed as a positive linear combination of
    the points (expressed as vectors from the center).  (A "positive"
    linear combination is one with all coefficients non-negative and at
    least one positive.)  Is that useful?
    
    The analysis in .9 is interesting, but I haven't had much time to
    examine it.  I am not clear on how you can find the probability of
    there being a fitting semicircle from the expected segment size rather
    than from the complete probability distribution of segment sizes.
                                       
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

   I've reduced the problem to one of combinatorics.

   Suppose we have n k-dimensional unit vectors (or what is the same
   thing, points on the k-sphere.)

   We can form n choose k k by k matrices, take their determinants,
   and look at the signs.  We're calculating whether the oriented
   areas of the k-parallelipeds generated by the vectors is positive
   or "inside out".

   Remark that if we are given a hyperplane spanned by k-1 vectors,
   we can decide if a k'th vector lies to one side or the other
   this way.

   If all the vectors lie to one side of a hyperplane, then
   only certain patterns of signs are possible!

   So enumerate the possibilities and we're done.

   Example, 4 points on the 3 sphere.  There are 2^(4 choose 3) = 16
   patterns of signs of the determinants.

   But if no hyperplane cordons off all the points, there are only
   2 patterns of signs that are possible, so the probability of
   this is 1/8, and the probability is 7/8 that 4 points on a sphere
   will lie in a hemisphere.

   In the case of 5 points, there are 2^(5 choose 3) = 1024 patterns
   of signs, and 704 of them are possible if all points lie in
   a hemisphere.  So p = .6875.

   The problem remains how to count these possibilities.

   I wager that Andrew-le-combinatard has found a way :-)
 
   - Jim

.5>        The hint in usenet was that all points lie within the same
>        hemisphere if and only if their convex hull does not include
>        the center.

Interesting.  Intuition tells me that this is the way to a solution, although I
still can't get there.

I was trying to solve this by mentally sliding hemispheres around on a spherical
surface.  Instead of thinking outside the box, I should have been thinking
inside the sphere.

re .9
    
>To extend this to the surface of the sphere, you need to change the length of
>the segment into the area of a polygon (on the surface of the sphere),
    
    Or can you get away with a "circular" region on the surface of the
    sphere, said region being bounded by the intersection of a cone with
    apex at the centre of the sphere and the surface of the sphere? One
    could use either the cone's half angle or the area as the metric.
    
    The usefulness of doing this probably depends on revisiting the use of
    expected lengths rather than distributions of lengths (for the curved
    boundary of the sector in the 2D case).

Re .13 (cone):

There are points that are outside the polygon but inside the cone. 
Diametrically opposite those are points that can be added and still fit in
a hemisphere.

   I realize I made a mistake in my enumeration; not all
   combinations of signs of determinants are possible, due to
   topological considerations.  However, those combinations
   of signs that are possible are all equally likely.  They are
   all possible in the simple case of 4 points.  But as soon as you have
   5 points, only 384 possible signs out of 1024 are possible, 264 of
   those are with all points in a hemisphere.

   The 264 possible cases arise because you have 120 cases where
   two points lie inside a triangular cone, 120 cases with one point
   in aside quadrilateral cone, and 24 ways to get a pentagonal cone
   with no points in the interior.

   But this gets hairy when you have more than 5 points.

   One type of equivalence relation that is interesting is
   that for any configuration of points in general position, you
   can generate others by reflecting any subset of points to their
   antipodal position.  I believe that given any configuration of
   points that do not lie in a hemisphere, you can reflect some
   points so that the new configuration will have that property,
   but possibly not vice-versa (with n > 3, in the case of a
   normal sphere.)

   I'm not sure if this is a key to solving the problem, but
   it leads to some interesting questions.

   The abelian group of reflections acts on the set of possible patterns of
   signs.  What is the structure of this group action in general?
   The symmetric group of permutations of points acts on the patterns
   of signs also, and so you have two ways of getting classes of signs.
   This is essentially why all possible classes of signs must be equally
   likely.  This is pure combinatorial topology.

   - Jim

re .14

    Yes, you're right.
    
    Too bad. It makes it hard to generalise your approach to 3D.

   My thought about reflecting points to antipodal position has
   borne fruit.

   Generate any set of n points on the sphere in general position.

   Now, run through all 2^n ways of reflecting any subset of
   those points to antipodal position and count the configurations
   that lie in a hemisphere.

   The percentage out of 2^n that does appears to be the probability
   for any configuration in general position!

   I haven't developed a closed form for the sequence yet, but I find:

   p(3)  =    1
   p(4)  =    7/8
   p(5)  =   22/32
   p(6)  =   32/64
   p(6)  =   44/128
   p(8)  =   58/256
   p(9)  =   74/512
   p(10) =   92/1024
   p(11) =  112/2048
   p(12) =  134/4096
   p(13) =  158/8192
   p(14) =  184/16384
   p(15) =  212/32768
   p(16) =  242/65536
   p(17) =  274/131072
   p(18) =  308/262144
   ...

   Now somebody has to explain why this works :-)

   I think there are a lot of interesting related questions, like
   how many ways are there of orienting a plane passing through the
   origin among a set of lines passing through the origin.

   How about in n dimensions?  You effectively have Grassman spaces,
   how can elements of these be combined with each other?  (A Grassman
   space is the space of k dimensional subspaces of an n dimensional linear
   space; the set of lines and planes passing through the origin are examples
   in 3 space...)

   There's a subject I've heard of called "Arrangements of Hyperplanes"
   that must explore these questions.

   - Jim

>   I haven't developed a closed form for the sequence yet, but I find:
>
>   p(3)  =    1       <--- better written as  8/8
>   p(4)  =    7/8     <--- better written as 14/16
>   p(5)  =   22/32
>   p(6)  =   32/64
>   p(6)  =   44/128
>   p(8)  =   58/256
>   p(9)  =   74/512
>   p(10) =   92/1024
>   p(11) =  112/2048
>   p(12) =  134/4096
>   p(13) =  158/8192
>   p(14) =  184/16384
>   p(15) =  212/32768
>   p(16) =  242/65536
>   p(17) =  274/131072
>   p(18) =  308/262144

   If I take divided differences of the numerator, I finally find the
   following closed form expression for the probability:

               n^2 - n + 2
	p(n) = -----------
                   2^n

   We can check the result in .9 with the same reasoning.

   Imagine n lines passing through the origin of the plane.  We can pivot
   another line around the origin in any of n positions with respect
   to these n lines (barring being coincident with any line.)

   Now, we have 2^n orientations of the n lines; for which ones will
   their positive sides be to one side of our pivot line?  There are 2n
   ways of that happening, out of 2^n orientations, so the probability on
   the circle is the amazingly simple

	p(n) = n / 2^(n-1)

	p(1) = 1 / 1 = 1
	p(2) = 2 / 2 = 1
	p(3) = 3 / 4
	p(4) = 4 / 8 = 1/2
	p(5) = 5 / 16
	p(6) = 6 / 32 = 3/16
        p(7) = 7 / 64

   Which (miracle!) matches Bill's results in .9

   - Jim

I got the same result for the circle and now for the sphere

                           (n-1)
  Circle : P(n) = n * (0.5)
                                      n
  Sphere : P(n) = [n� - n + 2] * (0.5)


-----*-----

Proof here for the circle:

   Suppose that among our n points, one of them is "blue" (all others are in 
colors I don't like). I want to know the probability that all points are in the 
upper hemicycle, with the blue one standing on the rightmost side of the 
circle. So after putting randomly your points on the cirle, just rotate the 
circle until the blue point stands on the rightmost side. Then the probability
that all other points stand in the upper hemicycle is (0.5)^(n-1).

   Now when the points are all in the upper hemicycle, there are n ways to 
choose the rightmost point (even if it's not the blue one). So:

                           (n-1)
  Circle : P(n) = n * (0.5)


  Stay tuned dear reader. An attempt of derivation for the sphere problem 
  coming soon.

Friendly,

##### R�my #####

Proof now for the sphere (more complicated than circle, sorry).

  Let's take the first point as origin, even if it's put randomly. So after 
  putting this point, just rotate your sphere, so that this points becomes the 
  uppermost point.

  The probability that all (n-1) incoming points     * uppermost point = first
  stand "within" an angle "a" is equal to :          |
                                                     |
                                     (n-1)           |
  P (angle max < a ) = [ sin� (a/2) ]                0 angle a
                                                      \
  So, deriving the above, we get the function          \
  "probability density" f(a), so :                      \
                                                         * lowermost point
                            (2n-3)
  f(a) = (n-1) [ sin (a/2) ]       cos (a/2)

- if a <= pi/2, then of course all points stand on the same hemisphere, the
  probability of such case is (0.5)^(n-1)
 
- if a > pi/2, then :

    . all points standing in the cone "opposite" to the empty cone will belong
      to any hemisphere. The probability of belonging to such cone is :

              P (points in free cone) = cos�(a/2) / sin� (a/2)

      Let's call "q" this quantity. So q = cos�(a/2) / sin� (a/2)

    . The number of points standing in the "free cone" is given by Bernouilli.
      Remember the first point is already fixed to the upper region, and another
      point determines the max angle "a". So we have still (n-2) more points
      to put on the sphere. The number of points (among n-2 points) that
      will go into the free cone is a quantity "i", given by Bernouilli:

                     i     i       n-2-i
             P(i) = C     q   (1-q)
                     n-2
        
      When "i" points stand in the free cone, then n-2-i points stand in the
      "non free" region. Their "horizontal angle" is constrained by the 
      circle problem (remember the "blue point" giving a direction). So the
      probability that they fit in the same "horizontal angle" compatible with
      the 2 first points, is P (horizontal) = (n-1-i) * (0.5)^(n-2-i)
        [I just used here the result of the circle problem, with n-2-i remaining
         points to be placed]

      So, for a given angle "a", the probability that all points are 
      "horizontally" visible in same hemisphere is:

              i=n-2
      P(h)     SUM   P(i) * (n-1-i) * (0.5)^(n-2-i)
               i=0
                                              
      We get (after some tricks around Binomial relation) :
             
                      (n-3)
      P(h) = [(1+q)/2]      [n-1+3q-nq]/2
  
                            [with q = cos�(a/2) / sin� (a/2)]


So now, we get the overall probability that all n points stand on same 
hemisphere, by integrating P(h) ponderated by the probability density
         
                     /a=pi
            (n-1)   |                    (n-3)
P(n) = (0.5)      + |      f(a) [(1+q)/2]      [n-1+3q-nq]/2   d(a)
                    |
                   /a=pi/2


                                 (2n-3)
with   f(a) = (n-1) [ sin (a/2) ]       cos (a/2)

If you do like trigonometry, you will reduce the above to:

               n 
   P(n) = (1/2)  [ n� - n + 2 ]


friendly,

##### Remy #####

   Neat analysis in .21!! (But Andrew said no calculus was required!!)

   Now, I have a conjecture for the k-dimensional case:

   let p[k](n) be the k-1 degree polynomial that takes on the values
   2^n for n = 1..k

   Then I conjuecture the probability of n points on a k-dimensional sphere
   lying in a hemispere is just p[k](n)/2^n

   Do the coefficients of such polynomials or the polynomials themselves
   already have a name? (like Sterling numbers...)

   I haven't had any time to explore this.

   I suspect that we can generalize the analysis in .21 to get some
   interesting trigonometric identities!

   - Jim

        So given the (x,y,z) coordinates of n random points on the
        sphere x^2 + y^2 + z^2 = 1, how do you compute yes/no whether
        there is a hemisphere that contains all of them?
        
        Dan

    re .20
    
    This is a very neat solution. (I understand it now!) Is there some way
    of generalising for the 3D case that does not involve calculus etc.?

    	Well, things are coming on great. I was going to give the clue:
    "antipodes" but no-one seemed to need it.
    
    	I'm glad that someone else checked .21: it's gets a bit hairy for
    me :-) I follow until it gets to "horizontal circles". The solution that I 
    read is more basic, but generalizes naturally to the case of k dimensions. 
    Jim is nearly there. 
    
    	There's also then a piece of established mathematics which tells us 
    what the polynomials would be for k dimensions. I wonder too if these 
    polynomials have a name...
    
    Andrew. 

> So given the (x,y,z) coordinates of n random points on the
> sphere x^2 + y^2 + z^2 = 1, how do you compute yes/no whether
> there is a hemisphere that contains all of them?

  That was one of my keys to understanding the problem better.

  Suppose the points do lie in a hemisphere.  Then there will
  exist at least one plane (of the n choose 2 possible ones) 
  passing through two of the points and the origin such that
  all the other points lie to one side of it.  If we rotate that
  plane infinitesimally in the obvious way we will have discovered a
  plane with all the points to one side.

  Topologically, there will have to be at least 3 such planes and
  can be as many as n, for the 2-sphere (our every-day sphere.)
  There are only 2 possible on the circle.  How many can
  there be for the k-sphere ?

  One question I have not answered is:  what is the probability
  distribution of the number of these planes for random configurations?
  Put another way, we can partition the configurations in classes,
  how are these distributed?

  - Jim

Let's take for granted Jim's conjecture in .22

>>   Then I conjecture the probability of n points on a k-dimensional sphere
>>   lying in a hemispere is just p[k](n)/2^n

The term in 1/2^n is easy to understand. When n -> infinity, we must have
Proba(n+1)/Proba(n) = 1/2 . Just because when n points already stand in one
hemisphere, with n -> infinity, then such hemisphere is almost drawn by these
n points, so this hemisphere is almost well defined. So the next point has
a probability 1/2 to go in such hemisphere. So when n -> infinity, the law
must be dominated by a rule in 1/2^n. 

Now the other term p[k] is a conjecture. However if we take it, then the degree
of p[k] must be "at least" equal to k-1. Yes, because for k-dim sphere, k points
always stand on the same hemisphere. So p[k] must solve k relations : 
	      . 1 point  => p[k](1)/2^1 == 1
	      . 2 points => p[k](2)/2^2 == 1
	      ... etc...
              . k points => p[k](k)/2^k == 1

Anyway, I cannot yet explain why this polynomial could not have a degree greater
than k-1. Maybe, in such case we should find funny probabilities greater
than 1, or lower than 0.

Now, starting with Jim's relation, if we apply it to the 4-dim case, we have
a probability Proba (n) = (a n^3 + b n^2 + c n + d) / 2^n

	1 point  => Proba (1) == 1 => (  a +   b +  c +  d) =  1
	2 points => Proba (2) == 1 => ( 8a +  4b + 2c +  d) =  4
	3 points => Proba (3) == 1 => (27a +  9b + 3c +  d) =  8
	4 points => Proba (4) == 1 => (64a + 16b + 4c +  d) = 16

                                              n� - 3 n� + 8 n
For 4-dim hyper-sphere, we get Proba (n) = [ ----------------- ] (1/2)^n 
                                                     3

##### R�my hyper-tired #####

  It finally occurred to me how to think about enumerating the number
  of ways to position a hyperplane among lines passing through the
  origin of n-space.

  In the case of n = 2, it's evident that there are n ways of putting a
  line among n others, so we can say that p[2](n) = n.

  In the case of 3 space, suppose we already have n lines and add one
  more.  How many more planes must we add?

  Project all the lines onto a plane orthogonal to the newly added one.
  Now we have the 2 dimensional situation, and there are n ways; but
  we don't want our new plane to contain the new line, so we must
  move it away an infinitesimal amount, leading to 2n ways.  But,
  n of these already exist among the previous planes, so we have the
  recurrance

	p[3](n+1) = p[3](n) + n = p[3](n) + p[2](n)

  This last form suggests how to handle the k dimensional case!
  Repeatedly project down onto k-1 dimensional spaces to get the
  next lower dimensional enumeration; we have in general

	p[k](n+1) = p[k](n) + p[k-1](n)

  This is exactly consistant with polynomials that take on
  the values of 2^(n-1) for n = 1...k.

  This is also the same process one can use to count how many ways to
  subdivide n-space with planes.

  On the line, we find, say, s[1](n) = n+1, since we n points
  split a line into n+1 pieces.

  In the plane, a new line cuts n others in n places, and so splits
  n+1 regions in two, leading to

	s[2](n+1) = s[2](n) + n+1 = s[2](n) + s[1](n)

  and this can be extended to n dimensions; only the "initial conditions"
  of this recurrance are different from Andrew's problem.

  Now, to return to Andrew's question:  Let's generate our n points
  in a two step process.  First, generate n lines at random, second,
  pick their orientations, one of 2^n possibilities.

  There are p[k](n) possible ways to position a plane among the lines,
  and 2 out of the 2^n line orientations will lie to one side of each one,
  so the ratio is

	2*p[k](n) / 2^n

  A possibly much harder problem is to give the expected number of
  topologically different configurations of points.  I don't know
  how to answer this, and it may require geometry.

  - Jim