# Expected value of the product of random integers summing to a constant value.

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.

-

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$.

-
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.

-
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