0

Given that $p$ is a proper distribution, $p_i \geq 0$, $\sum_i p_i = 1$

Maximize the following expression with respect to $p_i$ $$\sum_i \log(p_i + c_i)$$ where $c_i$ are known positive constants.

Is there any closed-form solution to the problem?

Kuzja
  • 450
  • 4
  • 12
Vuong Bui
  • 5
  • There's almost certainly something wrong with your question, because if $c_1,c_2$ are close to zero then putting $p_1,p_2 = 0$ would make the product have a large factor since $\log(c_1),\log(c_2)$ are both very negative. – user21820 Dec 14 '15 at 14:30
  • thanks, just a mistake, I've change the product to sum. – Vuong Bui Dec 14 '15 at 14:36

1 Answers1

1

Since $\ln$ is concave on $(0,\infty)$, it is easy to prove that $\ln(x)+\ln(y) \le \ln(z)+\ln(w)$ for any $0 < x \le z \le w \le y$ such that $x+y = z+w$. Thus the maximum of $\sum_i \ln(p_i+c_i)$ occurs when $(p_i+c_i)_i$ are as close to each other as possible, subject to the constraints. In general it may not be possible to make them all equal, if $(c_i)_i$ are too far apart. One situation where they can be made all equal is when $c_i \le \frac{1}{n-1}$, in which case one can easily choose $p_i = \frac{1}{n}(1+\sum_i c_i) - c_i$ which makes $(p_i)_i$ non-negative with total sum $1$ and makes $(p_i+c_i)_i$ all equal. ($n$ be the number of terms.)

Here is one way to systematically determine the optimal configuration for arbitrary $(c_i)_i$, just that there will not be a closed form. Start with all $(p_i)_i$ being zero. Increase all the $p_i$ for which $p_i+c_i$ is minimum at the same rate until $\sum_i p_i = 1$ or those $p_i+c_i$ are now equal to some other $p_j+c_j$. It is easy to determine which of these occurs first if $(c_i)_i$ are in sorted order. Repeat until $\sum_i p_i = 1$, which takes at most $n$ steps.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • thank you, I also have this result by applying Lagrange multiplier. however, what the problem insists is that $p_i > 0$, and the result must be valid for every values of $c_i$. – Vuong Bui Dec 14 '15 at 14:55
  • @VuongBui: I've edited my answer to explain roughly how to get the answer, but there will not be a closed form. Don't forget that Lagrange multipliers aren't enough, and you still need to check the boundaries, which would be complicated for arbitrary $(c_i)_i$. And your question only requires $(p_i)_i$ to be non-negative, which my answer solves, while your comment asks for them to be positive, which is impossible since if we have $n = 2$ and $(c_1,c_2) = (0,1)$ then we need $(p_1,p_2) = (1,0)$ otherwise there's no maximum. – user21820 Dec 14 '15 at 15:26
  • much clearer for me now, thank you once again very much – Vuong Bui Dec 14 '15 at 16:52
  • @VuongBui: You're welcome! You can mark my post as the answer if it satisfactorily addressed your question. – user21820 Dec 14 '15 at 19:32