# Is McDiarmid's Inequality ever tight?

I have seen over and over McDiarmid's inequality, which I will now re-state for ease for reference (in its most common version):

Let $$X_1,\ldots,X_n$$ be independent random variables and let $$f:\mathcal{X}^n\to\mathbb{R}$$ be a function such that for every $$k\in\{1,\ldots,n\}$$ $$x^n\in\mathcal{X}^n, \hat{x}\in \mathcal{X}$$ one has that $$|f(x_1,\ldots,x_k,\ldots,x_n)-f(x_1,\ldots,\hat{x},\ldots,x_n)| \leq c_k$$ for some $$c_k\geq 0$$. Then, given $$t>0$$ $$\mathbb{P}(|f(X_1,\ldots,X_n)-\mathbb{E}[f]|\geq t)\leq 2\exp\left(-\frac{t^2}{2\sum_i c_k^2}\right).$$

My question now is: is this inequality ever tight? Can one find a sequence of $$X^n$$ and an $$f$$ satisfying the assumption where the probability can be lower-bounded or computed with equality? Any reference to this will be greatly appreciated!

• It's better not to use letter $\eta$ because is looks like r.v. Jan 13, 2023 at 11:34

McDiarmid's inequality is a corollary of Azuma–Hoeffding inequality for martingales. Azuma–Hoeffding inequality for martingales is a corollary of Hoeffding's inequality (see https://en.wikipedia.org/wiki/Hoeffding%27s_inequality) for module of r.v.: \begin{align} \operatorname{P} \left(\left |S_n - \mathrm{E}\left [S_n \right] \right | \geq t \right) &\leq 2\exp \left(-\frac{2t^2}{\sum_{i=1}^n(b_i - a_i)^2} \right) \end{align} In its turn this inequality is a corollary of the next Hoeffding's inequality: \begin{align} \operatorname{P} \left(S_n - \mathrm{E}\left [S_n \right] \geq t \right) &\leq \exp \left(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right) \quad (*) \end{align}
It looks like if (*) is ever tight then it should be tight for $$n=1$$ and some r.v. $$\xi$$. In other words (put $$n=1$$) \begin{align} \operatorname{P} \left(\xi - \mathrm{E}\xi \geq t \right) &\leq \exp \left(-\frac{2t^2}{(b - a)^2} \right) \quad (**) \end{align} should be tight for some $$\xi$$ such that $$\xi \in [a,b]$$.