On Distributed Information Processing: Law of Small Numbers

In this work, we consider distributed processing of two sequences of correlated binary-valued random variables. The processing involves applying a boolean function on a sequence. This problem was studied by Witsenhausen in the 70's.
We establish a new inequality tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions. We derive a characterization of the correlation between the outputs of these functions as a function of block-length. This leads to a strange phenomenon where as the block-length of the processing is increased, the maximum correlation between the outputs is decreased (which we term as Law of small numbers). The characterization is useful in various disciplines which deal with common-information such as distributed estimation, control and hypothesis testing. We build upon Witsenhausen's bound on maximum-correlation. One possible application is to characterize the communication-cooperation tradeoff in multi-terminal communications.
S. Sandeep Pradhan obtained his M.E. degree from the Indian Institute of Science (IIS), India in 1996 and Ph.D. from the University of California at Berkeley in 2001. From 2002 to 2008 he was an assistant professor, and from 2008 to 2015 he was an associate professor in the Department of Electrical Engineering and Computer Science at the University of Michigan at Ann Arbor. Currently he is a professor. He is the recipient of 2001 Eliahu Jury award given by the University of California at Berkeley for outstanding research in the areas of systems, signal processing, communications and control, the CAREER award given by the National Science Foundation (NSF), and the Outstanding achievement award for the year 2009 from the University of Michigan. His research interests include sensor networks, multi-terminal communication systems, coding theory, quantization, information theory.