4
$\begingroup$

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.

2 Answers 2

2

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

  • 0
    Yes, I did mean compositions. Is it possible to establish the result without using induction?2012-09-22
1

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.

  • 0
    @keng5 Thank you for the interesting problem.2012-09-25