Automated Derivation of Limiting Distributions Of Combinatorial Random Variables Whose Generating Functions are Rational

By Doron Zeilberger

.pdf   .ps   .tex

Written: Dec. 24, 2016

[Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger]

In this seminal article I showed how to teach a computer to discover (and prove!) Central Limit Theorems for a wide class of combinatorial random variables. Here I extend it even further, to an even larger class, namely those whose bi-variate generating functions are rational functions in both variables. The same methodology can be applied to get the multi-distribution with several combinatorial random variables. But its implementation would have to wait for the future.

# Maple packages

• BiVariateMoms.txt, a Maple package to automatically derive explicit expressions for the expectation, variance, higher moments, and limiting distributions of combinatorial random variables whose generating functions are given by bivariate generating functions.

• RandComps.txt, a Maple package that tests the above package, by drawing random compositions of an arbitrary alphabet, and exploring the distribution of the random variable `number of occurrences of` one of its members.

# Sample Input and Output Files for the Maple package BiVariateMoms.txt

• If you want to see a computer-generated article about the average, variance, and the moments up to the 6th, of the random variable "number of 2's" defined on the set of compositions of n, only using 1's and 2's

the input file generates output file.

• If you want to see a computer-generated article about the average, variance, and the moments up to the 6th, of the random variable "number of Heads" defined on the set outcomes of n coin-tosses of a fair coin

the input file generates output file.

• If you want to see a computer-generated article about the average, variance, and the moments up to the 4th, of the random variable "number of monomers" defined on the set of monomer-dimer tilings of a 2 by n rectangle , 4 by n rectangle , and 6 by n rectangle,

the input file generates output file.

• If you want to see graphs of the function x vs. limit of log(a(n,n*x))/n as n goes to infinity, where a(n,m) is the coefficient of tnwm in the Maclaurin expansion of the rational function f(t,w), for various rational functions,

the input file generates output file.

• If you want to see several computer-generated articles about the average, variance, and the moments up to the 6th, of the random variable
• "number of occurences of 2s" defined on the set of compositions of n, only using {2,3}
• "number of occurences of 3s" defined on the set of compositions of n, only using {2,3}
• "number of occurences of 2s" defined on the set of compositions of n, only using {2,3,5}
• "number of occurences of 3s" defined on the set of compositions of n, only using {2,3,5}
• "number of occurences of 5s" defined on the set of compositions of n, only using {2,3,5}

the input file generates output file.

# Sample Input and Output Files for the Maple package RandComp.txt

• If you want to see the outcome of an experiment where 1000 (uniformly-at-random) compositions of 100, that only use {1,2}, and keeping track of the random variable `number of occurrences of 1'. It also returns the exact expectation and standard-deviation (the last component)

the input file generates output file.

• If you want to see the outcome of an experiment where 2000 (uniformly-at-random) compositions of 200, that only use {1,3,5}, and keeping track of the random variable `number of occurrences of 3'. It also returns the exact expectation and standard-deviation (the last component)

the input file generates output file.

• If you want to see the outcome of an experiment where 2000 (uniformly-at-random) compositions of 200, that only use {2,3,7}, and keeping track of the random variable `number of occurrences of 7'. It also returns the exact expectation and standard-deviation (the last component)

the input file generates output file.

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger