# Bounding sum of weighted exponential

I would like to upper bound $$\sum_{i}^{n} P_{i} \cdot \exp(-\beta \cdot P_{i} \cdot n)$$, where $$P_{i}$$ are probability measure such that $$\sum_{i}^{n} P_{i} = 1$$ and $$\beta > 0$$ is a constant. So basically it's a convex combination, which I could easily upper bound with Hölder's inequality that $$\sum_{i}^{n} P_{i} \cdot \exp(-\beta \cdot P_{i} \cdot n) \leq \max_{i} \exp(-\beta \cdot P_{i} \cdot n)$$

Is there any tighter upper bound for the sum like this ? Any idea or just reference would help !

• There's certainly no better upper bound in general unless you have more information about the $P_i$, since one might have $P_i=1$ for the $i$ that realizes the maximum. Dec 5, 2020 at 1:29
• I think in the case that $P_{i}=1$, the right hand side is 1, while the left hand side is $exp(-\beta \cdot n)$? Dec 5, 2020 at 2:01
• Yes indeed. Added the constraint. Dec 7, 2020 at 5:05
• But in the case I think right hand side is 1 right ? Dec 7, 2020 at 5:14
• I think $P_{argmax \exp(-\beta \cdot P_{i} \cdot n)} = 0$ ? Dec 7, 2020 at 5:21

Since there is no other information available on the $$P_i$$ and on $$\beta$$, here is a modest approach where no one-size-fits-all bounds can be expected, rather bounds which fit special bodies.

First observe that OP's bound is actually tight if all $$P_i = \frac{1}{n}$$. Hence it only makes sense to look for improved bounds for a rather broad distribution of probabilities. In this case, denote with $$P_{*}$$ the smallest $$P_i$$, we expect to have $$P_*$$ which is considerably lower than $$\frac{1}{n}$$.

Let us distinguish cases for $$\beta$$. Starting with very small $$\beta$$, we can use $$e^{-x} < 1-x + x^2/2$$ and obtain $$\sum_{i}^{n} P_{i} \cdot \exp(-\beta \cdot P_{i} \cdot n) \leq 1 -\beta \cdot n\sum_{i}^{n} P_{i}^2 + \frac{\beta^2 n^2}{2}\sum_{i}^{n} P_{i}^3$$ By Cauchy-Schwarz, $$n\sum_{i}^{n} P_{i}^2 \ge 1$$, and the obvious $$\sum_{i}^{n} P_{i}^3 \le 1$$, so we have $$\sum_{i}^{n} P_{i} \cdot \exp(-\beta \cdot P_{i} \cdot n) \leq 1 -\beta + \frac{\beta^2 n^2}{2}$$ Compare to OP's bound, and ignore terms of quadratic or higher order in $$\beta$$, we have indeed that $$1 -\beta \leq 1 -\beta P_{*} n \simeq \exp(-\beta \cdot P_{*} \cdot n) = \max_{i} \exp(-\beta \cdot P_{i} \cdot n)$$ since $$P_{*} < \frac{1}{n}$$ was where we started. So this bound improves on OP's bound.

For not so small $$\beta$$, consider the following:

Consider the function $$f(x) = x e^{- ax}$$. It has a maximum of $$\frac{e^{-1}}{a}$$ at $$x = \frac{1}{a}$$. Let $$a = \beta n$$, then if $$\beta > \frac{1}{n}$$, this is a good upper bound. It is valid in any case, however depending on the $$P_i$$ if may not be attained.

So you have $$\sum_{i}^{n} P_{i} \cdot \exp(-\beta \cdot P_{i} \cdot n) \leq \sum_{i}^{n} \frac{e^{-1}}{\beta n} = \frac{e^{-1}}{\beta}$$

We compare to OP's bound and ask how good this is. We require $$\frac{e^{-1}}{\beta} = \frac{e^{-1} P_{*} \cdot n}{\beta P_{*} \cdot n} \leq\!\! ? \; \exp(-\beta \cdot P_{*} \cdot n) = \max_{i} \exp(-\beta \cdot P_{i} \cdot n)$$ Understand $$q = \beta \cdot P_{*} \cdot n$$ as dependent on $$\beta$$ , then we require $$e^{-1} P_{*} \cdot n \leq\!\! ? \; q e^{-q} \le e^{-1}$$ So this is favourable (since $$P_{*} < \frac{1}{n}$$) if $$q$$ of Order 1, i.e. $$\beta \simeq \frac{1}{ P_{*} \cdot n} > 1$$.
If indeed $$P_{*} << \frac{1}{n}$$, then we have $$q << 1$$ and therefore approximately $$e^{-1} P_{*} \cdot n \leq\!\! ? \; q = \beta \cdot P_{*} \cdot n$$ i.e. $$\frac{1}{P_{*} \cdot n} >> \beta > e^{-1}$$ would then be the only requirement (where $$\frac{1}{P_{*} \cdot n}$$ is considered a very large number, so the left constraint is not severe).
From the discussion, it is also clear that the ranges for $$\beta$$ obtained right now match the $$\beta$$-case which we just discuss.

• Very inspiring ! Dec 7, 2020 at 23:57