Average Number of Matches. Torsten Sillke, Frankfurt, 1996
-------------------------- last update: 2001-04-01
This note is a collection of references for the matching problem.
I tried to classify the different approaches in finding the moments
and/or distribution. Several variation of matching problems considered
here are discussed in [Bar58], [DaB62]. A classical collection
of probability problems which contain this question is [Mos65].
Historial references can be found in [Tak80].
Problem 1:
The following are equivalent versions of the matching Problem:
(a) From a shuffled deck, cards are laid out on the table one at a time,
from left to right, and then another deck is laid out so that each of its
cards is beneath a card of the first deck. What is the average number of
matches of the card above the and the card below in repetitions if this
experiment?
(b) A typist types letters and envelopes to n persions. The letters are
randomly put into the envelopes. On the average, how many letters are put
into their own envelopes?
(c) Select a permutation from 1..n equal distributed.
What is the expected number of its fixpoints?
Problem 2: group
A finite Group G acts on a finite set X transitivly.
(In other words, for any x, y in X, there is a g in G with g(x) = y.)
The average number of fixed pointes (over all elements of the group) is 1.
Solution 1: the moments
The average number of matches is one (if n >= 1).
More general we can calculate the higher moments.
Let X be the random variable of the number of fixpoints.
(1) E((X) ) = 1 for k<=n otherwise 0.
k
(2) E( X^k ) = Bell_numbers(k) for k<=n.
(3) Cumulant (X) = 1 for k<=n, and Cumulant (X) = 0.
k n+1
Proof of (1):
-------------
1. Distribution Method: [GKP89 Chap. 8.3], [Knu68 Chap. 1.3.3]
Determine the probability generating function
for the number of fixpoints F_n(z).
Then show: F'_n(z) = F_{n-1}(z).
(k)
E((X) ) = F (1) = F (1) = 1 for k<=n otherwise 0.
k n n-k
2. Generating function method: [Whi92]
Let M(n,j) be the number of exactly j matches for n elements then
M(n,j) = (j+1)/(n+1) * M(n+1,j+1)
which is easily combinatorial interpreted.
From M(n,j)/n! = (j+1)*M(n+1,j+1)/(n+1)! follows
d/dz F_{n+1}(z) = F_{n}(z).
3. Expectation Method: [Torsten Sillke, 1990]
Typically expectation and variance will be calculated
by this method. See [GKP89] or [Wil85].
Now let us calculate the factorial moments or binomial moments direct.
Let Xi be the random variable which is one, if 'i' is a fixpoint of
the random permutation and otherwise zero. Then we have:
X = X1 + X2 + X3 + ... + Xn.
The Corallary (A) from the appendix gives.
E((X) ) = E((X1 + X2 + ... + Xn) )
k k
= k! * E(SymmetricFunction({X1,X2,...,Xn}, k))
= k! * Binomial(n,k) * E(X1*X2*X3*...*Xk) for k<=n otherwise 0.
= 1 for k<=n otherwise 0.
This follows from
E(X1*X2*X3*...*Xk) = Prob(X1=X2=X3=...=Xk=1)
= (n-k)! / n! (combinatorial reasoning)
= 1 / (n) (probability reasoning)
k
Proof (1) --> (2) and (3)
-------------------------
Generating Functions: [GKP89]
PF(z) : the probability generating function.
FM(z) : exponential factorial-moment generating function.
M (z) : exponential moment generating function.
C (z) : exponential cumulant generating function.
Relations between PF, FM, M, C: FM(z) = PF(z+1), M(z) = PF(exp z), C(z) = ln(M(z))
The exponential factorial-moment generation funktion FM_n of permutations
of n elements is:
FM_n(z) = exp_n(z)
with exp_n(z) = SUM_{0<=k<=n} z^k / k!
the truncated exponential function.
FM_oo(z) = exp(z)
as FM(z) = PF(z+1) we have
PF_n(z) = FM_n(z-1) = exp_n(z-1)
PF_oo(z) = FM_oo(z-1) = exp(z-1)
M_n(z) = FM_n(exp(z)-1) = exp_n(exp(z)-1)
M_oo(z) = FM_oo(exp(z)-1) = exp(exp(z)-1)
C_n(z) = ln(FM_n(exp(z)-1)) = ln(exp_n(exp(z)-1))
C_oo(z) = ln(FM_oo(exp(z)-1)) = exp(z) - 1
If the Bell and Stirling2nd numbers are known
(and their generating functions) we can give the k-th moments.
E( X^k ) = #{ set partitions of {1..k} in upto n parts }
= Stirling2nd(k,0) + Stirling2nd(k,1) + ... + Stirling2nd(k,n).
special values are
E( X^k ) = Bell_number(k) for k <= n
E( X^k ) = Bell_number(k) - 1 for k = n+1
E( X^k ) = Bell_number(k) - 1 - Binomial(k,2) for k = n+2
The first n cumulants (semi-invariants) can be computed by a trick
given in [GKP89, Chap 8.3]. For the kth cumulant depends only on
the first k factorial moments, we can use the limit distribution
has the same cumulants for k<=n. If we know that
Cumulant_k = FactorialMoment_k
+ polynom(FactorialMoment_1, ..., FactorialMoment_k-1)
we can calculate one term further. As FactorialMoment_n+1 is one too
large in the limit distribution Cumulant_n+1 is one too large.
Cumulant (X) = 1 for k<=n
k
Cumulant (X) = 0 for k=n+1
k
References: (annotated)
-----------
Bar58: David E. Barton;
The Matching Distributions:
Poisson Limiting Forms and Derived Methods of Approximation,
J. Royal Statist. Soc., (B) 20:1 (1958) 73-92
MR 20 # 7327
(variations and extensions of the matching problem)
BeW91: E. A. Bender, S. G. Williamson;
Foundations of Applied Combinatorics,
Addison Wessley, Reading (1991)
Exc. 2.2.4: Derangement Approximation (Independence Heuristic)
Exp. 4.11: Derangements (Sieving Method, semifactorial notation)
Exp. 8.1: The Number of Derangements (Recursions, Distribution-Free)
Exp. 11.8: Derangements (Generating Function -> Recursion)
Exp. 12.4: Counting Derangements (Determine the Generating Function)
ClS93: R. J. Clarke, M. Sved;
Derangements and Bell numbers,
Mathematics Magazine 66:5 (1993) 299-303,
MR 94k:05016
(Moments of the number of non-fixpoints for random matchings)
Com74: Louis Comtet;
Advanced Combinatorics,
Reidel Publishing Company, Dordrecht (1974)
Chap. 4.2: The 'Probleme des Rencontres'.
(Sieving Method, Inversion Method, antifactorial notation,
Generating Function -> 2 Recursions)
Exc. 4.4: Other properties of the number d(n) of derangements.
(Difference-Representation, differential equation of the GF,
exp(-t(1-u))/(1-t) is GF of permutaions with k-fixpoints)
Exc. 3.11: Characteristic numbers for a random variable.
(Let X be a Poisson RV with parameter l, then E(X^n) = Sum_k S(n,k) l^k)
DaB62: Florence N. David, David E. Barton;
Combinatorial Chance,
Griffin, London (1962)
(contains two chapters on derangement and matching problems.
Gives several relations for these models.)
Eng73: Arthur Engel;
Wahrscheinlichkeitsrechnung und Statistik, Band 1
Klett Studienb\"ucher, Stuttgart, 1973
Chap 3: Kombinatorik; 3.2.2 Beispiel 5: Fixpunkfreie Permutationen
(derangments: D(n) = (n-1)*(D(n-1) + D(n-2)) with interpretaion)
Chap 14: Anzahl der Fixpunkte einer Permutation
(Mean and Variance (Expectation Method) Limit distribution Poison(1))
Fel50: William Feller;
An Introduction to Probability Theory and Its Applications, Volume I,
Wiley International Edition, New York (1968), 3rd Ed.
Chap. IV: Combinations of Events
(The Inclusion-Exclusion-Principle is attributed to Frechet (Fre40))
Chap. IV.1 Example b: Matches (coincidences or rencontre)
(Probability of at least one match (Inclusion-Exclusion)
(Orig: Montmort 1708))
Chap. IV.4: Application to Matching and Guessing
(Distribution by Inclusion-Exclusion-Principle)
Fre40: M. Frechet;
Les probabilites associees a un systeme d'evenements compatibles
et dependants,
Actualites scientifiques et industrielles, nos. 859 and 942,
Paris (1940 and 1943)
(The general Inclusion-Exclusion-Principle)
Fry28: T. C. Frey;
Probability and Its Engeneering Uses,
Van Nostrand, New York, 1928,
(41-77, Matching Problems)
GKP89: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik;
Concrete Mathematics,
Addison Wessley, Reading (1994) 2nd Ed.
Chap. 5.3.3: Inversion
(Determines the distribution from a linear system of equations,
and solves it by an inversion formular.)
Chap. 8.2: Mean and Variance (Expectation Method)
Chap. 8.3: Probability Generating Functions (Distribution Method)
GrS92: G. R. Grimmett, D. R. Stirzaker;
Probalility and Random Processes,
Oxford Univ. Press, New York (1992), 2nd. Edition
Chap. 3.4: Indicators and matching (3. Matching problem)
Chap. 5.2: Some applications, Matching revisited & Matching and occupation
(Expand Binomial-Moments of a sum of indicator variables, but don't apply
it to the matching problem.)
Knu68: Donald E. Knuth;
The Art of Computer Programming Vol. 1,
Fundamental Algorithms,
Addison Wessley, Reading (1973) 2nd Ed.
Chap. 1.2.10: Analysis of an Algorithm
Chap. 1.3.3: Applications to Permutations
(- An unusal correspondence.
- expected number of k-cycles by direct counting.
- distribution of the number of fixpoints of a random permutation.
Determines the distribution from a linear system of equations.
- distribution -> GF and F'_{n+1}(z) = F_{n}(z).
- counting derangments by the principle of inclusion and exclusion.
- history: inclusion and exclusion -> Moivre 'Doctrine of Chance' 1718.)
Kre88: Ulrich Krengel;
Einf"uhrung in die Wahrscheinlichkeitstheorie und Statistik,
Vieweg Verlag, Braunschweig (1990), 2te Auflage,
Chap. 3.4 Das Rechnen mit Indikatorfunktionen
(Proofs the general inclusion-exclusion formula with indicator function.
Then determines the match-distribution (Koinzidenz-Verteilung).)
Lin97: John Linnell;
A Pattern in Permutation,
Crux Mathematicorum 23:3 (1997) 158-160
(the moments of the number of fixpoints are the Bell numbers.)
MM95.1454:
Names drawn from a hat,
Mathematics Magazine 68:4 (Oct. 1995) 308-309
Solution to Excercise 1454
(solution to Exc. 75 of Silverman (Sil71).)
Mos65: Frederick Mosteller;
Fifty Challenging Problems in Probability with Solutions,
Addison Wessley, Reading (1965) (reprint: Dover Publ.)
Exc. 45: Average Number of Matches (Expectation Method)
Exc. 46: Probabilities of Matches
(Determines the distribution from a linear system of equations)
Net01: E. Netto;
Lehrbuch der Combinatorik, 1901.
Chap 40: Absolute (relative) Euler'sche Permutationen
(D(n) = (n-1)*(D(n-1) + D(n-2)) by combinatorial reasoning (Euler's method).
derives for this the recursion: D(n) = n*D(n-1) + (-1)^n.)
Old38: E. G. Olds;
A moment generating function which is useful in
solving certain matching problems,
Bull. American Math. Soc. 44 (1938) 407-413
(tea testing problem, permanent, problem of (Fry28))
Sil71: David L. Silverman;
Your Move,
Mc Graw-Hill, New York (1971)
(german: 100 unterhaltsame Denkspiele : Spielend denken lernen,
Moderne Verlagsgesellschaft, 1984)
Exc. 75: Renkontre (Expected number of rounds (see MM95.1454))
Ste64: Hugo Steinhaus;
One Hundred Problems in Elementary Mathematics,
Pergamon, Oxford, 1964, MR 28 # 1110
Two Hundred Problems in Elementary Mathematics
(german: 100 Aufgaben, 1968)
(german: 100 neue Aufgaben, 1973)
Problem 90 (2nd Vol): Recontre
(the expected number of matches is 1, expectation method)
Wei88: P. Weisenhorn;
Von den Rencontre-Zahlen zu den Bell-Zahlen,
MNU 1988 Nr 6, 363-365
Whi92: P. Whittle;
Probability via Expectation,
Springer Verlag, Berlin (1992), 3rd Edition
Sect 4.6: Matching and other Combinatorial Problems
(generating function method: let M(n,j) be the number of exactly j
matches for n elements then M(n,j) = (j+1)/(n+1) * M(n+1,j+1)
which is easy combinatorial interpreted.
From M(n,j)/n! = (j+1)*M(n+1,j+1)/(n+1)!
follows d/dz F_{n+1}(z) = F_{n}(z).)
Wil85: Herbert S. Wilf;
Some examples of combinatorial averaging,
American Math. Monthly 92:4 (1985) 250-261
MR 87b:05014
Sect 2: The fixed points of permutations
(Mean and Variance, Expectation Method)
(MR: This paper was the text of an invited presentation to the annual
meeting of the MAA held in Louisville, Ky., 1984. It includes a wide
variety of problems whose solution is accomplished with the methods
of combinatorial averaging. [..])
Wil90: Herbert S. Wilf;
generatingfunctionology,
Academic Press, 1994, 2nd Edition
downloadable at http://www.cis.upenn.edu/~wilf/
Chap: 2 Exerciese 27
Chap: 4.2 A generatingfunctionological view of the sieve method
Example 1. The fixed points of permutations
- - - - - - - - - - - - - - - - - - - - - - - -
BHJ92: A. D. Barbour, L. Holst, S. Janson;
Poisson Approximations,
Clarendon Press, Oxford 1992
(pp 77-80, matching problems)
BeS95: M. Bernstein, N. J. A. Sloane;
Some Canonical Sequences of Integers,
Linear Algebra and its Applications, 226-228 (1995) 57-72
URL: www.research.att.com/~njas/doc/eigen.ps
MR 96i:05004
(MR: If you take an infinite sequence, consider it as a column vector
and multiply it on the left by an infinite lower triangular matrix you
get another column vector which represents the transformed sequence.
This ubiquitous technique has been used to do everything from acceleration
of convergence to proving combinatorial identities.
In this offbeat, entertaining paper the authors define an eigensequence
as one that transforms into something similar to itself, say shifted
one place or with every other term deleted. One can start with a known
matrix such as Pascal's triangle or the Stirling number triangles and
find the various eigensequences. Conversely, one can define a new type
of eigensequence and then try to find the transforming matrix. Many of
the examples included in this paper come from combinatorial enumeration
problems or are new.)
Bot79: Otto Botsch;
In der Werkstatt der Hirnverzwirner,
Aulis Verlag Deubner & Co KG, K"oln, 1979
(problem 33: grosses Missgeschick mit Briefen.
Combinatorial interpretation of the recurences)
BBS90: A. Brandt, M. Brandt, H. Sulanke;
A Representation of a Discrete Distribution by its Binomial Moments,
J. Appl. Prob. 27 (1990) 208-214
(Let alpha be the radius of convergence of the Probability-GF.
Ch. Jordan's inversion formular is valid for alpha > 2. A general
formular is derived for alpha > 1.)
Eul51: L. Euler;
Calcul de la probabilite dans le jeu de rencontre.
Euler Project: www.wcsu.ctstateu.edu/~sandifer/rencontre.htm
Eul79: L. Euler;
Solutio quaestionis curiosae ex doctrina combinationum.
(Mem. Acad. Sci. St. Petersbourg 3 (1809/10(1811)) 57-64.)
= Opera Omnia (1) 7 (1923) 435-440.
(This was presented to the Acad. on 18 Oct 1779.)
- Shows D(n) = (n-1) [D(n-1) + D(n-2)] and D(n) = nD(n-1) + (-1)^n.
FlO90: P. Flajolet, A. O. Odlyzko;
Random mapping statistics,
Advances in Cryptology, EUROCRYPT 89,
Lecture Notes in Comput. Sci. 434 (1990) 329-354
Zbl 747.05006
http://www.research.att.com/~amo/doc/crypto.html
KnS96: F. F. Knudsen, I. Skau;
On the asymptotic solution of the card-matching problem,
Mathematics Magazine 69:3 (1996) 190-197
MR 97f:15013
(given two packs of cards. One with n*k cards, k of each kind and
the other with n*l cards, l of each kind.
Thm: The limit (n->oo) distribution of the number of matches is
Poisson with parameter lambda = min(k,l).)
The current proof follows from some easy inequalities
and the principle of inclusion-exclusion. )
Kol86: V. F. Kolchin;
Random Mappings,
Optimization Software Inc. New York, 1986
(See (San98) but proof by complex analysis)
Lea85: S. Leader;
The Inclusion-Exclusion Probability Formulas by Taylor's Theorem,
American Math. Monthly 92 (1985) 343-345
Mic96: R. Michel;
Aspekte der Stirlingschen Zahlen zweiter Art,
Math. Semesterberichte 43 (1996) 81-92
(The Poisson-approximation of the matching problem,
n/(n+2)*2^n/(n+1)! <= sup_{k in N_0} | P_n(k)-Poisson_1(X=k) | <= 2^n/(n+1)!
)
Pen91: S. O. Penrice;
Derangements, permanents and Chrismas presents,
American Math. Monthly 98 (1991) 617-620
MR 92g:05014
(given n*k objects, k of each kind, asymthotic probability for no match
is exp(-k) using some "hard" inequalities for the permanent of a
doubly stochastic matrix. (but see (KnS96)))
Pit97: J. Pitman;
Some Probabilistic Aspects of Set Partitions,
American Math. Monthly 104:3 (Mar. 1997) 201-209
MR 97j:05009
(Bell and Stirling numbers, Moments of the Poisson Distribution
(factorial and others), the matching problem, 58 references.
MR: This review paper examines some properties of set partitions
with emphasis on a statistical viewpoint. The 58-item bibliography
will be of interest to researchers. A sample of topics: proofs
of Dobinski's formula and some variants, equality of Bell numbers
with moments of the Poisson distribution, derivation of the 2-variable
generating function for Stirling numbers $S(n,k)$, and how to generate
a set partition at random.)
mailto:pitman@stat.berkeley.edu
Rem83: J. B. Remmel;
A note on a recursion for the number of derangements,
European Journal of Combinatorics 4:4 (1983) 371-374,
MR 85i:05024
(Derangements, combinatorial interpretation of D(n) = n*D(n-1) + (-1)^n
using a q-analog formular.
MR: The author gives a combinatorial proof of the recursion
$D\sb {n+1} =(n+1)D\sb n+(-1)\sp {n+1}$ for derangement numbers,
and for its $q$-analogue. The proof uses a representation of
derangement cycle structures due to A. M. Garsia and the author
[same journal 1 (1980), no. 1, 47--59; MR 81g:05011].)
RBC74: W. W. Rouse Ball, H. S. M. Coxeter;
Mathematical Recreations and Essays;
Univ. of Toronto Press, (1974)
Section: Derangements, p46-47
(combinatorial interpretation D(n) = (n-1)*(D(n-1) + D(n-2)).)
San98: G. R. Sanchis:
Swapping Hats: A Generalization of Montmort's Problem
Mathematics Magazine 71:1 (1998) 53-57
(Let P_m(N) be the probability that m is the minimal cycle length
of the cycles of a random permutation of 1..N.
Thm: The limit (N->oo) of P_m(N) is exp(- H(m)) with
H(m) the harmonic series.
The proof is elementary by inclusion exclusion.
(A complex analysis proof can be found in (Kol86). )
Str97: H. K. Strick;
Pressemeldung(2), Erg"anzungen zum Rencontre-Problem,
Praxis der Mathematik 39:3 (Juni 1997) 101-103
(Ist Astrologie schlechter als raten?)
Tak67: L. Takacs;
On the Method of Inclusion and Exclusion,
Journal of the American Statistical Association 62 (1967) 102-113
Tak80: L. Takacs;
The problem of coincidences,
Arch. Hist. Exact Sci. 21:3 (1980), 229-244.
MR 82c:01025
(MR: This paper deals with the origin, history and various appearances
of the problem of coincidences (matches, rencontres) in the theory
of probability. The contributions of Montmort, Johann and
Nikolaus Bernoulli, DeMoivre, Euler, and Catalan are discussed.)
RPA:
http://xraysgi.ims.uconn.edu/rpa-output/probability/derangement.p
http://xraysgi.ims.uconn.edu/rpa-output/probability/derangement.p
Appendix:
---------
Counting Derangements: The 'Probleme des Rencontres'
----------------------------------------------------
Let D(n) the number of fix-point-free permutations of 1..n.
The notation of semifactorials [GKP89] and antifactorials [Com74] are equal.
These numbers satisfy the following recursions:
(1D) D(n) = n*D(n-1) + (-1)^n
(2D) D(n) = (n-1)*(D(n-1) + D(n-2))
It is easy to find a direct combinatorial proof of (2D) see [RBC74],
but (1D) is much harder.
[BeW91, Exp. 11.8] say: >> If you can find it an your own,
your professor might give you an "A" in this course! <<
[Con74, Chap. 4.2] only says:
>> combinatorial proofs are also easy to find! <<
[Rem83] gives a combinatorial interpretation of (1D).
(3D) D(n) = n! * exp_n(-1)
(4D) Sum_{n>=0} D(n) t^n/n! = exp(-t)/(1-t)
Counting Arrangements: [Com74, p 75 Exc. 9]
-------------------------------------------
The total number of arrangements of a set with n elements.
(The number of permutations of all subsets.)
This number P(n) = Sum_{k=0..n} (n)_k satisfies
(1P) P(n) = n*P(n) + 1 (for n>=1) P(0) := 1
(2P) P(n) = n! * exp_n(1).
Hence P(n) equals the integer closest to e*n!.
Moreover we have as GF:
(3P) Sum_{n>=0} P(n) t^n/n! = exp(t)/(1-t).
Difference Fring - generates relatives of the factorials
--------------------------------------------------------
The factorials F(n) and the semifactorials D(n) as well as
the arrangements P(n) and the factorials F(n)
are related by a difference fring.
D(n) = n! * exp_n(-1)
F(n) = n!
P(n) = n! * exp_n(1).
Note the similarity between D(n) and P(n).
1 1 2 6 24 120
0 1 4 18 96
1 3 14 78
2 11 64
9 53
44
1 2 5 16 65 326
1 3 11 49 261
2 8 38 212
6 30 174
24 144
120
More general we have the series:
(1R) R_k(n) = n*R_k(n) + k^n (for n>=1) R_k(0) := 1
(2R) R_k(n) = n! * exp_n(k)
(3R) Sum_{n>=0} R_k(n) t^n/n! = exp(k*t)/(1-t)
With exp_n(z) = SUM_{0<=k<=n} z^k / k! the truncated exponential function.
This difference scheme is called the EULER transformation and its
inverse the BINOMIAL transformation in [BeS95].
If b_0 b_1 b_2 ... is the original sequence, with exponential generating
function B(x), the difference fring a_0 a_1 a_2 ... has g.f.
A(x) = exp(-x) B(x).
If b_0 b_1 b_2 ... is the original sequence, with ordinary generating
function B(x), the difference fring a_0 a_1 a_2 ... has g.f.
A(x) = B(x/(1+x))/(1+x).
Multinomial Falling Factorials Theorem:
---------------------------------------
The following formular is attributed to M. Frechet [DaB62, p70]:
===
\
(X1 + X2 + ... + Xn) = > Multinomial(k;a1,a2,...,an) (X1) (X2) ... (Xn)
k / a1 a2 an
===
(a1, a2, ..., an)
a1+a2+ ...+an = k
this is equivalent (divide by k!) to
===
\
Binomial(X1+X2+...+Xn,k) = > Binomial(X1,a1) Binomial(X2,a2) ... Binomial(Xn,an)
/
===
(a1, a2, ..., an)
a1+a2+ ...+an = k
Proof: by induction
case n=1: Identity
case n=2: The Vandermonde-Convolution
===
\
Binomial(X1+X2,k) = > Binomial(X1,i) Binomial(X2,k-i)
/
===
i
case: n-1 -> n
===
\
Binomial(X1+X2+...+Xn,k) = > Binomial(X1+X2+...+X(n-1),i) Binomial(Xn,k-i)
/
===
i
===
\
= > Binomial(X1,a1) Binomial(X2,a2) ... Binomial(Xn,an)
/
===
(a1, a2, ..., an)
a1+a2+ ...+an = k
qed.
Corallary (A):
--------------
If all Xi are zero or one (that means Xi*(Xi-1) = 0) then:
===
\
(X1 + X2 + ... + Xn) = > Multinomial(a) (X1) (X2) ... (Xn)
k / a1 a2 an
===
(a1, a2, ..., an)
a1+a2+ ...+an = k
= k! * SymmetricFunction({X1,X2,...,Xn}, k)
Where the SymmetricFunction is defined as:
SymmetricFunction({X1,X2,...,Xn}, k)
n-k
= [z ] (z+X1)*(z+X2)*(z+X3)*...*(z+Xn)
===
\
(B) = > X X ... X
/ a1 a2 ak
===
1<=a1=2.
n
Prob(Z_n = 0) = (1 - 1/n)
This is allways too small (the exact value is exp_n(-1)).
The relative error is of first order as:
n 2 -2
( 1 + x/n ) = exp(x) ( 1 - x / 2n ) + O(n )
Possion distribution:
---------------------
PF(z) : the probability generating function.
FM(z) : exponential factorial-moment generating function.
M (z) : exponential moment generating function.
C (z) : exponential cumulant generating function.
PF(z) = exp( lambda(z-1) )
FM(z) = exp( lambda z )
M (z) = exp( lambda (exp(z) - 1) )
C (z) = lambda (exp(z) - 1)
(0) Prob(X=k) = lambda ^ k / k! * exp(-lambda) for k >= 0.
(1) E((X) ) = lambda ^ k
k
(2) E( X^k ) = Bell_polynimial(lambda)
(3) Cumulant (X) = lambda
k
See for example [Knu68, Chap. 1.2.10 Exercise 16] or [Pit97].
A bound for the maximal difference between the matching distribution
and the the Poisson distribution gives [Mic96].
Expected number of k-cycles:
----------------------------
Instead of counting fixpoints one can count the number of k-cycles.
X_i,k,n = [i is member of a k-cycle of an n-permutation]
Y_k,n = # elements i which are member of a k-cycle.
Z_k,n = # k-cycles.
Y_k,n = X_1,k,n + X_2,k,n + ... + Y_n,k,n.
Z_k,n = Y_k,n / k.
Now we can calculate the expectations.
Prob(X_i,k,n = 1) = E(X_i,k,n) = 1/n * [k<=n]
The Foata-Sch\"utzenberger Transformation (the cycle <-> block
correspondence) gives a calculation-free proof,
that all cycle-length are equal likely to contain number n.
[(Knu68, p176 (2nd Ed)] calls this transformation:
"An unusual correspondencs".)
E(Y_k,n) = [k<=n] // Knuth's characteristic function notation.
The expected number of k-cycles is:
E(Z_k,n) = 1/k * [k<=n]
This has been done in a more combinatorial manner in [Knu68, p 177 (2nd Ed)].
Therefore the expected number of cycles of a n-permutation is
E(#cycles) = 1 + 1/2 + 1/3 + ... + 1/n = ln(n) + O(1).
This derivation is generating function free.
Via the cycle-block correspondence we get
E(#left-right-maxima) = E(#cycles).
Renkontre (Expected number of rounds):
--------------------------------------
Silverman [Sil71, problem 75] considers the problem:
Put n letters at random into n envelopes.
Pull out all mismatched ones again.
This is one round.
Then put the remaining letters at random into the
remaining envelopes. Repeat the process until all
letters are matched.
What is the average number of rounds?
Let W_n be the waiting time until all letters are matched.
Silverman says:
>> As the expected number of fixpoints in each round is one,
the expected number of rounds is n. <<
The result is correct, but I don't see the principle it uses.
One can derive the result W_n = n as follows:
Let p_k,n be the probability that a random permutaion
on n points has exactly k fixpoints.
We know, that the expected number of fixpoints is one.
1 = SUM k * p_k,n (expected number of fixpoints)
Induction begin n=0:
W_0 = 0
Induction n-1 -> n:
W_n = 1 + Sum p_k,n * W_(n-k)
We know W_k = k for k < n.
Assume W_n = n one gets
n = Sum k * p_k,n + Sum p_k,n * (n-k) = n * Sum p_k,n = n
Therefore the recurrence is correct for n.
The same problem was solved in two ways in [MM95.1454].
Expected first match:
---------------------
>What is the prob that the first fixed point of a randomly chosen
>permutation of 1, 2, ... , N is k?
>
>[For clarity, X is the set {1, 2, ..., N}. f is a randomly chosen
>bijection on X. What is the prob. that k is the smallest value for which
>f(k)=k?]
Let f(n,k) be the number of permutations of {1,....n} with
first fixed point k. Then the answer to the question is
clearly f(n,k)/n!. It remains to evaluate f(n,k). I get:
k
===
\ t+1
f(n,k) = > (-1) C(k-1,t-1) (n-t)! (A)
/
===
t = 1
This follows pretty easily from the observations that
f(n,1) = (n-1)! (*)
f(n,k) = f(n,k-1) - f(n-1,k-1) (**)
To prove (**), observe that to construct a permutation of n
elements in which k is the first fixed point, you essentially
have to permute the n-1 remaining elements in such a way that
the first fixed point is not among the first k-1 elements.
This gives
k-1
===
\
f(n,k) = (n-1)! - > f(n-1,t)
/
===
t = 1
from which (*) follows.
Steven E. Landsburg
landsbur@troi.cc.rochester.edu
Another way of proving (A) is to use
the inclusion-exclusion principle. If F_j denotes the permutations in S_n
with j as a fixed point, then f(n,k) is the cardinality of K_k - F_1 - F_2 -
... - F_{k-1}. This set consists of the elements of F_k notin the union of
the F_j intersect F_k for j < k. Using the inclusion-exclusion principle to
count these gives the above formula.
Robin Chapman
--
http://www.mathematik.uni-bielefeld.de/~sillke/
mailto:Torsten.Sillke@uni-bielefeld.de