On Sub-optimality of Random Binning for Distributed Hypothesis Testing

In [1], Berger introduced a framework of statistical decision problems under communication constraint. Inspired by his work, many researchers studied various problems of this kind [2, 3, 4, 5, 6, 7, 8]; see [9] for a thorough review until 90s. More recently, the problem of communication constrained statistics has regained interest of researchers; see [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24] and references therein.

In this paper, we are interested in the most basic setting of hypothesis testing in which the sender and the receiver observe correlated sources $X^{n}$ and $Y^{n}$, respectively, and the observation $(X^{n},Y^{n})$ is distributed according to the product of the null hypothesis $P_{XY}$ or the alternative hypothesis $Q_{XY}$; the sender transmit a message at rate $R$, and the receiver decide the hypotheses based on the message and its observation.

In [2], Ahlswede and Csiszár introduced the so-called quantization scheme, and showed that the quantization scheme is optimal for the testing against independence, i.e., the alternative hypothesis is $Q_{XY}=P_{X}\times P_{Y}$. In [3], Han introduced an improved version of the quantization scheme that fully exploit the knowledge of the marginal types. In [25], Shimokawa, Han, and Amari introduced the quantize and binning scheme, which we shall call the SHA scheme in the following. For a long time, it has not been known if the SHA is optimal or not. In [13], Rahman and Wagner showed that the SHA scheme is optimal for the testing against conditional independence.¹¹1In fact, for the testing against conditional independence, it suffices to consider a simpler version of quantize and binning scheme than the SHA scheme. More recently, Weinberger and Kochman [17] (see also [26]) derived the optimal exponential trade-off between the type I and type II error probabilities of the quantize and binning scheme. Since the decision is conducted based on the optimal likelihood decision rule in [17], their scheme may potentially provide a better performance than the SHA scheme; however, since the expression involves complicated optimization over multiple parameters, and a strict improvement has not been clarified so far.

A main objective of this paper is to investigate if the SHA scheme is optimal or not. In fact, it turns out that the answer is negative, and there exists a scheme that improves upon the SHA scheme. Since the general SHA scheme is involved, we focus on the critical rate, i.e., the minimum rate that is required to attain the same type II exponent as the Stein exponent of the centralized testing. Then, under a certain non-degeneracy condition, we will prove that the auxiliary random variable in the SHA scheme must coincide with the source $X$ itself, i.e., we must use the binning without quantization. By leveraging this simplification, for the binary symmetric double sources (BSDS), we derive a closed form expression of the critical rate attainable by the SHA scheme. Next, we will consider a product of the BSDS such that each component of the null hypothesis and the alternative hypothesis is “reversely aligned.” Perhaps surprisingly, it turns out that the SHA is sub-optimal for such hypotheses. Our improved scheme is simple, and it uses the SHA scheme for each component in a sequential manner; however, it should be emphasized that we need to conduct binning of each component separately, and our scheme is not a naive random binning.

We consider the statistical problem of testing the null hypothesis $\mathtt{H}_{0}:P_{XY}$ on finite alphabets ${\cal X}\times{\cal Y}$ versus the alternative hypothesis $\mathtt{H}_{1}:Q_{XY}$ on the same alphabet. The i.i.d. random variables $(X^{n},Y^{n})$ distributed according to either $P_{XY}^{n}$ or $Q_{XY}^{n}$ are observed by the sender and the receiver; the sender encodes the observation $X^{n}$ to a message by an encoding function

and the receiver decides whether to accept the null hypothesis or not by a decoding function

When the block length $n$ is obvious from the context, we omit the subscript $n$. For a given testing scheme $T_{n}=(\varphi,\psi)$, the type I error probability is defined by

and the type II error probability is defined by

In the following, $P(\cdot)$ (or $Q(\cdot)$) means that $(X^{n},Y^{n})$ is distributed according to $P_{XY}^{n}$ (or $Q_{XY}^{n}$).

