Keywords: Coordination Games, Information Games, Amenability, Social Networks.

1 Introduction↩︎

This paper continues the study of pure coordination games on social networks, initiated in the recent work of Hutchcroft, Rospuskova, and Tamuz [1]. In these games, players must choose between two alternatives toward which they are initially unbiased. The only goal is that, on average, the players’ choices will match. Examples include the choice of a weekly day of rest, the side of the street on which to drive, and the paper size used for printing: a priori, the choice itself plays no significant role, but consistency among the players is crucial. The players are considered as part of a social network³, where they need to coordinate with their neighbors. We consider the case where coordination is local, that is, bounded by distance, and the network itself is large. In such a case, total coordination is unachievable, and therefore some inefficiency in the players’ choices must occur.

In [1] it was showed that a geometric property of the network, known as amenability, or hyperfiniteness in graph-theoretic terminology, is related to low inefficiency. Amenability of a network means that the network can be divided into local neighborhoods at only a small cost in inconsistencies between different neighborhoods. Indeed, given such a decomposition, total coordination can be achieved inside each neighborhood, while the only contribution to inefficiency comes from inconsistencies between adjacent neighborhoods. Quite surprisingly, the converse also holds: high coordination implies that the network is amenable. However, the cost of the resulting decomposition is asymptotically larger. It was conjectured by the authors that this gap can be improved, and this is precisely what we prove in the present paper.

Our approach follows the probabilistic formulation used in their proof. Each player is assigned a local random variable, determined only by the information available in a bounded neighborhood, and the quality of coordination is measured by the expected disagreement along edges. A key point in our argument is that, for the improved estimate, it is necessary to work specifically with \(\{-1,1\}\)-valued, unbiased random variables. In this binary setting, disagreement has an information-theoretic meaning: if two neighboring outputs disagree with probability \(p\), then the conditional uncertainty between them is controlled by the binary entropy \(h(p)\). This allows us to replace the square-root type estimate in the original argument by an entropy-type estimate. This is related in spirit to the approach of [2], where entropy is considered in place of variance, although the methods themselves are different.

We build on the technical framework presented in [1], which uses the Shapley influence distribution (see [3], [4]). This distribution measures how much a single variable affects the outcome of a function depending on several independent inputs. We modify this part of the argument by considering the Shapley values of a mutual-information game associated with the players’ local outputs. This yields an improved bound on the total variation distance between the resulting Shapley distributions, in terms of how often the two functions disagree. This, in turn, shows that the decomposition of the network can be obtained at a smaller cost in disagreements between neighboring players.

2 Preliminaries↩︎

2.1 The Model↩︎

