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?

  • 1
    $\begingroup$ Cross post: math.stackexchange.com/questions/38662/… . It's usually good form to wait a day or two before cross posting. $\endgroup$ Commented May 12, 2011 at 10:23
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 12, 2011 at 10:56
  • $\begingroup$ i.e. dynamic programming. $\endgroup$ Commented May 13, 2011 at 5:57

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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