# Minimize the Sum of Reciprocal of Probabilities

I need a probability distribution over $$n$$ events such that the sum of expected values is minimized. That is, minimize

The problem is given by:

\begin{aligned} \arg \min_{ {p}_{i} } & \; && \sum_{i = 1}^{n} \frac{1}{ {p}_{i} } \\ \text{subject to} & \; && \sum_{i = 1}^{n} {p}_{i} = 1 \end{aligned}

I guess it's a basic easy question. I would appreciate any hint.

• I believe the minimum value of this sum is just $1$ where we have a single event of probability $1$. Any other combination of events would have some $p_i\lt1$ for which $1/p_i\gt1$ hence the sum would be $\gt1$. – Peter Foreman Jul 1 '19 at 10:46
• I think there is an hidden assumption that $\forall i, \; {p}_{i} > 0$. – Royi Jul 31 '19 at 9:28

Let's use the method of Lagrange multipliers:

$$L=\sum_i\frac{1}{p_i}+\lambda\left(\sum_ip_i-1\right)\implies0=\frac{\partial L}{\partial p_i}=\lambda-\frac{1}{p_i^2}\implies\frac{\partial^2L}{\partial p_i^2}=\frac{2}{p_i^3}>0,$$

So it is guaranteed that the extreme point is a Minimum Point. Moreover:

$$0 = \lambda - \frac{1}{ {p}_{i}^{2} } \Rightarrow {p}_{i} = \frac{1}{ \sqrt{\lambda} }$$

And from the constraint:

$$\sum_{i = 1}^{n} \frac{1}{ \sqrt{\lambda} } = 1 \Rightarrow \lambda = {n}^{2}$$

Which suggests that $${p}_{i} = \frac{1}{n}$$.

• Doesn't $0 = \lambda - \frac{1}{ {p}_{i}^{2} }$ suggests that ${p}_{i} = \frac{1}{\sqrt{\lambda}}$? – Royi Jul 31 '19 at 9:08
• @Royi Thanks; fixed. – J.G. Jul 31 '19 at 9:22
• I also thinks that your solution only holds for the case ${p}_{i} > 0, \; \forall i$. If we are allowed to have value of $0$ (And then we need to take care of the reciprocal) then the result is different. – Royi Jul 31 '19 at 9:26
• @Royi You can't get a smaller, or even a finite, $\sum_i\frac{1}{p_i}$ if any $p_i$ is $0$. – J.G. Jul 31 '19 at 9:29
• This is why I wrote above that I think it is hidden assumption. – Royi Jul 31 '19 at 9:29

Here is an argument that tells you that the minimum value can only be attained the $$p_i$$'s are equal. Suppose the minimum value is attained when $$p_i=q_i, 1 \leq i \leq n$$. If possible let $$q_i \neq q_j$$. Note that $$\frac 1 {q_i} +\frac 1 {q_j} >\frac 1 {\frac {q_i+q_j} 2}+\frac 1 {\frac {q_i+q_j} 2}$$. [This is simply a re-writing of the inequality $$(q_i-q_j)^{2} >0]$$. Thus there is a choice of $$p_i$$'s for which we get a value lower than the minimum. This contradiction shows that $$p_i$$ are all equal when the minimum is attained.

• For the sake of rigor we may note that a continuous function on a compact set has a minimum, so there is indeed one choice $(p_i)$ which gives the minimum value. – Kavi Rama Murthy Jul 1 '19 at 12:32
• thanks for the nice proof! The definition of $q_i$ is not clear, but the idea is very clear. – Parham Jul 3 '19 at 10:17
• @Parham I used $(q_i)$ for the choice of $(p_i)$ which minimzes $\sum \frac 1 {p_i}$. – Kavi Rama Murthy Jul 3 '19 at 10:21
• @KaviRamaMurthy The set is not compact (it's not closed), no ? – Gabriel Romon Jul 31 '19 at 9:38
• For fixed $n$ the collection of all $(p_1,p_2,...,p_n)$ with $p_i >0$ and $\sum p_i=1$ is not closed. However we are minimizing $\sum \frac 1 {p_i}$ and it is easy to see that this function attains its minimum. – Kavi Rama Murthy Jul 31 '19 at 9:46