# Probabilities maximizing products

Given is an expression of the form $P=P_1\times P_2\times\dots\times P_n$, where each $P_i$ is a sum of some distinct elements from $\{x_1,x_2,\dots,x_k\}$. (For example, $P=x_1(x_1+x_2)(x_1+x_3)$.) We want to maximize this expression subject to the constraints $x_i\geq 0$ for all $i$, and $\sum_{i=1}^k x_i=1$. Let $A$ be the value of $P_1$ at the maximum. Let $B$ be the value of $P_1$ at the maximum if we instead maximize the expression $P'=P_2\times P_3\times\dots\times P_n$, subject to the same constraints.

Is it true that $A\geq \frac{n-1}{n}B+\frac{1}{n}$?

• not necessarily. Take $q_1 = 1, q_j = 0$ for $j=2,...,n$ and $p_2=1, p_j = 0$ for $j \neq 2$, and $S_1 = \{ 1 \}$ – Francisco Jul 30 '18 at 10:56
• @Francisco Your choice of $p_i$'s doesn't maximize the given product - it gives value $0$, whereas if we take $p_1=1$ we would get value $1$. – nan Jul 30 '18 at 11:52
• oh.. I see... then $q_j$ must be zero for any $j \in S_1$. That makes it easy, no? just need to prove that $\sum_{j \in S_1}p_j \geq 1/n$ for $j \in S_1$. Which does not seems so difficult to prove. – Francisco Jul 30 '18 at 12:01
• @Francisco No, it's not necessary that $q_j=0$ for $j\in S_1$. – nan Jul 30 '18 at 12:09
• what do you mean by "sum of distinct elements"? Each $x_i$ is in at most one $P_j$? – LinAlg Aug 2 '18 at 16:52

For what it's worth, I tried some Lagrange multipliers: Let $X=(x_1,...,x_k)$ and $Y_i\in \{0,1\}^k$ be such that $P_i=Y_i\cdot X$. Putting $$L(X)=\sum_i \ln(Y_i\cdot X)-\lambda(\textbf 1\cdot X-1)$$ gives for each $j$, either $x_j=0$ or $(\sum_i \frac1 {P_i}Y_i)_j=\lambda=n$. A couple observations:
1. $P_i=Y_i\cdot X$, so the above can be rewritten as $(\sum_i X+Z_i)_j=n$ where $Z_i\cdot X=0$.
2. $(\sum_i \frac1 {P_i}Y_i)\cdot X=n$
• Let $\displaystyle P = \prod_{i=1}^n\sum_{j=1}^k y_{ij}x_j$ and $\displaystyle Q = \prod_{i=2}^n\sum_{j=1}^k y_{ij}x_j$, where $y_{ij} \in \{0, 1\}$ are given constants and $x_j$ are the variables which we can optimize. Not sure if this elementary result will help to kick start of the problem: By the definition of the maximum, $\displaystyle \frac {P^*} {A} \leq Q^*$ and $\displaystyle BQ^* \leq P^*$ which implies $\displaystyle A \geq \frac {P^*} {Q^*} \geq B$ – BGM Aug 10 '18 at 5:27