On the computation of mixing coefficients between discrete-valued random variables

Mixing coefficients between two random variables act as a measure of their dependence. For stochastic processes mixing is another way of saying that the process is asymptotically independent. To measure mixing different types of mixing coefficients are introduced. In the literature, three kinds of mixing coefficients are commonly used, namely α-, β- and φ-mixing coefficients. While it is easy to derive an explicit closed-form formula for the β-mixing coefficient, no such formulas exist for the a- and the φ-mixing coefficients. We study the case where the two random variables assume values in a finite set. Under this setup, we show that the computation of alpha-mixing coefficient is NP-hard. Moreover, by using a semi-definite relaxation we obtain lower and upper bounds for the alpha-mixing coefficient. We also derive a closed form expression for the phi-mixing coefficient between two random variables. These results generalize earlier results by the authors.