5
$\begingroup$

Let $U_i$ be $[0,1]$ i.i.d. uniform random variables, for $i=1,\ldots,n$. As an example, let $n=3$. Now pick an ordering, say $x_1>x_2<x_3$. and consider the order statistics integral

$$3!\int\cdots\int_{x_1>x_2<x_3;\ \ 1>x_i>0} dx_1\,dx_2\,dx_3=2. $$

We get that this integral equals the number of permutations $\pi=(\pi_1,\pi_2,\pi_3)$ in $S_3$ with $\pi_1>\pi_2<\pi_3$. The only ones are $(3,1,2)$ and $(2,1,3)$ for a total of 2 as expected. In general, we have for a given fixed ordering $x_1?x_2\cdots?x_n$, where the question-marks correspond to $<$ or $>$:

$$|\{\pi: \pi_1?\cdots?\pi_n\}|=n!\int\cdots\int_{x_1?x_2\cdots?x_n;\ \ 1>x_i>0} dx_1\,dx_2\,dx_3.$$

Question: is there a sensible meaning for the integral:

$$n!\int_{x_1?x_2\cdots?x_n;\ \ 1>x_i>0} \,x_1\,dx_1\,dx_2\,dx_3\cdots dx_n.$$

I want to conclude that it's (related to) the expected value of the first element $\pi_1$ of a uniformly random permutation drawn from the set $\{\pi: \pi_1?\cdots?\pi_n\}$. Unfortunately, this does not seem to be the case. Is there a way to remedy this?

$\endgroup$
0
$\begingroup$

This isn't a full answer, but may be a helpful thought.

Consider the order $\pi_1>\pi_2>\dots>\pi_n$, so certainly $\mathbb{E}\ \pi_1=n$. Also, your integral now becomes $$n\int_{0< x_1< 1}\biggr(x_1(n-1)!\int_{x_2>\cdots> x_n:\ 0<x_i<x_1}dx_2\cdots dx_n\biggl) dx_1.$$ Now, based on your observation, $$(n-1)!\int_{x_2>\cdots>x_n:\ 0<x_i<x_1}dx_2\cdots dx_n=x_1^{n-1}(n-1)!\int_{x_2>\cdots>x_n:\ 0<x_i<1}dx_2\cdots dx_n=x_1^{n-1},$$ via the substitution $x_i\mapsto x_i/x_1$. Thus, the original integral is $n\int_0^1 x_1^n dx_1={n\over n+1}$.

Similarly, consider the order $\pi_1<\cdots<\pi_n$, so certainly $\mathbb{E}\ \pi_1=1$. Now the integral becomes $$n\int_{0<x_1<1}\biggl(x_1(n-1)!\int_{x_2<\cdots<x_n:\ x_1<x_i<1}dx_2\cdots dx_n\biggr)dx_1.$$ Again, based on your observation, $$(n-1)!\int_{x_2<\cdots<x_n:\ x_1<x_i<1}dx_2\cdots dx_n=(1-x_1)^{n-1}(n-1)!\int_{x_2<\cdots<x_n:\ 0<x_i<1}dx_2\cdots dx_n=(1-x_1)^{n-1},$$ via the substitution $x_i\mapsto {x_i-x_1\over 1-x_1}$. Hence, the original integral is $n\int_0^1 x_1(1-x_1)^{n-1}dx_1={1\over n+1}$.

Now, I know that these are both very simple examples, but they suggest that the following may be true: $$\mathbb{E}_{\pi\sim\{\pi\in S_n:\pi_1?\cdots ?\pi_n\}}\ \pi_1=(n+1)!\int_{x_1?\cdots ?x_n:\ 0<x_i<1}x_1dx_1\cdots dx_n.$$

Edit: Unfortunately, this isn't true in the example that you gave of $\pi_1>\pi_2<\pi_3$ where we have $\mathbb{E}\ \pi_1=2.5$. In this case, $$4!\int_{x_1>x_2<x_3:\ 0<x_i<1}x_1dx_1dx_2dx_3=4!\int_{x_2=0}^1\biggl(\int_{x_2}^1 x_1dx_1\int_{x_2}^1dx_3\biggr)dx_2={4!\over 2}\int_0^1(1-x_2)(1-x_2^2)dx_2=5.$$ However, there are precisely 2 permutations which have $\pi_1>\pi_2<\pi_3$. Thus, a better conjecture (which still agrees with the first two examples I gave) is $$\mathbb{E}_{\pi\sim\{\pi\in S_n:\pi_1?\cdots ?\pi_n\}}\ \pi_1={(n+1)!\over|\{\pi\in S_n:\pi_1?\cdots ?\pi_n\}|} \int_{x_1?\cdots ?x_n:\ 0<x_i<1}x_1dx_1\cdots dx_n.$$

Edit #2: Here is some extra partial evidence that the conjecture may be true. For an order $\pi_1?\cdots?\pi_n$, consider the set $A=\{x\in\mathbb{R}^n: x_1?\cdots?x_n,\ 0<x_i<1\}$. If we uniformly at random select a point in $A$, then $\mathbb{E}_{x\sim A}\ x_1={1\over |A|}\int_A x_1 dx_1\cdots dx_n$. Now, consider a random permutation $\pi\sim\{\pi\in S^n:\pi_1?\cdots ?\pi_n\}$ and consider the points $x={1\over n+1}(\pi_1,\dots,\pi_n)$. This is "kind of" a uniformly random point of $A$ (the reason I scale by $n+1$ is that if we scale only by $n$, then one of the coordinates of $x$ will always be $1$). Of course, it's not actually uniform since all of the coordinates of $x$ are of the form ${i\over n+1}$ for some $i\in[n]$ and $\sum_i x_i={n\over 2}$. If, however, $x$ is ``close enough'' to being uniform on $A$, then we could get the desired inequality since $${1\over|A|}\int_A x_1dx_1\cdots dx_n={n!\over|\{\pi\in S_n:\pi_1?\cdots ?\pi_n\}|} \int_{x_1?\cdots ?x_n:\ 0<x_i<1}x_1dx_1\cdots dx_n,$$ and then we'd get the extra $n+1$ from the scaling. Unfortunately, I don't see how to make this argument precise (especially since the scaling factor of $n+1$ seems rather arbitrary).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.