Exact Expectation and Variance of Minimal Basis of Random Matroids

Abstract

We formulate and prove a formula to compute the expected value of the minimal random basis of an arbitrary finite matroid whose elements are assigned weights which are independent and uniformly distributed on the interval [0, 1]. This method yields an exact formula in terms of the Tutte polynomial. We give a simple formula to find the minimal random basis of the projective geometry PG(r − 1, q).

Keywords

• minimal basis
• q-analog
• finite projective geometry
• tutte polynomial