Poisson binomial conjecture

Question

Let $X_i\in\{0,1\}$ be mutually independent and distributed according to $\mathrm{Bernoulli}(p_i)$ and similarly, $Y_i\sim\mathrm{Bernoulli}(q_i)$, for some parameters $p,q\in[0,1]^n$. Put $X:=\sum_{i=1}^n X_i$ and $Y:=\sum_{i=1}^n Y_i$; both take values in $\{0,\ldots,n\}$.

Assume $p_i\ge q_i$ and even $n$, put $\gamma:=\frac1n\sum_{i=1}^n(p_i-q_i)$, and let $\bar X\sim\mathrm{Binomial}(n,1/2+ \gamma/2)$ and $\bar Y\sim\mathrm{Binomial}(n,1/2- \gamma/2)$.

Conjecture: $$ \max_{k\ge 0} | \mathbb{P}(X\ge k) - \mathbb{P}(Y\ge k) | \ge \mathbb{P}(\bar X\ge n/2) - \mathbb{P}(\bar Y\ge n/2) .$$

This would imply, in particular, a positive resolution of the conjecture in Minimizing total variation under constraint

Answer 1

This is far from a complete answer. In particular, it loses a factor of 2. But I'll share anyway in case it is useful somehow.

For $p \in [0,1]$, let $B_p$ denote the Bernoulli distribution on $\{0,1\}$ with mean $p$. For $p \in [0,1]^n$, let $B_p = B_{p_1} \otimes B_{p_2} \otimes \cdots \otimes B_{p_n}$ be the product distribution on $\{0,1\}^n$ with mean $p$.

Fact 1: For product distributions $B_p$ and $B_q$ on $\{0,1\}^n$, we have $$TV(B_p,B_q) := \sup_{S \subset \{0,1\}^n} \mathbb{P}_{X \gets B_p}[ X \in S ] - \mathbb{P}_{Y \gets B_q} [Y \in S]$$ $$= \sup_{\theta \in \mathbb{R}^n, t \in \mathbb{R}} \mathbb{P}_{X \gets B_p}[\langle \theta, X \rangle \ge t] - \mathbb{P}_{Y \gets B_q}[\langle \theta, Y \rangle \ge t],$$ where the supremum is attained by setting $\theta_i = \log\left(\frac{p_i(1-q_i)}{q_i(1-p_i)}\right)$ for all $i$ and $t = \sum_i \log\left(\frac{1-p_i}{1-q_i}\right)$. This fact follows from the Neyman-Pearson lemma.

By Fact 1, the conjecture in the question follows from the following slightly stronger conjecture. $$\forall p,q\in[0,1]^n ~~~~~ TV(B_p,B_q) \ge TV(B_{\bar{p}},B_{\bar{q}}),\tag{$*$}$$ where $\bar{p}_i = 1-\bar{q}_i = \frac12 + \frac{1}{2n} \sum_j^n p_j-q_j$ for all $i$.

Lemma 2. For any $p,q \in [0,1]$ there exists a randomized function $F_{p,q} : \{0,1\} \to \{0,1\}$ such that $F_{p,q}(B_p)=B_{(1+\gamma)/2}$ and $F_{p,q}(B_q) = B_{(1-\gamma)/2}$, where $\gamma = \frac{p-q}{1+|p+q-1|}$.

