NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17559

Internet Message Format | 1992-12-31 | 3.5 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!swrinde!gatech!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
From: [e-mail] (Robert B. Israel)
Newsgroups: sci.math
Subject: Re: Two problems
Date: 31 Dec 92 21:04:40 GMT
Organization: The University of British Columbia
Lines: 65
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: unixg.ubc.ca

In <[e-mail]> [e-mail] (Robert B. Israel) writes:

>In <[e-mail]> [e-mail] (Timothy Murphy) writes:

>>[e-mail] (Robert B. Israel) writes:

>>>Suppose there are n couples.
>>>I'll assume that the men are seated in numerical order, so husband
>>>#i+1 is two places to the right of #i.

>>I like your silent assumption of perfect etiquette!
>>Thinks: must revise my idea of California ...

>Actually, Canada.

>BTW, while I'm here I should correct a minor slip in my posting.  I
>wrote that phi(s) -> exp(2 e^{i s}), which should of course be
>exp(2 e^{i s} - 2).  And I forgot to answer the original question:
>the probability is exp(-2).

>Maybe I misread the original problem.  I thought that the assumption was
>that men and women alternated around the table.  Looking back, I see that
>that wasn't stated.  Actually, though, the original poster ( Samuel Gustaf
>Siren, [e-mail], in <[e-mail]>) appears to
>have tacitly made that assumption as well, judging from his numerical
>results.  E.g. for two couples, he has p(2,0) = 0, while if arbitrary
>seating was allowed each man could have the other man on one side and the
>other man's wife on the other.

>I'll have to check what the answer would be for arbitrary seating.  Well, I
>can say what it _should_ be.  The probability of any particular man being
>on his wife's left would be 1/(2n-1), so the expected number of such men
>would be n/(2n-1).  The expected number sitting next to their wives would
>be 2n/(2n-1).  If the limiting distributions are still Poisson, the answers
>would be exp(-1/2) for problem 1 and exp(-1) for problem 2.

OK, I checked.  To show that the limiting distribution is Poisson in the
arbitrary-seating case (where n couples are seated randomly around a
table), you can use the variables
   X_j = 1 if the people in seats j and j+1 (mod 2n) are a couple
         0 if not.
Then for subset S of {1...2n} such that S and S+1 are disjoint,
  E prod_{j in S} X_j = 1/((2n-1)(2n-3)...(2n-2|S|+1))
As n -> infinity, the proportion of subsets S of {1..2n} with fixed
cardinality k that have S and S+1 disjoint tends to 1.  So in the
expansion of
    phi(s) = E exp(is sum_j X_j) =
           sum_{k = 0}^n r^k sum_{|S|=k} E prod_{j in S} X_j
with r = exp(is)-1, the coefficient of r^k tends to
    lim_{n \to infty} (2n choose k)/((2n-1)(2n-3)...(2n-2k+1))
          = 1/k!
and the limiting characteristic function is exp(r), corresponding to
a Poisson distribution of mean 1.  This applies to the second question
(number of men seated next to their wives).  For the first question,
(the men on the left of their wives) let Y_j = 1 if X_j = 1 and the man
is in seat j.  Clearly E prod_{j in S} Y_j = 2^{-|S|} E prod_{j in S} X_j,
leading to a limiting characteristic function of exp(r/2) and a Poisson
distribution of mean 1/2.


--
Robert Israel                            [e-mail]
Department of Mathematics             or [e-mail]
University of British Columbia
Vancouver, BC, Canada V6T 1Y4