[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*}[/step]

[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: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]