Return to Question

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ ||\mathrm{Ber}(p) - \mathrm{Ber}(q)||_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I thought I could prove, but now only conjecture (with very compelling numerical evidence) that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$.

How does one prove this?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.

Update Aug-22-2024. The above conjecture easily follows from this stronger one, for which there is very strong numerical evidence:

Poisson binomial conjecture

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ \lVert\mathrm{Ber}(p) - \mathrm{Ber}(q)\rVert_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I thought I could prove, but now only conjecture (with very compelling numerical evidence) that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$.

How does one prove this?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.

Update Aug-22-2024. The above conjecture easily follows from this stronger one, for which there is very strong numerical evidence:

Poisson binomial conjecture

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ ||\mathrm{Ber}(p) - \mathrm{Ber}(q)||_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I thought I could prove, but now only conjecture (with very compelling numerical evidence) that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$.

How does one prove this?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ ||\mathrm{Ber}(p) - \mathrm{Ber}(q)||_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I thought I could prove, but now only conjecture (with very compelling numerical evidence) that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$.

How does one prove this?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.

Update Aug-22-2024. The above conjecture easily follows from this stronger one, for which there is very strong numerical evidence:

Poisson binomial conjecture

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ ||\mathrm{Ber}(p) - \mathrm{Ber}(q)||_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I think I can prove, using standard constrained convex optimization with subgradients, that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$, but it's kind of messy. Is there a "soft" -- perhaps probabilistic? -- proof?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.

For $p\in[0,1]$, we write $\mathrm{Ber}(p)$ to denote the Bernoulli measure on $\{0,1\}$; that is, $\mathrm{Ber}(p)(0)=1-p$, $\mathrm{Ber}(p)(1)=p$. For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]^n$, $\mathrm{Ber}(p)$ denotes the product of $n$ Bernoulli distributions with parameters $p_i$: $$ \mathrm{Ber}(p) = \mathrm{Ber}(p_1) \otimes \mathrm{Ber}(p_2)\otimes \ldots \otimes \mathrm{Ber}(p_n). $$ Thus, $\mathrm{Ber}(p)$ is a probability measure on $\{0,1\}^n$, with $$ \mathrm{Ber}(p)(x) = \prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i} , \qquad x\in\{0,1\}^n, $$

Consider the following (non-convex*) optimization problem: Minimize $$ ||\mathrm{Ber}(p) - \mathrm{Ber}(q)||_1 $$ over all $p,q\in[0,1]^n$ under the constraints $p_i-q_i=\varepsilon_i\ge0$ and $\sum_{i=1}^n \varepsilon_i=\ell$.

I am only interested in the case of even $n$. I thought I could prove, but now only conjecture (with very compelling numerical evidence) that the unique minimum occurs at $p_i=1/2+\ell/(2n)$ and $q_i=1/2-\ell/(2n)$.

How does one prove this?

Warning: the above is only optimal for even $n$, not odd.

*I had previously wrongly claimed that the problem was convex.