A Linear Time, and Constant Space, Algorithm to Compute the Mixed Moments of the Multivariate Normal Distributions

By Shalosh B. Ekhad and Doron Zeilberger

.pdf    .tex

Written: Feb. 20, 2022

Abstract: Using recurrences gotten from the Apagodu-Zeilberger Multivariate Almkvist-Zeilberger algorithm we present a linear-time, and constant-space, algorithm to compute the general mixed moments of the k-variate general normal distribution, with any covariance matrix, for any specific k. Besides their obvious importance in statistics, these numbers are also very significant in enumerative combinatorics, since they count in how many ways, in a species with k different genders, a bunch of individuals can all get married, keeping track of the different kinds of heterosexual marriages. We completely implement our algorithm (with an accompanying Maple package, MVNM.txt) for the bivariate and trivariate cases (and hence taking care of our own 2-sex society and a putative 3-sex society), but alas, the actual recurrences for larger k took too long for us to compute. We leave them as computational challenges.

# Maple package

• MVNM.txt, a Maple package for the fast computation of mixed moments for the bivariate and trivariate normal distribution (with arbitrary covariance matrix)

# Sample Input and Output for MVNM.txt

• If you want to see the list-of-lists-of-lists,let's call it L, such that L[m1][m2][m3] is the (m1,m2,m3)-mixed moment of the trivariate normal distribution with covariance matrix

1   c12   c13
c12  1   c23
c13  c23   1

for SYMBOLIC (i.e. general) c12,c13, c23, for
1 ≤ m1,m2,m3 ≤ 20

The input file generates the output file

• If you want to see the list of length 35, such that , such that L[m1] is the (2*m1,2*m1,2*m1)-mixed moment of the trivariate normal distribution with correlation matrix [[1,c12,c13],[c12,1,c23],[c13,c23,1]], for SYMBOLIC (i.e. general) c12,c13, c23

The input file generates the output file