# Efficient computation of $E\left[\frac{1}{1+\sum_iX_i}\right]$ where $X_i$ is RV with Bernoulli distribution with different probabilities

Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ and 0 with probability $1-p_1$. Is there an efficient way to compute $E\left[\frac{1}{1+\sum_iX_i}\right]$ in polynomial time in $n$? If not, is there an approximate solution?

-
Cross post: math.stackexchange.com/questions/38662/… . It's usually good form to wait a day or two before cross posting. –  dorkusmonkey May 12 '11 at 10:23
I suppose you mean that the $X_i$'s are independent. Can't you just inductively on the number of variables find completely the probability distribution of $\sum_iX_i$? Sort of like Pascal's triangle. –  Johan Wästlund May 12 '11 at 10:56
i.e. dynamic programming. –  Ori Gurel-Gurevich May 13 '11 at 5:57

An approach is through generating functions. For every nonnegative random variable $S$, $$E\left(\frac1{1+S}\right)=\int_0^1E(t^S)\mathrm{d}t.$$ If $S=X_1+\cdots+X_n$ and the random variables $X_i$ are independent, $E(t^S)$ is the product of the $E(t^{X_i})$. If furthermore $X_i$ is Bernoulli $p_i$, $$E\left(\frac1{1+S}\right)=\int_0^1\prod_{i=1}^n(1-p_i+p_it)\mathrm{d}t.$$ This is an exact formula. I do not know how best to use it to compute the LHS efficiently. Of course one can develop the integrand in the RHS, getting a sum of $2^n$ terms indexed by the subsets $I$ of $\{1,2,\ldots,n\}$ as $$E\left(\frac1{1+S}\right)=\sum_I\frac1{|I|+1}\prod_{i\in I}p_i\cdot\prod_{j\notin I}(1-p_j).$$

But it might be more useful to notice that $$\prod_{i=1}^n(1-p_i+p_it)=\sum_{k=0}^n(-1)^k\sigma_k(\mathbf{p})(1-t)^k,$$ where $\sigma_0(\mathbf{p})=1$ and $(\sigma_k(\mathbf{p}))_{1\le k\le n}$ are the symmetric polynomials of the family $\mathbf{p}=\{p_i\}$. Integrating with respect to $t$, one gets $$E\left(\frac1{1+S}\right)=\sum_{k=0}^n(-1)^k\frac{\sigma_k(\mathbf{p})}{k+1}.$$ The computational burden is reduced to the determination of the sequence $(\sigma_k(\mathbf{p}))_{1\le k\le n}$.

Note 1 The last formula is an integrated version of the algebraic identity stating that, for every family $\mathbf{x}=\{x_i\}_i$ of zeroes and ones, $$\frac1{1+\sigma_1(\mathbf{x})}=\sum_{k\ge0}(-1)^k\frac{\sigma_k(\mathbf{x})}{k+1},$$ truncated at $k=n$ since, when at most $n$ values of $x_i$ are non zero, $\sigma_k(\mathbf{x})=0$ for every $k\ge n+1$. To prove the algebraic identity, note that, for every $k\ge0$, $$\sigma_1(\mathbf{x})\sigma_k(\mathbf{x})=k\sigma_k(\mathbf{x})+(k+1)\sigma_{k+1}(\mathbf{x}),$$ and compute the product of $1+\sigma_1(\mathbf{x})$ by the series in the RHS. To apply this identity to our setting, introduce $\mathbf{X}=\{X_i\}_i$ and note that, for every $k\ge0$, $$E(\sigma_k(\mathbf{X}))=\sigma_k(\mathbf{p}).$$

Note 2 More generally, for every suitable complex number $z$, $$\frac1{z+\sigma_1(\mathbf{x})}=\sum_{k\ge0}(-1)^ka_k(z)\sigma_k(\mathbf{x}),\qquad a_k(z)=\frac{\Gamma(k+1)\Gamma(z)}{\Gamma(k+1+z)}.$$

Note 3 When $p_i=p$ for every $i$, $$\frac1{1+pn}< E\left(\frac1{1+S}\right)=\frac{1-(1-p)^{n+1}}{p(n+1)}< \frac1{p(n+1)}.$$

-

The result is indeed computable in polynomial time. Didier has shown in his answer that $$E\left(\frac1{1+\sum_{i=1}^n}\right)=\sum_{k=0}^n\frac{(-1)^k}{k+1}\sigma_k(p_1,\dots,p_n),$$ where $\sigma_k$ are the elementary symmetric polynomials. In order to finish this argument, it thus suffices to compute in polynomial time the numbers $\sigma_k(p_1,\dots,p_n)$. This can be done easily using the recurrence \begin{align} \sigma_0(p_1,\dots,p_m)&=1,\\\\ \sigma_{k+1}(p_1,\dots,p_m)&=\sum_{i=k+1}^mp_i\sigma_k(p_1,\dots,p_{i-1}). \end{align} We compute all the numbers $\sigma_k(p_1,\dots,p_m)$ for $k\le m\le n$ inductively: if we already know the sequence of values $\sigma_k(p_1,\dots,p_m)$ for all $m=k,\dots,n$, we use the recurrence to compute $\sigma_{k+1}(p_1,\dots,p_m)$ for all $m=k+1,\dots,n$. Thus the whole computation takes $O(n^2)$ evaluations of the sum above, hence $O(n^3)$ arithmetical operations.

-