2
$\begingroup$

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 !

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 5, 2020 at 1:29
  • $\begingroup$ 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)$? $\endgroup$
    – exteral
    Dec 5, 2020 at 2:01
  • 1
    $\begingroup$ Yes indeed. Added the constraint. $\endgroup$
    – exteral
    Dec 7, 2020 at 5:05
  • $\begingroup$ But in the case I think right hand side is 1 right ? $\endgroup$
    – exteral
    Dec 7, 2020 at 5:14
  • 1
    $\begingroup$ I think $P_{argmax \exp(-\beta \cdot P_{i} \cdot n)} = 0$ ? $\endgroup$
    – exteral
    Dec 7, 2020 at 5:21

1 Answer 1

2
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very inspiring ! $\endgroup$
    – exteral
    Dec 7, 2020 at 23:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .