Let $X_1,X_2,Y$ be independent, with $X_1,X_2$ distributed as $X$. Apply part (b) to $X_1,-Y,X_2$:Adding an independent random variable cannot decrease information entropy, soIn terms of Entropic Ruzsa distance, this is $d_R(X,-X)\le 2d_R(X,Y)$. The Entropic Ruzsa triangle inequality and invariance under simultaneous negation now givewhich is the Entropic Ruzsa sum-difference inequality.

Because the Entropic Ruzsa distance depends only on marginal distributions, take $X,Y,Z$ independent with the required marginals. Since $X-Z=(X-Y)+(Y-Z)$ is a function of $(X-Y,Y-Z)$, the data processing inequality for mutual information yieldsThe map $(X,X-Y,Y-Z)\mapsto (X,Y,Z)$ is a bijection. Using independence and the chain rule for information entropy, the left side iswhereas the right side is $H(X-Z)-H(Z)$. Hencewhere the final step is subadditivity of information entropy. Substituting this inequality into the definition of $d_R$ gives the Entropic Ruzsa triangle inequality

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

Suppose $X\to Y\to Z$ is a Markov chain, so $I(X;Z\mid Y)=0$. The chain rule for mutual information givesand alsobecause conditional mutual information is nonnegative. Therefore $I(X;Z)\le I(X;Y)$. Similarly,while $I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)\ge I(X;Z)$, so $I(X;Z)\le I(Y;Z)$. These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.

Now both the number of groups and their size equal $\sqrt{n}$. A group mean is approximately $N(\mu ,{\sigma }^2/\sqrt{n})$, whose density at $\mu$ is approximately $n^{1/4}/(\sigma \sqrt{2\pi })$. The asymptotic distribution of a sample median based on $\sqrt{n}$ such values therefore has varianceThis suggests the conjectureprovided a sufficiently uniform central and local limit approximation controls the triangular array.

Write $k=2r+1$ and $m=n/k$. The central limit theorem gives jointlywhere the $Z_j$ are independent standard normal variables. HenceIts limiting cumulative distribution function is

The analogous statement is false under only a finite-variance assumption. Let $X=0$ with probability $3/4$ and $X=4$ with probability $1/4$. Then $\mu =1$, while the unique population median is zero. With fixed $k$ and group size $n/k\to \infty$, every group median converges in probability to zero, so their mean also converges to zero. Its error from $\mu$ tends to one rather than having order $n^{-1/2}$. Medians inside groups estimate the population median, while means inside groups preserve the population mean.

Randomly partition the observations into $k$ groups of size $m=n/k$, form the group means ${\overline{X}}_1,\dots ,{\overline{X}}_k$, and define the median-of-means estimator byChebyshev givesA binomial tail bound shows that at least half the groups are good with probability at least $1-e^{-k/8}\ge 1-\delta$. Thereforewith probability at least $1-\delta$.

Choose $v\in {\mathbb{R}}^p$ outside the finitely many hyperplanes $\{v:x_i^{\top }v=0\}$. Then $x_i^{\top }v\ne 0$ for every $i$. For ${\theta }_t=tv$, every residual $y_i-t{x}_i^{\top }v$ eventually has absolute value greater than $L$. Every indicator in the estimating equation is then zero, so the equation is satisfied for every sufficiently large $t$.

Thus arbitrarily large solutions already exist without contamination. Under the definition in the question, the skipped-mean regression estimator has breakdown point zero. This is a standard pathology of an exactly redescending score when every root is admitted as an estimator.

Away from the two nondifferentiable cutoffs, the skipped-mean score is ${\psi }_L(u)=2u{1}_{\{|u|\le L\}}$. The estimating equation is therefore

For fixed residual $r=y_i-x_i^{\top }\theta$, choosing ${\gamma }_i=0$ costs $r^2$, while choosing ${\gamma }_i=r$ costs $\ell$. No other nonzero choice improves on ${\gamma }_i=r$. Thuswith $L=\sqrt{\ell }$. Summing over observations proves the equivalence.

For residual $r=y_i-x_i^{\top }\theta$, minimizeover $\gamma$. Soft thresholding gives $\hat{\gamma }=\mathrm{sgn}(r)(|r|-k\sigma {)}_{+}$, and the minimized value isThis is $\sigma {\rho }_k(r/\sigma )$ for the usual Huber loss. Multiplication by the positive constant $\sigma$ does not change the minimizing $\theta$, proving equivalence.

If $v_T=\mathbb{E}[operatornameIF(X;T,N({\theta }_0,1){)}^2]$, asymptotic normality gives an asymptotically level-$\alpha$ test that rejects whenFor the median, $v_T=\pi /2$. For Huber,For the trimmed mean, with $q={\Phi }^{-1}(1-\gamma )$,These tests have bounded influence functions, so a small contamination proportion has bounded first-order effect on their statistics, asymptotic levels, and powers. Their finite-contamination protection is quantified by the breakdown points in part (c).

The sample median attains the equivariant upper bound:For the Huber estimator, fewer than half the observations cannot overpower the bounded scores of the uncontaminated majority. Evaluating the estimating equation below $x_{(1)}-k$ or above $x_{(n)}+k$ makes every uncontaminated score have the same sign. A contaminating majority can balance these scores arbitrarily far away, soA $\gamma$-trimmed mean remains bounded while at most $\lfloor \gamma n\rfloor$ arbitrary observations are removed by each tail trim; one more arbitrarily large replacement survives. Hence

Let replacement tolerance mean the greatest number of observations that can be replaced while the estimator remains bounded. For $n=2m$, a sample with $m$ zeros and $m$ copies of $a$ is within $m$ replacements of both the all-zero sample and its translate by $a$. If an equivariant estimator tolerated $m$ replacements, it would remain within bounded distance of both $T(0^n)$ and $T(0^n)+a$, which is impossible as $a\to \infty$. Thus at most $m-1$ replacements are tolerable.

For $n=2m+1$, a sample with $m$ zeros and $m+1$ copies of $a$ is obtained from the all-zero sample by $m+1$ replacements and from the all-$a$ sample by $m$ replacements. Translation equivariance again forces breakdown by $m+1$ replacements. In both cases the finite-sample replacement breakdown point is at most

The gross-error sensitivity is ${\gamma }^{\ast }(T,F)={\sup }_x|\mathrm{IF}(x;T,F)|$. At $N(\theta ,1)$, the influence function of the sample median has magnitude $1/(2\phi (0))=\sqrt{\pi /2}$, soFor the Huber location estimator, ${\psi }_k(u)=\max (-k,\min (u,k))$ and $\mathbb{E}{\psi }_k^{\prime }(Z)=\mathbb{P}(|Z|\le k)=2\Phi (k)-1$, givingFor the symmetric normal law, the trimmed population mean is $\theta$. Writing $q_{\gamma }={\Phi }^{-1}(1-\gamma )$ in the supplied influence function gives