## 4 A Decomposition Theorem for General Finite Sequences
: _The subset of \(S^{n}\) containing all ordered \(n\)-entry sequences with respect to some total ordering \(\prec\) on \(S\) is called the ordered sub-domain of \(S^{n}\), denoted by \(\operatorname{Ord}(S^{n})\):_  
\[\operatorname{Ord}(S^{n})=\{(x_{1},\ldots,x_{n})\mid x_{i}\in S,\ (\forall i),\ x_{1}\prec\ldots\prec x_{n}\}.\]  
_A probability measure on \(S^{n}\) is called order respecting (for the ordering \(\prec\)), if \(\mu(A)=0\) holds for every measurable set \(A\subseteq S^{n}\), whenever \(A\cap\operatorname{Ord}(S^{n})=\emptyset\)._  
Now we are ready to state and prove our representation theorem for arbitrary finite sequences of random variables. **Theorem 11**. : _Let \(X=(X_{1},\ldots,X_{n})\) be an arbitrary finite sequence of random variables, each \(X_{i}\) taking values in a measurable space \(S\). Then \(X\) can be represented as a mixture of elementary sequences. Formally, there exist a probability measure \(\mu\) on \(S^{n}\) (mixing measure), such that for any measurable \(A\subseteq S^{n}\)_  
\[\Pr(X\in A)=\int_{S^{n}}\Pr\left((\alpha\circ\beta_{x})(x)\in A\ \right)d\mu(x) \tag{6}\]  
_holds, where \(\alpha,\beta_{x}\in\Sigma_{n}\) are uniform random permutations, possibly not independent of each other, and \(\beta_{x}\) is drawn independently for each \(x\in S^{n}\). Furthermore, the claim remains true if the mixing measure \(\mu\) is restricted to be order respecting for a total ordering \(\prec\) on \(S\) (see Definition 5). In that case, the representation is given by the formula_  
\[\Pr(X\in A)=\int_{\operatorname{Ord}(S^{n})}\Pr\left((\alpha\circ\beta_{x})( x)\in A\ \right)d\mu(x). \tag{7}\]  
For the proof we need two lemmas. The first is a folklore result, stating that if an arbitrary sequence (deterministic or random, with any distribution) is subjected to a uniform random permutation, independent of the sequence, then the sequence becomes exchangeable. We state it below as a lemma for further reference. **Lemma 1**. : _Applying an independent uniform random permutation to an arbitrary finite sequence gives an exchangeable sequence._  
Proof. : Let \(X=(X_{1},\ldots,X_{n})\) be an arbitrary finite sequence, taking values from a set \(S\). Let \(Y=(Y_{1},\ldots,Y_{n})\) be the sequence obtained by applying an independent uniform random permutation \(\alpha\) to \(X\), i.e., \(Y=\alpha(X)\). Pick \(k\leq n\) distinct indices \(i_{1},\ldots,i_{k}\in[n]\). Then for any \(a_{1},\ldots,a_{k}\in S\) we can write  
\[\Pr(Y_{i_{1}}=a_{1},\ldots,Y_{i_{k}}=a_{k})=\frac{1}{\binom{n}{k}k!}\sum_{j_{1 },\ldots,j_{k}\in[n],\text{distinct}}\Pr(X_{j_{1}}=a_{1},\ldots,X_{j_{k}}=a_ {k}). \tag{8}\]The reason is that under the independent uniform random permutation any set of \(k\) distinct indices have equal chance to take the place of \(i_{1},\ldots,i_{k}\), and there are \(\binom{n}{k}k!\) such sets. As a result, the average obtained on the right-hand side of (8) does not depend on the specific \(i_{1},\ldots,i_{k}\) values, only on \(k\). Therefore, \(\Pr(Y_{i_{1}}=a_{1},\ldots,Y_{i_{k}}=a_{k})\) depends only on \(k\), but not on \(i_{1},\ldots,i_{k}\). This is precisely one of the equivalent definitions of an exchangeable sequence. The second lemma expresses the fact that a uniform random permutation can \"swallow\" any other permutation, making their composition also a uniform random permutation. Let \(\sigma,\gamma\in\Sigma_{n}\) be two permutations, such that  
* \(\sigma\) is a uniform random permutation
* \(\gamma\) is an arbitrary permutation (deterministic or random, possibly non-uniform, and possibly dependent on the sequence to which it is applied)
* \(\sigma\) and \(\gamma\) are independent of each other. Then \(\sigma\circ\gamma\) is a uniform random permutation. Proof. : Let \(\xi=(\xi_{1},\ldots,\xi_{n})\) be the sequence (deterministic or random) to which the permutation \(\gamma\) is applied. Fix an index \(k\in[n]\), and let \(\
u\) be the index to which \(\gamma\) maps the index \(k\), i.e., \(\gamma(k)=\
u\).