A Dichotomy for Distributed Detection With Limited Communication

This paper identifies the Stein exponent of two distributed detection (binary hypothesis testing) setups with limited communication over a discrete memoryless channel (DMC). In the first setup, the DMC can only be used k(n) times, where k(n) grows sublinearly in the length of the observations n. In the second setup, the DMC can be used n times, however a block-input cost constraint C_n is imposed and C_n grows sublinearly in n. The optimal Stein exponent coincides for both setups and depends on whether the DMC is partially-connected, i.e., one of the output symbols can only be induced by a strict subset of the input symbols, or fully-connected. For partially-connected DMCs, the optimal Stein exponent of our setups coincides with the optimal Stein exponent (identified by Han and by Shalaby and Papamarcou) for the scenario where the sensor can communicate a sublinear (in n) number of bits to the decision center and communication is over a noiseless link. In contrast, for fully-connected DMCs the optimal Stein exponent collapses and is given by the optimal Stein exponent of the local test at the decision center. In this case, the sensor and the DMC do not help in improving the Stein exponent. Our results hold for general independent and identically distributed sources.