2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – Peter Foreman Jul 1 '19 at 10:46
  • $\begingroup$ I think there is an hidden assumption that $ \forall i, \; {p}_{i} > 0 $. $\endgroup$ – Royi Jul 31 '19 at 9:28
4
$\begingroup$

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} $.

$\endgroup$
  • $\begingroup$ Doesn't $ 0 = \lambda - \frac{1}{ {p}_{i}^{2} } $ suggests that $ {p}_{i} = \frac{1}{\sqrt{\lambda}} $? $\endgroup$ – Royi Jul 31 '19 at 9:08
  • $\begingroup$ @Royi Thanks; fixed. $\endgroup$ – J.G. Jul 31 '19 at 9:22
  • $\begingroup$ 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. $\endgroup$ – Royi Jul 31 '19 at 9:26
  • $\begingroup$ @Royi You can't get a smaller, or even a finite, $\sum_i\frac{1}{p_i}$ if any $p_i$ is $0$. $\endgroup$ – J.G. Jul 31 '19 at 9:29
  • $\begingroup$ This is why I wrote above that I think it is hidden assumption. $\endgroup$ – Royi Jul 31 '19 at 9:29
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kavi Rama Murthy Jul 1 '19 at 12:32
  • $\begingroup$ thanks for the nice proof! The definition of $q_i$ is not clear, but the idea is very clear. $\endgroup$ – Parham Jul 3 '19 at 10:17
  • 1
    $\begingroup$ @Parham I used $(q_i)$ for the choice of $(p_i)$ which minimzes $\sum \frac 1 {p_i}$. $\endgroup$ – Kavi Rama Murthy Jul 3 '19 at 10:21
  • $\begingroup$ @KaviRamaMurthy The set is not compact (it's not closed), no ? $\endgroup$ – Gabriel Romon Jul 31 '19 at 9:38
  • $\begingroup$ 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. $\endgroup$ – Kavi Rama Murthy Jul 31 '19 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.