4
$\begingroup$

Let $a_i$ be $n$ distinct real numbers. What is the expectation:

$$\mathbb E_\sigma \left[ \sum_{i=1}^{n} \frac {1} {a_{\sigma(i)} - \sum_{j=1}^{i-1}a_{\sigma(j)}} \right] $$

where the expectation is taken over all $n!$ permutations $\sigma:[1,2,..,n]\rightarrow[1,2,..,n]$

I appreciate your help.

  • 0
    Not sure what here is random that admits taking expected values?2012-12-20
  • 0
    nothing is random, it's just the sum of all these n! terms, divided by n!. maybe average is a more appropriate word.2012-12-20
  • 1
    I don't see how it can be made any simpler than the expression you already have.2012-12-20
  • 0
    can't it be independant of $\sigma$? or any way to calculate it more efficiently than o(n!)?2012-12-20
  • 0
    $\sigma$ is just a dummy variable; the sum is fixed. Who are you directing that question at?2012-12-20
  • 0
    the sum is not fixed. the terms aren't symmetric. i encountered this when investigating a family of Gram matrices in the scope of computational learning.2012-12-20
  • 0
    Edit: I see we are talking about different sums. I am talking about the whole sum, taken over all $\sigma$s and then divided by $n!$, which you mention in your first comment. I was just wondering why you asked "can't it be independant of $\sigma$."2012-12-20
  • 0
    Edit: the outer sum (the expectation taking) has n! components. the inner big sum has n elements, and there is the last sum under the fraction which depends on the big sum. everything is fixed except for the permutation. you can replace $\mathbb E$ with $\frac {1} {n!} \sum_{\sigma\in S^n}$2012-12-20
  • 1
    For every subset $J\subseteq \{1,2,\cdots,n\}$ denote $$R_J:=\sum_{\ell\in J}\frac{1}{x_\ell-\sum\limits_{t\in J\setminus \{\ell\}}x_t}.$$ Intuitively then the average should be $$\sum_{J\subseteq\{1,\cdots,n\}}(n-|J|)!(|J|-1)!R_J.$$ This might help, if it is correct.2012-12-20
  • 0
    @anon: I think you mean $|J|$ where you have $|R|$?2012-12-20
  • 0
    @joriki Indeed I do, thanks.2012-12-20
  • 0
    please note that the sum under the fraction is only of the first $i$ terms. so for $\sigma(i)=i$, it looks like $\frac 1 a_1 + \frac 1 {a_2 - a_1} + \frac 1 {a_3 - a_2 - a_1}$2012-12-20
  • 0
    @anon is almost right: you have to divide that by $n!$ to take the average, rather than sum, over permutations. And of course you only want the nonempty subsets $J$.2012-12-20
  • 0
    can you please explain me more? i didn't understand the development. also i dont understand how it get along with my previous comment2012-12-20

0 Answers 0