Conference rusure::math

>>	The above discussion suggests a general formula.  What is it?

	Probability and statistics are counterintuitive.

	Dan

    To quote David J. Farber:  "Nobody goes there anymore.  It's too crowded."
    
    The problem is that one person sees only himself (1) while two people
    each see two people (2*2=4) etc.  You get a quadratic effect where only
    a linear one is warranted.  (He said, waving his hands).
    
      John

    Digging deep in the dusty attic of memory, I think this
    problem belongs to a specialised field known as the Theory
    of Ramsey Graphs. As I recall, most problems in this field
    produce as solutions numbers of about the same order as the
    diameter of a galaxy in microns.
    

>>    Digging deep in the dusty attic of memory, I think this
>>    problem belongs to a specialised field known as the Theory
>>    of Ramsey Graphs. As I recall, most problems in this field
>>    produce as solutions numbers of about the same order as the
>>    diameter of a galaxy in microns.

	No, not as stated.  In the worst case, all N people go
	to one restaurant, see there are N people in the one of
	M restaurants, and so assume that there are about NM
	people total.  The numbers won't get any bigger.

	The base note only deals with partitioning the N people
	into disjoint sets.  It doesn't really become a Ramsey
	type problem until you are partitioning something like
	(unordered) pairs of people.  You even use the term
	"Ramsey Graphs" and undirected graphs involve unordered
	pairs of whatever make a vertex (here, people).

	Finally, in the basic version of a Ramsey graph problem,
	R(m,n) is the minimum number of points you must have such
	that every undirected graph on that many points contains
	either m points all connected to every other m, or n points
	none of which is connected to any of the other n.  The value
	of R is not so super large, what is large is the number of
	possible graphs on k points, in case you exhaustively check
	each to see if each has one of the required subgraphs (which
	would show that R(m,n) <= k).

	Dan

    Yes, now I recall.....very well described, Dan!
    

>For a simpler example, consider 3 restaurants and 4 people.  They can 'split'
>the following ways:
>
>	4,0,0	1/27
>	2,2,0	6/27
>	3,1,0	8/27
>	2,1,0	12/27
>
>Thus, the expected number of people someone will see is:
>
>	  (4� + 0� + 0�)(1/27)
>	+ (2� + 2� + 0�)(6/27)
>	+ (3� + 1� + 0�)(8/27)
>	+ (2� + 1� + 0�)(12/27) = 204/27 = 68/9 = 7 5/9

I think the last case should be {2,1,1}, for which the last result is 
exactly 8. 

Thanks, Lynn.  It's curious the answer is exactly twice the number of people.

Corrected for Lynn's observation:

>For a simpler example, consider 3 restaurants and 4 people.  They can 'split'
>the following ways:
>
>	4,0,0	1/27
>	2,2,0	6/27
>	3,1,0	8/27
>	2,1,1	12/27
>
>Thus, the expected number of people someone will see is:
>
>	  (4� + 0� + 0�)(1/27)
>	+ (2� + 2� + 0�)(6/27)
>	+ (3� + 1� + 0�)(8/27)
>	+ (2� + 1� + 1�)(12/27) = 216/27 = 8
>
	No, that is the expected number of sightings.   To find the expected
number of people someone will see, divide by 4.   This gives 2 as the expected
number anyone sees, one of which is himself!

	Basically with n people in r restaurants, a person I will expect to
see 1 + (n-1)/r people.   Overall, this leads to n(1 + (n-1)/r) sightings.
If you compare I's experience to what a waiter W sees, W's expectation is
n/r.   The difference I-W = (r-1)/r is due entirely to the fact that I always
sees himself.   I don't see this "crowding effect" that Peter is talking of.

>If each person were to extrapolate on the total number of people present, the
>answer would be (8 people per restaurant)x(3 restaurants) = 24.
>

	No, there aren't 8 people expected per restaurant, there are 8 
sightings expected.   The extrapolation is that there is one other person per 
restaurant, plus I himself, gives 4.

	I just don't "see" what you're trying to get at.

Regards,
Andrew

    Looking at the July 'Scientific American', which has just got to
    this part of the world, I see an Article on Ramsey Graphs! I haven't
    had time to read it yet, but the diagrams are like abstract art.
    
    

	Then there is this, which just came in ... now where is
	that Ramsey topic, anyway?

Path: ryn.esg.dec.com!shlump.nac.dec.com!bacchus.pa.dec.com!decwrl!apple!usc!samsung!munnari.oz.au!csc!bdm659
From: [email protected]
Newsgroups: sci.math
Subject: R(4,4;3) = 13.
Message-ID: <[email protected]>
Date: 15 Jul 90 15:50:35 GMT
Organization: Computer Services, Australian National University
Lines: 10
 
 
This is to announce the first determination of a classical Ramsey number
for hypergraphs.  Specifically, we have R(4,4;3) = 13, where R(4,4;3) is
defined to be the least n such that any colouring of the 3-subsets of an
n-set using two colours yields a monochromatic tetrahedron.  The full
paper will not be available for some time, but a longer announcement may
be obtained from either of us.
 
Brendan McKay, Australian National University. [email protected]
Stanislaw Radziszowski, Rochester Institute of Technology. [email protected]

The base note discusses an interesting problem, but there were a few confusing
points in the way it was stated.  So let me try another statement.

A city has a number of restaurants and a much larger number of citizens who
sometimes eat out.  Somebody notices that when the citizens who have eaten out
get together the next morning, they usually report that the restaurants were
crowded, but the restaurant managers feel that they were not crowded.  So
somebody does a comprehensive survey of diners, asking each to count the number
of diners in their restaurant.  The surveyor averages all the counts and
multiplies by the number of restaurants, to get the total number of diners as
estimated by the diners themselves.  Amazingly, it is usually a lot larger than
the careful counts by the restaurant managers.  It is never smaller.  Why?

Let r be the number of restaurants, and ni be the number of diners in restaurant
i.  Then nt, the total number of diners is just the sum of ni for i=1 to r.

For a given restaurant i, each diner will count ni diners, and this ni will
be reported to the surveyor ni times.  So the contribution of restaurant i to
the average will increase with ni^2, the quadratic effect waved at by .2.

With slightly more math, define E(nt) as the surveyor's estimate of nt

	E(nt) 	= r * ( SUM( ni^2 ) / nt )

		= ( r/nt ) * SUM( ni^2 )

Substitute for ni its mean and deviation, defined by ni = na + di, where by
definition the sum of di is zero.

		= ( r/nt ) * SUM( (na+di)^2 )

		= ( r/nt ) * SUM( na^2 + 2*na*di + di^2 )

		= ( r/nt ) * r * na^2  + 0 + ( r/nt ) * SUM( di^2 )

		= nt + ( r/nt ) * SUM( di^2 )

So the estimate of the diners is always wrong by a non-negative number.  It is 
zero only when it happens that exactly the same number of diners are found at
each restaurant.

The sum can be related to the standard deviation, part of the reason why 
standard deviations show up so often in risk and decision problems.