A construction of permuted stochastic sequences

42 Views Asked by At

I am trying to understand what, probabilistically, a random permutation of a finite list of random variables is, and I tried to draw some ideas from stopped random sequences. For example, seeing a list of random variables $X=\{X_1,\ldots,X_N\}$ as measurable map from $\Omega\times[N]\longrightarrow\mathbb{R}$ (the typical approach in stochastic processes: seeing $X_n(\omega)$ as $X(\omega,n)$) works when defining the stopped sequence $X^\tau$ at random time $\tau\in[N]$, by composing the measurable map with the map which sends $\omega$ into $(\omega,\tau(\omega))$. It is easy to show that this composition, is still a measurable random variable $X_\tau=X_{\tau(\omega)}(\omega)$. I would like to do something similar by considering a randomly permuted list (say by a random permutation $\pi\in S_N$, which we can see in one-line notation as $(\pi_1,\ldots,\pi_N)$), but here I find a difficulty: I cannot start with the same map $\Omega\times[N]\longrightarrow\mathbb{R}$ as a point of view for my list, because I need a notion of order, to get to $X^\pi=\{X_{\pi_1},\ldots,X_{\pi_N}\}$. So I considered seeing an ordered list of random variables as a map from $\Omega\times S_N$ to $\mathbb{R}^N$, that is it sends $(\omega, \pi)$ into $(X_{\pi_1}(\omega),\ldots,X_{\pi_N}(\omega))$. The original list is obtained with $\pi=id$. Then I can see the randomly permuted list $X^\pi$ as a composition of this map with the map that sends $\omega$ into $(\omega,\pi(\omega))$, yielding the desired $(X_{\pi_1(\omega)}(\omega),\ldots,X_{\pi_N(\omega)}(\omega))$. My first question is: is there a more economic approach to this? EDIT: I came to think there might actually be. By also seeing a random permutation as a vector, through its one-line notation, that is a map from $\Omega\times [N+1]$ to $[N+1]$, sending $(\omega,n)$ into $\pi_n(\omega)$, we can exploit the usual map that adds $\omega$ in the first component instead of simply using the permutation, and compose it with the standard point of view of stochastic processes earlier described: thus we define $X^\pi$ as the composition of the map sending $(\omega,n)$ into $(\omega,\pi_n(\omega))$ first and the one sending $(\omega,m)$ into $X_m(\omega)$ secondly, thus achieving $X_{\pi_n(\omega)}(\omega)$. The overall composition goes from $\Omega\times [N+1]$ to $\mathbb{R}$ and is therefore a random vector (it passes through $\Omega\times [N+1]$ in the middle step so it is a valid composition). It seems that these maps that doubles the $\omega$ argument (like $(\omega,\pi_n(\omega))$) are quite useful in these kinds of constructions. Do they have a name and a standard notation?