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 X 1 , X 2 , … , X m X_{1},X_{2},\ldots,X_{m} , with X i X_{i} having distribution function F i ⁢ ( 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 F i ⁢ ( x ) F_{i}(x) . Assuming one can simulate values from each distribution, one can generate such “non-iid” order statistics by simulating X i X_{i} from F i F_{i} , for i = 1 , 2 , … , m i=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 F i ⁢ ( x ) F_{i}(x) . This problem arises in Bayesian principal components analysis (BPCA) where the X i X_{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.