Controlled accuracy Gibbs sampling of order-constrained non-iid ordered random variates

Order statistics arising from 𝑚 independent but not identically distributed random variables are typically constructed by arranging some X1,X2,…,XmX_{1},X_{2},\ldots,X_{m}, with XiX_{i} having distribution function Fi⁢(x)F_{i}(x), in increasing order denoted as X(1)≤X(2)≤⋯≤X(m)X_{(1)}\leq X_{(2)}\leq\cdots\leq X_{(m)}. In this case, X(i)X_{(i)} is not necessarily associated with Fi⁢(x)F_{i}(x). Assuming one can simulate values from each distribution, one can generate such “non-iid” order statistics by simulating XiX_{i} from FiF_{i}, for i=1,2,…,mi=1,2,\ldots,m, and arranging them in order. In this paper, we consider the problem of simulating ordered values X(1),X(2),…,X(m)X_{(1)},X_{(2)},\ldots,X_{(m)} such that the marginal distribution of X(i)X_{(i)} is Fi⁢(x)F_{i}(x). This problem arises in Bayesian principal components analysis (BPCA) where the XiX_{i} are ordered eigenvalues that are a posteriori independent but not identically distributed. We propose a novel coupling-from-the-past algorithm to “perfectly” (up to computable order of accuracy) simulate such order-constrained non-iid order statistics. We demonstrate the effectiveness of our approach for several examples, including the BPCA problem.