Ewens distribution on Sn is a wavy probability distribution with respect to n partitions

Udrea Păun


We show that the Ewens distribution on Sn, the set of permutations of order n, is a wavy probability distribution with respect to an order relation and n partitions which will be specified --- the fact that the number of partitions is n is important. We then construct a Gibbs sampler in a generalized sense for the Ewens distribution. This chain leads
    1) to a fast exact (not approximate) Markovian method for sampling from Sn according to the Ewens distribution and, as a result, to a fast exact method for sampling from An, a set which will be specified, according to the Ewens sampling formula;
    2) to the computation of normalization constant of Ewens distribution;
    3) to the computation, by Uniqueness Theorem, of certain important probabilities for the Ewens distribution and, as a result, to upper bounds for the cumulative distribution function of number of cycles of permutation chosen from Sn according to the Ewens distribution.
         Our sampling Markovian method has something in common with the swapping method. The number of steps of our sampling Markovian method is equal to the number of steps of swapping method, i.e., n-1; moreover, both methods use the best probability distributions on sampling, the swapping method uses uniform probability distributions while our method uses almost uniform probability distributions (all the components of an almost uniform probability distribution are, here, identical, excepting at most one of them).

Full Text:


DOI: https://doi.org/10.52846/ami.v47i1.1202