13
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Once we prove that the objective is convex, the rest follows easily from symmetry. The optimal solution must be invariant under the permutation group (acting on the indices of $p_i$ and $q_i$) and "reflections": $(p, q) \mapsto (1 - q, 1- p)$. The only fixed point is your solution. $\endgroup$
    – Yury
    Commented Aug 13 at 15:49
  • $\begingroup$ Note that this is false for odd n, so where does your argument fail there? $\endgroup$
    – Aryeh Kontorovich
    Commented Aug 13 at 15:58
  • 1
    $\begingroup$ My plot shows that it is not a convex function of $x$ even when all $p_i = x + 0.1$ and $q_i = x$, $n = 3$. $\endgroup$
    – Yury
    Commented Aug 13 at 16:56
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Yury
    Commented Aug 13 at 17:41
  • 1
    $\begingroup$ Induction -- as well as all other "local" methods seem to fail badly here. I can prove the minimizer claim for $n=2$, but not that it's unique. The minimizer for odd $n$ has all $p_i$s equal and all $q_i$s too but otherwise doesn't have the nice, simple form that even $n$ does. $\endgroup$
    – Aryeh Kontorovich
    Commented Aug 16 at 8:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .