Experimenting with the Garsia-Milne Involution Principle
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.tex
First Written: Jan. 30, 2025 . This version: Feb. 24, 2025.
In memory of Adriano Garsia (1928-2024) and in honor of Stephen C. Milne on his 75th birthday.
published in SIGMA 21 (2025), 015, 6 pages.
Added Feb. 26, 2025: This paper will soon apper in Special issue of Sigma in honor of Stephen Milne's 75th birthday.
We thank editor Gaurav Bhatnagar for converting this to
journal format
We use symbolic computation to find explicit expressions for the average, variance, and many higher moments, for the complexity of mappings produced by the
amazing Garsia-Milne Involution Principle.
Maple package
-
GMIP.txt,
a Maple package that experiments with the Garsia-Milne Involution Principle
Sample Input and Output for GMIP.txt
-
If you want to see a paper about the central moments of the TOTAL complexity (sum of all paths-length) of the bijection induced by the Garsia-Milne Involution Principle
The input file
yields the output file
-
If you want to see a paper about the central moments of the INDIVIDUAL complexity (of one specific randomly chosen faithful man) of the bijection induced by the Garsia-Milne Involution Principle
The input file
yields the output file
-
If you want to see the values of the average, variance, and (scaled, about the mean) moments up to the 6th of simulation compared to the exact values
with 400 faithful men (and women) and 300 cheating men (and women), running 1000 times
The input file
yields the output file
-
If you want to see the values of the average, variance, and (scaled, about the mean) moments up to the 6th of simulation compared to the exact values
with 400 faithful men (and women) and 300 cheating men (and women), running 10000 times
The input file
yields the output file
-
If you want to see the values of the average, variance, and (scaled, about the mean) moments up to the 6th of simulation compared to the exact values
with 400 faithful men (and women) and 300 cheating men (and women), running 1000 times
The input file
yields the output file
-
If you want to see the values of the average, variance, and (scaled, about the mean) moments up to the 6th of simulation compared to the exact values
with 400 faithful men (and women) and 300 cheating men (and women), running 10000 times
The input file
yields the output file
-
If you want to see a random example of matching faithful men to faithful women via the Garsia-Milne mapping for
a random example of 30 cheating men (and women) and 10 faithrul men (and women)
The input file
yields the output file
-
If you want to see the limits, as n goes to infinity of the first 30 moments of the r.v.
length of path joining one specific (say the first) faithful man to the faithful woman mapped to him
where there are n faithful men (and women) and k*n cheating men (and women),
as well as what happens at k=1 and confirming that starting at secod moment, the limit as n goes to infinity of
the i-th moment about the mean it equals
i! times the coeff. of xi in 1/(exp(x)*(2-exp(x))
The input file
yields the output file
-
If you want to see the simulations for the complexity of a SINGLE faithful man with 400 faitfhul men (and women) and 300 cheating men (and women)
by running it 10000 times
The input file
yields the output file
-
If you want to see the simulations for the complexity of a SINGLE faithful man with 400 faitfhul men (and women) and 300 cheating men (and women)
by running it 100000 times
The input file
yields the output file
Articles of Doron Zeilberger
Doron Zeilberger's Home Page