Information theoretic problems in networks and active sensing

Abstract

This dissertation covers three related topics. They are on network information theory, search, and tracking respectively. In the first part of the first topic, wo propose a group theoretic model for information. Exploiting this formalization, we identify a comprehensive both qualitative and quantitative parallelism between information lattices and subgroup lattices. As a consequence of this fundamental relation, we show that any continuous law holds in general for the entropies of information elements if and only if the same law holds in general for the log-indices of subgroups. By constructing subgroup counterexamples we find surprisingly that common information obeys neither the submodularity nor the supermodularity law. Our mathematic model for information is conceptually significant. In the second part of the first topic, we show that none of the three extra conditional mutual information terms in the Zhang-Yeung inequality can be dropped for the inequality to remain valid and that quasi-Hamilton groups satisfy the Ingleton inequality. This is the first time that certain classes of non-abelian groups are found to satisfy the Ingleton inequality. In the second topic, we study a class of search problems. Both bounded and unbounded search problems are considered. We show that the Bounded Discrete Linear Search Problem is quadratic-time solvable but that the graph search problem is NT-complete, derive bounds for the erroneous BDLSP, and show that optimal policies for an Unbounded Discrete Linear Search Problem (UBDLSP) exist if and only if the double-sided mean of its underlying distribution is finite. We propose a provable effective procedure approximating optimal values and optimal policies for UBDLSPs and show that the increments of the optimal policies for UBDLSPs with heavy-tailed distributions are necessarily unbounded. In the third topic, we study the fundamental limits of trackability using information theoretic approach. We show that for a target to be trackable the minimum query quota required is no less than the entropy rate H of the Markov chain of the target but no more than [H + 1]. Subsequently, we propose an adaptive strategy to learn the target motion law and track the target simultaneously. It is remarkable that the extra burden of learning the motion law sacrifices no loss of tracking performance in the asymptotic region.