In the problem of distributed hypothesis testing, we are interested in the trade-off among the communication rate and the type I and type II error probabilities. Particularly, we focus on the optimal trade-off between the communication rate and the exponent of the type II error probability when the type I error probability is vanishing, which is sometimes called “Stein regime”.

For a given communication rate $R$, the maximum exponent is denoted by

When there is no communication constraint, i.e., $R\geq\log|{\cal X}|$, the sender can send the full observation without any encoding, and the receiver can use a scheme for the standard (centralized) hypothesis testing. In such a case, the Stein exponent $D(P_{XY}\|Q_{XY})$ is attainable. We define the critical rate as the minimum communication rate required to attain the Stein exponent:

When the communication rate $R$ is not sufficient to send $X$, the standard approach is to quantize $X$ using a test channel $P_{U|X}$ for some finite auxiliary alphabet ${\cal U}$. For $P_{UXY}=P_{U|X}P_{XY}$ and $Q_{UXY}=Q_{U|X}Q_{XY}$ with $Q_{U|X}=P_{U|X}$, let

In [3], a testing scheme based on quantization was proposed, and the following achievability bound was derived: for any test channel $P_{U|X}$,

In [25], a testing scheme based on quantization and binning was proposed, and the following achievability bound was derived: for any test channel $P_{U|X}$ such that $R\geq I(U\wedge X|Y)$,

where $|t|^{+}=\max[t,0]$, and

Particularly, by taking $P_{U|X}$ to be noiseless test channel, i.e., $U=X$, we have

where

In the following, we focus on the critical rate. Under some mild conditions, in order to attain the Stein exponent, we must take $U=X$ in the quantization-bining bound, i.e., no quantization. In the rest of this section, we prove this claim.

Suppose that $P_{XY}$ and $Q_{XY}$ have full support. Let $\hat{\Lambda}$ be a function on ${\cal X}\times{\cal Y}$ defined by²²2We suppose that alphabets are ${\cal X}=\{0,\ldots,m_{\mathsf{x}}\}$ and ${\cal Y}=\{0,\ldots,m_{\mathsf{y}}\}$; taking $y=0$ as a special symbol in (3) is just notational convenience.

Since the quantization-binning bound is at most $E(P_{UXY}\|Q_{UXY})$, when the assumption of Proposition 2 is satisfied, $U=X$ is the only choice of test channel to attain the Stein exponent.³³3Even though we can take a redundant test channel $P_{U|X}$ such that $\mathtt{supp}(P_{U|X}(\cdot|x))\cap\mathtt{supp}(P_{U|X}(\cdot|x^{\prime}))=\emptyset$ for any $x\neq x^{\prime}$, such a test channel does not improve the attainable exponent.

In Proposition 2, the assumption that every raws of $\hat{\Lambda}(x,y)$ are distinct cannot be replaced by the assumption that every raws of the log-likelihood function

are distinct; for instance, when $P_{XY}$ and $Q_{XY}$ are given by

for some $a>0$, then every raws $\Lambda(x,\cdot)$ are distinct but $\hat{\Lambda}(1,\cdot)=\hat{\Lambda}(2,\cdot)$. In fact, as is shown in the following Proposition 3, the symbols $x=1$ and $x=2$ in this example can be merged while maintaining $E(P_{UXY}\|Q_{UXY})=D(P_{XY}\|Q_{XY})$. Even though Proposition 3 is not used in the rest of the paper, it may be of independent interest.

Let ${\cal X}={\cal Y}=\{0,1\}$, and let $P_{XY}$ and $Q_{XY}$ be given by

for $0\leq p,q\leq 1$ and $p\neq q$. Since $\hat{\Lambda}(0,0)=\hat{\Lambda}(1,0)=0$ and

