Gibbs sampling allocations for time dependent observations from this model

Question

I observe $N$ observations $\{x_{1,t_1}, \dots, x_{N,t_N}\}$ from a $k$ component Gaussian Mixture model. The $i$th observation is seen at time stamp $t_i$ and is distributed such that each $x_{i,t_i}|\boldsymbol{\pi}, \boldsymbol{\mu} \sim \sum_{j=1}^{k} \pi_j \mathcal{N}(\mu_j, \sigma_j)$. However, it is true that each observation with the same time stamp $t_i$ must (each) come from different components. Therefore, if I observe $x_{1,1}, x_{2,1}, x_{3,1}$ at time stamp $1$, then I know that each of the $3$ observations come from 3 different components and also that $k \geq 3$.

Now say I have a Gibbs sampler, and I wish to in one of the steps sample the group/allocation label of each observation to its group $z_i \in \{1, \dots k\}$. In a standard Gibbs sampler, this can be done by putting a dirichlet prior over the mixing weights and sampling the allocation of each observation $z_i$ to each of the $j = \{1, \dots, k\}$ components with probability proportional to $\pi_j \exp \left(\frac{(x_{i,t_i} - \mu_j)^2}{2\sigma_j^2} \right).$ However, I cannot directly use this now because observations are not time dependent. In particular, if at one MCMC iteration, $x_{1,1}$ has already been allocated cluster $2$, then the conditional probability of allocating, say, $x_{2,1}$ to cluster $2$ will be zero, but it still able to take this class.

One idea I had was to block sample all observations seen at the same time stamp, however, I realise this may get computationally heavy if the number of observations seen at any one time is large, and $k$ is also large. Does anyone know how this can be done? Thanks.

Answer 1

Here is a proposal for the joint distribution on the $Z_i$'s:

"A sample of size n is to be drawn without replacement from a population of size N in such a way that the probability of inclusion $\pi_i$ of unit $i$ is proportional to $p_i$, where $p_1 + ... +p_N=1$." M. R. Sampford, Biometrika, 1967, 54, 499-513

Sampford's definition of this joint distribution is, when setting $$\lambda_i=\dfrac{p_i}{1-np_i}$$(the case when there are indices $i$ for which $np_i>1$ can be dealt with by a deterministic inclusion of the said indices in the sample, as many times as necessary to reach $np_i<1$) given by $$\mathbb{P}((Z_1,\ldots,Z_n)=(i_1,\ldots,i_n))= K_n \sum_{u=1}^n p_{i_u} \prod_{{\ \ v\ne u}\\{1\le v\le n}} \lambda_{i_v} $$ which also writes as $$ P{S(n)} = nK_n \prod_{u=1}^n \lambda_u \left(1-\sum_{u=1}^n p_{i_u}\right)$$