Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For $1 \le i \le n$, let $X_i$ be $n$ integer-valued random variables that sum to the constant $s$. None of the $X_i$ are zero and they can have identical values. I need to find the the expected value of the product of the random variables, i.e. $E[X_1 X_2\cdots X_n]$. I have been told that there is a simple expression for the answer:

$$E[X_1X_2\cdots X_n] = s(s+1)(s+2)\cdots(s+n-1)/n(n+1)(n+2)\cdots(2n-1).$$

Example: $s = 9$, $n = 5$. The values $X_1, X_2, X_3, X_4, X_5$ can take are all possible arrangements of the following integer partitions of $9$, i.e.

$$5,1,1,1,1$$

$$4,2,1,1,1$$

$$3,3,1,1,1$$

$$3,2,2,1,1$$

$$2,2,2,2,1$$

By direct calculation, $E[X_1X_2X_3X_4X_5] = 715/70 = 143/14$

Using the suggested answer, $E[X_1X_2X_3X_4X_5] = 9\cdot10\cdot12\cdot13/5\cdot6\cdot7\cdot8\cdot9 = 143/14$

I'm not sure whether this is a well-known result, and I have not been able to find any references to it. I have verified that the result holds for various values of s and n, but I am not sure how to prove the result.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You are talking about equally likely compositions and there are $70$ compositions of $9$ into $5$ positive parts.

Hints:

  1. In general there are ${s-1 \choose n-1}$ compositions of $s$ into $n$ positive parts, and there are ${s-x-1 \choose n-2}$ compositions of $s$ into $n$ positive parts where the final part is $x$.

  2. So you can use induction to prove the result (which is clearly true when $n=1$) by taking a weighted sum of the products over the different possible values of $x$.

share|improve this answer
    
To be fair, he said arrangements of partitions and used the number 70. It is pretty clear he means compositions, and that he didn't want to type out all 70 of them! –  Byron Schmuland Sep 22 '12 at 14:58
    
@Byron you are probably correct, but there is nothing in the introduction stating the distribution and I read "i.e." in the the example to mean that was a complete list. –  Henry Sep 22 '12 at 15:07
    
Yes, I did mean compositions. Is it possible to establish the result without using induction? –  keng5 Sep 22 '12 at 17:29

A slight generalization: For $1\leq k\leq n$, using induction it is not hard to show that $$\mathbb{E}(X_1X_2\cdots X_k)={{s+k-1\choose n+k-1}\over{s-1\choose n-1}}.$$


Added: To prove this, we follow Henry's suggestion. If you fix one element, the remaining elements form a random partition with fewer numbers and a smaller sum. So by the induction hypothesis we get $$\mathbb{E}(X_1X_2\cdots X_k\,|\,X_k=x)=x\ {{(s-x)+(k-2)\choose (n-1)+(k-2)}\over{s-x-1\choose(n-1)-1}}.$$ Therefore \begin{eqnarray*} \mathbb{E}(X_1X_2\cdots X_k)&=&\sum_x x\ {{(s-x)+(k-2)\choose (n-1)+(k-2)}\over{s-x-1\choose (n-1)-1}}\ {{s-x-1\choose n-2}\over{s-1\choose n-1}}\\[5pt] &=&\sum_x x\ {{(s-x)+(k-2)\choose (n-1)+(k-2)}\over {s-1\choose n-1}}\\[5pt] &=&{{s+k-1\choose n+k-1}\over{s-1\choose n-1}}. \end{eqnarray*}

In the last step we have used the formula $$\sum_x {x\choose 1}{\ell-x\choose m}={\ell+1\choose m+2}, $$ see for example (5.26) on page 169 of Concrete Mathematics by Graham, Knuth, and Patashnik.

share|improve this answer
    
That is very interesting. Could you provide more details of the proof using induction? –  keng5 Sep 24 '12 at 10:55
    
Thanks! The generalization and its proof are both neat –  keng5 Sep 25 '12 at 10:25
    
@keng5 Thank you for the interesting problem. –  Byron Schmuland Sep 25 '12 at 13:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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