2
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

Not full answer.

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

Now it's sufficient to check if the proof (see, e.g. https://en.wikipedia.org/wiki/Hoeffding%27s_inequality#Proof ) allows us to have equality in (**).

I didn't check it but it looks like there are two possibilities: either (**) can't be tight or it can be tight in some degenerate case. If the second variant (about degenerate case) is true then it gives a counterexample for original question.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .