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.
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.