home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17490 < prev    next >
Encoding:
Internet Message Format  |  1992-12-29  |  3.4 KB

  1. Path: sparky!uunet!gatech!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
  2. From: israel@unixg.ubc.ca (Robert B. Israel)
  3. Newsgroups: sci.math
  4. Subject: Re: Two problems
  5. Date: 30 Dec 92 02:12:18 GMT
  6. Organization: The University of British Columbia
  7. Lines: 70
  8. Message-ID: <israel.725681538@unixg.ubc.ca>
  9. References: <1992Dec28.220454.129@front.se>
  10. NNTP-Posting-Host: unixg.ubc.ca
  11.  
  12. In <1992Dec28.220454.129@front.se> samuel@front.se (Samuel Gustaf Siren) writes:
  13.  
  14. >Problem 1 (This is an old problem)
  15. >----------------------------------
  16. >Suppose that a big (infinite) number of married couples are invited to a party.
  17. >All the guests are sitting around a big round table. If every guest is placed
  18. >randomly at the table, what is the probability that no man will sit at the 
  19. >LEFT of wis wife ?
  20.  
  21. >Problem 2
  22. >---------
  23. >Same as above, but what is the probability that no man will sit next to his
  24. >wife at all (left or right) ?
  25.  
  26.  
  27. The first problem is the well-known "probl\`eme des rencontres", 
  28. see e.g. Feller vol. 1.  The second may be more interesting because 
  29. I don't think you can get a simple closed-form answer for P(m,n). 
  30.  
  31. Suppose there are n couples.  
  32. I'll assume that the men are seated in numerical order, so husband 
  33. #i+1 is two places to the right of #i.  Let X_i = 1 if husband #i sits 
  34. on his wife's left, 0 otherwise; Y_i = 1 if husband #1 sits on his 
  35. wi8fe's right, 0 otherwise.  We are interested in the random variable 
  36. Z = sum_{i=1}^n (X_i + Y_i).  Clearly E(Z) = 2.  I claim that Z tends 
  37. in distribution to a Poisson r.v. with mean 2 as n -> infinity. 
  38.  
  39. The characteristic function of Z is (with r = exp(i s) - 1)
  40.    phi(s) = E exp(i s Z)
  41.           = E prod_{j=1}^n (1 + r X_j) (1 + r Y_j)
  42.   = sum_{S_1, S_2 subset {1...n}} r^{|S_1|+|S_2|} 
  43.            E prod_{j in S_1} X_j prod_{k in S_2} Y_k
  44.  
  45. Note that X_j Y_j = X_{j+1} Y_j = 0.  On the other hand, if S_1 and S_2
  46. are disjoint and S_1 + 1 and S_2 are disjoint (S_1 + 1 being S_1 rotated
  47. right by 1) then E prod_{j in S_1} X_j prod_{k in S_2} Y_k 
  48. = (n - |S_1| - |S_2|)!/n!.  Thus we obtain
  49.   phi(s) = sum_{m=0}^n Q(m,n) r^m (n-m)!/n!
  50. where Q(m,n) is the number of pairs of subsets S_1, S_2 of {1...n}
  51. such that |S_1| + |S_2| = m, S_1 and S_2 are disjoint, and S_1 + 1 and
  52. S_2 are disjoint. 
  53.  
  54. We can obtain such a pair by first choosing a subset S of {1..n} with 
  55. |S| = m, then splitting it up into S_1 and S_2. There are (n choose m) 
  56. ways to choose S, and then 2^m ways to split it up (neglecting the 
  57. requirement that S_1 + 1 is disjoint from S_2). Thus 
  58.   Q(m,n) (n-m)!/n! <= 2^m/m!
  59.  
  60. On the other hand, S_1 + 1 and S_2 are automatically disjoint if S+1 
  61. and S are disjoint, i.e. S contains no pairs of nearest neighbours.  
  62. As n -> infinity with m fixed, the fraction of S's with this property 
  63. approaches 1 (in fact, the expected number of pairs in a randomly
  64. chosen S is m(m-1)/(n-1), so the probability of having such a pair is 
  65. <= this).  So the term for m in the series for phi(s) approaches 
  66. (2r)^m/m!.  By a dominated-convergence argument, we get 
  67.    phi(s) -> sum_{m=0}^infinity (2r)^m/m! = exp(2 e^{i s})
  68. which is the characteristic function of the Poisson distribution with 
  69. mean 2.  Since this is continuous, we can conclude that the limit in 
  70. distribution of Z is Poisson. 
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77. -- 
  78. Robert Israel                            israel@math.ubc.ca
  79. Department of Mathematics             or israel@unixg.ubc.ca
  80. University of British Columbia
  81. Vancouver, BC, Canada V6T 1Y4
  82.