Oblivious communication channels and their capacity

Let C = {x(1), ... , x(N)} subset of {0, 1}(n) be an [n, N],binary error correcting code (not necessarily linear). Let e is an element of {0, 1}(n) be an error vector. A codeword x is an element of C is said to be disturbed by the error e if the closest codeword to x circle plus e is no longer x. Let A(e) be the subset of codewords in C that are disturbed by e. In this work, we study the size of A(e) in random codes C (i.e., codes in which each codeword x(i) is chosen uniformly and independently at random from {0, 1}(n)). Using recent results of Vu [Random Structures and Algorithms, vol. 20 , no. 3, pp. 262-316, 2002] on the concentration of non-Lipschitz functions, we show that vertical bar A(e)vertical bar is strongly concentrated for a wide range of values of N and \\e\\. We apply this result in the study of communication channels we refer to as oblivious. Roughly speaking, a channel W(y/x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x, A family of channels W is said to be oblivious if every member W of the family is oblivious. In this work, we define oblivious and partially oblivious families of (not necessarily memoryless) channels and analyze their capacity. When considering the capacity of a family of channels W, one must address the design of error correcting codes which allow communication under the uncertainty of which channel W is an element of W is actually used. The oblivious channels we define have connections to Arbitrarily Varying Channels with state constraints.