Let $N$ be a large integer, let $x_1, \ldots, x_{2N}$ be a subset of some space $\mathcal{X}$ (the details of which are irrelevant), and let $f, g, h$ be functions mapping $\mathcal{X}$ to $(0, \infty)$, which are cheap and easy to evaluate (this is a computational statement).
I will use the notation $[M] = \{1, 2, \ldots, M - 1, M \}$
Let $(A, B)$ be an equally-sized partition of $[2N]$, i.e. a pair of subsets of $[2N]$ such that
- $|A| = |B| = N$,
- $A \cap B = \emptyset$,
- $A \cup B = [2N]$,
and define
$$S ( A, B ) \triangleq \left( \sum_{i \in A} f ( x_i ) \right) \times \left( \frac{\sum_{j \in B} g ( x_j ) }{ \sum_{j \in B} h ( x_j ) }\right).$$
Computing $S(A, B)$ for a given $(A, B)$ takes $O(N)$ time, and there are ${2N \choose N } \in \Omega ( 2^{2N} N^{-1/2} )$ such pairs $(A, B)$.
I would like to compute the average of $ S(A,B) $ over all such partitions $(A, B)$, i.e.
$$\bar{S} = {2N \choose N }^{-1} \sum_{(A, B) \vdash [2N] } S ( A, B )$$
but I am not prepared to expend an exponential amount of time doing so.
I suspect that it might be possible to do this in a more reasonable amount of time (e.g. $O(N^2)$, or something of this magnitude) by using some form of dynamic programming / recursion, but I haven't been able to come up with a solution on my own. Are there known solutions for this problem, or can somebody derive one?
Equally, if there's a good reason why I shouldn't be able to compute $\bar{S}$ in time which is polynomial in $N$, I'd also be happy to hear it.
Some remarks: I actually don't really care that $|A| = |B|$; in principle it would be nice to compute averages over all partitions of $[M]$ into subsets of sizes $(R, M - R)$. I'm undecided as to whether formulating the task in such full generality is ultimately useful in this case.