Let $f(x) = \log \sum_i^n \exp x_i$, where $x \in \mathbb R^n$, I read that the following inequlities hold:
$$\max\{x_1, x_2, \ldots, x_n\} \le f(x) \le \max\{x_1, x_2, \ldots, x_n\} + \log n$$
, but I have no idea how to prove this conclusion.
I can see that the first inequality is tight when there's only one non-zero element in $x$, and the second inequality is tight when all of the elements of $x$ are equal, but I don't know how to prove that these two cases form the lower bound and upper bound or the function.
Best Answer
For any positive real numbers $y_1,\dots,y_n$, we have $$ \max\{y_1,\dots,y_n\}\leq y_1+\dots+y_n\leq n\max\{y_1,\dots,y_n\}$$ Taking $y_i=e^{x_i}$ and using the fact that the exponential function is increasing, we get $$ \exp(\max\{x_1,\dots,x_n\})\leq \sum_{i=1}^ne^{x_i}\leq n\exp(\max\{x_1,\dots,x_n\})$$ and then taking logs yields $$ \max\{x_1,\dots,x_n\}\leq \log\sum_{i=1}^ne^{x_i}\leq \max\{x_1,\dots,x_n\}+\log n$$