0
$\begingroup$

Let $X_1,\dots,X_m$ be dependent random variables. We are interested in efficient algorithms for computing the following quantity: $$E\Big[\Big(\sum_{i=1}^m X_i\Big)^k\Big],$$ where $k\in\mathbb{N}$ and $E$ denotes the expectation. This has to be computed for several $k$'s.

Are there any ideas or good references? Is it optimal to first do the combinatorial part, and then evaluate the expectations?

Improve this question
$\endgroup$
4
  • $\begingroup$ Without more information I don't see how a reasonable answer can be given. Since the variable are dependent, their sum could be anything at all. What information is available to work from? $\endgroup$
    – Brendan McKay
    Commented Feb 19, 2013 at 22:56
  • $\begingroup$ Thanks for your reply. We know the probability distribution, the characteristic function and the moments for each X_i, and also the joint law of (X_1,...,X_m) and the moments of the form E(X_i*...*X_l), for all i,...l,. The question is how to combine these efficiently for several, consecutive k's. Is it better to compute the quantity (\sum_i=1^m X_i)^k in an efficient way and then take expectations? $\endgroup$
    – Antonis
    Commented Feb 20, 2013 at 11:58
  • $\begingroup$ If you know things like $E(X_1^3X_2X_3^2)$, you can expand $(\sum X_i)^k$ using the multinomial theorem and apply your known expectations to each term. But that will only be feasible if $k$ and $m$ are not too large. If the formulas for the moments are not too messy, or there are symmetries (eg the variables are exchangeable), you might be able to simplify the summation analytically to make the computation shorter. I don't know how to do better in general without some precise model for the dependency. $\endgroup$
    – Brendan McKay
    Commented Feb 21, 2013 at 4:34
  • $\begingroup$ Of course if $\sum X_i$ can only have a small number of different values, computing its actual distribution might be better. $\endgroup$
    – Brendan McKay
    Commented Feb 21, 2013 at 4:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .