Problem setting

Let $X_1,X_2,\cdots,X_n$ be tosses of coins (heads = 1, tails = 0) with mean $\mu_1, \mu_2, \cdots,\mu_n$. Let $S(\vec{X})=\sum_{i=1}^n X_i$ and denote variance of the random variable $X_i$ by $\operatorname{Var}(X_i)$.


  1. Can we upperbound $ \sum_{i=1}^n \operatorname{Var}(X_i )- \sum_{i=1}^n\mathbb{E} \Big[\operatorname{Var}\big(X_i \;\big|\; S(\vec{X}) \big)\Big]$? This measures of how much one learns about $X_i$'s given their sum.
  2. Is the above difference maximized for $\mu_i=1/2$?


When all the $\mu_i$'s are equal, the above difference is upper-bounded by a constant lesser than 1/4.


closed as off-topic by Xi'an, Peter Flom Nov 20 '16 at 14:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Self-study questions (including textbook exercises, old exam papers, and homework) that seek to understand the concepts are welcome, but those that demand a solution need to indicate clearly at what step help or advice are needed. For help writing a good self-study question, please visit the meta pages." – Xi'an, Peter Flom
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I suspect the above difference is bounded by $\log (n)$ because $S(\vec{X})$ only gives $\log n$ bits of information. However, I am not sure how to make this rigorous $\endgroup$ – Vivek Bagaria Oct 4 '16 at 22:08
  • 2
    $\begingroup$ Relevant topic that could be useful: en.wikipedia.org/wiki/Poisson_binomial_distribution. $\endgroup$ – dsaxton Oct 5 '16 at 2:02
  • $\begingroup$ Relevant paper for question 2 - arxiv.org/pdf/1503.01570.pdf $\endgroup$ – Vivek Bagaria Oct 5 '16 at 4:40
  • $\begingroup$ Also I think you're interested in a lower and not an upper bound. The only upper bound is a trivial one equal to the leftmost term since if the sum is zero or $n$ all the variances are zero. $\endgroup$ – dsaxton Oct 5 '16 at 12:35
  • $\begingroup$ @dsaxton : I have added an expectation on the negative term to answer your question. $\endgroup$ – Vivek Bagaria Oct 5 '16 at 17:50