Computational Aspects of Association for Bivariate Discrete Distributions

For bivariate discrete probability distributions, P, on the M x N lattice, various aspects for checking association (Esary, Proschan and Walkup (1967)) are considered. A new algorithm is given for verifying whether or not P is associated. The efficiency of this algorithm is obtained and compared to the efficiency of a simple algorithm based on the definition of association. When M = N = 5, for example, the new algorithm requires less than 3% of the computations required for the simple algorithm. In obtaining these results a new set function Q is constructed from P, on all upper sets in the lattice. In order to construct the algorithm to check association, we define a computationally important set of extreme points and consider related combinatorics.