home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!gatech!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
- 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
- Lines: 70
- Message-ID: <israel.725681538@unixg.ubc.ca>
- References: <1992Dec28.220454.129@front.se>
- 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
-