the assumption of Proposition 2 is satisfied. Thus, we need to set $U=X$ in the quantization-binning bound to attain the Stein exponent. In the minimization of (1), since $P_{\tilde{X}}=P_{X}$ and $P_{\tilde{Y}}=P_{Y}$ are the uniform distribution, the only free parameter is the crossover probability $P_{\tilde{Y}|\tilde{X}}(1|0)=P_{\tilde{Y}|\tilde{X}}(0|1)=\tilde{p}$. Then, we can easily find that the binning bound for BSDS is

for $R\geq h(p)$. Furthermore, this bound implies that the critical rate attainable by the SHA scheme is

Next, let us consider the case where $P_{XY}=P_{X_{1}Y_{1}}\times P_{X_{2}Y_{2}}$ and $Q_{XY}=Q_{X_{1}Y_{1}}\times Q_{X_{2}Y_{2}}$, and $P_{X_{i}Y_{i}}$ and $Q_{X_{i}Y_{i}}$ for $i=1,2$ are DSBSs with parameters $0\leq p_{1},p_{2},q_{1},q_{2}\leq 1$, respectively. Particularly, we consider the case where $p_{1}=q_{2}$, $p_{2}=q_{1}$, where $p_{1}\neq q_{1}$. Note that, for the product source, the function defined by (3) can be decomposed as

where

Furthermore, we have $\hat{\Lambda}_{1}(1,1)=-\hat{\Lambda}_{1}(0,1)$, $\hat{\Lambda}_{2}(0,1)=-\hat{\Lambda}_{1}(0,1)$, and $\hat{\Lambda}_{2}(1,1)=\hat{\Lambda}_{1}(0,1)$. Thus, by denoting $a=\hat{\Lambda}_{1}(0,1)$, we have

and the assumption of Proposition 2 is satisfied. Thus, we need to set $U=X$ in the quantization-binning bound to attain the Stein exponent.

Since $p_{1}=q_{2}$ and $p_{2}=q_{1}$, the conditional entropies $H_{P}(X|Y)$ and $H_{Q}(X|Y)$ with respect to $P_{XY}$ and $Q_{XY}$ satisfy $H_{P}(X|Y)=H_{Q}(X|Y)$. Thus, we find that the inner minimization of the binning bound is attained by $P_{\tilde{X}\tilde{Y}}=Q_{XY}$, and

Furthermore, this bound implies that the critical rate attainable by the SHA scheme is

Now, we describe a modified version of SHA scheme for the product of BSDS. For $i=1,2$, let $T_{\mathtt{b}}^{[i]}=(\varphi^{[i]},\psi^{[i]})$ be the SHA scheme (without quantization) for $P_{X_{i}Y_{i}}$ versus $Q_{X_{i}Y_{i}}$. For a given rate $R$, we split the rate as $R=R_{1}+R_{2}$, and consider sequential scheme $\tilde{T}_{\mathtt{b}}=(\varphi,\psi)$ constructed from $(T_{\mathtt{b}}^{[1]},T_{\mathtt{b}}^{[2]})$ as follows. Upon observing $\bm{x}=(\bm{x}_{1},\bm{x}_{2})$, the sender transmit $m_{1}=\varphi^{[1]}(\bm{x}_{1})$ and $m_{2}=\varphi^{[2]}(\bm{x}_{2})$.⁴⁴4Note that $m_{1}$ and $m_{2}$ include indices of random binning as well as marginal types of $\bm{x}_{1}$ and $\bm{x}_{2}$. Then, upon receiving $(m_{1},m_{2})$ and observing $\bm{y}=(\bm{y}_{1},\bm{y}_{2})$, the receiver decides $\psi(m_{1},m_{2},\bm{y})=\mathtt{H}_{0}$ if $\psi^{[1]}(m_{1},\bm{y}_{1})=\mathtt{H}_{0}$ and $\psi^{[2]}(m_{2},\bm{y}_{2})=\mathtt{H}_{0}$. The type I and type II error probabilities of this sequential scheme $\tilde{T}_{\mathtt{b}}$ can be evaluated as

by the union bound, and

