An upper bound for an average exponentiated weighted sum of a vector from $\{-1,1\}^n$

Question

Suppose $\mathcal{S}=\{\mathbf{x}:\mathbf{x}\in\{-1,1\}^n\}$, that is, $\mathcal{S}$ contains all $2^n$ vectors of length $n$ containing -1 and 1.

I am interested in the following average:

$$A_{f(n)}(n)=\frac{1}{2^n}\sum_{\mathbf{x}\in\mathcal{S}}\exp\left[f(n)\sum_{i=1}^nx_i\right]$$

where $f(n)$ is a well-behaved real function (possibly of $n$ but not of $\mathbf{x}$) and $x_i$ denotes the $i$-th element of $\mathbf{x}$.

I am looking for a tight upper bound for $A_{f(n)}(n)$ in terms of $n$ and $f(n)$. The trivial upper bound $\exp[nf(n)]$ doesn't seem tight from my numerical exploration. Is a better bound available?

Answer 1

We have, $$\sum_{\mathbf{x}\in\mathcal{S}}\exp\left[f(n)\sum_{i=1}^nx_i\right] = \sum_{\mathbf{x}\in\mathcal{S}} \prod_{(x_i)_{i=1}^{n} = \mathbf{x}} e^{f(n)x_i}=\left(e^{f(n)}+e^{-f(n)}\right)^n$$

The identity is a consequence of: $\displaystyle \left(t^{1}+t^{-1}\right)^{n} = \sum\limits_{\substack{1 \le i \le n\\ \epsilon_i = \pm1}} t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_n}$ follows from the product rule.

Each $(t+t^{-1})$ of the $n$-product contributes a $t^{1}$ or a $t^{-1}$ to form a product of $n$ terms like $t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_n}$, and all such terms gives the final summation expression.

Alternatively we could also argue by induction on $n$. For $n = 1$ it's obvious, lets say its true for a $n = m$,

then, $$\begin{align} \displaystyle \left(t^{1}+t^{-1}\right)^{m+1} &= (t+t^{-1})\left(\sum\limits_{\substack{1 \le i \le m\\ \epsilon_i = \pm1}} t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_m}\right) \\&= \sum\limits_{\substack{1 \le i \le m\\ \epsilon_i = \pm1}} t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_m}.t + \sum\limits_{\substack{1 \le i \le m\\ \epsilon_i = \pm1}} t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_m}.t^{-1} \\ &= \sum\limits_{\substack{1 \le i \le m+1\\ \epsilon_i = \pm1}} t^{\epsilon_1}.t^{\epsilon_2}\cdots .t^{\epsilon_m}.t^{\epsilon_{m+1}}\end{align}$$

proving the identity for $n=m+1$, and hence establishing the induction hypothesis.

Now we can give it a suitable upper-bound depending on the function $f(n)$.

As you point out $\displaystyle A_{f(n)}(n) = \left(\frac{e^{f(n)}+e^{-f(n)}}{2}\right)^n = \cosh^n f(n)$ indeed.

Answer 2

We have that there are $n\choose r$ vectors in $S$ with exactly $r$ negative components, and that the sum of the components of any one of these vectors is $n-2r$, so your sum is $$A_{f(n)}(n)=\frac{1}{2^n}\sum_{\mathbf{x}\in\mathcal{S}}\exp\left[f(n)\sum_{i=1}^nx_i\right] = \frac{1}{2^n}\sum_{r=0}^n {n \choose r} \exp(f(n)(n-2r))$$ $$\le \frac{1}{2^n}\sum_{r=0}^n \frac{n^r}{r!} e^{f(n)(n-2r)} < \frac{e^{nf(n)}}{2^n}\sum_{r=0}^\infty \frac{n^r}{r!} e^{-2f(n)r} $$

We can rewrite this last expression as $$A_{f(n)}(n) < \frac{e^{nf(n)}}{2^n}e^{ne^{-2f(n)}} = e^{nf(n)-n\ln2 + ne^{-2f(n)}}$$

In fact, if $\lim_{n\to\infty} ne^{-2f(n)} = 0$, then we can show that

$$\lim_{n\to\infty} \frac{A_{f(n)}(n)}{e^{nf(n)-n\ln2 + ne^{-2f(n)}}} = 1$$

using Sciona's expression for $A_{f(n)}(n)$.