# Construction of some function on the group of permutations

Let $x=(x_1,\ldots, x_{2m})$ be vector in $R^{2m}$ and let $r=(r_1,\ldots,r_{2m})$be sequence, such that $P(r_i=1)=P(r_i=-1)=1/2.$ Consider the following set

\begin{align*} X=\{r \in\{-1, 1\}^{2m}| \sum_{i=1}^{2m}r_i=0\}=\{r\in\{-1, 1\}^{2m}| r_i=\left\{ \begin{array}{rcl} 1,&\quad i\in Y\\[4mm] -1,&\quad i \notin Y \end{array}\right.\}, \end{align*} where $Y\subset \{1,.., 2m\}, card(Y)=m.$ For set $X$ we put into correspondence the group $S_{2m}$ of all permutations of set $\{1,..., 2m\}$ as \begin{align*} \pi(\cdot)\longrightarrow r_{\pi(i)}=\left\{ \begin{array}{rcl} 1,&\quad \pi(i)\leq m\\[4mm] -1,&\quad \pi(i)> m \end{array}\right.. \end{align*}

One can define $f:S_{2m}\longrightarrow R$ to be \begin{align} f(\pi)=\left|\sum_{i=1}^mx_{\pi(i)}-\sum_{i=m+1}^{2m}x_{\pi(i)}\right|. \end{align}

Please help me to understand how the function $f(\pi)$ was constructed?

(I am confused because one element in the probability space corresponds few elements in the group of permutations--we have $2^{2m}$ elements in the probability space and $(2m)!$ elements in the group of permutations).

Thank you.

-
(a) We have $r_i$, depending on $\pi$ (maybe better denoted by $r_\pi(i)$), and $x_{\pi(i)}$ here. (b) The backwards arrow in the definition of $r-i$ is unwarranted. The permutation $\pi$ cannot be reconstructed from the data $r_\pi(i)$ $\,1\leq i\leq 2m)$. – Christian Blatter Sep 1 '12 at 18:26
Why not just start with a given $(x_1, \ldots, x_{2m})$ and define $f$ right-away by $f(\pi)=\ldots$? – Hagen von Eitzen Sep 1 '12 at 21:22
@ Hagen von Eitzen: I wanted to understand the logic--how one define $f(\pi)$. So I've wrote whale steps... – Michael Sep 2 '12 at 2:40

The question has quite unrelated parts, this makes difficult to understand what is really asked, but one part is clear, which asks:

(I am confused because one element in the probability space corresponds few elements in the group of permutations--we have $2^{2m}$ elements in the probability space and $(2m)!$ elements in the group of permutations).

The confusion might be explained as follows. The sample space $X_0$ of the random sequence $r=(r_k)_{1\leqslant k\leqslant2m}$ is indeed $X_0=\{-1,1\}^{2m}$, which has size $2^{2m}$, but this is irrelevant for two reasons:

• First, the function $f$ uses only permutations corresponding to sequences $r$ in $X\subset X_0$, where $X$ is defined by the condition $\sum\limits_{k=0}^{2m}r_k=0$. And the size of $X$ is ${2m\choose m}$, much less than the size $2^{2m}$ of $X_0$.
• Second, the correspondence $\pi\mapsto r_\pi$ from $\mathfrak S_{2m}$ to $X$ is many-to-one since $r_\pi$ only keeps track of whether $\pi(i)\leqslant m$ or not, for each $i$, and not of the exact value of $\pi(i)$. For a given $r$ in $X$, to know that $r=r_\pi$ is not sufficient to know $\pi$ since one lacks the exact value of $\pi(i)$, either in $\{1,\ldots,m\}$ or in $\{m+1,\ldots,2m\}$. There are $(m!)^2$ possible such choices hence each $r$ in $X$ corresponds to $q=(m!)^2$ permutations $\pi$ in $\mathfrak S_{2m}$.

The take-home message is as follows:

The correspondence $\pi\mapsto r_\pi$ goes from $\mathfrak S_{2m}$ to $X$ (hence the size $2^{2m}$ of $X_0$ is irrelevant), and is $q$-to-one (and not one-to-one).
As was to be expected, $q\cdot|X|=|\mathfrak S_{2m}|$, since $|\mathfrak S_{2m}|=(2m)!$, $|X|={2m\choose m}$ and $q=(m!)^2$.

Nothing in the above is probabilistic in any way, and, in fact, the whole part of the question mentioning probability is really confusing. Maybe what the OP has in mind could be reformulated as follows. Consider a random permutation $Q$, distributed uniformly in $\mathfrak S_{2m}$, and let $$R=r_Q.$$ That is, $(\Omega,\mathcal F,\mathrm P)$ is the underlying probability space, $Q:\Omega\to\mathfrak S_{2m}$, $R:\Omega\to X$, for every $\pi$ in $\mathfrak S_{2m}$, $\mathrm P(Q=\pi)=|\mathfrak S_{2m}|^{-1}=[(2m)!]^{-1}$, and, for every $\omega$ in $\Omega$, $R(\omega)=r_{Q(\omega)}$, where, for every $\pi$ in $\mathfrak S_{2m}$, $r_\pi$ is defined as in the post. Then:

The random variable $R=(R_k)_{1\leqslant k\leqslant 2m}$ is distributed uniformly in $X$, in particular, $\sum\limits_{k=0}^{2m}R_k=0$ almost surely, and, for every $k$, $\mathrm P(R_k=+1)=\mathrm P(R_k=-1)=\frac12$.

-

I'm not sure what's meant by "how the function $f$ was constructed." It seems pretty clear how it's defined and evaluated - and it seems to have nothing to do with $X$ or probability.

You have some $x$ in ${\bf R}^{2m}$. Let's say, $m=3$, and $x=(3,1,4,1,5,9)$. Then you have some permutation $\pi$; let's say, $$\pi=\pmatrix{1&2&3&4&5&6\cr3&6&1&5&4&2\cr}$$ in the 2-row notation. Then $$f(\pi)=\left|(x_{\pi(1)}+x_{\pi(2)}+x_{\pi(3)})-(x_{\pi(4)}+x_{\pi(5)}+x_{\pi(6)})\right|=\left|(x_3+x_6+x_1)-(x_5+x_4+x_2)\right|=\left|(4+9+3)-(5+1+1)\right|$$

-