Controlled Accuracy Gibbs Sampling of Order Constrained Non-IID Ordered Random Variates

Order statistics arising from $m$ independent but not identically distributed random variables are typically constructed by arranging some $X_{1}, X_{2}, \ldots, X_{m}$,with$X_{i}$havingdistributionfunction$F_{i}(x)$, in increasing order denoted as $X_{(1)}\le X_{(2)}\le \dots \le X_{(m)}$. In this case, $X_{(i)}$ is not necessarily associated with $F_i(x)$. Assuming one can simulate values from each distribution, one can generate such “non-iid” order statistics by simulating $X_i$ from $F_i$, for $i=1,2,\dots ,m$, and arranging them in order. In this paper, we consider the problem of simulating ordered values $X_{(1)},X_{(2)},\dots ,X_{(m)}$ such that the marginal distribution of $X_{(i)}$ is $F_i(x)$. This problem arises in Bayesian principal components analysis (BPCA) where the $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 {\emph{order-constrained non-iid}} order statistics. We demonstrate the effectiveness of our approach for several examples, including the BPCA problem.