From: israel@unixg.ubc.ca (Robert B. Israel)
Newsgroups: sci.math
Subject: Re: Two problems
Date: 30 Dec 92 02:12:18 GMT
Organization: The University of British Columbia
NNTP-Posting-Host: unixg.ubc.ca

In <1992Dec28.220454.129@front.se> samuel@front.se (Samuel Gustaf Siren) writes:

>Problem 1 (This is an old problem)
>----------------------------------
>Suppose that a big (infinite) number of married couples are invited to a party.
>All the guests are sitting around a big round table. If every guest is placed
>randomly at the table, what is the probability that no man will sit at the 
>LEFT of wis wife ?

>Problem 2
>---------
>Same as above, but what is the probability that no man will sit next to his
>wife at all (left or right) ?


The first problem is the well-known "probl\`eme des rencontres", 
see e.g. Feller vol. 1.  The second may be more interesting because 
I don't think you can get a simple closed-form answer for P(m,n). 

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.  Let X_i = 1 if husband #i sits 
on his wife's left, 0 otherwise; Y_i = 1 if husband #1 sits on his 
wi8fe's right, 0 otherwise.  We are interested in the random variable 
Z = sum_{i=1}^n (X_i + Y_i).  Clearly E(Z) = 2.  I claim that Z tends 
in distribution to a Poisson r.v. with mean 2 as n -> infinity. 

The characteristic function of Z is (with r = exp(i s) - 1)
   phi(s) = E exp(i s Z)
          = E prod_{j=1}^n (1 + r X_j) (1 + r Y_j)
  = sum_{S_1, S_2 subset {1...n}} r^{|S_1|+|S_2|} 
           E prod_{j in S_1} X_j prod_{k in S_2} Y_k

Note that X_j Y_j = X_{j+1} Y_j = 0.  On the other hand, if S_1 and S_2
are disjoint and S_1 + 1 and S_2 are disjoint (S_1 + 1 being S_1 rotated
right by 1) then E prod_{j in S_1} X_j prod_{k in S_2} Y_k 
= (n - |S_1| - |S_2|)!/n!.  Thus we obtain
  phi(s) = sum_{m=0}^n Q(m,n) r^m (n-m)!/n!
where Q(m,n) is the number of pairs of subsets S_1, S_2 of {1...n}
such that |S_1| + |S_2| = m, S_1 and S_2 are disjoint, and S_1 + 1 and
S_2 are disjoint. 

We can obtain such a pair by first choosing a subset S of {1..n} with 
|S| = m, then splitting it up into S_1 and S_2. There are (n choose m) 
ways to choose S, and then 2^m ways to split it up (neglecting the 
requirement that S_1 + 1 is disjoint from S_2). Thus 
  Q(m,n) (n-m)!/n! <= 2^m/m!

On the other hand, S_1 + 1 and S_2 are automatically disjoint if S+1 
and S are disjoint, i.e. S contains no pairs of nearest neighbours.  
As n -> infinity with m fixed, the fraction of S's with this property 
approaches 1 (in fact, the expected number of pairs in a randomly
chosen S is m(m-1)/(n-1), so the probability of having such a pair is 
<= this).  So the term for m in the series for phi(s) approaches 
(2r)^m/m!.  By a dominated-convergence argument, we get 
   phi(s) -> sum_{m=0}^infinity (2r)^m/m! = exp(2 e^{i s})
which is the characteristic function of the Poisson distribution with 
mean 2.  Since this is continuous, we can conclude that the limit in 
distribution of Z is Poisson. 






-- 
Robert Israel                            israel@math.ubc.ca
Department of Mathematics             or israel@unixg.ubc.ca
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
Newsgroups: sci.math