Proof. We may assume $p \ne q$, since, if $p=q$, then the randomized function can just ignore its input and return a sample from $B_p=B_q$. We define $F_{p,q}$ by its stochastic matrix $$M = \left(\begin{array}{cc} \mathbb{P}[F_{p,q}(1)=1] & \mathbb{P}[F_{p,q}(1)=0] \\ \mathbb{P}[F_{p,q}(0)=1] & \mathbb{P}[F_{p,q}(0)=0] \end{array}\right) = \left(\begin{array}{cc} \frac12 + \frac{\gamma}{p-q}\frac{2-p-q}{2} & \frac12 - \frac{\gamma}{p-q}\frac{2-p-q}{2} \\ \frac12 - \frac{\gamma}{p-q}\frac{p+q}{2} & \frac12 + \frac{\gamma}{p-q}\frac{p+q}{2} \end{array}\right).$$ The randomized function is well-defined as long as $M$ is a valid stochastic matrix. The rows of $M$ sum to $1$ and the entries are non-negative, since $$0 \le \frac{\gamma}{p-q}\frac{2-p-q}{2} = \frac12 \frac{2-p-q}{1+|1-p-q|} \le \frac12$$ and $$0 \le \frac{\gamma}{p-q} \frac{p+q}{2} = \frac12 \frac{p+q}{1+|p+q-1|} \le \frac12.$$ Next we verify $F_{p,q}(B_p) = B_{(1+\gamma)/2}$, which boils down to a matrix-vector multiplication: $$\big(\mathbb{P}[F(B_p)=1] ~,~ \mathbb{P}[F(B_p)=0\big) = \big(\mathbb{P}[B_p=1] ~,~ \mathbb{P}[B_p=0]\big) M = \big(p ~,~ 1-p\big) M$$ $$=\left( \frac{p+1-p}{2} + \frac{\gamma}{2(p-q)}\big(p(2-p-q) -(1-p)(p+q)\big) ~,~ \frac{p+1-p}{2} - \frac{\gamma}{2(p-q)}\big(p(2-p-q)-(1-p)(p+q)\big)\right)$$ $$= \left( \frac12 + \frac{\gamma}{2} ~,~ \frac12 - \frac{\gamma}{2}\right).$$ A similar calculation shows that $F_{p,q}(B_q)=B_{(1-\gamma)/2}$, as required. ∎

Back to the question: Suppose we are given $p,q\in[0,1]^n$. Define $\gamma,\hat{p},\hat{q} \in [0,1]^n$ by $\gamma_i = \frac{p_i-q_i}{1+|p_i+q_i-1|}$ and $\hat{p}_i=1-\hat{q}_i=\frac12+\frac12\gamma_i$ for all $i$. Define a randomized function $F_{p,q} : \{0,1\}^n \to \{0,1\}^n$ as follows. Given $x \in \{0,1\}^n$, independently for each $i$, let $y_i = F_{p_i,q_i}(x_i)$, where $F_{p_i,q_i}$ is the function given by Lemma 1; then $F_{p,q}(x)=y$. By Lemma 1 and the fact that all the coordinates are independent, we have $F_{p,q}(B_p) = B_{\hat{p}}$ and $F_{p,q}(B_q) = B_{\hat{q}}$.

By the data processing inequality for total variation distance, we now have $$TV(B_p,B_q) \ge TV(F_{p,q}(B_p),F_{p,q}(B_q)) = TV(B_{\hat{p}},B_{\hat{q}}). \tag{$\dagger$}$$

What we can show ($\dagger$) is weaker than what we want ($*$) in two ways: First, $\bar{p}$ and $\bar{q}$ are uniform across coordinates, while $\hat{p}$ and $\hat{q}$ are not. Secondly, we lose a factor of 2; we want $\|\bar{p}-\bar{q}\|_1 = \|p-q\|_1$, but instead we have $$\frac12 \|p-q\|_1 \le \|\hat{p}-\hat{q}\|_1 = \|\gamma\|_1 = \sum_i^n \frac{|p_i-q_i|}{1+|p_i+q_i-1|} \le \|p-q\|_1.$$

Answer 2

I have an approach to solve the problem for $\gamma>2/n$, which can perhaps be adapated to work for smaller $\gamma$.

Consider first the optimization problem: minimize $\mathbb P( X \geq k) $ where $X = \sum_{i=1}^n X_i$ with the $X_i$ Bernoulli with parameters $p_i$ and subject to the constraint $\sum_{i=1}^n p_i = m$. So this is a problem with two parameters, $k \in \{1,\dots,n-1\}$ in $m\in [0,n]$.

Let's describe the range of parameters where the minimum is attained for i.i.d. Bernoulli random variables (and thus with $p_i =m/n$).

Observe the following: For any $i\neq j$, $X_i+X_j$ takes the value $0,1$, or $2$. Increasing $p_i$ and decreasing $p_j$ has the function of changing the probabilities of $0,1,2$ while keeping the expectation of $X_i+X_j$ constant. This keeps the probabilities of $0,1,2$ in a one-dimensional linear space. The function to be optimized is a linear function of these three probabilities, so is optimized by one of the extreme points. The extremes are attained when either $p_i= p_j$, which maximizes the probabilities of $0$ and $2$, or $p_i$ and $p_j$ are as far apart as possible, so one of them is $1$ and one of them is $0$, which maximizes the probability of $1$.

So the optimizer must have, for each $i\neq j$ either $p_i=p_j$ or $p_i=1$ or $p_j=1$ or $p_i=0$ or $p_0=0$. Considering this for all $i,j$, we see that $p_i$ takes only one value other than $1$, which I will call $p$.

More precisely, it only matters what $X_i +X_j$ is if the sum of all the other $X_{i'}$ variables is either $k-1$ or $k-2$. If it's $k-2$ then we want $X_i + X_j$ to be $0$ or $1$ and if it's $k-1$ then we want $X_i + X_j$ to be $0$. So if the probability of the sum of the other variables being $k-2$ is less then the probability of the sum of the other variables being $k-1$, then the maximum is attained at $p_i=p_j$, which we want.

These probabilities can be computed. If $a$ is the number of $p_{i'}$ other than $p_i$ or $p_j$ equal to $p$ and $b$ is the number of $p_{i'}$ other than $p_i$ or $p_j$ equal to $1$ then the probability of getting $k-2$ is $\binom{a}{k-2-b} p^{k-2-b} (1-p)^{a+b +2-k}$ and the probability of getting $k-1$ is $\binom{a}{k-1-b} p^{k-1-b} (1-p)^{a+b +1-k}$ so the probability of getting $k-2$ divided by the probability of getting $k-1$ is $$ \frac{k-1-b }{ a+b+2-k } \frac{1-p}{p} $$ which is less than $1$ if and only if $$ (k-1-b) (1-p) < (a+b+2-k) p $$ i.e. if and only if $$ k < (a+1) p +1 + b$$ Now $ap + b +p_i+p_j = m$ so this occurs if and only if $$k< m + p+1 -p_i + p_j.$$ If $p_i$ and $p_j$ are distinct then one is at most $1$ and the other is at most $p$ so their sum is at most $p+1$, so as long as $k<m$ this condition will be satisfied for every $p_i,p_j$ distinct. In this case, the optimum is attained for all $p_i$ equal.

Symmetrically the maximum of $ \mathbb P(Y \geq k )$, which is equivalent to the minimum of $\mathbb P (Y \leq k-1)$ is attained for all $q_i$ equal as long as $m< k-1$.

Now for any solution with $\gamma>2/n$, we can find $k$ such that $\sum_{i=1}^n p_i > k > k-1 > \sum_{i=1}^n q_i$ so that $P(X \geq k)$ is at least the probability $X \geq k$ if we replace all the $X_i$ with i.i.d. Bernoulli variables with probability $\frac{1}{n} \sum_{i=1}^n p_i $ and $\mathbb P(Y \geq k)$ is at most the probability $Y \geq k$ if we replace all the $Y_i$ with i.i.d Bernoulli variables with probability $\frac{1}{n} \sum_{i=1}^n q_i $. So the difference between the probabilities is at least the difference in the i.i.d. case.

So it remains to check that the difference in the i.i.d. case is minimized by taking i.i.d. Bernoullis with probability symmetric around $1/2$, where we restrict attention in the max to $k$ sandwiched between the means in this way. But $k$ sandwiched between the means are likely to have the greatest difference in probabilities anyways, so this is plausible. However, I didn't check this.