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$ – dorkusmonkey May 12 '11 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$ – Johan Wästlund May 12 '11 at 10:56
  • $\begingroup$ i.e. dynamic programming. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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