## 4 A Decomposition Theorem for General Finite Sequences
Note that \(\
u\) may possibly be random, non-uniform, and dependent on \(\xi\). Let us express the probability that \(\sigma\) maps \(\
u\) into a fixed index \(i\):  
\[\Pr(\sigma(\
u)=i)=\sum_{\sigma_{0}}\Pr(\sigma(\
u)=i\mid\sigma=\delta_{0})\Pr (\sigma=\delta_{0}), \tag{9}\]  
where the summation runs over all fixed permutations \(\delta_{0}\) of \([n]\). Observe that \(\Pr(\sigma=\delta_{0})=1/n!\), as \(\sigma\) is uniform and \(\delta_{0}\) is fixed. Furthermore,  
\[\Pr(\sigma(\
u)=i\mid\sigma=\delta_{0})=\Pr(\delta_{0}(\gamma(k))=i\mid\sigma =\delta_{0}).\]  
From this, using the independence of \(\sigma\) and \(\gamma\), we obtain  
\[\Pr(\sigma(\
u)=i\mid\sigma=\delta_{0})=\Pr(\delta_{0}(\gamma(k))=i\mid\sigma =\delta_{0})=\Pr(\delta_{0}(\gamma(k))=i)=\Pr(\delta_{0}(\
u)=i).\]  
Then we can continue (9) as  
\[\Pr(\sigma(\
u)=i)=\frac{1}{n!}\sum_{\delta_{0}}\Pr(\delta_{0}(\
u)=i)=\frac{ 1}{n!}\sum_{j=1}^{n}\sum_{\delta_{0}}\Pr(\delta_{0}(j)=i\mid\
u=j)\Pr(\
u=j). \tag{10}\]  
In the above expression, the event \(\{\delta_{0}(j)=i\}\) involves only fixed values, so it is not random, it happens either with probability 1 or 0, depending solely on whether \(\delta_{0}(j)=i\) or not. As such, it is independent of the condition \(\{\
u=j\}\), so we have \(\Pr(\delta_{0}(j)=i\mid\
u=j)=\Pr(\delta_{0}(j)=i)\), whenever the conditional probability is defined, i.e., \(\Pr(\
u=j)>0\). If \(\Pr(\
u=j)=0\), then the conditional probability is undefined, but in this case the term cannot contribute to the sum, being multiplied with \(\Pr(\
u=j)=0\). Thus, we can continue (10) as  
\[\Pr(\sigma(\
u)=i)=\frac{1}{n!}\sum_{j=1}^{n}\sum_{\delta_{0}}\Pr(\delta_{0}( j)=i)\Pr(\
u=j).\]  
Here the sum \(\sum_{\delta_{0}}\Pr(\delta_{0}(j)=i)\) is the number of permutations that map a fixed \(j\) into a fixed \(i\). The number of such permutations is \((n-1)!\), as the image of \(j\) is fixed at \(i\), and any permutation is allowed on the rest. This yields\[\operatorname{Ord}(S^{n})=\{(x_{1},\ldots,x_{n})\mid x_{i}\in S,\ (\forall i),\ x_{1}\prec\ldots\prec x_{n}\}.\]0  
Thus, we obtain \(\Pr(\sigma(\
u)=i)=1/n\), which means that the position to which \(\
u=\gamma(k)\) is mapped by \(\sigma\) is uniformly distributed over \([n]\), no matter how \(\
u\) was selected, and how it depended on \(\xi\). This holds for every \(k\), making \(\sigma\circ\gamma\) a uniform random permutation. Before turning to the proof of Theorem 4.1, let us point out that a consequence of the above lemma is interesting in its own right:  
Corollary 1: _Any permutation (deterministic or random) can be represented as the composition of two uniform random permutations. Formally, let \(\gamma\in\Sigma_{n}\) be an arbitrary permutation, deterministic or random; if random, then drawn from an arbitrary distribution. Then there exist two uniform random permutations \(\alpha,\beta\in\Sigma_{n}\) (possibly not independent of each other), such that \(\alpha\circ\beta=\gamma\)._  
Proof. : Let \(\sigma\in\Sigma_{n}\) be a uniform random permutation, independent of \(\gamma\). Then by Lemma 2, the permutation \(\beta=\sigma\circ\gamma\) becomes a uniform random permutation. Set \(\alpha=\sigma^{-1}\), which is also a uniform random permutation. Further, let \(\varepsilon\) denote the identity permutation that keeps everything in place. Then we can write  
\[\operatorname{Ord}(S^{n})=\{(x_{1},\ldots,x_{n})\mid x_{i}\in S,\ (\forall i),\ x_{1}\prec\ldots\prec x_{n}\}.\]1  
yielding \(\alpha\circ\beta=\gamma\). As \(\alpha,\beta\) are both uniform random permutations (possibly not independent of each other), this proves the claim. The above corollary also provides an opportunity to characterize elementary sequences:  
Lemma 3 (Characterization of elementary sequences): _A sequence \(X=(X_{1},\ldots,X_{n})\in S^{n}\) is elementary if and only if for any \(a\in S\) the occurrence count \(F(a,X)\) (see Definition 3) is constant._  
Proof.