Does the shuffling of a sequence of measurements produce an i.i.d. sequence?

Question

Given a stationary sequence of measurements, say, of response times (i.e., sojourn times), of a queue (e.g., M/M/1), if we randomly reshuffle such samples, will we get a sequence of i.i.d. samples? If so, how to prove it?

Answer 1

If I understand your question correctly, you have a sequence $X_1, X_2, \ldots$ of random variables from some joint random distribution. You require this to be stationary: ie for any $k>0$, the joint distribution of $(X_i,\ldots, X_{i+k-1})$ is the same for all $i$.

Now, you randomly shuffle the $X_i$ into a new sequence, say $Y_1, Y_2,\ldots$, and ask if this makes the $Y_i$ independent.

It's not fully clear to me how to shuffle an infinite sequence. The best I can come up with is to take a sequence of length $n$, shuffle this, and then see if the limit is a well-defined probability distribution. For the sake of argument, let's assume it does. (Maybe someone can elaborate on this?)

Clement C has already in the comment given an example of how shuffling a finite sequence need not give iid: essentially by taking a joint distribution where the sum $X_1+\cdots+X_n$ is constant. However, this might still result in iid in the limit of $n\rightarrow\infty$.

As a counter-example for an infinite sequence of variables, assume $X_i\sim F_\Theta$ for some random distribution $F_\Theta$ depending on a parameter $\Theta$, where $\Theta$ itself is a random variable. For example, $X_i\sim N(U,\sigma_X^2)$ where $U\sim N(\mu_U,\sigma_U^2)$. This is the kind of models that arise in multi-level models and empirical Bayes. Now, the conditional distribution of $(X_1, X_2, \ldots)|U$, ie conditional on $U$ is iid. However, because of their joint dependence on $U$, the $X_i$ are not iid.

However, the example above, as well as the randomised sequence of observations from your question (if well-defined), are examples of exchangable sequences of variables. This simply means that the distribution is invariant under any reordering.