<s>[INST] Obtaining a tight bound for an Expectation w.r.t a uniform random variable Let $x\in [0,1]^{n+1}$, let $t > 0$, and let $u$ be a uniform random variable over {$1,\ldots, n, n+1$}, then I want to tightly bound
$$a_t(x) = E_u \left[ \mathrm{exp}\left\lbrace t\left(\frac{1}{n}\sum_{i\neq u}x_i - x_u \right) \right\rbrace \right]$$
with respect to a fixed value of $x$, or
$$\sup_{x\in[0,1]^{n+1}} a_t(x)$$
1st Attempt: (Hoeffding's Lemma)
This attempt bounds the supremum (and hence $a_t(x)$ for any x). If we let $Y = \frac{1}{n}\sum_{i\neq u}x_i - x_u$, then  $E_u[Y] = 0$ and $ -1\leq Y \leq 1$ since $x_i\in [0,1]$ for all $i$. Then I can use Hoeffding's Lemma to get that:
$$a_t \leq e^{t^2\frac{(1 - (-1))^2}{8}} = e^{\frac{t^2}{2}}$$
I was wondering if one could obtain a tighter bound. Possibly a bound that depends on $n$. I tried to check whether $a_t$ is a convex or concave in $x$, so that maybe i could find the maximum analytically, but unfortunately it is neither.
Update: (Numerics)
I tried to find the supremum numerically and compare it to $e^{\frac{t^2}{2}}$. Since $a_t(x)$ is neither convex or concave, I maximized it with different initial points $x_0$ and averaged the maximum. I did this for each $n\in \left\lbrace 2,4\ldots, 40\right\rbrace$. I find it surprising that the difference initially increases rapidly but then somewhat plateaus for larger values of $n$. I tried this for several values of $t$ and it consistently followed this pattern.

Thank you!
Edit 1: Fixed a typo.
Edit 2: Added some numerics.
 [/INST] I think we can get a fairly close bound by optimizing $a$ analytically.  Note that
\begin{align*}
a_t(x) &= \frac{1}{n+1}\sum_{j = 1}^{n+1} \exp\left(t \left(\frac 1n \sum_{i \ne j} x_i - x_j \right) \right) \\
&= \frac{1}{n+1}\sum_{j = 1}^{n+1} \exp\left(t \left(\frac 1n \sum_{i} x_i - x_j - \frac 1n x_j\right) \right) \\
&= \frac{1}{n+1} \exp\left( \frac tn \sum_i x_i \right) \sum_i \exp\left(-t \left(1+\frac 1n \right)x_i\right) \\
&=: \frac{1}{n+1} f(x).
\end{align*}
For ease of notation, let $z := t(1+\frac 1n)$.  Although $f$ may be neither concave nor convex, its maximum still occurs at a critical point.  We compute
\begin{align*}
\frac{\partial}{\partial x_j} f &= te^{\frac tn \sum_i x_i} \left(\frac 1n \sum_i e^{-z x_i} - \left(1+\frac 1n\right) e^{-z x_j}\right).
\end{align*}
Therefore, at any critical point, we must have for all $j$ either $x_j = 0$, $x_j = 1$, or $x_j = -\frac 1z \ln(Y)$, where
\begin{align}
Y &= \frac 1{n+1} \sum_i e^{-z x_i} &(=e^{-z x_j})
\end{align}
We now attempt to find the critical point which is the maximizer.  Let $J$ be the number of $x_j$ which are $0$, $K$ be the number of $x_j$ which are $1$, so $n+1-(J+K)$ are $-\frac 1z \ln(Y)$.  We compute, from the definition of $Y$,
\begin{align*}
Y &= \frac 1{n+1} \sum_i e^{-z x_i} \\
&= \frac 1{n+1} (J + K e^{-z} + (n+1-J-K)Y),
\end{align*}
and solving gives
\begin{equation}
Y = \frac{J+Ke^{-z}}{J+K}.
\end{equation}
Then we compute
\begin{align*}
f(x) &= \exp\left( \frac tn \sum_i x_i \right) \sum_i e^{-zx_i} \\
&= \exp\left( \frac tn \left(K - \frac{1}{z} \ln(Y)(n+1-(J+K))\right) \right)(n+1)Y \\
&= (n+1) \exp \left( \frac tn K + \frac{J+K}{n+1} \ln(Y)\right),
\end{align*}
so we attempt to solve
\begin{align*}
\max_{J,K \ge 0}&\quad \frac tn K + \frac{J+K}{n+1} \ln(Y)\\
\text{s.t. } & \quad J+K \le n+1.
\end{align*}
Since $J$ and $K$ are integers, this could be done with a brute force search by checking at most $n^2$ values, but we can obtain an analytic upper bound by maximizing over $J, K \in \mathbb{R}_+$.  Our Lagrangian is
\begin{align*}
\min_{\lambda \ge 0} \max_{J,K \ge 0} L(J,K,\lambda) &= \min_{\lambda \ge 0} \max_{J,K \ge 0}  \left(\frac tn K + \frac{J+K}{n+1} \ln(Y) - \lambda (J+K-(n+1))\right)
\end{align*}
We first compute
\begin{align*}
\frac{\partial}{\partial J} Y &= \frac{K(1-e^{-z})}{(J+K)^2} \\
\frac{\partial}{\partial K} Y &= -\frac{J(1-e^{-z})}{(J+K)^2},
\end{align*}
so our first order conditions are
\begin{align*}
0 = \frac{\partial}{\partial J} L &= \frac{K(1-e^{-z})}{(n+1)(J+Ke^{-z})} + \frac{\ln(Y)}{n+1} - \lambda \\
0 = \frac{\partial}{\partial K} L &= \frac tn - \frac{J(1-e^{-z})}{(n+1)(J+Ke^{-z})} + \frac{\ln(Y)}{n+1} - \lambda. 
\end{align*}
Setting them equal to one another yields
\begin{align*}
\frac tn - \frac{J(1-e^{-z})}{(n+1)(J+Ke^{-z})} &= \frac{K(1-e^{-z})}{(n+1)(J+Ke^{-z})}.
\end{align*}
Manipulating this expression shows
\begin{align*}
Y = \frac{J+Ke^{-z}}{J+K} &= \frac{1-e^{-z}}{z} \\
J &= \frac{1-e^{-z}-ze^{-z}}{z-1+e^{-z}}K \\
J+K &= \frac{z(1-e^{-z})}{z-1+e^{-z}}K.
\end{align*}
Substituting these expressions in, we see that we now need to find
\begin{align*}
\max_{K \ge 0} & \quad \frac tn K \left(1 + \frac{(1-e^{-z})}{z-1+e^{-z}}\ln \left(\frac{1-e^{-z}}{z}\right) \right) \\
\text{s.t.} & \quad K \le \frac{z-1+e^{-z}}{z(1-e^{-z})}(n+1).
\end{align*}
It is possible to show $1 + \frac{(1-e^{-z})}{z-1+e^{-z}}\ln \left(\frac{1-e^{-z}}{z}\right) > 0$ for all $z > 0$, so this expression is maximized by $K = \frac{z-1+e^{-z}}{z(1-e^{-z})}(n+1)$.  Hence our maximizers are
\begin{align*}
K^* &= \frac{z-1+e^{-z}}{z(1-e^{-z})}(n+1) \\
J^* &= n+1-K \\
Y^* &= \frac{1-e^{-z}}{z}
\end{align*}
Plugging into our expression, we have
\begin{align*}
f(x) &\le (n+1) \exp \left( \frac tn K^* + \frac{J^*+K^*}{n+1} \ln(Y^*)\right) \\
&= (n+1) Y^*e^{\frac tn K^*} \\
&= (n+1) \left(\frac{1-e^{-z}}{z} \right)\exp \left( \frac{z-1+e^{-z}}{1-e^{-z}} \right),
\end{align*}
and therefore
\begin{align*}
a_t(x) &\le \left(\frac{1-e^{-z}}{z} \right)\exp \left( \frac{z-1+e^{-z}}{1-e^{-z}} \right),
\end{align*}
where $z = t(1+\frac 1n)$.  I haven't checked precisely how this compares to the $e^{\frac{t^2}2}$ bound, but it should beat it quite handily for large $t$.  As $n$ increases, $z$ initially decreases (relatively) rapidly but plateaus around $t$.  Since the bound is an increasing function of $z$, this agrees with the behavior you saw numerically.
</s>