Thus, if the type I error probabilities of each scheme is vanishing, then the type I error probability $\alpha[\tilde{T}_{\mathtt{b}}]$ is also vanishing. On the other hand, the type II exponent of the sequential scheme is the summation of the type II exponent of each scheme.

As in Section V, suppose that $p_{1}=q_{2}$ and $p_{2}=q_{1}$. Furthermore, let $h(q_{1})<h(p_{1})$. Then, from the above argument, and (9), we find that the following exponent is attainable by the sequential scheme:

for $R_{1}\geq h(p_{1})$ and $R_{2}\geq h(p_{2})$. By setting $R_{1}=h(p_{1})$ and $R_{2}=h(p_{2})+D(p_{2}\|q_{2})$, we can derive the following bound on the critical rate:

Interestingly, the bound on the critical rate in (15) improves upon the bound in (13).

From an operational point of view, this improvement can be explained as follows. In the SHA scheme (without quantization), we use the minimum entropy decoder to compute an estimate $\hat{\bm{x}}$ of $X^{n}=\bm{x}$; then, if the joint type $\mathsf{t}_{\hat{\bm{x}}\bm{y}}$ is close to $P_{XY}$, we accept the null hypothesis. When the empirical conditional entropy $H(\bm{x}|\bm{y})$ is such that $H_{P}(X|Y)\gnsim H(\bm{x}|\bm{y})$, even if there exists $\hat{\bm{x}}$ satisfying $H(\bm{x}|\bm{y})\geq H(\hat{\bm{x}}|\bm{y})$, the type II testing error does not occur though the receiver may erroneously compute $\hat{\bm{x}}\neq\bm{x}$.⁵⁵5Note that $H_{P}(X|Y)\gnsim H(\bm{x}|\bm{y})\geq H(\hat{\bm{x}}|\bm{y})$ implies that $\mathsf{t}_{\hat{\bm{x}}\bm{y}}$ is not close to $P_{XY}$. Consequently, the type II testing error may occur only if $(X^{n},Y^{n})=(\bm{x},\bm{y})$ satisfies $H(\bm{x}|\bm{y})\gtrsim H_{P}(X|Y)$.

For the product of BSDSs, when the types of modulo sums $\bm{x}_{1}+\bm{y}_{1}$ and $\bm{x}_{2}+\bm{y}_{2}$ are $H(\mathsf{t}_{\bm{x}_{1}+\bm{y}_{1}})\simeq h(\tau_{1})$ and $H(\mathsf{t}_{\bm{x}_{2}+\bm{y}_{2}})\simeq h(\tau_{2})$, the type II testing error may occur only if $h(\tau_{1})+h(\tau_{2})\gtrsim h(p_{1})+h(p_{2})$; see Fig. 1a(a). In the modified SHA scheme, $\bm{x}_{1}$ and $\bm{x}_{2}$ are binned and estimated separately. Because of this, the constraint of type II testing error event become more stringent, i.e., $h(\tau_{1})\gtrsim h(p_{1})$ and $h(\tau_{2})\gtrsim h(p_{2})$; see Fig. Fig. 1a(b).

In this paper, we have developed tools to evaluate the critical rate attainable by the SHA scheme, and exemplified that the SHA scheme is sub-optimal for a product of BSDSs. A future problem is to generalize the idea of sequential scheme in Section VI and develop a new achievability scheme for the distributed hypothesis testing. Another future problem is a potential utility of the scheme in [17]; as we mentioned in Section I, it has a potential to improve upon the SHA scheme, but strict improvement is not clear since the expression involves complicated optimization over multiple parameters.

Lastly, it should be pointed out that certain kinds of “structured” random coding is known to improve upon the naive random coding in the context of the mismatched decoding problem; eg. see [29, 30] and references therein. Even though there is no direct connection between the two problems, it might be interesting to pursue a mathematical connection between these problems.

The author appreciates Marat Burnashev for valuable discussions at an early stage of the work. The author also thanks Te Sun Han and Yasutada Oohama for fruitful discussions.