Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site princeton.UUCP
Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!eisx!npoiv!npois!hogpc!houxm!mhuxi!mhuxj!mhuxl!achilles!ulysses!princeton!levy
From: levy@princeton.UUCP
Newsgroups: net.math
Subject: Re: circle probability (spoiler)
Message-ID: <66@princeton.UUCP>
Date: Sun, 18-Sep-83 01:36:47 EDT
Article-I.D.: princeto.66
Posted: Sun Sep 18 01:36:47 1983
Date-Received: Mon, 19-Sep-83 01:07:44 EDT
References: <33@ism780.UUCP>
Organization: Princeton University
Lines: 23


Jim Balter's solution to the circle problem is wrong.  I have run the
simulation and the result for n=4 agrees with my result, 1/2.  Moreover
I have an inductive proof that the probability for arbitrary n is equal
to n/(2^(n-1)).  The proof goes like this (very sketchily):

The distribution of probabilities for n-1 points to be in a segment of length
at most x is at worst a polynomial of degree n-2 in x; this is seen by induction
since it is obtained by integration of the distr. of prob. for n-2 points.
Now for x small we have (Probability of n points in a segment of length x) ~
coeff*x^(n-2); this means there is *only* one term in the polynomial, and that's
the highest term.  Now for y=1 the probability is P(n-1), so the coefficient
of the monomial is P(n-2)/pi^(n-2), the probability distribution is P(n-2)*
x^(n-2)/pi^(n-2), and the density function is 
(n-2)*P(n-1)*x^(n-3)/pi^(n-2).
Adding the n-th point means integrating the function 1-(x/2pi) with the density
above.  Assuming that P(n-1) is given by the formula (n-1)/(2^(n-2)) (which is
certainly true for n=2, so the induction is valid), we finally get, with
a little bit of work, P(n)=n / 2^(n-1), proving the induction.

Some values: P(3) = .75, P(4) = .5, P(5) = 5/16 = .3125, P(6) = 3/16 = .1875.

			-- Silvio Levy