[proofplan]
We disprove the proposed universal comparison by a one-coordinate family. Take a Bernoulli [random variable](/page/Random%20Variable) with success probability $p$ and let $f$ be the indicator of the success state. The bounded-difference constant is fixed equal to $1$, so the McDiarmid proxy is always $1/4$, while the actual variance is $p(1-p)$ and tends to $0$ as $p \downarrow 0$. Choosing $p$ small enough contradicts any proposed finite universal constant.
[/proofplan]
[step:Reduce the universal comparison to a one-coordinate counterexample]
Assume, for contradiction, that there exists a constant $C < \infty$ such that for every admissible tuple with $f(X_1,\dots,X_n)$ square-integrable,
\begin{align*}
\frac{1}{4}\sum_{i=1}^n c_i^2 \le C\,\operatorname{Var}(f(X_1,\dots,X_n)).
\end{align*}
It is enough to contradict this assertion when $n=1$, because the asserted inequality is required to hold for all $n \in \mathbb{N}$.
If $C \le 0$, take $p=1/2$ in the construction below; the left-hand side is $1/4$, while the right-hand side is $C\operatorname{Var}(f_p(X_p))=C/4 \le 0$, a contradiction. Hence we may assume $C>0$.
[/step]
[step:Construct a Bernoulli example with fixed bounded-difference constant]
Fix $p \in (0,1)$. Set $\Omega_p:=\{0,1\}$, set $\mathcal{F}_p:=2^{\{0,1\}}$, and define the probability measure $\mathbb{P}_p:\mathcal{F}_p\to[0,1]$ by $\mathbb{P}_p(\{1\})=p$ and $\mathbb{P}_p(\{0\})=1-p$. Define the random variable $X_p:(\Omega_p,\mathcal{F}_p)\to(\{0,1\},2^{\{0,1\}})$ by $X_p(\omega)=\omega$. Then $X_p$ has distribution $\operatorname{Ber}(p)$, so $\mathbb{P}_p(X_p=1)=p$ and $\mathbb{P}_p(X_p=0)=1-p$. The one-member family $(X_p)$ is independent because every one-member family of random variables is independent.
Define the measurable function $f_p:\{0,1\}\to\mathbb{R}$ by $f_p(x)=\mathbb{1}_{\{1\}}(x)$.
Then $f_p(X_p)=X_p$, so $f_p(X_p)$ is square-integrable because it only takes the values $0$ and $1$.
We verify the bounded-differences condition with $c_1=1$. For all $x,x' \in \{0,1\}$,
\begin{align*}
|f_p(x)-f_p(x')| \le 1.
\end{align*}
Moreover this constant is sharp, since $|f_p(1)-f_p(0)|=1$. Therefore the McDiarmid bounded-difference proxy for this one-coordinate example is
\begin{align*}
\frac{1}{4}c_1^2=\frac{1}{4}.
\end{align*}
[guided]
We choose the smallest possible product space because a universal inequality must survive every special case. Set $\Omega_p:=\{0,1\}$, set $\mathcal{F}_p:=2^{\{0,1\}}$, and define the probability measure $\mathbb{P}_p:\mathcal{F}_p\to[0,1]$ by $\mathbb{P}_p(\{1\})=p$ and $\mathbb{P}_p(\{0\})=1-p$. Define the random variable $X_p:(\Omega_p,\mathcal{F}_p)\to(\{0,1\},2^{\{0,1\}})$ by $X_p(\omega)=\omega$. Then $X_p$ has Bernoulli distribution with parameter $p$, meaning $\mathbb{P}_p(X_p=1)=p$ and $\mathbb{P}_p(X_p=0)=1-p$. The tuple has only one random variable, and a one-member family is independent by the definition of independence for finite subfamilies.
The function is the indicator of the success state: define $f_p:\{0,1\}\to\mathbb{R}$ by $f_p(x)=\mathbb{1}_{\{1\}}(x)$.
This function is measurable because every subset of $\{0,1\}$ is measurable. Also $f_p(X_p)=X_p$, and since $X_p$ takes only the values $0$ and $1$, it is square-integrable.
Now check the bounded-differences condition. With one coordinate, two points differ only in coordinate $1$ precisely when they are two points of $\{0,1\}$. For any $x,x' \in \{0,1\}$,
\begin{align*}
|f_p(x)-f_p(x')| \le 1.
\end{align*}
The value $1$ is actually attained, because
\begin{align*}
|f_p(1)-f_p(0)|=|1-0|=1.
\end{align*}
Thus $c_1=1$ is a valid bounded-difference constant, even the sharp one. Consequently the McDiarmid proxy is independent of $p$:
\begin{align*}
\frac{1}{4}c_1^2=\frac{1}{4}.
\end{align*}
This fixed lower size is the point of the example: the bounded-difference proxy records the worst possible change of the function, not how likely that change is under the input distribution.
[/guided]
[/step]
[step:Compute the true variance and make it arbitrarily small]
Since $f_p(X_p)=X_p$ and $X_p$ is Bernoulli with parameter $p$, we have $\mathbb{E}[f_p(X_p)]=p$ and $\mathbb{E}[f_p(X_p)^2]=p$. Therefore
\begin{align*}
\operatorname{Var}(f_p(X_p)) = \mathbb{E}[f_p(X_p)^2]-\mathbb{E}[f_p(X_p)]^2 = p-p^2 = p(1-p).
\end{align*}
As $p \downarrow 0$, the quantity $p(1-p)$ tends to $0$.
[/step]
[step:Choose the Bernoulli parameter to contradict the proposed universal constant]
Since $C>0$, set $\varepsilon:=1/(4C)>0$. From the preceding limit $p(1-p)\to 0$ as $p\downarrow 0$, there exists $\delta\in(0,1)$ such that whenever $0<p<\delta$,
\begin{align*}
p(1-p) < \varepsilon = \frac{1}{4C}.
\end{align*}
Choose such a $p\in(0,\delta)$. For the corresponding admissible tuple, the proposed universal inequality would give
\begin{align*}
\frac{1}{4} \le C\,\operatorname{Var}(f_p(X_p)) = C p(1-p) < \frac{1}{4},
\end{align*}
which is impossible. Hence no finite universal constant $C$ can satisfy the stated comparison for all bounded-difference functions and all input distributions.
[/step]