Let \(G=(N,E)\) be a finite undirected graph. The elements of \(N\) represent the players, and an edge \(\{i,j\}\in E\) means that \(i\) and \(j\) are neighbors. We write \[B_r(i):=\{j\in N:\operatorname{dist}_G(i,j)\le r\}\] for the radius-\(r\) ball around \(i\). We think of \(r\) as the radius to which information can travel before actions are chosen. Each player chooses an action in \(\{+1,-1\}\). The underlying game is a pure coordination game: each player wants to match the actions of her neighbors (the payoff of player \(i\) at an action profile \(a=(a_j)_{j\in N}\in \{+1,-1\}^N\) is \(u_i(a):= -\sum_{j\in N_i}|a_i-a_j|.\)

The model presented in [1] allows players to communicate locally before choosing actions. Communication is restricted to distance \(r\), and there are two kinds of messages: each player \(i \in N\) may send a locally public and private message observed by all players in \(B_r(i)\).

For our purposes, incentives and the precise message structure will not play a role. We use the probabilistic abstraction appearing in [[1], Theorem 5]. Namely,

Let \((Z_i)_{i\in N}\) be independent random variables associated to the vertices, and let \((X_i)_{i\in N}\) be a family of random variables, such that \(X_i \text{ is measurable with respect to } \sigma(Z_j:j\in B_r(i))\), and are unbiased, meaning \(\mathbb{E}[X_i]=0, \;\mathbb{E}[X_i^2]=1.\) Thus, \(X_i\) is determined by information inside the radius-\(r\) ball of \(i\). We will be interested in the average expected inefficiency, or average disagreement, of a given family \(X = (X_i)_{i \in N}\) which is given by \[\frac{1}{|E|} \sum_{\{i,j\}\in E} \frac{1}{2}\mathbb{E} [X_i- X_j]^2.\]

2.2 Amenable Graphs↩︎

The geometric property governing local coordination is amenability, also called hyperfiniteness in parts of the graph theory literature.

Equivalently, \(G\) is \((\varepsilon,r)\)-amenable if one can delete at most an \(\varepsilon\)-fraction of the edges so that every connected component of the remaining graph has radius at most \(r\).

On such graph there is a natural coordination strategy—all the players at some component may coordinate on the same signal from some chosen leader, which then imply that disagreements occur only along the boundary edges between different parts. In particular, this strategy⁴ guarantee inefficiency of at most \(\varepsilon\).

2.3 Bounds of Amenability Parameter↩︎

One of the main results in [1] is that low inefficiency in local coordination is governed by the amenability of the underlying graph. They prove that on amenable graphs one can construct efficient leader equilibria, while on non-amenable graphs low-inefficiency coordination is impossible. We shall use the following theorem as the benchmark result.

For \(\{-1,+1\}\)-valued variables, this hypothesis is equivalent, up to a constant, to small average disagreement. Indeed, \(\mathbb{E}[(X_i-X_j)^2]=4\Pr[X_i\neq X_j].\) Thus Theorem 1 gives a square-root converse: sufficiently good local coordination forces an amenable decomposition, but with a \(\sqrt{\varepsilon}\)-loss.

The authors then pose the conjecture that this bound can be improved, perhaps even to \((C\varepsilon,r)\)-amenability. We show that this bound can be improved for \(\{+1,-1\}\)-valued variables, yet without this restriction it cannot. Indeed, we first show that the square root bound in Theorem 1 is tight, in the sense that it cannot be improved asymptotically.

Proof. Consider the cycle graph \(C_n\), with \(n\) much larger than \(r\). Let \(Z_1,\ldots,Z_n\) be independent random variables taking values \(\pm1\) with probability \(1/2\).

For each \(i\in C_n\), define \[Y_i:=\sum_{j=-r}^r (r+1-|j|)Z_{i+j},\] where indices are taken modulo \(n\), and put \(X_i:=Y_i/\|Y_i\|_2\). Then \(X_i\) is measurable with respect to \(B_r(i)\), and \(\mathbb{E} X_i=0\), \(\mathbb{E} X_i^2=1\).

We have \[\|Y_i\|_2^2=\sum_{j=-r}^r (r+1-|j|)^2=(r+1)^2+2\sum_{k=1}^r k^2.\] In particular, \(\|Y_i\|_2^2\ge r(r+1)(2r+1)/3\). Therefore

\[\mathbb{E}((X_i-X_{i+1})^2) = \frac{1}{||Y_i||_2^2} \cdot \mathbb{E}(\sum_{j = -r}^{r+1} Z_{j+i}^2 +2\sum_{j,j'} \pm Z_{j+i}Z_{j'+i}) =\] \[=\frac{1}{||Y_i||_2^2} \cdot \mathbb{E}(\sum_{j = -r}^{r+1} Z_{j+i}^2) =\frac{2r+2}{\|Y_i\|_2^2} \le \frac{6}{r(2r+1)} \le \frac{6}{r^2}.\] Thus the inefficiency satisfies \[\epsilon_r:=\frac{1}{|E(C_n)|}\sum_{\{i,j\}\in E(C_n)}\frac{1}{2}\mathbb{E}[(X_i-X_j)^2] \le \frac{3}{r^2}.\]

On the other hand, every subset of \(C_n\) of radius at most \(r\) has size at most \(2r+1\). Hence any partition of \(C_n\) into radius-\(r\) parts has at least \(n/(2r+1)\) parts, and therefore cuts at least order \(n/r\) edges. Since \(|E(C_n)|=n\), the best possible amenability parameter is at least \(c/r\) for some universal \(c>0\), provided \(n\) is sufficiently large compared with \(r\). This proves that the square-root dependence is sharp up to constants.  

Lemma 1 shows that if one wishes to improve the amenability parameter, then \(\{-1,1\}\)-valued variables must be considered.

The proof of Theorem 5 in [1] proceeds in two main steps. First, to each local output \(X_i\) they associate a Shapley influence distribution \(\mu_i\), a probability measure supported on \(B_r(i)\). They prove a contraction estimate saying that if two neighboring outputs are close in \(L^2\), then the corresponding influence distributions are close in total variation. Second, they use a grand coupling theorem to couple the measures \((\mu_i)_{i\in N}\), producing random leaders \(L_i\in B_r(i)\). Vertices with the same leader form communities, and the probability that an edge crosses between communities is controlled by the total variation distance between the corresponding influence distributions.

In the present argument we keep the same general architecture, but replace the variance-based game by an information-theoretic one. For Bernoulli outputs we associate to \(X_i\) the Transferable Utility game \[u_i(S):=I(X_i;Z_S),\] and use the Shapley values of this mutual-information game. This approach leads us to the main result:

We dedicate the remaining part of this paper to the proof of Theorem 2.

3 Proof of the Main Result↩︎

We first recall the relevant information-theoretic notation (for a detailed exposition of the topic, we refer the reader to [5],[6]). Let \(X,Y,Z\) be random variables, the mutual information of \(X,Y\) is defined as \[I(X;Y):=H(X)-H(X\mid Y).\] The conditional mutual information of \(X,Y\) conditioned on \(Z\) is defined as \[I(X;Y\mid Z):=H(X\mid Z)-H(X\mid Y,Z).\] We also recall the chain rule \[I((X_1,X_2);Y) = I(X_1;Y)+I(X_2;Y\mid X_1),\] and the non-negativity property \[I(X;Y\mid Z)\ge 0.\]

We define a TU game,

Given \(X\sim\operatorname{Bernoulli}(1/2)\), such that \(X\) is measurable with respect to \(Z_N\), we denote by \(Sh_i(u_X)\) the Shapley value of player \(i \in N\) [7]. We notice that \(Sh(u_X) = (Sh_i(u_X))_{i\in N}\) is a probability measure on \(N\). Indeed, \[\sum_{i\in N}Sh_i(u_X)=u_X(N)-u_X(\varnothing)=I(X;Z_N)-I(X;Z_\varnothing)=H(X)-0=1.\] where the last equality comes from the fact that \(X\sim\operatorname{Bernoulli}(1/2)\).

Also, we notice that If \(S\subseteq T\), then by the chain rule, \[I(X;Z_T)-I(X;Z_S) = I(X;Z_{T\setminus S}\mid Z_S)\ge0.\] Therefore each Shapley value is nonnegative. We turn to prove an auxiliary Lemma.

Proof. Define the joint information game \[U(S):=I((X_1,X_2);Z_S).\] By the chain rule, \[U(S) = I(X_1;Z_S)+I(X_2;Z_S\mid X_1).\] Hence \(U(S)-u_1(S) = I(X_2;Z_S\mid X_1).\) and Similarly, \(U(S)-u_2(S) = I(X_1;Z_S\mid X_2).\)

By linearity of the Shapley value, \[Sh(u_1)-Sh(u_2) = Sh(U-u_2)-Sh(U-u_1).\] We claim that \(U-u_1\) and \(U-u_2\) are monotone games. Indeed, if \(S\subseteq T\), then \[(U-u_1)(T)-(U-u_1)(S) = I(X_1;Z_T\mid X_2)-I(X_1;Z_S\mid X_2) = I(X_1;Z_{T\setminus S}\mid X_2,Z_S)\geq 0,\] where again the middle equality holds by the chain rule. For \(U-u_2\) its the same.

Since \(v_1\) and \(v_2\) are monotone, their Shapley values are nonnegative⁷. \[\begin{align} \|Sh(u_1)-Sh(u_2)\|_{\operatorname{TV}} &= \|Sh(U-u_1)-Sh(U-u_2)\|_{\operatorname{TV}}\\ &= \frac{1}{2} \sum_{i\in N} \left| Sh_i(U-u_1)-Sh_i(U-u_2) \right| \\ &\le \frac{1}{2} \sum_{i\in N} \left( Sh_i(U-u_1)+Sh_i(U-u_2) \right). \end{align}\]

However, \[\sum_{i\in N}Sh_i(U-u_1)=(U-u_1)(N)-(U-u_1)_1(\varnothing).\] Now \((U-u_1)_1(\varnothing)=I(X_1;Z_\varnothing\mid X_2)=0,\) and \((U-u_1)(N)=I(X_1;Z_N\mid X_2)\). Since \(X_1\) is measurable with respect to \(Z_N\), \[H(X_1\mid Z_N,X_2)=0.\] Thus \[I(X_1;Z_N\mid X_2) = H(X_1\mid X_2)-H(X_1\mid Z_N,X_2) = H(X_1\mid X_2).\] Therefore all together \[\|Sh(u_1)-Sh(u_2)\|_{\operatorname{TV}} \le \frac{1}{2} \left( H(X_1\mid X_2)+H(X_2\mid X_1) \right).\]

It remains to compute the two conditional entropies. Recall \(X_1\) and \(X_2\) are both unbiased Bernoulli variables and \(p=\Pr[X_1\neq X_2]\), thus, conditional on \(X_2\), the variable \(X_1\) differs from \(X_2\) with probability \(p\). Hence \[H(X_1\mid X_2)=h(p), \quad \text{and similarly} \quad H(X_2\mid X_1)=h(p).\] Therefore \[\|Sh(u_1)-Sh(u_2)\|_{\operatorname{TV}} \le h(p).\] as wanted  

Using the Lemma above we are ready to prove Theorem 2—this part follows the same route as in [1].

Proof of Theorem 2. For each \(i\in N\), define the information game \[u_i(S):=I(X_i;Z_S), \qquad S\subseteq N.\] Let \(\mu_i:=Sh(u_i)\) be the probability measure on \(N\) defined above.

We first observe that \[\operatorname{supp}(\mu_i)\subseteq B_r(i).\] Indeed, if \(a\notin B_r(i)\), then \(X_i\) is measurable with respect to \(Z_{B_r(i)}\), and \(Z_a\) is independent of the variables determining \(X_i\). Therefore, for every \(S\subseteq N\setminus\{a\}\), we see that \(I(X_i;Z_a\mid Z_S)=0.\) Equivalently, \(u_i(S\cup\{a\})-u_i(S)=0,\) thus every marginal contribution of \(a\) to the game \(u_i\) is zero, and hence \(\mu_i(a)=0.\)

For every edge \(\{i,j\}\in E\), set \[p_{ij}:=\Pr[X_i\neq X_j].\] Applying lemma 2 to \(X_i\) and \(X_j\), we get \[d_{\operatorname{TV}}(\mu_i,\mu_j)\le h(p_{ij}).\]

As in [1], we use the following coupling theorem (see [8],[9]). what is shown is that one can simultaneously couple many random variables so that every pair is coupled within a constant factor of its optimal total-variation coupling.

By Theorem 4, there exist random variables \((L_i)_{i\in N}\) such that \(L_i\sim\mu_i\) for every \(i\in N\), and for every edge \(\{i,j\}\in E\), \[\Pr[L_i\neq L_j]\le 2h(p_{ij}).\]

Averaging over edges gives \[\frac{1}{|E|} \sum_{\{i,j\}\in E} \Pr[L_i\neq L_j] \le \frac{2}{|E|} \sum_{\{i,j\}\in E}h(p_{ij}).\] The binary entropy function \(h\) is concave on \([0,1]\). Hence Jensen’s inequality gives \[\frac{1}{|E|} \sum_{\{i,j\}\in E}h(p_{ij}) \le h\left( \frac{1}{|E|} \sum_{\{i,j\}\in E}p_{ij} \right).\] Since \[\frac{1}{|E|} \sum_{\{i,j\}\in E}p_{ij}\le\varepsilon\] and \(h\) is increasing on \([0,1/2]\), we obtain \[\frac{1}{|E|} \sum_{\{i,j\}\in E} \Pr[L_i\neq L_j] \le 2h(\varepsilon).\]

Using the same argument as in [1] we conclude that \(G\) is \((2h(\varepsilon),r)\)-amenable.  

Appendix↩︎

Bound on the Total variation Distance of Shapley measures in Variance Game↩︎

The proof of Theorem 2, presented in the previous section, relies on redefining the underlying TU game. This allows us to bypass the main obstacle arising from the variance game \[v_X(S)=\left|\mathbb{E}[X\mid Z_S]\right|_2^2.\] we show here that, under the additional assumption that the independent random variables \((Z_i)\) are Bernoulli distributed, the same improved bound can also be obtained while working with this original variance game (yet with a worse constant).

The idea is the same: we want to bound the total variation distance between the Shapley-value measures associated with the games \(v_X\). Once such a bound is established, the same coupling argument used in the previous section gives the desired improvement in the amenability parameter. The following result provides precisely this estimate. It bounds the total variation distance between the Shapley-value measures of the original variance games in the special case where the output variable \(X\) is viewed as a Boolean function of independent Bernoulli inputs (For a detailed exposition of this topic, we refer the reader to [10].).

Proof.

We recall the construction of the Shapely-value measure presented in [1]. Let \(f:\{-1,1\}^n\to\{-1,1\}\) be a Boolean function with \(\mathbb{E}[f]=0\). For each subset \(S\subseteq[n]\), define the cooperative game \[v_f(S) := \operatorname{Var}\!\big(\mathbb{E}[f\mid X_S]\big),\] where \(X=(X_1,\dots,X_n)\) is uniformly distributed on \(\{-1,1\}^n\) and \(X_S\) denotes the coordinates indexed by \(S\). Denote the shapley-value probability measure by \(\mu_f(i)\).

Using the Fourier expansion \(f=\sum_{T\subseteq[n]}\widehat f(T)\chi_T\), where \(\chi_T := \prod _{i \in T} X_i\), and \(\widehat f(T)\) is the associated Fourier coefficient, the authors show that the Shapley-value measure is given explicitly by \[\mu_f(i) = \sum_{\substack{i \in T}} \frac{\widehat f(T)^2}{|T|}.\]

Recall that the total variation distance is given by \[d_{\operatorname{TV}}(\mu_f,\mu_g) = \frac{1}{2} \sum_{i=1}^n \bigl|\mu_f(i)-\mu_g(i)\bigr| = \frac{1}{2} \sup_{\theta_i\in[-1,1]} \sum_{i=1}^n \theta_i\bigl(\mu_f(i)-\mu_g(i)\bigr).\] Now fix \(\theta=(\theta_1,\dots,\theta_n)\in[-1,1]^n\), and define the operator⁸ \[M_\theta \chi_S = m_\theta(S)\chi_S, \text{ where, } \; m_\theta(S):= \frac{1}{|S|} \sum_{i\in S}\theta_i \qquad(S\neq\emptyset),\] Notice that \(\sum_i\theta_i\mu_f(i)= \langle f,M_\theta f\rangle\), which gives us \(\sum_i\theta_i\bigl(\mu_f(i)-\mu_g(i)\bigr)=\langle f,M_\theta f\rangle-\langle g,M_\theta g\rangle.\) Putting \(h:=f-g\), and noticing the operator \(M_\theta\) is self-adjoint, one may verify \[\langle f,M_\theta f\rangle-\langle g,M_\theta g\rangle = \langle h,M_\theta f\rangle+\langle g,M_\theta h\rangle = \langle h,M_\theta f\rangle+\langle h,M_\theta g\rangle.\] Thus we now wish to bound the expressions of the form \(|\langle h,M_\theta u\rangle|\) where \(u:\{-1,1\}^n\to[-1,1]\).

We prove the following auxiliary lemma.

Proof of the lemma. Fix a permutation \(\pi\) of \([n]\). we reveal the coordinates according to the order of \(\pi\), and define the filtration \(\mathcal{F}_k^\pi := \sigma(X_{\pi(1)},\dots,X_{\pi(k)}).\) Define the Doob martingale \[u_k^\pi := \mathbb{E}[u\mid \mathcal{F}_k^\pi].\] we denote the differences \(d_k^\pi := u_k^\pi-u_{k-1}^\pi\), and the martingale transform [11] \[T_{\theta,\pi}u := \sum_{k=1}^n \theta_{\pi(k)}d_k^\pi.\]

We recall the definition of the martingale \(\mathrm{BMO}_2\)-norm

Notice that \(T_{\theta,\pi}u\) has BMO\(_2\)-norm bounded by \(2\). Indeed, for every stopping time \(\tau\) we have \[\mathbb{E}\left[ \left(\sum_{k>\tau} \theta_{\pi(k)}d_k^\pi\right)^2 \mid \mathcal{F}_\tau^\pi \right] = \mathbb{E}\left[ \sum_{k>\tau} \theta_{\pi(k)}^2(d_k^\pi)^2 \mid \mathcal{F}_\tau^\pi \right]+2 \mathbb{E}\left[ \sum_{m>k>\tau} \theta_{\pi(k)}\theta_{\pi(m)}d_k^\pi d_m^\pi \mid \mathcal{F}_\tau^\pi \right] \underset{(*)}{=}\] \[\mathbb{E}\left[ \sum_{k>\tau} \theta_{\pi(k)}^2(d_k^\pi)^2 \mid \mathcal{F}_\tau^\pi \right] \le \mathbb{E}\left[ \sum_{k>\tau}(d_k^\pi)^2 \mid \mathcal{F}_\tau^\pi \right] \underset{(*)}{=} \mathbb{E}\left[ \sum_{k>\tau}(d_k^\pi)^2 \mid \mathcal{F}_\tau^\pi \right] +2 \mathbb{E}\left[ \sum_{m>k>\tau} d_k^\pi d_m^\pi \mid \mathcal{F}_\tau^\pi \right] =\] \[\mathbb{E}\left[ (u_n^\pi-u_\tau^\pi)^2 \mid \mathcal{F}_\tau^\pi \right].\] Where the equalities marked \((*)\) follows from the fact that \(\mathbb{E}[d_k^\pi d_m^\pi\mid \mathcal{F}_k] = d_k^\pi\,\mathbb{E}[d_m^\pi \mid \mathcal{F}_k] = 0\) (since \(\mathcal{F} _{k}\subseteq \mathcal{F}_{m-1}\) and \(\mathbb{E} [d_m^{pi}| \mathcal{F}_{m-1}] = \mathbb{E} [u_m^{\pi}-u_{m-1}^{\pi}| \mathcal{F}_{m-1}] = u_{m-1}^{\pi} - u_{m-1}^{\pi} = 0\)), which in turn implies that \(\mathbb{E}[d_k^\pi d_m^\pi\mid \mathcal{F}_\tau] = \mathbb{E} [ \mathbb{E}[d_k^\pi d_m^\pi\mid \mathcal{F}_k]\mid \mathcal{F}_\tau]=0\).

Since \(|u|\le1\), we have \(|u_n^\pi-u_\tau^\pi|\le2\), and therefore \(\|T_{\theta,\pi}u\|_{\mathrm{BMO}_2}\le2.\)

By the martingale John–Nirenberg inequality (see [12]), given a martingale \(M\) with bounded BMO\(_2\)-norm, there exist constants \(c,C>0\) such that for any stopping time \(\tau\) we have \[\mathbb{E} [ \, \exp (c|M_\infty -M_T|)| \mathcal{F} _T] \le C\] Taking \(\tau = 0\), we get \(\int \exp\bigl(c|T_{\theta,\pi}u|\bigr)\,d\mu \le C.\)

For every subset \(\emptyset \neq S\) we notice that, \[\mathbb{E}[\chi_S\mid \mathcal{F}_k^\pi] = \begin{cases} 0, & S\not\subseteq\{\pi(1),\dots,\pi(k)\},\\ \chi_S, & S\subseteq\{\pi(1),\dots,\pi(k)\}. \end{cases}\] Thus, if \(i\in S\) is the last coordinate in \(S\) that is revealed by \(\pi\) then the element \(d_i^\pi\) (with respect to \(\chi_S\)) is the only non zero element, so \[T_{\theta,\pi}\chi_S = \theta_i\chi_S.\] Yet under a uniformly chosen random permutation, each \(i\in S\) is equally likely to be the last coordinate of \(S\) which is revealed. Therefore, taking expectation with respect to the uniform choice of \(\pi\) we get \[\mathbb{E}_\pi[T_{\theta,\pi}\chi_S] = \frac{1}{|S|} \sum_{i\in S}\theta_i\chi_S = M_\theta\chi_S.\] Then we deduce that for every \(u\) we have \[M_\theta u = \mathbb{E}_\pi[T_{\theta,\pi}u].\]

One may verify the convexity of the function \(z\mapsto \exp(c|z|)\), then for each point \(x\in\{-1,1\}^n\), Jensen’s inequality gives \[\exp\bigl(c|M_\theta u(x)|\bigr) = \exp\left(c\left|\mathbb{E}_\pi[T_{\theta,\pi}u(x)]\right|\right) \le \mathbb{E}_\pi \exp\bigl(c|T_{\theta,\pi}u(x)|\bigr).\] taking expectation in \(x\) and using the previously established inequality from John-Nirenberg inequality yields \[\int \exp\bigl(c|M_\theta u|\bigr)\,d\mu \le C.\]

Denote \(F:=|M_\theta u|\), treating it as a measurable function. We follow standart notation and denote by \(F^*\) the decreasing rearrangement of \(|F|\). That is, \[F^*(s) := \inf\{t\ge0:\mu(F>t)\le s\}, \quad 0<s\le1\] We notice that from the previously established bound for every \(t \ge 0\), \[\exp(ct) \mu(F>t)=\int \exp(ct) \mathbf{1}_{F>t} d\mu \le\int \exp\bigl(cF\bigr)\,d\mu \le C \Rightarrow \mu(F>t) \le C \exp(-ct)\] Which by the definition of \(F^*\), implies⁹ \(F^*(s)\le \frac{1}{c} \log \frac{C}{s}\) for every \(0<s\le1.\)

Now, let \(A\subseteq\{-1,1\}^n\) and apply the Hardy–Littlewood rearrangement inequality on the functions \(F\text{ and } \mathbf{1}_A.\) The decreasing rearrangement of \(\mathbf{1}_A\) is \[(\mathbf{1}_A)^*(s) = \mathbf{1}_{(0,{\mu(A)})}(s).\] Thus Hardy–Littlewood inequality [13] gives \[\int_A F\,d\mu = \int F \, \mathbf{1}_A\,d\mu \le \int_0^1 F^*(s)(\mathbf{1}_A)^*(s)\,ds = \int_0^{\mu(A)} F^*(s)\,ds.\] Using the bound on \(F^*\) we finally get, \[\int_A F\,d\mu \le \frac{1}{c} \int_0^{\mu(A)} \log\frac{C}{s}\,ds = \frac{1}{c} \left( \mu(A)(\log C +1 ) + \mu(A)\log \frac{1}{\mu(A)} \right) \le C'{\mu(A)}\left(1+\log\frac{1}{\mu(A)}\right)\] or in other words, \[\int_A |M_\theta u|\,d\mu \le C'{\mu(A)}\left(1+\log\frac{1}{\mu(A)}\right).\] as wanted  

We return to the proof of the theorem. Let \(A:=\{x:f(x)\neq g(x)\}\). Then \(\mu(A)=\Pr (f \neq g)\), and \(h=f-g=2\cdot \mathbf{1}_A.\) For every \(u:\{-1,1\}^n\to[-1,1]\) we have, \[|\langle h,M_\theta u\rangle| = \left| \int h\,M_\theta u\,d\mu \right| \le 2\int_A |M_\theta u|\,d\mu \le C{\mu(A)}\left(1+\log\frac{1}{\mu(A)}\right)\] by the lemma. Applying this with \(u=f,g\), gives (together with the first part of the proof) that \[\left| \sum_i\theta_i(\mu_f(i)-\mu_g(i)) \right| \le C{\mu(A)}\left(1+\log\frac{1}{\mu(A)}\right).\] Thus \[d_{\operatorname{TV}}(\mu_f,\mu_g) \le C{\mu(A)}\left(1+\log\frac{1}{\mu(A)}\right).\]

completing the proof of the theorem  

References↩︎